A comparative study utilizing hybridized ant colony optimization algorithms for solving dynamic capacity of vehicle routing problems in waste collection system
Abstract
The waste collection stage generated 70% of the cost of the total Municipal Solid Waste (MSW) management system. Therefore, choosing the most affordable waste collection method is essential to accurately estimate the waste collection and transportation costs, thus selecting the required vehicle capacity. The study aims to design a waste collection system for calculating waste collection and transportation costs using a systematic framework that includes Hybridized Ant Colony Optimization (HACO) with Sequential Variable Neighborhood Search Change Step (SVNSCS) and Sequential Variable Neighborhood Decent (SVND). The framework addresses a Dynamic Capacity of Vehicle Routing Problem (DCVRP) and improves ACO's ability in exploration and exploitation stages. The objectives are to minimize the cost of travel distance and arrival time formulated in a mathematical model and to design a new strategy for eliminating the sub-tour problem in the following steps: (1) minimize the number of routes assigned, (2) increase the amount of waste in the vehicle capacity, and (3) define the best amount of waste allowed in vehicle capacity. The waste collection system compared HACO with ACO across four benchmark datasets. The results indicate HACO outperformance ACO at 100%, 91%, 100%, and 87%, respectively. The visualization results demonstrated that HACO has fast convergence and can be considered another essential tool for route optimization in the waste collection system.
References
Md. M. Hoque and M. T. U. Rahman, “Landfill area estimation based on solid waste collection prediction using ANN model and final waste disposal options,” J Clean Prod, vol. 256, p. 120387, May 2020, https://doi.org/10.1016/j.jclepro.2020.120387
S. O. Kwakye, E. E. Y. Amuah, K. A. Ankoma, E. B. Agyemang, and B.-G. Owusu, “Understanding the performance and challenges of solid waste management in an emerging megacity: Insights from the developing world,” Environmental Challenges, vol. 14, p. 100805, Jan. 2024, https://doi.org/10.1016/j.envc.2023.100805
M. Al Duhayyim et al., “Deep Reinforcement Learning Enabled Smart City Recycling Waste Object Classification,” Computers, Materials & Continua, vol. 71, no. 3, pp. 5699–5715, 2022, https://doi.org/10.32604/cmc.2022.024431
S. Saxena, C. Rajendran, V. Sanjeevi, and P. Shahabudeen, “Optimization of solid waste management in a metropolitan city,” Mater Today Proc, vol. 46, pp. 8231–8238, 2021, https://doi.org/10.1016/j.matpr.2021.03.219
G. Boskovic, N. Jovicic, S. Jovanovic, and V. Simovic, “Calculating the costs of waste collection: A methodological proposal,” Waste Management & Research: The Journal for a Sustainable Circular Economy, vol. 34, no. 8, pp. 775–783, Aug. 2016, https://doi.org/10.1177/0734242X16654980
O. Munyai and W. N. Nunu, “Health effects associated with proximity to waste collection points in Beitbridge Municipality, Zimbabwe,” Waste Management, vol. 105, pp. 501–510, Mar. 2020, https://doi.org/10.1016/j.wasman.2020.02.041
A. S. Silva et al., “Capacitated Waste Collection Problem Solution Using an Open-Source Tool,” Computers, vol. 12, no. 1, p. 15, Jan. 2023, https://doi.org/10.3390/computers12010015
S. Kaza, L. C. Yao, P. Bhada-Tata, and F. Van Woerden, What a Waste 2.0: A Global Snapshot of Solid Waste Management to 2050. 2018. https://doi.org/10.1596/978-1-4648-1329-0
A. Iqbal et al., “Municipal Solid Waste Collection and Haulage Modeling Design for Lahore, Pakistan: Transition toward Sustainability and Circular Economy,” Sustainability, vol. 14, no. 23, p. 16234, Dec. 2022, https://doi.org/10.3390/su142316234
R. Aziz, G. P. Adfuza, and Y. Arbi, “Preliminary Study of Solid Waste Treatment of Padang Beach Tourism Area, Padang City,” Jurnal Pendidikan Teknologi Kejuruan, vol. 4, no. 1, pp. 31–34, Jun. 2021, https://doi.org/10.24036/jptk.v4i1.16323
G. Rahmanifar, M. Mohammadi, M. Hajiaghaei-Keshteli, G. Fusco, and C. Colombaroni, “An integrated temporal and spatial synchronization for two-echelon vehicle routing problem in waste collection system,” J Ind Inf Integr, vol. 40, p. 100611, Jul. 2024, https://doi.org/10.1016/j.jii.2024.100611
N. Rattanawai, S. Arunyanart, and S. Pathumnakul, “Optimizing municipal solid waste collection vehicle routing with a priority on infectious waste in a mountainous city landscape context,” Transp Res Interdiscip Perspect, vol. 24, p. 101066, Mar. 2024, https://doi.org/10.1016/j.trip.2024.101066
C. Wei, S. Wøhlk, and A. Che, “A multi-level capacitated arc routing problem with intermediate facilities in waste collection,” Comput Oper Res, vol. 167, p. 106671, Jul. 2024, https://doi.org/10.1016/j.cor.2024.106671
A. Chaabane, J. Montecinos, M. Ouhimmou, and A. Khabou, “Vehicle routing problem for reverse logistics of End-of-Life Vehicles (ELVs),” Waste Management, vol. 120, pp. 209–220, Feb. 2021, https://doi.org/10.1016/j.wasman.2020.11.008
T. M. Sahib, R. Mohd Mokhtar, A. F. H. Alharan, N. S. Ali, and A. A. Kadhum, “An Improved Strategy for Solid Waste Management based on Programmable Logic Controller,” Int J Environ Waste Manag, vol. 1, no. 1, p. 1, 2023, https://doi.org/10.1504/IJEWM.2023.10048103
M. Akhtar, M. A. Hannan, R. A. Begum, H. Basri, and E. Scavino, “Backtracking search algorithm in CVRP models for efficient solid waste collection and route optimization,” Waste Management, vol. 61, pp. 117–128, Mar. 2017, https://doi.org/10.1016/j.wasman.2017.01.022
B.-I. Kim, S. Kim, and S. Sahoo, “Waste collection vehicle routing problem with time windows,” Comput Oper Res, vol. 33, no. 12, pp. 3624–3642, Dec. 2006, https://doi.org/10.1016/j.cor.2005.02.045
A. M. Benjamin and J. E. Beasley, “Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities,” Comput Oper Res, vol. 37, no. 12, pp. 2270–2280, Dec. 2010, https://doi.org/10.1016/j.cor.2010.03.019
T. M. Sahib, R. Mohd-Mokhtar, and A. M. Kassim, “Survey on Meta-Heuristic Algorithms for Solving Vehicle Route Problems in a Waste Collection System,” in LNEE, vol. 829, 2022, pp. 363–369. https://doi.org/10.1007/978-981-16-8129-5_57
E. B. Tirkolaee, I. Mahdavi, and M. Mehdi Seyyed Esfahani, “A robust periodic capacitated arc routing problem for urban waste collection considering drivers and crew’s working time,” Waste Management, vol. 76, pp. 138–146, Jun. 2018, https://doi.org/10.1016/j.wasman.2018.03.015
T. Henke, M. G. Speranza, and G. Wäscher, “The multi-compartment vehicle routing problem with flexible compartment sizes,” Eur J Oper Res, vol. 246, no. 3, pp. 730–743, Nov. 2015, https://doi.org/10.1016/j.ejor.2015.05.020
Y. P. Li, G. H. Huang, and S. L. Nie, “A mathematical model for identifying an optimal waste management policy under uncertainty,” Appl Math Model, vol. 36, no. 6, pp. 2658–2673, Jun. 2012, https://doi.org/10.1016/j.apm.2011.09.049
G. Ghiani, A. Manni, E. Manni, and V. Moretto, “Optimizing a waste collection system with solid waste transfer stations,” Comput Ind Eng, vol. 161, p. 107618, Nov. 2021, https://doi.org/10.1016/j.cie.2021.107618
A. A. Ismail, R. Krisnaputra, and I. Bahiuddin, “Application of Ant Colony Optimization for the Shortest Path Problem of Waste Collection Process,” Kinetik: Game Technology, Information System, Computer Network, Computing, Electronics, and Control, Aug. 2021, https://doi.org/10.22219/kinetik.v6i3.1307
J. Edwards, M. Othman, S. Burn, and E. Crossin, “Energy and time modelling of kerbside waste collection: Changes incurred when adding source separated food waste,” Waste Management, vol. 56, pp. 454–465, Oct. 2016, https://doi.org/10.1016/j.wasman.2016.06.033
F. S. Sahib and N. S. Hadi, “Truck route optimization in Karbala city for solid waste collection,” Mater Today Proc, vol. 80, pp. 2489–2494, 2023, https://doi.org/10.1016/j.matpr.2021.06.394
J. A. Knowles, “National solid waste management plan for Iraq,” Waste Management & Research: The Journal for a Sustainable Circular Economy, vol. 27, no. 4, pp. 322–327, Jun. 2009, https://doi.org/10.1177/0734242X09104129
N. A. Mat, A. M. Benjamin, and S. Abdul-Rahman, “Enhanced heuristic algorithms with a vehicle travel speed model for time-dependent vehicle routing: A waste collection problem,” Journal of Information and Communication Technology, vol. 17, no. 1, 2018, https://doi.org/10.32890/jict2018.17.1.8245
E. T. Yassen, M. Ayob, M. Z. A. Nazri, and N. R. Sabar, “An adaptive hybrid algorithm for vehicle routing problems with time windows,” Comput Ind Eng, vol. 113, pp. 382–391, Nov. 2017, https://doi.org/10.1016/j.cie.2017.09.034
M. A. Hannan, M. Akhtar, R. A. Begum, H. Basri, A. Hussain, and E. Scavino, “Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm,” Waste Management, vol. 71, pp. 31–41, Jan. 2018, https://doi.org/10.1016/j.wasman.2017.10.019
İ. İLHAN, “An improved simulated annealing algorithm with crossover operator for capacitated vehicle routing problem,” Swarm Evol Comput, vol. 64, p. 100911, Jul. 2021, https://doi.org/10.1016/j.swevo.2021.100911
C.-Y. Lee, Z.-J. Lee, S.-W. Lin, and K.-C. Ying, “An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem,” Applied Intelligence, vol. 32, no. 1, pp. 88–95, Feb. 2010, https://doi.org/10.1007/s10489-008-0136-9
A. M. Altabeeb, A. M. Mohsen, and A. Ghallab, “An improved hybrid firefly algorithm for capacitated vehicle routing problem,” Appl Soft Comput, vol. 84, p. 105728, Nov. 2019, https://doi.org/10.1016/j.asoc.2019.105728
H. Ali and A. K. Kar, “Discriminant Analysis using Ant Colony Optimization – An Intra-Algorithm Exploration,” Procedia Comput Sci, vol. 132, pp. 880–889, 2018, https://doi.org/10.1016/j.procs.2018.05.100
M. Pedemonte, S. Nesmachnow, and H. Cancela, “A survey on parallel ant colony optimization,” Appl Soft Comput, vol. 11, no. 8, pp. 5181–5197, Dec. 2011, https://doi.org/10.1016/j.asoc.2011.05.042
S. Ebadinezhad, “DEACO: Adopting dynamic evaporation strategy to enhance ACO algorithm for the traveling salesman problem,” Eng Appl Artif Intell, vol. 92, p. 103649, Jun. 2020, https://doi.org/10.1016/j.engappai.2020.103649
S. Faiz, S. Krichen, and W. Inoubli, “A DSS based on GIS and Tabu search for solving the CVRP: The Tunisian case,” The Egyptian Journal of Remote Sensing and Space Science, vol. 17, no. 1, pp. 105–110, Jun. 2014, https://doi.org/10.1016/j.ejrs.2013.10.001
N. Guo, B. Qian, R. Hu, H. P. Jin, and F. H. Xiang, “A Hybrid Ant Colony Optimization Algorithm for Multi-Compartment Vehicle Routing Problem,” Complexity, vol. 2020, pp. 1–14, Oct. 2020, https://doi.org/10.1155/2020/8839526
S.-H. Huang, Y.-H. Huang, C. A. Blazquez, and G. Paredes-Belmar, “Application of the ant colony optimization in the resolution of the bridge inspection routing problem,” Appl Soft Comput, vol. 65, pp. 443–461, Apr. 2018, https://doi.org/10.1016/j.asoc.2018.01.034
Z. Borčinová, “Kernel Search for the Capacitated Vehicle Routing Problem,” Applied Sciences, vol. 12, no. 22, p. 11421, Nov. 2022, https://doi.org/10.3390/app122211421
P. Augerat, D. Naddef, J.-M. Belenguer, E. Benavent, Á. Corberán, and G. Rinaldi, “Computational results with a branch and cut code for the capacitated vehicle routing problem,” 1998. [Online]. Available: https://api.semanticscholar.org/CorpusID:60747070
N. Christofides and S. Eilon, “An Algorithm for the Vehicle-Dispatching Problem,” OR, vol. 20, no. 3, 1969, https://doi.org/10.2307/3008733
P. P. Matthopoulos and S. Sofianopoulou, “A firefly algorithm for the heterogeneous fixed fleet vehicle routing problem,” International Journal of Industrial and Systems Engineering, vol. 33, no. 2, p. 204, 2019, https://doi.org/10.1504/IJISE.2019.102471
F. Arnold, Í. Santana, K. Sörensen, and T. Vidal, “PILS: Exploring high-order neighborhoods by pattern mining and injection,” Pattern Recognit, vol. 116, p. 107957, Aug. 2021, https://doi.org/10.1016/j.patcog.2021.107957
Copyright (c) 2024 Thaeer Mueen Sahib, Rosmiwati Mohd-Mokhtar, Azleena Mohd-Kassim (Authors)
This work is licensed under a Creative Commons Attribution 4.0 International License.
