Heuristics for Waste Collection Arc Routing Problem

HEURISTICS FOR WASTE COLLECTION ARC ROUTING PROBLEM Vlastim´ır Nevrl´y  , Radovan ˇ Sompl´ak, Pavel Popela Institute of Process Engineering, Faculty of Mechanical Engineering, Brno University of Technology, Czech Republic [email protected]  Abstract Waste management is still an expanding field which needs to be constantly enhanced so that waste transportation and treatment is as effective as possible. An important part of this process is a waste collection at the municipal level. Decisionmaking about daily routing for all vehicles from a heterogenous fleet substantially influences the expenses of technical services. The need of route scheduling comes also from the newly separated fractions. Transportation features include the capacity of vehicles, number and type of containers on the route, traffic light delays and many others. The mathematical model that properly describes the real practice of servicing containers has not been published yet. Moreover, routing problems are generally not solvable by exact methods, so the appropriate heuristic algorithm has been developed. A case study with obtained results is discussed. This solution serves not only to improve the current operational situation, but also to create new route schedules for increasing number of collected commodities. Keywords: waste management, combinatorial optimization, heuristics, routing problem, waste collection, arc routing. Received: 30 April 2019 Accepted: 31 May 2019 Published: 24 June 2019 1 Introduction Effective waste management contributes to economic and environmental sustainability. As a result of increasing operational requirements and changing systems, the development of new methods in various areas is necessary. For some waste producers (municipalities), the collection plan is simple because of the small scale of the problem. Using elementary knowledge and calculations, a weekly collection plan can be created for the vehicle and adapted to the current season and needs throughout the year. However, this statement can only be made for small areas where dozens of containers of a particular type of waste occur. For larger territories, it is advisable to move to more sophisticated methods, most often based on mathematical programming and computational algorithms. An extensive up-to-date research in the field of operational research was addressed in [1], where opportunities and challenges for further development were identified. The focus of the article, in addition to the number of publications in each sector, was more general in nature, where decision-making and planning were divided into strategic, tactical and operational, also with regards to data access (deterministic, stochastic or robust). The complex point of view for the waste management was presented in [2]. In [3] was dealt with mobile waste collection, while places to stop the vehicle were analysed. Collecting mobile sites have been selected here based on the demand of citizens for specific time windows. Four different heuristic algorithms - Tabu Search, Greedy Algorithm, Simulated Annealing (SA), Bee Colony Optimization - were tested to solve the problem. According to testing on 3 different real instances with installation and collection infrastructure (Tokyo, Philadelphia, Warsaw), the SA algorithm proved to be the most suitable for the given problem. The proposed solution to the task was to reduce the costs and emissions generated by the waste transfer. It may be useful sites for identifying warehouse, depots or waste treatment plant for the area. The facility location problem represents a challenging task, especially, when randomness is involved, the genetic algorithm showed its strength in combination with the Benders decomposition [4]. Existing systems also have drawbacks due to poor cooperation between different areas. In the case of the collection and subsequent logistic chain of packaging waste, it may be the identification of suitable locations for the warehouses, depots or waste treatment plants for the area. The paper [5] analysed the impact of the target site for waste disposal at collection costs. Several smaller areas have been integrated in the calculation to identify the potential for change. Individual collection containers were aggregated into larger areas to simplify the collection section to allow for a more macroscopic view, while the capacities of both transfer stations and terminal equipments were also taken into account. This was followed by an analysis of collection planning for recyclable waste from an economic and environmental point of view [6]. Different systems of curbside collection were analysed in [7]. Multi compartment vehicles might be desirable for some areas, however, transport requirements depends on other factors such as vehicle size, compression factors, and packing. Plastic waste collection was modelled in [8] through vehicle routing problem in terms of sustainability. Scenarios of different system were compared from cost point of view for the real world case. https://doi.org/10.13164/mendel.2019.1.015 ISSN: 1803-3814 (Printed), 2571-3701 (Online) MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 15 Waste operations may also depend on their type and properties, e.g., the collection of kitchen waste was planned using a heuristic algorithm in [9]. A tailor-made procedure for this type of waste has been presented because of its properties such as high mass versus volume or large variation in demand between collection points (restaurants, bars, supermarkets, etc.). The test calculations of this algorithm are shown in the historic center of Genoa and compared with the currently used plan with partial savings. Savings can also be ensured by a robust waste collection view. This was introduced in [10], where Periodic Capacitated Arc Routing Problem (PCARP) was formulated. The solution was found using the Simulated Annealing algorithm, with the demand for waste collection being considered randomly. The vehicle routing problem was solved using multi-chaotic variant of differential evolution in [11] and for capacited version in [12]. The multi-period fleet size and mix vehicle routing problem with stochastic demands was presented to make strategic fleet sizing decisions [13]. The models deal with a specific problems such as periodicity, different fleet, different capacities. However, there is no combination of Multi-Processor Multi-Trip PCARP with Heterogeneous Fleet in the literature that describes the real problem for solving tasks in the context of collection companies in the Czech Republic. Another novelty is a way of describing a task and simplifying it in the context of quality preprocessing, which greatly simplifies the model, different fractions, type of edges, etc. 2 Problem Formulation Assuming a heterogeneous fleet (each vehicle has a different capacity) with vehicles that stand at depot. A time horizon defines days in which a vehicle can be operated (working days) and also the time of working shift is limited. Vehicles can operate within the streets during the working hours, while repeated return to processing facilities is allowed. The routing is performed on the oriented graph that describes the urban infrastructure transport network in which we have both bidirectional edges and unidirectional edges. Edges can be divided into four groups. Edges representing the exit from the depot, level crossing edges, edges with demand for collection and processing edges, i.e. edges where waste is disposed of (disposal at the landfill, incineration at the Waste-to-Energy plant or other). All considered edges do not have to be served. A positive demand for waste collection is assigned to demand edges. If the edge is defined for both directions (the arc and its inverse arc), only one has to be serviced. Each demand edge has a specified frequency with which the waste must be collected. Based on this parameter, possible scenarios are constructed with regard to a reasonable time gap between the collection days. The goal of the mathematical model is to find scenarios for all edges and to assign vehicles in order to minimize total costs with respect to time and capacity constraints. 2.1 Notation To formulate a mathematical model, sets, parameters, and variables must be defined. The notation and symbol description is stated in the following. Sets Iset of working days for collection, i.e., time horizon, Jvehicle fleet, set of available vehicles, Aset of all arcs, Nset of demand arcs and depot, N0set of demand arcs, Mset of processing arcs, M0set of processing arcs and depot, Sset of possible servicing scenarios, S(k) subset of scenarios Sinduced by demand arc k, Parameters cD k,l transport cost from arc kto arc l(k, l ∈ A), cS kservicing cost of demand arc k(k∈ N0), dldemand of arc l(l∈ N), Qjvehicle capacity j(j∈ J ), tD k,l transport time from arc kto arc l(k, l ∈ A), Heuristics for Waste Collection Arc Routing Problem MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 16 tS kservicing time of arc k(k∈ N0), tP kservicing time of processing arc k(k∈ M), mI k,l indicator matrix element, i.e., existence of inverse arc lwith arc k(k, l ∈ N0), gi,s 1 colection is performed on day iin scenario s(i∈ I, s ∈ S) 0 otherwise, Mbig constant, i.e., number used as limit on constraints (activation and deactivation), Tdaily working hours (available time), Variables Li,j,k maximal load of vehicle jon day iafter servicing of arc k, (i∈ I, j ∈ J , k ∈ A), xi,j,k,l    1 if arc lis served after arc kby vehicle jon day i (i∈ I, j ∈ J , k, l ∈ A) 0 otherwise, δi,j,k    1 if demand arc kis served by vehicle jon day i (i∈ I, j ∈ J , k ∈ N0) 0 otherwise, yk,s    1 if demand arc kuses scenario s (k∈ N0, s ∈ S(k)) 0 otherwise. 2.2 Model Formulation Using the notation from 2.1, a mathematical model that matches the given problem can be formulated with objective function considering cost as in equation (1). This model will find a scenario for each demand edge and edge sequence to be served for each vehicle for all days considered so that the total cost is minimal. min X i∈I X j∈J X k∈A X l∈A cD k,lxi,j,k,l +X i∈I X j∈J X k∈N 0 cS kδi,j,k (1) s.t. X k∈A xi,j,k,h −X l∈A xi,j,h,l = 0,∀i∈ I,∀j∈ J ,∀h∈ A,(2) Li,j,k +dl−Li,j,l ≤(1 −xi,j,k,l)M, ∀i∈ I,∀j∈ J ,∀k∈ A,(3) ∀l∈ N, Li,j,k ≤Qj,∀i∈ I,∀j∈ J ,∀k∈ N 0,(4) Li,j,k = 0,∀i∈ I,∀j∈ J ,∀k∈ M0,(5) X l∈A xi,j,0,l ≤1,∀i∈ I,∀j∈ J ,(6) X k∈A X l∈A xijkl ≤MX l∈A xi,j,0,l,∀i∈ I,∀j∈ J ,(7) X k∈A X l∈A tD k,lxi,j,k,l +X k∈N 0 tS kδi,j,k +X k∈A X l∈M tP lxi,j,k,l ≤T, ∀i∈ I,∀j∈ J ,(8) δi,j,l ≤X k∈A xi,j,k,l,∀i∈ I,∀j∈ J ,∀l∈ N 0,(9) X k∈A xi,j,k,l ≤δi,j,lM, ∀i∈ I,∀j∈ J ,∀l∈ N0,(10) mI k,l(yk,s −yl,s) = 0,∀k, l ∈ N 0:l > k, ∀s∈ S(k),(11) X s∈S(k) yk,s = 1,∀k∈ N0,(12) X s∈S(k) gi,syk,s −X j∈J (δi,j,k +X l∈N 0 mI k,lδi,j,l) = 0,∀k∈ N0,∀i∈ I,(13) V. Nevrly et al. MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 17 Li,j,k ≥0,∀i∈ I,∀j∈ J ,∀k∈ A,(14) xi,j,k,l ∈ {0,1},∀i∈ I,∀j∈ J ,∀k, l ∈ A,(15) δi,j,k ∈ {0,1},∀i∈ I,∀j∈ J ,∀k∈ N 0,(16) yk,s ∈ {0,1},∀k∈ N0,∀s∈ S(k).(17) The objective function (1) minimizes the cost for transportation through the streets (both servicing and transferring), which are generally assumed different for mutually inverse arcs. This means that in terms of costs, it is distinguished between the direction in which the street is passed. This can be caused, for example, by a steep rise in the street. The equations (2) ensure continuity between successive arcs i.e. if the vehicle enters the arc, it must also leave it. Constraints (3) prevent the creation of forbidden subtours and, at the same time, recalculate the current vehicle load after visiting the given arc. In the next equations (4), the vehicle load is limited by its capacity. Constraints (5) indicate that the vehicle load in processing plants and in depot is zero. The equations (6) ensure that every vehicle can start the trip from depot at most once per day of the time horizon. However, the number of collection routes is not limited - the waste can transported to processing facilities multiple times (when all other constraints are met). If the vehicle services any arc, then it has to leave the depot (7). Operating time of the vehicle is restricted in equations (8), while counting transportation time, servicing time and a waste unloading time at the processing plant. Constraints (9) and (10) describe the relationship between δi,j,k and xi,j,k,l. One binary variable indicates the other and vice versa, while for xi,j,k,l the value is aggregated. Arcs that are inverse to each other must met equations (11), where the same collection planning scenario is chosen for both. The choice of just one scenario for each demand arc is provided by the equation (12). The equations (13) define the collection plan for all arcs. The selected scenario is applied for demand arcs or their inversions, if they exist. The equations (14) indicate the non-negativity of the load. Finally, (15), (16) and (17) introduce variables as binary. 3 Problem Solution Mathematical models such as the one in the previous section are very difficult to solve [14]. Since there are enormous number of binary variables for the real instance of the model, it is preferable to use heuristic approach. The input data such as the matrix of distances and times has to be defined prior the calculation, i.e. the distance of the end node of one arc to the initial node of the second arc. The shortest path among all arcs has to be found. The Dijkstra algorithm is used in this step [15]. This procedure eliminates the crossing arcs. To get the final route the predecessor matrix is used [14]. It defines the sequence of arcs across the shortest path. The algorithm of route computation is described in the next subsection. 3.1 Algorithm The proposed algorithm is based on a combination of a genetic algorithm with local search (LS). Programming language C++ was used for its implementation. Specifically, the idea of maintaining two separate populations was derived. Individuals were kept in a set of feasible and infeasible solutions. In addition, the so-called biased fitness and diversification were used to select individuals who survive and go to the next generation. Solution representation is explicit here to avoid complex and time-consuming decoding processes while running the algorithm. The solution is then in the form of demand arc sequences for each route of each vehicle for all days of the time horizon. Due to the crossover process, the processing facilities and the depot are not included in this sequence, but given implicitly. The key component of this algorithm is the fitness function, which is considered for solution Sol as follows: fit(S) = E(S) + wQvQ(S) + wTvT(S),(18) where vQ(S) and vT(S) are exceeded values of capacity and time, wQand wTare the respective penalization and E(S) defines the total cost. The initialization of populations is performed through two algorithms that create reasonable routes, i.e. Route-Merging and Path-Scanning, see [16]. Algorithm 1 describes the main scheme in the pseudocode. The stopping criterion depends on the decision, it can be the total number of iterations, the running time of the algorithm, the number of diversification operations performed, or a combination of the previous ones. The crossover process is a phase where two P1and P2ancestors are selected to create a new individual C. This selection is for both ancestors realized by binary tournament, i.e. two individuals are randomly selected from the entire population (merge of feasible and infeasible populations) and choose the one with the better (less) fitness. Heuristics for Waste Collection Arc Routing Problem MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 18 Algorithm 1 General scheme of the algorithm 1: Initialize population; 2: while stopping criteria is not met do 3: Select parents P1and P2 4: Perform crossover of P1and P2to yield offspring C 5: Perform local search or repair of Cwith probabilities PLS , resp. PRep 6: if Cis feasible then Insert Cinto feasible subpopulation 7: end if 8: if Cis infeasible then Insert Cinto infeasible subpopulation 9: end if 10: if One of the subpopulation reached its maximum size then 11: Perform survivor selection with this subpopulation 12: end if 13: if best solution not improved for ItDIV iterations then 14: Diversify population 15: end if 16: end while 17: return best feasible solution These two individuals then enter their own process of crossover, which begins by selecting the day from the time horizon i. On this day, the vehicle is randomly picked from both and their routes are combined to get a new individual C. At this stage, the assignment of the scenario to demand arcs must be performed in order to meet all requirements of individual C. After crossover, there is a phase of local search or repair of the solution. These adjustments try to make solutions feasible and to improve their fitness. There are considered three possible movements from the initial solution. •Single Insertion (SI): moves the demand arc from the sequence to another position. •Double Insertion (DI): moves two consecutive demand arcs from a sequence to another positions. •Swap: the positions of two demand arcs are swapped. All of these movements take place on the same day to keep the assigned scenario. Both possible directions (inversion to arc) are tested. These movements are performed in random order while the solution is being improved. The repair phase uses local search and, in addition, it adds penalty parameters wQand wTto the fitness function during iterations to emphasize the importance of getting a feasible solution. Another part of the algorithm is the survivor selection, which is performed when a specified number of individuals in one population is reached. The aim is to reduce the size of the population to a certain level, and then resume with crossover. The main priority is to remove the clones, which are very similar individuals. Having two similar individuals in the population has no benefit in terms of the genetic algorithm. Hamming distance is used to find similarity, see [17]. Furthermore, the biased fitness is introduced to select individuals who will be removed from the population. This selection is based on two characteristics of how good a given solution is and how much it contributes to the diversity of the population. The last procedure to manage the population is diversification. This process is performed when there is no improvement during a certain number of iterations. From both populations, some individuals are removed by selecting survivors and replaced by several new individuals using the initialization phase. This process will dramatically change the diversity of the population and revive further searches. The procedure of SI movement is described in detail, while the others are based on the similar idea. The process begins by selecting the day from the time horizon where the SI will take the part. It goes through each arc of the sequence of all vehicles to test the improvement. For tested arc T A (two consecutive arcs in the case of DI), the fitness contribution is calculated according to the equation: contribution =cD m,T A +cS T A +cD T A,n −cD m,n,(19) where mand nare the previous and the next arcs in the sequence. Then the neighbourhood N(T A) is searched and for the position nof each arc is calculated contribution of arc T A. If the contribution at new position is lesser than the original one, then the solution is evaluated and its feasibility checked (vehicle capacity and operating time). The pseudocode of the algorithm is displayed in Algorithm 2. V. Nevrly et al. MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 19 Algorithm 2 Local Search algorithm 1: Choose i∈Sol 2: for all j, k, l ∈Sol[i]do 3: T A := Sol[i, j, k, l] 4: Calculate oldContribution 5: for all n∈N(T A) : nused in Sol[i]do 6: Calculate newContribution 7: if newContribution < oldContribution then 8: Copy old solution and perform move 9: Check feasibility 10: if feasible then 11: Replace by new sub-solution and return improved Solution 12: end if 13: end if 14: end for 15: end for The second most challenging operation is crossover. Similarly to LS, the method utilises more accurate neighbourhood and recalculation with contribution. The inputs of the algorithm are two ancestors P1and P2. The algorithm starts with random selection of day ifrom time horizon, vehicle j1∈P1[i] and vehicle j2∈P2[i]. Then a new individual Cis created by copying the P1solution, and its vehicle j1is replaced by a j2vehicle while the capacity of individual Cremains the same. Arcs occurring multiple times at day iare deleted from the solution. The change of scenarios for all arcs of P1[i, j1]∪P2[i, j2] follows according to the ancestor P2and removing the arcs that have changed. Now a set Rthat contains all missing arcs is created. For the next steps, the parameters conCost,conT vQ and conT vT are introduced. This means the contribution of the arc, the increase in capacity constraint violation and the increase in time constraint violation. There are also parameters with the Bflag, indicating the same properties for the best nBposition to insert. The algorithm then goes through all the non-assigned arcs e∈R, and for each of them selects from the neighbourhood N(e) the arc position nBsuch that all the previously mentioned properties are the smallest. This position is then used for insertion of arc eand the fitness function is recalculated. Algorithm 3 describes the whole approach. Algorithm 3 Crossover algorithm 1: Input: P1, P 2 2: Randomly choose i∈ I 3: Randomly choose j1∈P1[i] and j2∈P2[i] 4: C:= P1 5: Replace j1of Cby j2and remove redundant tasks in period iof C 6: for all e∈P1[i, j1]∪P2[i, j2]do 7: replace scenarios for eof Cwith that in P2 8: end for 9: Remove all tasks of Cwhose scenario was changed 10: Add all missed tasks to set R 11: for all e∈Rdo 12: BconCost, BconTvQ, BconTvT, nB:= infinity 13: for all n∈N(e) : scenarios of eand nare equal do 14: Calculate conCost, conTvQ and conTvT 15: if conCost ≤BconCost ∧conT vQ ≤BconT vQ ∧conT vT ≤BconT vT then 16: BconCost := conCost 17: BconT vQ := conT vQ 18: BconT vT := conT vT 19: nB:= n 20: end if 21: end for 22: Insert eto position of nBand recalculate fitness of C 23: end for Heuristics for Waste Collection Arc Routing Problem MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 20 In this way, a new individual Cis created. This individual is further sent to other procedures - LS or Repair, depending on the feasibility of the given solution, see algorithm 1. An adaptive parameter control has been introduced to improve the algorithm’s performance. This control changes the parameters wQand wTaccording to the ratio of frequencies of feasible and infeasible solutions. The smaller the proportion is (generating more infeasible solutions), the greater are the penalties, and vice versa. 4 Testing The presented algorithm was tested on the real network of Jihlava. The considered network contains 1,467 vertices and 3,529 edges. Other input parameters (costs of operation and capacities of vehicles, production and demand for waste collection) were appropriately generated on the basis of demographic data and waste management expert estimates. The best performance was obtained with probabilities 0.57 and 0.61 for PLS , resp. PRep. The need of randomness in evolutionary algorithms was discussed and numerically tested in [18]. The functionality and speed of the algorithm were studied on these data. The maximum population size was set to 100 for both feasible and infeasible. The average calculation time per iteration was 0.69 second. Fitness value development was highly dependent on the penalization rates (wQand wT). Initially, the algorithm quickly improves the solution but with increasing iterations, the improvement interval increases. Once the solution has not been improved for 30 iterations, a diversification procedure is introduced, which adds diversity to the population and thus revives the entire crossover procedure. The real case study was conducted for another city with 8,594 nodes. The calculation was performed for specific district and route, where 264 arcs including inverse arcs were linked with 160 containers for paper waste collection. The output was compared with the currently operated route and savings were identified. The operated route distance is 71.4 km, while the result of the algorithm suggested route of 66.7 km length. This reveals the potential of almost 7 % of savings, which corresponds with 1,400 EUR annually per one route. 5 Conclusion An advanced tool for supporting planning in the field of waste logistics at a micro-regional level is needed to effectively implement and meet goals. Tasks from waste collection mostly fall into operations research field. However, such supply chain models are very complex and have hight time requirements for computing the solution, which is mainly due to the combinatorial nature of the problem. Thus, it is necessary to proceed with a heuristic approach. In this paper, the combination of genetic algorithm and local search was presented in pseudocodes and the whole approach was described. These tasks are also demanding from the input data point of view, therefore it is necessary to perform thorough preprocessing and statistical evaluation. Tasks related to waste collection, fleet sizing, locating containers, and assessing the overall economic and environmental impact must meet operational requirements to credibly model the reality. The use of defined tasks is designed to support investment decision-making and project implementation, primarily by minimizing costs, impact on the population or the environment. The heuristic algorithm was used for real infrastructure and better performance was found for already operated routes. Potential savings of almost 7 % were identified for studied problem. If such lesser cost would be realizable for all routes and vehicles during the year, it would be saved up to tens of thousands of euros on costs. New limitations and decision criteria can be implemented in the algorithm as well as in the model. In heuristic algorithms, the fitness for emissions, costs and time can be defined and compared in the future. In addition, the option for collection days might be added. One variant considers fixed collection days according to the current plan. In the second variant, the aim is to create a schedule of collection days for all containers. So far, allowed combinations of collection days have been generated based on frequency. Identical solutions often appear in the current population of acceptable solutions, so the next challenge is to prevent the creation of clones that already exist in the population. Thus, a clone test may be performed before a new solution is included in the population. Acknowledgement: The authors gratefully acknowledge financial support provided by ERDF within the research project No. CZ.02.1.01/0.0/0.0/16 026/0008413 “Strategic Partnership for Environmental Technologies and Energy Production”. The authors also sincerely thank for the financial support given by the Ministry of Education, Youth and Sports of the Czech Republic under the standard specific research project FCH/FSI-J19-5794. V. Nevrly et al. MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 21 References [1] Barbosa-P´ovoa, A. P., da Silva, and C., Carvalho, A. 2018. Opportunities and challenges in sustainable supply chain: An operations research perspective. European Journal of Operational Research 268, 2, pp. 399–431. DOI: 10.1016/j.ejor.2017.10.036 [2] M´alek, M., ˇ Sompl´ak, R., Popela, P., and K˚udela, J. 2018. Stochastic integer waste management problem solved by a modified progressive hedging algorithm. Mendel 24, 2, pp. 17–22. [3] Nowakowski, P., Szwarc, K., and Boryczka, U. 2018. Vehicle route planning in e-waste mobile collection on demand supported by artificial intelligence algorithms. Transportation Research Part D: Transport and Environment 63, pp. 1–22. DOI: 10.1016/j.trd.2018.04.007 [4] K˚udela, J. and Popela, P. 2018. Two-stage stochastic facility location problem: GA with benders decomposition. Mendel 21, pp. 53–58. [5] Ramos, T. R. P., Gomes, M. I., and Barbosa-P´ovoa, A. P. 2014. Assessing and improving management practices when planning packaging waste collection systems. Resources, Conservation and Recycling 85, pp. 116–129. DOI: 10.1016/j.resconrec.2013.12.013 [6] Ramos, T. R. P., Gomes, M. I., and Barbosa-P´ovoa, A. P. 2014. Economic and environmental concerns in planning recyclable waste collection systems. Transportation Research Part E: Logistics and Transportation Review 62, pp. 34–54. DOI: 10.1016/j.tre.2013.12.002 [7] Zbib, H. and Wøhlk, S. 2019. A comparison of the transport requirements of different curbside waste collection systems in Denmark. Waste Management 87, pp. 21–32. DOI: 10.1016/j.wasman.2019.01.037 [8] Bing, X., de Keizer, M., Bloemhof-Ruwaard, J. M., and van der Vorst, J. G. A. J. 2014. Vehicle routing for the eco-efficient collection of household plastic waste. Waste Management 34, 4, pp. 719–729. DOI: 10.1016/j.wasman.2014.01.018 [9] Laureri, F., Minciardi, R., and Robba, M. 2016. An algorithm for the optimal collection of wet waste. Waste Management 48, pp. 56–63. DOI: 10.1016/j.wasman.2015.09.020 [10] Tirkolaee, E. B., Mahdavi, I., Esfahani, M. M. S. 2018. A robust periodic capacitated arc routing problem for urban waste collection considering drivers and crew’s working time. Waste Management 76, pp. 138–146. DOI: 10.1016/j.wasman.2018.03.015 [11] Viktorin, A., Hrabec, D., and Pluh´aˇcek, M. 2016. Multi-chaotic differential evolution for vehicle routing problem with profits. In 30th European Conference on Modelling and Simulation. European Council for Modelling and Simulation (ECMS), Regensburg, pp. 245–251. [12] Davendra, D., Zelinka, I., Bialic-Davendra, M., ˇ Senkeˇr´ık, R., and Jaˇsek, R. 2011. Discrete self organising migrating algorithm for the task of capacitated vehicle routing problem. Mendel 17, pp. 259–265. [13] Pasha, U., Hoff, A., and Hvattum, L. M. 2018. The multi-period fleet size and mix vehicle routing problem with stochastic demands. Computational Methods in Applied Sciences 45, pp. 121–146. DOI: 10.1007/9783-319-54490-8 9 [14] Wolsey, L. A. 1998. Integer programming. Wiley, New York. [15] Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 1, pp. 269–271. DOI: 10.1007/BF01386390 [16] Golden, B. L., Dearmon, J. S., and Baker, E. K. 1983. Computational experiments with algorithms for a class of routing problems. Computers and Operations Research 10, 1, pp. 47–59. DOI: 10.1016/03050548(83)90026-6 [17] Vidal, T., Crainic, T. G., and Gendreau, M. 2012. A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems. Operations Research 60, 3, pp. 611–624. [18] Zelinka, I., ˇ Senkeˇr´ık, R., and Pluh´aˇcek, M. 2013. Do evolutionary algorithms indeed require randomness?. In 2013 IEEE Congress on Evolutionary Computation. IEEE, Cancun, Mexico, pp. 2283–2289. DOI: 10.1109/CEC.2013.6557841 Heuristics for Waste Collection Arc Routing Problem MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 22