State of the art on the problem of vehicle routing and solid waste collection
Estado del arte sobre el problema de ruta vehículo y recogida de residuos sólidos
DOI:
https://doi.org/10.56712/latam.v6i1.3528Palabras clave:
VRP, VRPPD, VRPB, recogida de residuos, ARPResumen
El problema de la recolección de residuos sólidos es uno de los principales inconvenientes presentes en cualquier asentamiento humano, el cual consta de dos procesos: el primero, la recolección de residuos, y el último, la entrega de los residuos a las entidades recicladoras o puntos de destino final. El modelado de este tipo de problema de recolección puede abordarse desde la perspectiva de los modelos VRP, dependiendo de las restricciones presentes en cada área geográfica donde se aborda. Así, esta investigación aplicada a la problemática de los centros urbanos, propone un análisis del estado del arte, los diferentes problemas de recorrido relacionados y los aportes más recientes relacionados con la recolección de residuos sólidos.
Descargas
Citas
Alinaghian, M., & Shokouhi, N. (2018). Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search. Omega, 76, 85-99. https://doi.org/10.1016/j.omega.2017.05.002 DOI: https://doi.org/10.1016/j.omega.2017.05.002
Alweshah, M., Almiani, M., Almansour, N., Al Khalaileh, S., Aldabbas, H., Alomoush, W., & Alshareef, A. (2022). Vehicle routing problems based on Harris Hawks optimization. Journal of Big Data, 9(1), 42. https://doi.org/10.1186/s40537-022-00593-4 DOI: https://doi.org/10.1186/s40537-022-00593-4
Angelelli, E., & Speranza, M. G. (2002). The Application of a Vehicle Routing Model to a Waste Collection Problem: Two Case Studies. En A. Klose, M. G. Speranza, & L. N. Van Wassenhove (Eds.), Quantitative Approaches to Distribution Logistics and Supply Chain Management (pp. 269-286). Springer. https://doi.org/10.1007/978-3-642-56183-2_16 DOI: https://doi.org/10.1007/978-3-642-56183-2_16
Arnold, F., & Sörensen, K. (2019). What makes a VRP solution good? The generation of problem-specific knowledge for heuristics. Computers & Operations Research, 106, 280-288. https://doi.org/10.1016/j.cor.2018.02.007 DOI: https://doi.org/10.1016/j.cor.2018.02.007
Ban, H.-B., & Nguyen, P. K. (2021). A hybrid metaheuristic for solving asymmetric distance-constrained vehicle routing problem. Computational Social Networks, 8(1), 3. https://doi.org/10.1186/s40649-020-00084-7 DOI: https://doi.org/10.1186/s40649-020-00084-7
Becker, C., Gauthier, J. B., Gschwind, T., & Schneider, M. (2023). In-depth analysis of granular local search for capacitated vehicle routing. Discrete Applied Mathematics, 329, 61-86. https://doi.org/10.1016/j.dam.2022.12.019 DOI: https://doi.org/10.1016/j.dam.2022.12.019
Beliën, J., De Boeck, L., & Van Ackere, J. (2014). Municipal Solid Waste Collection and Management Problems: A Literature Review. Transportation Science, 48(1), 78-102. DOI: https://doi.org/10.1287/trsc.1120.0448
Berhan, E., Beshah, B., Kitaw, D., & Abraham, A. (2014). Stochastic Vehicle Routing Problem: A Literature Survey. Journal of Information & Knowledge Management, 13(03), 1450022. https://doi.org/10.1142/S0219649214500221 DOI: https://doi.org/10.1142/S0219649214500221
Bierlaire, M. (2015). Simulation and optimization: A short review. Transportation Research Part C: Emerging Technologies, 55(Supplement C), 4-13. https://doi.org/10.1016/j.trc.2015.01.004 DOI: https://doi.org/10.1016/j.trc.2015.01.004
Boudali, I., & Ragmoun, M. (2022). A Memetic Approach for Routing Problem with Capacity and Time Constraints. En C. Bădică, J. Treur, D. Benslimane, B. Hnatkowska, & M. Krótkiewicz (Eds.), Advances in Computational Collective Intelligence (pp. 612-626). Springer International Publishing. https://doi.org/10.1007/978-3-031-16210-7_50 DOI: https://doi.org/10.1007/978-3-031-16210-7_50
Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300-313. https://doi.org/10.1016/j.cie.2015.12.007 DOI: https://doi.org/10.1016/j.cie.2015.12.007
Brownlee, J. (2012). Clever Algorithms: Nature-Inspired Programming Recipes. Lulu.com.
Chen, J., & Shi, J. (2019). A multi-compartment vehicle routing problem with time windows for urban distribution – A comparison study on particle swarm optimization algorithms. Computers & Industrial Engineering, 133, 95-106. https://doi.org/10.1016/j.cie.2019.05.008 DOI: https://doi.org/10.1016/j.cie.2019.05.008
Chiussi, A., de Paula Felix, G., Iori, M., & dos Santos, A. G. (2022). Industrial Waste Collection Optimization: A Real-World Case Study in Northern Italy. En J. de Armas, H. Ramalhinho, & S. Voß (Eds.), Computational Logistics (pp. 147-161). Springer International Publishing. https://doi.org/10.1007/978-3-031-16579-5_11 DOI: https://doi.org/10.1007/978-3-031-16579-5_11
Corberán, Á., Eglese, R., Hasle, G., Plana, I., & Sanchis, J. M. (2021). Arc routing problems: A review of the past, present, and future. Networks, 77(1), 88-115. https://doi.org/10.1002/net.21965 DOI: https://doi.org/10.1002/net.21965
Deep, L., & Tanmay, S. (2022). Study and Review of Various Techniques on Searching Optimal Route for Online Ordering System. En J. Shah, S. S. Arkatkar, & P. Jadhav (Eds.), Intelligent Infrastructure in Transportation and Management (pp. 261-270). Springer. https://doi.org/10.1007/978-981-16-6936-1_21 DOI: https://doi.org/10.1007/978-981-16-6936-1_21
Del Pia, A., & Filippi, C. (2006). A variable neighborhood descent algorithm for a real waste collection problem with mobile depots. International Transactions in Operational Research, 13(2), 125-141. https://doi.org/10.1111/j.1475-3995.2006.00539.x DOI: https://doi.org/10.1111/j.1475-3995.2006.00539.x
Doerner, K. F., Kiefer, A., & Wolfinger, D. (2016). Twenty Years of Vehicle Routing in Vienna. En H. Dawid, K. F. Doerner, G. Feichtinger, P. M. Kort, & A. Seidl (Eds.), Dynamic Perspectives on Managerial Decision Making: Essays in Honor of Richard F. Hartl (pp. 491-520). Springer International Publishing. https://doi.org/10.1007/978-3-319-39120-5_26 DOI: https://doi.org/10.1007/978-3-319-39120-5_26
Eglese, R. W., & Letchford, A. N. (2000). Polyhedral Theory for Arc Routing Problems. En M. Dror (Ed.), Arc Routing: Theory, Solutions and Applications (pp. 199-230). Springer US. https://doi.org/10.1007/978-1-4615-4495-1_6 DOI: https://doi.org/10.1007/978-1-4615-4495-1_6
El-Gharably, N. E., El-Kilany, K. S., & El-Sayed, A. E. (2013). Optimization Using Simulation of the Vehicle Routing Problem. International Journal of Industrial and Manufacturing Engineering, 7(6), 1236-1242.
Elshaer, R., & Awad, H. (2020). A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants. Computers & Industrial Engineering, 140, 106242. https://doi.org/10.1016/j.cie.2019.106242 DOI: https://doi.org/10.1016/j.cie.2019.106242
Expósito-Márquez, A., Expósito-Izquierdo, C., Brito-Santana, J., & Moreno-Pérez, J. A. (2018). Solving an Eco-efficient Vehicle Routing Problem for Waste Collection with GRASP. En J. Del Ser, E. Osaba, M. N. Bilbao, J. J. Sanchez-Medina, M. Vecchio, & X.-S. Yang (Eds.), Intelligent Distributed Computing XII (pp. 215-224). Springer International Publishing. https://doi.org/10.1007/978-3-319-99626-4_19 DOI: https://doi.org/10.1007/978-3-319-99626-4_19
Fan, W., Xu, H., & Xu, X. (2009). Simulation on vehicle routing problems in logistics distribution. COMPEL - The international journal for computation and mathematics in electrical and electronic engineering, 28(6), 1516-1531. https://doi.org/10.1108/03321640910992056 DOI: https://doi.org/10.1108/03321640910992056
Gendreau, M., Laporte, G., & Séguin, R. (1996). Stochastic vehicle routing. European Journal of Operational Research, 88(1), 3-12. https://doi.org/10.1016/0377-2217(95)00050-X DOI: https://doi.org/10.1016/0377-2217(95)00050-X
Ghiani, G., Guerriero, F., Improta, G., & Musmanno, R. (2005). Waste collection in Southern Italy: Solution of a real-life arc routing problem. International Transactions in Operational Research, 12(2), 135-144. https://doi.org/10.1111/j.1475-3995.2005.00494.x DOI: https://doi.org/10.1111/j.1475-3995.2005.00494.x
Gunes, C., van Hoeve, W.-J., & Tayur, S. (2010). Vehicle Routing for Food Rescue Programs: A Comparison of Different Approaches. En A. Lodi, M. Milano, & P. Toth (Eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (pp. 176-180). Springer. https://doi.org/10.1007/978-3-642-13520-0_21 DOI: https://doi.org/10.1007/978-3-642-13520-0_21
Hasni, S., Toumi, S., Jarboui, B., & Mjirda, A. (2017). GVNS based heuristic for solving the multi-product multi-vehicle inventory routing problem. Electronic Notes in Discrete Mathematics, 58, 71-78. https://doi.org/10.1016/j.endm.2017.03.010 DOI: https://doi.org/10.1016/j.endm.2017.03.010
Herazo-Padilla, N., Montoya-Torres, J. R., Isaza, S. N., & Alvarado-Valencia, J. (2015). Simulation-optimization approach for the stochastic location-routing problem. Journal of Simulation, 9(4), 296-311. https://doi.org/10.1057/jos.2015.15 DOI: https://doi.org/10.1057/jos.2015.15
Juan, A. A., Faulin, J., Pérez-Bernabeu, E., & Domínguez, O. (2013). Simulation-Optimization Methods in Vehicle Routing Problems: A Literature Review and an Example. En Modeling and Simulation in Engineering, Economics, and Management (pp. 115-124). Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38279-6_13 DOI: https://doi.org/10.1007/978-3-642-38279-6_13
Kocatü, F., rk, Tü, G. Y., tü, ncü, & Salhi, S. (2021). The multi-depot heterogeneous VRP with backhauls: Formulation and a hybrid VNS with GRAMPS meta-heuristic approach. Annals of Operations Research, 307(1-2), 277-303. DOI: https://doi.org/10.1007/s10479-021-04137-6
Laporte, G. (2009). Fifty Years of Vehicle Routing. Transportation Science, 43(4), 408-416. JSTOR. DOI: https://doi.org/10.1287/trsc.1090.0301
Lesch, V., König, M., Kounev, S., Stein, A., & Krupitzer, C. (2022). Tackling the rich vehicle routing problem with nature-inspired algorithms. Applied Intelligence, 52(8), 9476-9500. https://doi.org/10.1007/s10489-021-03035-5 DOI: https://doi.org/10.1007/s10489-021-03035-5
Li, J., Cai, L., Lichen, J., Pan, P., Wang, W., & Liu, S. (2021). An Approximation Algorithm for Solving the Heterogeneous Chinese Postman Problem. Algorithmic Aspects in Information and Management, 38-46. https://doi.org/10.1007/978-3-030-93176-6_4 DOI: https://doi.org/10.1007/978-3-030-93176-6_4
Mahéo, A., Rossit, D. G., & Kilby, P. (2022). Solving the integrated bin allocation and collection routing problem for municipal solid waste: A Benders decomposition approach. Annals of Operations Research. https://doi.org/10.1007/s10479-022-04918-7 DOI: https://doi.org/10.1007/s10479-022-04918-7
Máximo, V. R., & Nascimento, M. C. V. (2021). A hybrid adaptive iterated local search with diversification control to the capacitated vehicle routing problem. European Journal of Operational Research, 294(3), 1108-1119. https://doi.org/10.1016/j.ejor.2021.02.024 DOI: https://doi.org/10.1016/j.ejor.2021.02.024
Minh, T. T., Van Hoai, T., & Nguyet, T. T. N. (2013). A Memetic Algorithm for Waste Collection Vehicle Routing Problem with Time Windows and Conflicts. En B. Murgante, S. Misra, M. Carlini, C. M. Torre, H.-Q. Nguyen, D. Taniar, B. O. Apduhan, & O. Gervasi (Eds.), Computational Science and Its Applications – ICCSA 2013 (pp. 485-499). Springer. https://doi.org/10.1007/978-3-642-39637-3_38 DOI: https://doi.org/10.1007/978-3-642-39637-3_38
Mohammed, M. A., Ghani, M. K. A., Hamed, R. I., Mostafa, S. A., Ahmad, M. S., & Ibrahim, D. A. (2017). Solving Vehicle Routing Problem by Using Improved Genetic Algorithm for Optimal Solution. Journal of Computational Science. https://doi.org/10.1016/j.jocs.2017.04.003 DOI: https://doi.org/10.1016/j.jocs.2017.04.003
Mohammed, M. A., Mohd Khanapi Abd Ghani, Obaid, O. I., Mostafa, S. A., Ahmad, M. S., Dheyaa Ahmed Ibrahim, & Burhanuddin, M. A. (2017). A Review of Genetic Algorithm Applications in Solving Vehicle Routing Problem. https://www.medwelljournals.com/abstract/?doi=jeasci.2017.4267.4283
Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2008a). A survey on pickup and delivery problems. Journal Für Betriebswirtschaft, 58(2), 81-117. https://doi.org/10.1007/s11301-008-0036-4 DOI: https://doi.org/10.1007/s11301-008-0036-4
Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2008b). A survey on pickup and delivery problems. Journal Für Betriebswirtschaft, 58(1), 21-51. https://doi.org/10.1007/s11301-008-0033-7 DOI: https://doi.org/10.1007/s11301-008-0033-7
Policroniades Chípuli, G., & Flores de la Mota, I. (2021). Analysis, design and reconstruction of a VRP model in a collapsed distribution network using simulation and optimization. Case Studies on Transport Policy. https://doi.org/10.1016/j.cstp.2021.07.002 DOI: https://doi.org/10.1016/j.cstp.2021.07.002
Policroniades, G., & Flores de la Mota, I. (2016). State of the Art of the Different Models of Transportation Most Used in the Supply Chain of Automotive Industry. International Journal of Combinatorial Optimization Problems and Informatics, 7(3), 44-53.
Policroniades, G., Flores de la Mota, I., Sihirai Reyna, O. S., & Lara de Paz, J. (2018). The Vehicle Routing Problem Complex Network Analysis. Journal of Applied Mathematics and Computation, 2(12). https://doi.org/10.26855/jamc.2018.12.001 DOI: https://doi.org/10.26855/jamc.2018.12.001
Queiroga, E., Frota, Y., Sadykov, R., Subramanian, A., Uchoa, E., & Vidal, T. (2020). On the exact solution of vehicle routing problems with backhauls. European Journal of Operational Research, 287(1), 76-89. https://doi.org/10.1016/j.ejor.2020.04.047 DOI: https://doi.org/10.1016/j.ejor.2020.04.047
Quila, D., Morillo, D., Cabrera, G., Linfati, R., & Gatica, G. (2020). A New Mathematical Model for the Vehicle Routing Problem with Backhauls and Time Windows. En Á. Rocha, C. Ferrás, C. E. Montenegro Marin, & V. H. Medina García (Eds.), Information Technology and Systems (pp. 46-53). Springer International Publishing. https://doi.org/10.1007/978-3-030-40690-5_5 DOI: https://doi.org/10.1007/978-3-030-40690-5_5
Raffaele, A., Zavatteri, M., Bazzoli, F., Gussago, M., & Rizzi, R. (2023). A Two-Phase Approach to Evaluate and Optimize an Interlibrary Loan Service: The Case Study of Provincia di Brescia. En M. Cosmi, L. Peirano, A. Raffaele, & M. Samà (Eds.), Operations Research and Data Science in Public Services (pp. 17-33). Springer International Publishing. https://doi.org/10.1007/978-3-031-34546-3_2 DOI: https://doi.org/10.1007/978-3-031-34546-3_2
Rezaei, B., Guimaraes, F. G., Enayatifar, R., & Haddow, P. C. (2023). Combining genetic local search into a multi-population Imperialist Competitive Algorithm for the Capacitated Vehicle Routing Problem. Applied Soft Computing, 142, 110309. https://doi.org/10.1016/j.asoc.2023.110309 DOI: https://doi.org/10.1016/j.asoc.2023.110309
Rodrigues, A. M., & Soeiro Ferreira, J. (2015). Waste collection routing—Limited multiple landfills and heterogeneous fleet. Networks, 65(2), 155-165. https://doi.org/10.1002/net.21597 DOI: https://doi.org/10.1002/net.21597
Rodriguez, H., Díaz, J., Fajardo-Calderín, J., Perallos, A., & Onieva, E. (2021). Waste Collection Vehicle Routing Problem Using Filling Predictions. En H. Sanjurjo González, I. Pastor López, P. García Bringas, H. Quintián, & E. Corchado (Eds.), Hybrid Artificial Intelligent Systems (pp. 637-648). Springer International Publishing. https://doi.org/10.1007/978-3-030-86271-8_53 DOI: https://doi.org/10.1007/978-3-030-86271-8_53
Salehi Sarbijan, M., & Behnamian, J. (2022). Multi-fleet feeder vehicle routing problem using hybrid metaheuristic. Computers & Operations Research, 141, 105696. https://doi.org/10.1016/j.cor.2022.105696 DOI: https://doi.org/10.1016/j.cor.2022.105696
Santos, M. J., Jorge, D., Ramos, T., & Barbosa-Póvoa, A. (2023). Green reverse logistics: Exploring the vehicle routing problem with deliveries and pickups. Omega, 118, 102864. https://doi.org/10.1016/j.omega.2023.102864 DOI: https://doi.org/10.1016/j.omega.2023.102864
Segura, E. L., Melquiades, J. R., & Segura, F. G. (2022). Tabu Search for Locating-Routing in the Goods Delivery and Waste Pickup in Trujillo-Peru. En K. Arai (Ed.), Intelligent Systems and Applications (pp. 51-69). Springer International Publishing. https://doi.org/10.1007/978-3-030-82196-8_5 DOI: https://doi.org/10.1007/978-3-030-82196-8_5
Sgarro, G. A., Santoro, D., & Grilli, L. (2024). Ant Colony Optimization for solving Directed Chinese Postman Problem. Neural Computing and Applications, 36(28), 17615-17630. https://doi.org/10.1007/s00521-024-10052-1 DOI: https://doi.org/10.1007/s00521-024-10052-1
Simsir, F., & Ekmekci, D. (2019). A metaheuristic solution approach to capacitied vehicle routing and network optimization. Engineering Science and Technology, an International Journal, 22(3), 727-735. https://doi.org/10.1016/j.jestch.2019.01.002 DOI: https://doi.org/10.1016/j.jestch.2019.01.002
Solano-Charris, E., Prins, C., & Santos, A. C. (2015). Local search based metaheuristics for the robust vehicle routing problem with discrete scenarios. Applied Soft Computing, 32, 518-531. https://doi.org/10.1016/j.asoc.2015.03.058 DOI: https://doi.org/10.1016/j.asoc.2015.03.058
Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35(2), 254-265. DOI: https://doi.org/10.1287/opre.35.2.254
Subramanian, A., & Queiroga, E. (2020). Solution strategies for the vehicle routing problem with backhauls. Optimization Letters, 14(8), 2429-2441. https://doi.org/10.1007/s11590-020-01564-5 DOI: https://doi.org/10.1007/s11590-020-01564-5
Sukhpal, & Kumar, K. (2023). Multi-trip multi-compartment vehicle routing problem with backhauls. International Journal of System Assurance Engineering and Management. https://doi.org/10.1007/s13198-023-02040-w DOI: https://doi.org/10.1007/s13198-023-02040-w
Tlili, T., Faiz, S., & Krichen, S. (2014). A Hybrid Metaheuristic for the Distance-constrained Capacitated Vehicle Routing Problem. Procedia - Social and Behavioral Sciences, 109, 779-783. https://doi.org/10.1016/j.sbspro.2013.12.543 DOI: https://doi.org/10.1016/j.sbspro.2013.12.543
Torres Matus, R. (2005). Un Algoritmo Genético para Resolver el Problema de Asignar y Secuenciar Entregas con Restricción de Ventanas de Tiempo-Edición Única—Repositorio del Tecnologico de Monterrey. https://repositorio.itesm.mx/ortec/handle/11285/572509
Vaferi, M., Fallah, M. S., & Tayebi, A. H. (2018). A Metaheuristic for the Containership Feeder Routing Problem with Port Choice Process. The Asian Journal of Shipping and Logistics, 34(2), 119-128. https://doi.org/10.1016/j.ajsl.2018.06.008 DOI: https://doi.org/10.1016/j.ajsl.2018.06.008
Valizadeh, J., Mozafari, P., & Hafezalkotob, A. (2021). Municipal waste management and electrical energy generation from solid waste: A mathematical programming approach. Journal of Modelling in Management, 17(1), 309-340. https://doi.org/10.1108/JM2-07-2020-0193 DOI: https://doi.org/10.1108/JM2-07-2020-0193
Vieira, B. S., Ribeiro, G. M., & Bahiense, L. (2023). Metaheuristics with variable diversity control and neighborhood search for the Heterogeneous Site-Dependent Multi-depot Multi-trip Periodic Vehicle Routing Problem. Computers & Operations Research, 153, 106189. https://doi.org/10.1016/j.cor.2023.106189 DOI: https://doi.org/10.1016/j.cor.2023.106189
Voigt, S., Frank, M., Fontaine, P., & Kuhn, H. (2022). Hybrid adaptive large neighborhood search for vehicle routing problems with depot location decisions. Computers & Operations Research, 146, 105856. https://doi.org/10.1016/j.cor.2022.105856 DOI: https://doi.org/10.1016/j.cor.2022.105856
Wang, Y., Assogba, K., Fan, J., Xu, M., Liu, Y., & Wang, H. (2019). Multi-depot green vehicle routing problem with shared transportation resource: Integration of time-dependent speed and piecewise penalty cost. Journal of Cleaner Production, 232, 12-29. https://doi.org/10.1016/j.jclepro.2019.05.344 DOI: https://doi.org/10.1016/j.jclepro.2019.05.344
Wu, H., Gao, Y., Wang, W., & Zhang, Z. (2023). A hybrid ant colony algorithm based on multiple strategies for the vehicle routing problem with time windows. Complex & Intelligent Systems, 9(3), 2491-2508. https://doi.org/10.1007/s40747-021-00401-1 DOI: https://doi.org/10.1007/s40747-021-00401-1
Xin, J., Yu, B., D’Ariano, A., Wang, H., & Wang, M. (2022). Time-dependent rural postman problem: Time-space network formulation and genetic algorithm. Operational Research, 22(3), 2943-2972. https://doi.org/10.1007/s12351-021-00639-0 DOI: https://doi.org/10.1007/s12351-021-00639-0
Zenil Chávez, H. (2005). Computación evolutiva y sistemas complejos adaptativos: La sopa primigenia de las conductas inteligentes emergentes. Ciencia - Academia Mexicana de Ciencias, 56(2), Article 2.
