Format And Type Fonts CHEMICAL ENGINEERING TRANSACTIONS VOL. 45, 2015 A publication of The Italian Association of Chemical Engineering www.aidic.it/cet Guest Editors: Petar Sabev Varbanov, Jiří Jaromír Klemeš, Sharifah Rafidah Wan Alwi, Jun Yow Yong, Xia Liu Copyright © 2015, AIDIC Servizi S.r.l., ISBN 978-88-95608-36-5; ISSN 2283-9216 DOI: 10.3303/CET1545123 Please cite this article as: Šomplák R., Touš M., Pavlas M., Gregor J., Popela P., Rychtář A., 2015, Multi-commodity network flow model applied to waste processing cost analysis for producers, Chemical Engineering Transactions, 45, 733- 738 DOI:10.3303/CET1545123 733 Multi-Commodity Network Flow Model Applied to Waste Processing Cost Analysis for Producers Radovan Šomplák* ,a , Michal Touš a , Martin Pavlas a , Jiří Gregor a , Pavel Popela b , Adam Rychtář b a Institute of Process and Environmental Engineering, Faculty of Mechanical Engineering, Brno University of Technology, Technická 2896/2, 616 69 Brno,Czech Republic b Institute of Mathematics, Faculty of Mechanical Engineering, Brno University of Technology, Technická 2896/2, 616 69, Brno, Czech Republic somplak@upei.fme.vutbr.cz Supply chain models and network flow models represent a frequent task, where transport of product(s) or service(s) between supplier(s) and consumer(s) is optimized. Several models applied to energy systems and supply chains including biofuels and/or renewables have been developed and recently published. In this paper, we deal with a network flow problem where waste is transported from producers (municipalities) through pre-processing facilities to its final treatment. The results obtained for minimum total treatment cost including transport provide us with optimal total waste flow along edges (roads, railways) in a selected region. However, the information about the waste flow through the network from a particular producer and related processing cost is often lost due to the merging and splitting streams in vertices. This limits the practical utilization of the results. This shortage can be solved by a secondary network flow problem where capacities of edges are given by results from total waste flow problem and waste from different producers is modelled by new variables. The needed constraints are introduced and new suitable criterion is specified. The model follows principle ideas of multi-commodity network flow modelling. It is implemented in GAMS and presented through a case study. 1. Introduction This paper deals with recent improvement of a large-scale computational tool called NERUDA which provides support for strategic decision making in the field of waste management. This tool is shortly introduced in the paper by Šomplák et al. (2013) and described in more details in work by Šomplák et al. (2014). The key part of NERUDA is based on the implementation of a mathematical model for a waste management related logistic problem. The logistic problem is solved by mathematical programming and is used to simulate competitive environment in waste management. Scenario approach to the issue of network flows, location of waste treatment facilities and the number of these facilities was also presented in the paper Ferri et al. (2015). Fan et al. (2013) deals with a different approach, where the methods of fuzzy nonlinear programming are used. There are waste producers (municipalities) and waste processors (incinerators, mechanical-biological treatment plants, landfills, etc.). The producers and processors (vertices) are connected through roads and railways (edges). This forms a well-known transportation network; see Bazaraa et al. (2010) for utilised concepts from the area of network flows and linear programming. An example of such network is shown in Figure 1. The processors compete in waste collection from producers. This competition is ruled by total costs of waste treatment, i.e. processing cost plus transportation cost. We search for minimum total treatment costs for waste producers by which we simulate the competitive environment. Results from this optimization problem provide us with information about waste flow along edges, capacities of processors (amount of processed waste) and gate fees. This is enough from a global point of view. However, if we want to evaluate treatment costs for particular municipality we get into a problem. To 734 do it, we need to know information about the waste flow from particular municipality to processing site(s). A solution of the logistic problem does not contain such information. Figure 1: Network for the logistic problem The problem is demonstrated by using a simple network shown in Figure 2. Waste from producers A, B and C flows separately to vertex D and then together to vertex E. In vertex E the waste flow is split up and part goes to vertex F, part to vertex G. At this point we lose the information about waste flow from particular producer. From the solution of the logistic problem, we get only the information about total waste flows along the edges, and therefore, we do not know in what ratio waste from particular producer is split up in the vertex E. There are infinite numbers of options. The remaining of the paper shows our approach to handle this problem. Figure 2: Simple network to demonstrate difficulties in the logistic problem 2. Multi-commodity network flow and waiting list of waste producers It is clear that we need to track waste flow to processor(s) for each municipality. The idea proposed in this contribution is based on the fact that municipalities have to make a contract with processor(s) individually. The municipality is represented by a mayor. If the mayor is responsible person he/she starts negotiation with waste processors soon. While if the mayor does not care about future so much he/she postpone this issue. Following this idea we generate a waiting list of mayors (municipalities/waste producers). The waste flow along the edges, as well as, capacities of processors given by the solution of the logistic problem cannot be exceeded. The later a mayor makes a contract the more is limited in options of waste treatment. The mayor first in the order has the best position since full capacities of all edges and processors are available. The mayor second in the order has a little bit worse position because the first mayor decreased available capacity of particular processor(s) and available waste flow capacity of particular edges. The mayor last in the order is in the worst position since there is only one (the capacities are already taken by the other mayors) and probably very expensive option. There are two options how to implement a waiting list. First, we can solve the problem for each producer separately following the waiting list order. For each producer, the capacity of processors and edges are decreased according to the solution for previous producers. This leads to high demands on pre-processing of input data (the results have to be processed and implemented into inputs for the next producer). Therefore, we prefer the other option. It consists in introduction of weights in the objective (cost) function. These weights represent order of producers in the waiting list. In this case the problem is solved for all producers simultaneously. By this, we get a multi-commodity nature into the problem – waste from each producer is a commodity. Incinerator Landfill Utilization of refused derived fuel Municipality 735 This leads to a multi-commodity network flow problem with limited capacity of edges and limited capacity of processors, see Ghiani et al. (2004), for related network flow models with logistic applications and Bazaraa et al. (2010) for solution techniques. We should note that this could be implemented directly into the logistic model. However, from our point of view, it is better to have these models separated. Separated models have fewer variables and constraints than united model. Considering related steps like sensitivity analyses, Monte-Carlo simulations, etc., separated models are better with respect to computational time – analyses of costs for producers are not needed every time when only multi-commodity network flow problem can be solved. The data flow between separated models is shown in Figure 3. Figure 3: Data flow within Neruda system 3. Mathematical model In this section we convert the presented idea into a mathematical model. We have a network shown in Figure 2. We want to minimize the objective function, which represents the total treatment cost: ∑( ) (1) where is set of producers, is processing cost for producer p, is a transportation cost for producer p and is a weight of producer p. The weights have to be ordered and no two weights are equal. The first producer in the waiting list has the highest weight and the last one has the lowest weight. The weights artificially increase total costs. Considering a minimization problem, this means that total costs for a producer with a high weight has corresponding impact on the value of the objective function. Let us show it on an example based on Figure 2. Let us assume that the order of municipalities in the waiting list is A, B, C. So we can assign the weights to the municipalities, e.g., in the following way: , , and . The effect of the total cost (separately related to municipalities) on the value of the objective function for municipality A is 2 times stronger, resp. six times stronger, than effect of costs for municipality B, resp. C. So, the algorithm puts the strongest emphasis on the total costs for municipality A, weaker emphasis on B and the weakest on C. Clearly, the order in the waiting list is achieved by this. So far, we have discussed the objective function only. Now let us have a look at the constraints. We should introduce mathematical notation first but due to limited space of the paper we only introduce municipal solid waste and waste compressed in transfer stations (the other commodity is refused derived fuel and rejects from mechanical-biological treatment), roads (there is also railway network) and incinerators and transfer stations (the other processors are mechanical biological treatment, landfills and plants utilizing refused derived fuel): Sets set of all vertices (producers and processors together) set of producers (subset of all vertices) set of raw waste processors (transfer stations, incinerators) set of processors producing compressed waste (has to be transported to incinerators) set of edges Parameters: incidence matrix of the road network capacity of an edge for raw waste capacity of an edge for compressed waste amount of waste produced in a municipality Allocation problem Multi-commodity network flow problem Waste production in municipalities Function: gate fee = f(capacity) Transport costs Length of road edges Capacities of edges Waste flow along edges from particular producer Waiting list of producers 736 Variables: flow of raw waste produced in a municipality along the edge flow of compressed waste produced in a municipality along the edge amount of raw waste from a municipality processed in vertex amount of compressed waste from municipality processed in vertex The first constraints Eq(2) says that the sum of waste flow along an edge produced by different municipalities is equal to an edge capacity (given by the logistic problem). The next constraints, Eq(3), represent the condition that the waste produced in a municipality is processed (production has sign opposite to processing). Eq(4) says that the waste produced in a municipality has to be loaded on a truck. Eq(5) provides constraints to make sure that the waste flows through a network. Eq(6) is a vertex related balance – simply what flows in or is produced in the vertex has to flow out or to be processed in the vertex. Eq(7) is pre-processing constraint (MBT or transfer stations) i.e. the amount of raw waste pre-processed in a vertex has to leave the vertex in a different form (in our simplified example this is related to transfer stations only – raw waste becomes compressed waste). According to Eq(8), the waste produced in a municipality has to be transported to processor(s). Eq(9) says that the waste transported from all producers to a processor has to be processed. Eq(10) is introduced to keep sign rules (production is positive, processing is negative). Eq(11) to (14) say that the edge variables are nonnegative. The above mentioned objective function is further implemented in the GAMS using variables of model Eq(2) to (14) and detail cost coefficients. ∑ ∑ (2) ∑ ∑ (3) (4) ∑ ( ) ∑ ( ) (5) ∑ ( ) ∑ (6) (7) ∑( ) ∑∑ ( ) (8) ∑( ) ∑∑ ( ) ∑ (9) (10) (11) (12) (13) (14) 4. Model applications The model application is demonstrated through a study involving the Czech Republic. The Czech Republic is divided into 214 sub-regions – waste producers. The vertex of a sub-region is located in the biggest municipality within a sub-region. Furthermore, there are vertices of processors and also a road network (roads are modelled by edges). This network is used in the logistic problem as well as in the network flow problem. We want to estimate waste treatment costs for the producers. Firstly, we solve the logistic problem. This provides us with the capacities of the edges. We have to decide about the order of the producers in the waiting list. Of course, this is unknown information and in fact it is impossible to predict. So, we use randomly generated order and then we continue computations. The results are shown in Figure 4. We can see that total cost vary across the Czech Republic a lot. 737 With a different order we may expect different results. If we want to provide a mayor of a municipality with more robust information we may carry out a Monte-Carlo simulation. The Monte-Carlo simulation consists of performing many simulation runs with randomly generated number(s) in order to obtain the distribution of an unknown probabilistic entity – total costs for municipalities in our case. Let us take a look at variability of total costs for the municipality marked with white dot in Figure 4. We carried out 50 simulation runs. The frequencies of different total costs are presented in histogram in Figure 5. Clearly, there are two processing options for this municipality. And if the mayor is not active in the issue of waste treatment there is relatively high risk of significantly higher costs in comparison with the case of the active attitude. Figure 4: Waste treatment cost Figure 5: Frequency of treatment cost for particular municipality The following figures present results from Monte-Carlo simulation for the entire Czech Republic. Figure 6(a) shows mean values, Figure 6(b) shows standard deviations. Municipalities will deal with expected costs of waste treatment in the future and they should consider it while making economic decision. Further, those municipalities, which are dark coloured in Figure 6(b), should start dealing the issue of waste treatment since there is a risk that capacities of cheap options will be already taken by other municipalities. (a) (b) Figure 6: (a) Average waste treatment cost, (b) standard deviation of waste treatment cost So far we have shown benefits for municipalities only. But multi-commodity approach provides valuable information to processors as well. Waste availability is a crucial moment for them. If they are not able to operate at least at nearly full load it leads to worse cash flow and the project gets unprofitable. But there is still competing environment between processors. In this case, it is good to know which municipalities should be included in the collection area of a processor. Figure 7 shows the collection area for a selected Cost of waste treatment Min Max Total costs (EUR/t) 33 52 70 89 107 0 15 30 F re q u e n c y Average treatment cost Min Max Max Min Standard deviation of waste treatment cost 738 processor. The dark colour means that the municipality is likely to be in the collection area while white coloured municipalities are not there. Negotiation with white coloured municipalities is rather a waste of time because they have clearly cheaper options. However, the other municipalities should be considered. Based on the Monte-Carlo simulation there is a chance about 50 % that the manager of the incinerator will make a contract with them. 50 % indicates that there is a competing processor. A manager of the incinerator should not wait with negotiations since the other processor represents almost equally good option for those municipalities. Figure 7: Probability of including sub-regions into waste collection area of particular incinerator 5. Conclusion The presented approach shows an option how to track commodity flow from a producer to processor in the logistic problem where this information is lost due to merging and splitting streams in vertices. We have developed a model, which is based on the multi-commodity approach and the idea of the waiting list of producers. It is applied to a waste logistic problem. Model may be utilized to obtain various results which are valuable for both producers (municipalities) and processors in a process of strategic decision making. Since there are many uncertainties we apply Monte-Carlo simulation to get robust results. The results are presented in a short case study (section 4), which shows the estimation of waste treatment costs for particular localities (sub-regions of Czech Republic). The solution of this task enables a deeper insight into what could be the waste treatment costs for a single municipality in case of active or passive approach to negotiation of particular contracts with processors. Acknowledgement The authors gratefully acknowledge financial support provided within the research project No. CZ.1.07/2.3.00/30.0039 “Excellent young researchers at Brno University of Technology”, further with financial support from the MEYS under the National Sustainability Programme I (Project LO1202) and financial support provided by Technology Agency of the Czech Republic within the research project No. TE02000236 "Waste-to-Energy (WtE) Competence Centre”. References Bazaraa M.S., Jarvis J.J., Sherali H.D., 2010, Linear Programming and Network Flows, 4th edition, John Wiley and Sons, Hoboken, N.J., USA. Fan Y.R., Huang G.H., Yang A.L., 2013. Generalized fuzzy linear programming for decision making under uncertainty: Feasibility of fuzzy solutions and solving approach. Information Sciences 241, 12–27. doi:10.1016/j.ins.2013.04.004 Ferri G.L., Diniz Chaves G. de L., Ribeiro G.M., 2015. Reverse logistics network for municipal solid waste management: The inclusion of waste pickers as a Brazilian legal requirement. Waste Management 40, 173–191. doi:10.1016/j.wasman.2015.02.036 Ghiani G., Laporte G., Musmanno R., 2004, Introduction to Logistics Systems Planning and Control, John Wiley and Sons, Hoboken, N.J. Šomplák R., Procházka V., Pavlas M., Popela P., 2013, The logistic model for decision making in waste management, Chemical Engineering Transactions, 35, 817-822. Šomplák R., Pavlas M., Kropáč J., Putna O., Procházka V., 2014, Logistic model-based tool for policy- making towards sustainable waste management, Clean Technologies and Environmental Policy, 16(7), 1275-1286. WtE plant Probability [%]