Routing in waste collection: A simulated annealing algorithm for an Argentinean case study

Diego G. Rossit; Adrián A. Toncovich; Matías Fermani; Diego G. Rossit; Adrián A. Toncovich; Matías Fermani

doi:10.3934/mbe.2021470

Mathematical Biosciences and Engineering

2021, Volume 18, Issue 6: 9579-9605. doi: 10.3934/mbe.2021470

Previous Article Next Article

Research article Special Issues

Routing in waste collection: A simulated annealing algorithm for an Argentinean case study

1.
Department of Engineering, Universidad Nacional del Sur, Alem Av. 1253, Bahía Blanca 8000, Argentina
2.
INMABB UNS-CONICET, Alem Av. 1253, Bahía Blanca 8000, Argentina

Academic Editor：Yang Kuang

Received: 11 August 2021 Accepted: 12 October 2021 Published: 03 November 2021

The management of the collection of Municipal Solid Waste is a complex task for local governments since it consumes a large portion of their budgets. Thus, the use of computer-aided tools to support decision-making can contribute to improve the efficiency of the system and reduce the associated costs, especially in developing countries, which usually suffer from a shortage of resources. In the present work, a simulated annealing algorithm is proposed to address the problem of designing the routes of waste collection vehicles. The proposed algorithm is compared to a commercial solver based on a mixed-integer programming formulation and two other metaheuristic algorithms, i.e., a state-of-the-art large neighborhood search and a genetic algorithm. The evaluation is carried out on both a well-known benchmark from the literature and real instances of the Argentinean city of BahȪa Blanca. The proposed algorithm was able to solve all the instances, having a performance similar to the large neighborhood procedure, while the genetic algorithm showed the worst results. The simulated annealing algorithm was also able to improve the solutions of the solver in many instances of the real dataset.
- municipal solid waste,
- waste collection,
- vehicle routing problem,
- simulated annealing,
- large neighborhood search,
- genetic algorithm,
- mixed-integer programming
Citation: Diego G. Rossit, Adrián A. Toncovich, Matías Fermani. Routing in waste collection: A simulated annealing algorithm for an Argentinean case study[J]. Mathematical Biosciences and Engineering, 2021, 18(6): 9579-9605. doi: 10.3934/mbe.2021470

Related Papers:

Abstract

The management of the collection of Municipal Solid Waste is a complex task for local governments since it consumes a large portion of their budgets. Thus, the use of computer-aided tools to support decision-making can contribute to improve the efficiency of the system and reduce the associated costs, especially in developing countries, which usually suffer from a shortage of resources. In the present work, a simulated annealing algorithm is proposed to address the problem of designing the routes of waste collection vehicles. The proposed algorithm is compared to a commercial solver based on a mixed-integer programming formulation and two other metaheuristic algorithms, i.e., a state-of-the-art large neighborhood search and a genetic algorithm. The evaluation is carried out on both a well-known benchmark from the literature and real instances of the Argentinean city of BahȪa Blanca. The proposed algorithm was able to solve all the instances, having a performance similar to the large neighborhood procedure, while the genetic algorithm showed the worst results. The simulated annealing algorithm was also able to improve the solutions of the solver in many instances of the real dataset.

References

[1]	D. Hoornweg, P. Bhada-Tata, What a waste: a global review of solid waste management, World Bank, 15 (2012), 116.
[2]	G. Tchobanoglous, F. Kreith, M. Williams, Introduction, in Handbook of solid waste management (eds. G. Tchobanoglous, F. Kreith), McGraw-Hill, (2002).
[3]	E. Tirkolaee, P. Abbasian, M. Soltani, S. Ghaffarian, Developing an applied algorithm for multi-trip vehicle routing problem with time windows in urban waste collection: A case study, Waste Manage. Res., 37 (2019), 4–13. doi: 10.1177/0734242X18807001
[4]	M. Fermani, D. Rossit, A. Toncovich, A simulated annealing algorithm for solving a routing problem in the context of municipal solid waste collection, in Proceedings of the Xth International Conference of Production Research-Americas 2020, (2021).
[5]	P. Pop, L. Fuksz, A. Marc, C. Sabo, A novel two-level optimization approach for clustered vehicle routing problem, Comput. Ind. Eng., 115 (2018), 304–318. doi: 10.1016/j.cie.2017.11.018
[6]	C. Miller, A. Tucker, R. Zemlin, Integer programming formulation of traveling salesman problems. J. ACM, 7 (1960), 326–329. doi: 10.1145/321043.321046
[7]	J. Lenstra, A. Kan, Complexity of vehicle routing and scheduling problems, Networks, 11 (1981), 221–227. doi: 10.1002/net.3230110211
[8]	D. Rossit, J. Toutouh, S. Nesmachnow, Exact and heuristic approaches for multi-objective garbage accumulation points location in real scenarios, Waste Manage., 105 (2020), 467–481. doi: 10.1016/j.wasman.2020.02.016
[9]	S. Nesmachnow, D. Rossit, J. Toutouh. Comparison of multiobjective evolutionary algorithms for prioritized urban waste collection in Montevideo, Uruguay, Electron. Notes Discrete Math., 69 (2018), 93–100. doi: 10.1016/j.endm.2018.07.013
[10]	A. Toncovich, T. Burgos, M. Jalif, Planificación de la logística de recolección de miel en una empresa apícola, in Proceedings of the X Congreso Argentino de Ingeniería Industrial, (2017), 397–406.
[11]	A. Toncovich, D. Rossit, M. Frutos, D. Rossit, Solving a multi-objective manufacturing cell scheduling problem with the consideration of warehouses using a Simulated Annealing based procedure, Int. J. Ind. Eng. Comput., 10 (2019), 1–16.
[12]	S. Kirkpatrick, C. Gelatt, M. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671–680. doi: 10.1126/science.220.4598.671
[13]	G. Erdoğan, An open source spreadsheet solver for vehicle routing problems, Comput. Oper. Res., 84 (2017), 62–72. doi: 10.1016/j.cor.2017.02.022
[14]	M. Dror, G. Laporte, P. Trudeau, Vehicle routing with split deliveries, Discrete Appl. Math., 50 (1994), 239–254. doi: 10.1016/0166-218X(92)00172-I
[15]	D. Naddef, G. Rinaldi, Branch-and-cut algorithms for the capacitated VRP, in The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, (2002), 53–84.
[16]	D. Pisinger, S. Ropke, A general heuristic for vehicle routing problems, Comput. Oper. Res., 34 (2007), 2403–2435. doi: 10.1016/j.cor.2005.09.012
[17]	P. Shaw, Using constraint programming and local search methods to solve vehicle routing problems, in Proceedings of the International Conference on Principles and Practice of Constraint Programming, (1998), 417–431.
[18]	C. Groër, B. Golden, E. Wasil, A library of local search heuristics for the vehicle routing problem, Math. Program. Comput., 2 (2010), 79–101. doi: 10.1007/s12532-010-0013-5
[19]	D. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., (1988).
[20]	F. Fortin, F. De Rainville, M. Gardner, M. Parizeau, C. Gagné, DEAP: Evolutionary algorithms made easy, J. Mach. Learn. Res., 13 (2012), 2171–2175.
[21]	M. Haj-Rachid, W. Ramdane-Cherif, P. Chatonnay, C. Bloch, Comparing the performance of genetic operators for the vehicle routing problem, IFAC Proc. Vol., 43 (2010), 313–319.
[22]	J. Beliën, L. De Boeck, J. Van Ackere, Municipal solid waste collection and management problems: a literature review, Trans. Sci., 48 (2012), 78–102.
[23]	H. Han, E. Ponce Cueto, Waste collection vehicle routing problem: literature review, PROMET Traffic Trans., 7 (2015) 345–358.
[24]	B. Kim, S. Kim, S. Sahoo, Waste collection vehicle routing problem with time windows, Comput. Oper. Res., 33 (2006), 3624–3642. doi: 10.1016/j.cor.2005.02.045
[25]	A. Benjamin, J. Beasley, Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities, Comput. Oper. Res., 37 (2010), 2270–2280. doi: 10.1016/j.cor.2010.03.019
[26]	E. Tirkolaee, I. Mahdavi, M. Esfahani, A robust periodic capacitated arc routing problem for urban waste collection considering drivers and crew's working time, Waste Manage., 76 (2018), 138–146. doi: 10.1016/j.wasman.2018.03.015
[27]	P. Nowakowski, K. Szwarc, U. Boryczka, Vehicle route planning in e-waste mobile collection on demand supported by artificial intelligence algorithms, Trans. Res. Part D Trans. Environ., 63 (2018), 1–22. doi: 10.1016/j.trd.2018.04.007
[28]	K. Mekamcha, M. Souier, H. Bessenouci, M. Bennekrouf, Two metaheuristics approaches for solving the traveling salesman problem: an Algerian waste collection case, Oper. Res., 2019 (2019), 1–21.
[29]	F. Bonomo, G. Durán, F. Larumbe, J. Marenco, Optimización de la Recolección de Residuos en la Zona Sur de la Ciudad de Buenos Aires, Revista Ingenierıa de Sistemas, 23 (2009).
[30]	F. Bonomo, G. Durán, F. Larumbe, J. Marenco, A method for optimizing waste collection using mathematical programming: a Buenos Aires case study, Waste Manage. Res., 30 (2012), 311–324. doi: 10.1177/0734242X11402870
[31]	F. Bertero, Optimización de recorridos en ciudades. Una aplicación al sistema de recolección de residuos sólidos urbanos en el Municipio de Concordia, Master thesis, Universidad Nacional de Rosario, 2015.
[32]	M. Bianchetti, G. Durán, I. Koch, J. Marenco, Algoritmos de zonificación para el problema de la recolección de residuos urbanos: el caso de estudio de una ciudad argentina, Revista Ingeniería de Sistemas, 21 (2017), 81–110.
[33]	G. Braier, G. Durán, J. Marenco, F. Wesner, An integer programming approach to a real-world recyclable waste collection problem in Argentina, Waste Manage. Res., 35 (2017), 525–533. doi: 10.1177/0734242X16688776
[34]	D. Delle Donne, V. Di Tomaso, G. Duran, Optimizing leaf sweeping and collection in the Argentine city of Trenque Lauquen, Waste Manage. Res., 39 (2021), 209–220. doi: 10.1177/0734242X20922597
[35]	A. Cavallin, D. Rossit, V. Herrán, D. Rossit, M. Frutos, Application of a methodology to design a municipal waste pre-collection network in real scenarios, Waste Manage. Res., 38 (2020), 117–129. doi: 10.1177/0734242X19894630
[36]	D. Rossit, S. Nesmachnow, J. Toutouh. A bi-objective integer programming model for locating garbage accumulation points: A case study, Revista Facultad de Ingeniería, 93 (2019), 70–81.
[37]	D. Rossit, F. Tohmé, M. Frutos, D. Broz, An application of the augmented ε-constraint method to design a municipal sorted waste collection system, Decis. Sci. Lett., 6 (2017), 323–336.
[38]	J. Toutouh, D. Rossit, S. Nesmachnow, Soft computing methods for multiobjective location of garbage accumulation points in smart cities, Ann. Math. Artificial Intell., 88 (2020), 105–131. doi: 10.1007/s10472-019-09647-5
[39]	A. Vázquez, Ruteo de alta perfomance con OSRM, 2018. Available from: https://rpubs.com/HAVB/osrm.
[40]	N. Christofides, S. Eilon, An algorithm for the vehicle-dispatching problem, J. Oper. Res. Soc., 20 (1969), 309–318. doi: 10.1057/jors.1969.75
[41]	J. Mendoza, M. Hoskins, C. Guéret, V. Pillac, D. Vigo, VRP-REP: a vehicle routing community repository, in Proceedings of Third meeting of the EURO Working Group on Vehicle Routing and Logistics Optimization VeRoLog'14, (2014).
[42]	IBM, IBM ILOG CPLEX 20.1 User's Manual, 2020. Available from: https://www.ibm.com/docs/en/icos/20.1.0?topic=cplex-users-manual.
[43]	GAMS, GAMS Documentation Center, 2021. Available from https://www.gams.com/35/docs/index.html.
[44]	P. Augerat, Approche Polyèdrale du Problème de Tournées de Véhicules, Ph.D thesis, Institut polytechnique de Grenoble, 1995.
[45]	M. Friedman, The use of ranks to avoid the assumption of normality implicit in the analysis of variance, J. Am. Stat. Assoc., 32 (1937), 675–701. doi: 10.1080/01621459.1937.10503522
[46]	O. Cosma, P. Pop, D. Dănciulescu, A novel matheuristic approach for a two-stage transportation problem with fixed costs associated to the routes, Comput. Oper. Res., 118 (2020), 104906. doi: 10.1016/j.cor.2020.104906
[47]	S. Shapiro, M. Wilk, An analysis of variance test for normality, Biometrika, 52 (1965), 591–611. doi: 10.1093/biomet/52.3-4.591
[48]	W. Kruskal, W. Wallis, Use of ranks in one-criterion variance analysis, J. Am. Stat. Assoc., 47 (1952), 583–621. doi: 10.1080/01621459.1952.10483441
[49]	A. Mahéo, D. Rossit, P. Kilby, A Benders decomposition approach for an integrated bin allocation and vehicle routing problem in municipal waste management, in Proceedings of the Xth International Conference of Production Research-Americas, (2020).

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)