ANT COLONY OPTIMIZATION ALGORITHM WITH SEQUENTIAL VARIABLE NEIGHBOURHOOD SEARCH CHANGE STEP IN THE WASTE COLLECTION SYSTEM

Thaeer Mueen Sahib; Rosmiwati Mohd-Mokhtar; Azleena Mohd-Kassim

doi:10.11113/jurnalteknologi.v87.19726

Authors

Thaeer Mueen Sahib ᵃSchool of Electrical and Electronic Engineering, Universiti Sains Malaysia, Engineering Campus, 14300 Nibong Tebal, Pulau Pinang, Malaysia ᵇDepartment of Electrical Techniques, Kufa Technical Institute, Al-Furat Al-Awsat Technical University, 54003, Iraq
Rosmiwati Mohd-Mokhtar School of Electrical and Electronic Engineering, Universiti Sains Malaysia, Engineering Campus, 14300 Nibong Tebal, Pulau Pinang, Malaysia
Azleena Mohd-Kassim School of Computer Science, Universiti Sains Malaysia, 11800 Minden, Pulau Pinang, Malaysia

DOI:

https://doi.org/10.11113/jurnalteknologi.v87.19726

Keywords:

Ant colony optimization, capacitated vehicle routing problem, optimization algorithm, sequential variable neighbourhood search change step, solid waste collection

Abstract

This study improves the exploration of ant colony optimization (ACO) ability by adapting it with the Sequential Variable Neighbourhood Search Change Step (SVNSCS) algorithm as post-improvements for solving the Capacitated Vehicle Routing Problem (CVRP) in solid waste collection methodology. The aim is to reduce the cost of waste collection by minimizing the route distance and the number of vehicles to serve all containers within the route. Technically, SVNSCS explores the search space depending on the information associated with the demands and coordinates of the nodes. Based on the result, the proposed algorithm demonstrates its superiority over the traditional ACO algorithm by having 66.7%, 81.81%, 62.5%, and 77.77% in terms of the best solution for four CVRP benchmark datasets of A, B, E, and P, respectively. Each dataset has different characteristics, such as the number of containers, vehicle capacity, objective function, weight of each container, and geographical distribution.

References

Akhtar, M., Hannan, M. A., Basri, H., and Scavino, E. 2015. Solid Waste Generation and Collection Efficiencies: Issues and Challenges. Jurnal Teknologi. 75(11).

Doi: https://doi.org/10.11113/jt.v75.5331.

Ismail, N., and Ani, F. N. 2015. A Review on Plasma Treatment for the Processing of Solid Waste. Jurnal Teknologi. 72(5).

Doi: https://doi.org/10.11113/jt.v72.3938.

Munyai, O. and Nunu, W.N. 2020. Health Effects Associated with Proximity to Waste Collection Points in Beitbridge Municipality, Zimbabwe. Waste Management. 105: 501–510.

Doi: https://doi.org/10.1016/j.wasman.2020.02.041.

Jiang, P., Van Fan, Y., Zhou, J., Zheng, M., Liu, X. and Klemeš, J. J. 2020. Data-driven Analytical Framework for Waste-dumping Behaviour Analysis to Facilitate Policy Regulations. Waste Management. 103: 285–295.

Doi: https://doi.org/10.1016/j.wasman.2019.12.041.

Hoque, M. M. and Rahman, M. T. U. 2020. Landfill Area Estimation based on Solid Waste Collection Prediction using ANN Model and Final Waste Disposal Options. Journal of Cleaner Production. 256: 120387.

Doi: https://doi.org/10.1016/j.jclepro.2020.120387.

Samsudin, M. D. M. and Don, M. M. 2013. Municipal Solid Waste Management in Malaysia: Current Practices, Challenges, and Prospects. Jurnal Teknologi. 62(1).

Doi: https://doi.org/10.11113/jt.v62.1293.

Liman, A. and Ngah, I. 2015. Appraisal of Municipal Solid Waste Management (MSWM) in Jimeta-Yola Adamawa State of Nigeria: The Need for Innovative, PPP Strategies. Jurnal Teknologi. 77(15).

Doi: https://doi.org/10.11113/jt.v77.6537.

Bees, A. D. and Williams, I. D. 2017. Explaining the Differences in Household Food Waste Collection and Treatment Provisions between Local Authorities in England and Wales. Waste Management. 70: 222–235.

Doi: https://doi.org/10.1016/j.wasman.2017.09.004.

Hannan, M. A., Akhtar, M., Begum, R. A., Basri, H., Hussain, A. and Scavino, E. 2018. Capacitated Vehicle-routing Problem Model for Scheduled Solid Waste Collection and Route Optimization using PSO Agorithm. Waste management. 71: 31–41.

Doi: https://doi.org/10.1016/j.wasman.2017.10.019.

Foday, Jr, E. H., Ramli, N. A. S., Ismail, H. N., Malik, N. A., Basri, H. F., Aziz, F. S. A., Nor, N. S.M. and Jumhat, F. 2017. Municipal Solid Waste Characteri stics in Taman Universiti, Skudai, Johore, Malaysia. Journal of Advanced Research Design. 38(1): 13–20.

Nasir, S. M., Othman, N. H., Isa, C. M. and Ibrahim, C. C. 2016. The Challenges of Construction Waste Management in Kuala Lumpur. Jurnal Teknologi. 78: 5–3.

Doi: https://doi.org/10.11113/jt.v78.8522.

Sahib, F. S. and Hadi, N. S. 2021. Truck Route Optimization in Karbala City for Solid Waste Collection. Materials Today: Proceedings.

Doi: https://doi.org/10.1016/j.matpr.2021.06.394.

Tirkolaee, E. B., Mahdavi, I. and 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: 138–146.

Doi: https://doi.org/10.1016/j.wasman.2018.03.015.

Sahib, T. M., Mohd-Mokhtar, R., Alharan, A. F. H., Ali, N. S., & Kadhum, A. A. 2024. An Improved Strategy for Solid Waste Management based on Programmable Logic Controller. Int. J. of Environment & Waste Management. 34(3): 297–310. https://doi.org/10.1504/IJEWM.2024.139963.

Louati, A. 2016. Modeling Municipal Solid Waste Collection: A Generalized Vehicle Routing Model with Multiple Transfer Stations, Gather Sites and Inhomogeneous Vehicles in Time Windows. Waste Management. 52: 34–49.

Doi: https://doi.org/10.1016/j.wasman.2016.03.041.

Armington, W. R. and Chen, R. B. 2018. Household Food Waste Collection: Building Service Networks through Neighbourhood Expansion. Waste Management. 77: 304–311.

Doi: https://doi.org/10.1016/j.wasman.2018.04.012.

Han, H. and Ponce Cueto, E. 2015. Waste Collection Vehicle Routing Problem: Literature Review. PROMET-Traffic & Transportation. 27(4): 345–358.

Doi: https://doi.org/10.7307/ptt.v27i4.1616.

Vu, H. L., Ng, K. T. W., Fallah, B., Richter, A. and Kabir, G. 2020. Interactions of Residential Waste Composition and Collection Truck Compartment Design on GIS Route Optimization. Waste Management. 102: 613–623.

Doi: https://doi.org/10.1016/j.wasman.2019.11.028.

Akpinar. S. 2016. Hybrid Large Neighbourhood Search Algorithm for Capacitated Vehicle Routing Problem. Expert Systems with Applications. 61: 28–38.

Doi: https://doi.org/10.1016/j.eswa.2016.05.023.

Imran. A, Luis. M. and Okdinawati. L. 2016. A Variable Neighborhood Search for the Heterogeneous Fixed Fleet Vehicle Routing Problem. Jurnal Teknologi. 78(9): 53–58.

Doi: https://doi.org/10.11113/jt.v78.6062.

İlhan, İ. L. H. A. N. 2021. An Improved Simulated Annealing Algorithm with Crossover Operator for Capacitated Vehicle Routing Problem. Swarm and Evolutionary Computation. 64: 100911.

DOI: https://doi.org/10.1016/j.swevo.2021.100911.

Dalbah, L. M., Al-Betar, M. A., Awadallah, M. A. and Zitar, R. A. 2022. A Modified Coronavirus Herd Immunity Optimizer for Capacitated Vehicle Routing Problem. Journal of King Saud University-Computer and Information Sciences. 34(8): 4782–4795.

Doi: https://doi.org/10.1016/j.jksuci.2021.06.013.

Sahib, T. M., Mohd-Mokhtar, & R., Kassim, A. M. 2022. Survey on Meta-Heuristic Algorithms for Solving Vehicle Route Problems in a Waste Collection System. In: Mahyuddin N. M., Mat Noor N. R., Mat Sakim H. A. (Eds). Proceedings of the 11th International Conference on Robotics, Vision, Signal Processing and Power Applications. Lecture Notes in Electrical Engineering, vol 829. Springer, Singapore. https://doi.org/https://doi.org/10.1007/978-981-16-8129-5_57.

Tirkolaee, E. B., Alinaghian, M., Bakhshi Sasi, M. and Seyyed Esfahani, M. M. 2016. Solving a Robust Capacitated Arc Routing Problem Using a Hybrid Simulated Annealing Algorithm: A Waste Collection Application. Journal of Industrial Engineering and Management Studies. 3(1): 61–76.

Tirkolaee, E. B., Alinaghian, M., Hosseinabadi, A. A. R., Sasi, M. B. and Sangaiah, A. K. 2019. An Improved Ant Colony Optimization for the Multi-trip Capacitated Arc Routing Problem. Computers & Electrical Engineering. 77: 457–470.

Doi: https://doi.org/10.1016/j.compeleceng.2018.01.040.

Raflesia, S. P. and Pamosoaji, A. K. 2019, November. A Novel Ant Colony Optimization Algorithm for Waste Collection Problem. 2019 4th International Conference on Information Technology, Information Systems and Electrical Engineering (ICITISEE) on IEEE. 413–416.

Doi: https://doi.org/10.1109/ICITISEE48480.2019.9003896.

Delgado-Antequera, L., Caballero, R., Sánchez-Oro, J., Colmenar, J. M. and Martí, R. 2020. Iterated Greedy with Variable Neighborhood Search for a Multiobjective Waste Collection Problem. Expert Systems with Applications. 145: 113101.

Doi: https://doi.org/10.1016/j.eswa.2019.113101.

Máximo, V. R. and Nascimento, M. C. 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. Doi: https://doi.org/10.1016/j.ejor.2021.02.024.

Akhtar, M., Hannan, M. A., Begum, R. A., Basri, H. and Scavino, E. 2017. Backtracking Search Algorithm in CVRP Models for Efficient Solid Waste Collection and Route Optimization. Waste Management. 61: 117–128.

Doi: https://doi.org/10.1016/j.wasman.2017.01.022.

Jorge, D., Antunes, A. P., Ramos, T. R. P. and Barbosa-Póvoa, A. P. 2022. A Hybrid Metaheuristic for Smart Waste Collection Problems with Workload Concerns. Computers & Operations Research. 137: 105518.

Doi: https://doi.org/10.1016/j.cor.2021.105518.

Wy, J. and Kim, B. I. 2013. A Hybrid Metaheuristic Approach for the Rollon–rolloff Vehicle Routing Problem. Computers & Operations Research. 40(8): 1947–1952.

Doi: https://doi.org/10.1016/j.cor.2013.03.006.

Jabir, E., Panicker, V. V., & Sridharan, R. 2017. Design and Development of a Hybrid Ant Colony-variable Neighbourhood Search Algorithm for a Multi-depot Green Vehicle Routing Problem. Transportation Research Part D: Transport and Environment. 57: 422–457. https://doi.org/10.1016/j.trd.2017.09.003.

Hansen, P., Mladenović, N., Todosijević, R. and Hanafi, S. 2017. Variable Neighborhood Search: Basics and Variants. EURO Journal on Computational Optimization. 5(3): 423–454.

Doi: https://doi.org/10.1007/s13675-016-0075-x.

Yassen, E. T., Ayob, M., Nazri, M. Z. A. and Sabar, N. R. 2017. An Adaptive Hybrid Algorithm for Vehicle Routing Problems with Time Windows. Computers & Industrial Engineering. 113: 382–391.

Doi: https://doi.org/10.1016/j.cie.2017.09.034.

Souza, I. P., Boeres, M. C. S., & Moraes, R. E. N. 2023. A Robust Algorithm based on Differential Evolution with Local Search for the Capacitated Vehicle Routing Problem. Swarm and Evolutionary Computation. 77: 101245. https://doi.org/10.1016/j.swevo.2023.101245.

Ali. H and Kar. A. K. 2018. Discriminant Analysis using Ant Colony Optimization - An Intra-Algorithm Exploration. Procedia Computer Science. 132: 880–889.

Doi: https://doi.org/10.1016/j.procs.2018.05.100.

Pedemonte. M., Nesmachnow. S. and Cancela. H. 2011. A Survey on Parallel Ant Colony Optimization. Applied Soft Computing Journal. 11(8): 5181–5197.

Doi: https://doi.org/10.1016/j.asoc.2011.05.042.

Ebadinezhad. S. 2020. DEACO: Adopting Dynamic Evaporation Strategy to Enhance ACO Algorithm for the Traveling Salesman Problem. Engineering Applications of Artificial Intelligence. 92: 103649.

Doi: https://doi.org/10.1016/j.engappai.2020.103649.

Faiz, S., Krichen, S. and Inoubli, W. 2014. A DSS based on GIS and Tabu Search for Solving the CVRP: The Tunisian Case. The Egyptian Journal of Remote Sensing and Space Science. 17(1): 105–110.

Doi: https://doi.org/10.1016/j.ejrs.2013.10.001.

Huang, S. H., Huang, Y. H., Blazquez, C. A. and Paredes-Belmar, G. 2018. Application of the Ant Colony Optimization in the Resolution of the Bridge Inspection Routing Problem. Applied Soft Computing. 65: 443–461.

Doi: https://doi.org/10.1016/j.asoc.2018.01.034.

Guo, N., Qian, B., Hu, R., Jin, H. P. and Xiang, F. H. 2020. A Hybrid Ant Colony Optimization Algorithm for Multi-Compartment Vehicle Routing Problem. Complexity. 2020.

Doi: https://doi.org/10.1155/2020/8839526.

Tang, J., Zhang, J. and Pan, Z. 2010. A Scatter Search Algorithm for Solving Vehicle Routing Problem with Loading Cost. Expert Systems with Applications. 37(6): 4073–4083.

Doi: https://doi.org/10.1016/j.eswa.2009.11.027.

Buhrkal, K., Larsen, A. and Ropke, S. 2012. The Waste Collection Vehicle Routing Problem with Time Windows in a City Logistics Context. Procedia-Social and Behavioral Sciences. 39: 241–254.

Doi: https://doi.org/10.1016/j.sbspro.2012.03.105.

Zhang, D., Dong, R., Si, Y.W., Ye, F. and Cai, Q. 2018. A Hybrid Swarm Algorithm based on ABC and AIS for 2L-HFCVRP. Applied Soft Computing. 64: 468–479.

Doi: https://doi.org/10.1016/j.asoc.2017.12.012.

Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T. and Subramanian, A. 2017. New Benchmark Instances for the Capacitated Vehicle Routing Problem. European Journal of Operational Research. 257(3): 845–858.

Doi: https://doi.org/10.1016/j.ejor.2016.08.012.

Kyriakakis, N.A., Marinaki, M. and Marinakis, Y. 2021. A Hybrid Ant Colony Optimization-Variable Neighborhood Descent Approach for the Cumulative Capacitated Vehicle Routing Problem. Computers & Operations Research. 134: 105397.

Doi: https://doi.org/10.1016/j.cor.2021.105397.

Matthopoulos, P. P., & Sofianopoulou, S. 2019. A Firefly Algorithm for the Heterogeneous Fixed Fleet Vehicle Routing Problem. International Journal of Industrial and Systems Engineering. 33(2): 204–224.

Arnold, F., Santana, Í., Sörensen, K. and Vidal, T. 2021. PILS: Exploring High-order Neighborhoods by Pattern Mining and Injection. Pattern Recognition. 116: 107957.

Doi: https://doi.org/10.1016/j.patcog.2021.107957.

Gunduz. M. and Aslan. M. 2021. DJAYA: A Discrete Jaya Algorithm for Solving Traveling Salesman Problem. Applied Soft Computing. 105: 107275.

Doi: https://doi.org/10.1016/j.asoc.2021.107275.