Heuristics for Waste Collection Arc Routing Problem

Vlastimír Nevrlý; Radovan Šomplák; Pavel Popela

doi:10.13164/mendel.2019.1.015

Vlastimír Nevrlý Institute of Process Engineering, Faculty of Mechanical Engineering, Brno University of Technology, Czech Republic https://orcid.org/0000-0001-6613-0340
Radovan Šomplák Institute of Process Engineering, Faculty of Mechanical Engineering, Brno University of Technology, Czech Republic https://orcid.org/0000-0002-5714-4537
Pavel Popela https://orcid.org/0000-0003-4152-1884

DOI: https://doi.org/10.13164/mendel.2019.1.015

Keywords: waste management, combinatorial optimization, heuristics, routing problem, waste collection, arc routing

Abstract

Waste management is still an expanding eld which needs to be constantly enhanced so that waste transportation and treatment is as eective as possible. An important part of this process is a waste collection at the municipal level. Decision-making about daily routing for all vehicles from a heterogenous eet substantially in uences 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.

References

Barbosa-Povoa, 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

Malek, M., Somplak, R., Popela, P., and Kudela, J. 2018. Stochastic integer waste management problem solved by a modified progressive hedging algorithm. Mendel 24, 2, pp. 17-22.

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 andEnvironment 63, pp. 1-22. DOI: 10.1016/j.trd.2018.04.007

Kudela, J. and Popela, P. 2015. Two-stage stochastic facility location problem: GA with benders decomposition. Mendel 21, pp. 53-58.

Ramos, T. R. P., Gomes, M. I., and Barbosa-Povoa, 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

Ramos, T. R. P., Gomes, M. I., and Barbosa-Povoa, 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

Zbib, H. and Wohlk, 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

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

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

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

Viktorin, A., Hrabec, D., and Pluhacek, M. 2016. Multi-chaotic differential evolution for vehicle routing problem with prots. In 30th European Conference on Modelling and Simulation. European Council for Modelling and Simulation (ECMS), Regensburg, pp. 245-251.

Davendra, D., Zelinka, I., Bialic-Davendra, M., Senkerik, R., and Jasek, R. 2011. Discrete self organising migrating algorithm for the task of capacitated vehicle routing problem. Mendel 17, pp. 259-265.

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/978-3-319-54490-8_9

Wolsey, L. A. 1998. Integer programming. Wiley, New York.

Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 1, pp. 269-271. DOI: 10.1007/BF01386390

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/0305-0548(83)90026-6

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.

Zelinka, I., Senkerik, R., and Pluhacek, 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