Application of Greedy Algorithm and Simulated Annealing Algorithm on the Asymmetric Capacitated Vehicle Routing Problem Model in Designing Optimal Garbage Transportation Routes

Bella Arisha; Fitri Maya Puspita; Bambang Suprihatin; Indrawati

doi:10.26740/vubeta.v3i2.45644

Authors

Bella Arisha Department of Mathematics Education, Faculty of Teacher and Training Education, Universitas Jambi, Jambi, Indonesia
Fitri Maya Puspita Department of Mathematics, Mathematics and Natural Sciences, Universitas Sriwijaya, Palembang, Indonesi
Bambang Suprihatin Department of Mathematics, Mathematics and Natural Sciences, Universitas Sriwijaya, Palembang, Indonesia
Indrawati Department of Mathematics, Mathematics and Natural Sciences, Universitas Sriwijaya, Palembang, Indonesia

DOI:

https://doi.org/10.26740/vubeta.v3i2.45644

Keywords:

Greedy Algorithm, Optimal Route, Waste Transportation, Vehicle routing problem, Simulation annealing

Abstract

Waste management remains a recurring issue, particularly in large urban areas. An optimal waste collection route is essential to prevent the problem from becoming more severe and persistent. This study aims to determine the minimum distance and route for waste collection in the Seberang Ulu 1 District, Palembang, using the Greedy and Simulated Annealing algorithms. The calculations were carried out by dividing the district into four work zones. The results show that, using the Greedy algorithm, the minimum distances and routes for work zones 1 through 4 were 24.655 km, 29.7 km, 22.7 km, and 24.705 km, respectively. Meanwhile, using the Simulated Annealing algorithm, the minimum distances and routes for each work zone were 24.325 km, 32.45 km, 22.5 km, and 22.385 km. On average, SA reduces the total distance traveled by 2.1% compared to Greedy, but it requires a longer computation time due to its iterative process of finding the global optimum. These indicate that both algorithms are equally effective in solving the ACVRP problem, with different advantages. SA's advantage in optimizing more complex routes and Greedy's advantage in computation speed for practical implementation. These findings indicate that the Simulated Annealing Algorithm and the Greedy Algorithm almost the same results in solving the Asymmetric Capacitated Vehicle Routing Problem in Seberang Ulu 1 District, Palembang.

Author Biographies

Bella Arisha, Department of Mathematics Education, Faculty of Teacher and Training Education, Universitas Jambi, Jambi, Indonesia

Department of Mathematics Education, Faculty of Teacher and Training Education, Universitas Jambi, Jambi, Indonesia

Fitri Maya Puspita, Department of Mathematics, Mathematics and Natural Sciences, Universitas Sriwijaya, Palembang, Indonesi

Department of Mathematics, Mathematics and Natural Sciences, Universitas Sriwijaya, Palembang, Indonesia

Bambang Suprihatin, Department of Mathematics, Mathematics and Natural Sciences, Universitas Sriwijaya, Palembang, Indonesia

Department of Mathematics, Mathematics and Natural Sciences, Universitas Sriwijaya, Palembang, Indonesia

Indrawati, Department of Mathematics, Mathematics and Natural Sciences, Universitas Sriwijaya, Palembang, Indonesia

Department of Mathematics, Mathematics and Natural Sciences, Universitas Sriwijaya, Palembang, Indonesia

References

[1] S. Purba, H. Khotimah, A. Suli, & M. Wahyuningsi, “The Impact of Educational Conditions on Income Inequality and Economic Growth in South Sumatra,” Kne Social Sciences, 2024. https://doi.org/10.18502/kss.v9i14.16104.

[2] M. Pratama and S. Zubaidah, “Poverty Alleviation Policy Strategy through Sustainability Development Goals (SDGs) and Indonesia's Economic Resources,” Kne Social Sciences, 2024. https://doi.org/10.18502/kss.v9i18.16329.

[3] S. Anthony, A. Iriani, S. Nofrima, & R. Basista, “Dynamic Governance in increasing Millennial Participation Food Independent South Sumatra Movement Program (GSMP),” Jurnal Public Policy, vol. 9, no. 3, pp. 208, 2023. https://doi.org/10.35308/jpp.v9i3.7463.

[4] R. Kautsar, S. Fauziyah, F. Aquaresta, A. Widya, N. FAJAR, M. Damayanti et al., “Detection of Legionella pneumophila bacteria from water sources in Palembang City, Indonesia,” Biodiversitas Journal of Biological Diversity, vol. 25, no. 4, 2024. https://doi.org/10.13057/biodiv/d250417.

[5] E. Fatma, W. Kartika, & A. Madyanti, “Determination of Optimization Medical Waste Route Transportation using Vehicle Routing Problem with Time Window in Multi Depot Case,” Journal of Management and Organization, vol. 13, no. 4, pp. 324-335, 2022. https://doi.org/10.29244/jmo.v13i4.38587.

[6] D. Bantoro, S. Suatmiati, & A. Wardhana, “Implementation of Road Equipment Installation in South Sumatera Province (Case Study of Installation of Street Lighting Equipment on the Betung – BTS Section, Palembang City),” International Journal of Social Science Research and Review, vol. 7, no. 3, pp. 66-70, 2024. https://doi.org/10.47814/ijssrr.v7i3.1892.

[7] M. Shiri, F. Ahmadizar, D. Thiruvady, & H. Farvaresh, “A Sustainable and Efficient Home Health Care Network Design Model under Uncertainty,” Expert Systems with Applications, vol. 211, pp. 118185, 2023. https://doi.org/10.1016/j.eswa.2022.118185.

[8] M. Belhiah and S. Ziti, “Optimising Unplanned Waste Collection: An IoT‐Enabled System for Smart Cities: A Case Study in Tangier, Morocco,” IET Smart Cities, vol. 6, no. 1, pp. 27-40, 2023. https://doi.org/10.1049/smc2.12069.

[9] S. Gulyamov, “Intelligent Waste Management using IoT, Blockchain Technology and Data Analytics,” E3S Web of Conferences, vol. 501, pp. 01010, 2024. https://doi.org/10.1051/e3sconf/202450101010.

[10] C. Mbama, A. Otegbulu, I. Beverland, & T. Beattie, “Solid Waste Recycling within Higher Education in Developing Countries: A Case Study of the University of Lagos,” Journal of Material Cycles and Waste Management, vol. 25, no. 2, pp. 886-898, 2022. https://doi.org/10.1007/s10163-022-01569-5.

[11] A. Addas, M. Khan, & F. Naseer, “Waste Management 2.0 Leveraging Internet of Things for an Efficient and Eco-Friendly Smart City Solution,” Plos One, vol. 19, no. 7, pp. e0307608, 2024. https://doi.org/10.1371/journal.pone.0307608.

[12] A. Maroof, Q. Khalid, M. Mahmood, K. Naeem, S. Maqsood, S. Khattak et al., “Vehicle Routing Optimization for Humanitarian Supply Chain: A Systematic Review of Approaches and Solutions,” IEEE Access, vol. 11, pp. 127157-127175, 2023. https://doi.org/10.1109/access.2023.3331062.

[13] G. Thakur, A. Pal, N. Mittal, M. Yajid, & F. Gared, “A Significant Exploration on Meta-Heuristic based Approaches for Optimization in the Waste Management Route Problems,” Scientific Reports, vol. 14, no. 1, 2024. https://doi.org/10.1038/s41598-024-64133-1.

[14] Y. Bahi, L. Ezzine, Z. Aman, I. Moussaoui, M. Rahmoune, & H. Moussami, “Distribution Management Problem: Heuristic Solution for Vehicle Routing Problem with Time Windows (VRPTW) in the Moroccan Petroleum Sector,” Advances in Science Technology and Engineering Systems Journal, vol. 8, no. 4, pp. 66-72, 2023. https://doi.org/10.25046/aj080408.

[15] E. Lam, “Hybrid Optimization of Vehicle Routing Problems,” Constraints, vol. 28, no. 2, pp. 67-68, 2023. https://doi.org/10.1007/s10601-023-09352-5.

[16] B. Ali, M. Javed, A. Alharbi, S. Alotaibi, & M. Alkhathami, “Internet of Things-Assisted Vehicle Route Optimization for Municipal Solid Waste Collection,” Applied Sciences, vol. 14, no. 1, pp. 287, 2023. https://doi.org/10.3390/app14010287.

[17] T. Calamoneri, F. Corò, & S. Mancini, “Management of a Post-Disaster Emergency Scenario through Unmanned Aerial Vehicles: Multi-Depot Multi-Trip Vehicle Routing with Total Completion Time Minimization,” Expert Systems with Applications, vol. 251, pp. 123766, 2024. https://doi.org/10.1016/j.eswa.2024.123766.

[18] U. Dereci and M. Karabekmez, “The Applications of Multiple Route Optimization Heuristics and Meta-Heuristic Algorithms to Solid Waste Transportation: A Case Study in Turkey,” Decision Analytics Journal, vol. 4, pp. 100113, 2022. https://doi.org/10.1016/j.dajour.2022.100113.

[19] Y. Hartono, F. Puspita, D. Permatasari, & B. Arisha, “LINGO-based on Robust Counterpart Open Capacitated Vehicle Routing Problem (RC-OCVRP) Model of Waste Transportation in Palembang,” 2018 International Conference on Information and Communications Technology (ICOIACT), pp. 429-435, 2018. https://doi.org/10.1109/icoiact.2018.8350689.

[20] J. Obari, S. Ahmed, I. Monday, & A. Busayo, “An Emission and Weight of Vehicles-Based Road Traffic Congestion Pricing System and Control with Consideration of Investment Worthiness,” Vokasi Unesa Bulletin of Engineering Technology and Applied Science, vol. 2, no. 3, pp. 401-411, 2025. https://doi.org/10.26740/vubeta.v2i3.38528.

[21] J. Li, T. Li, Y. Yu, Z. Zhang, P. Pardalos, Y. Zhang et al., “Discrete Firefly Algorithm with Compound Neighborhoods for Asymmetric Multi-Depot Vehicle Routing Problem in the Maintenance of Farm Machinery,” Applied Soft Computing, vol. 81, pp. 105460, 2019. https://doi.org/10.1016/j.asoc.2019.04.030.

[22] Z. Li, H. Sang, J. Li, Y. Han, K. Gao, & Z. Zheng, “Invasive Weed Optimization for Multi-AGVs Dispatching Problem in a Matrix Manufacturing Workshop,” Swarm and Evolutionary Computation, vol. 77, pp. 101227, 2023. https://doi.org/10.1016/j.swevo.2023.101227.

[23] Z. Liu, H. Sang, C. Zheng, H. Ran, K. Gao, & Y. Han, “An Effective Multi-Restart Iterated Greedy Algorithm for Multi-AGVs Dispatching Problem in the Matrix Manufacturing Workshop,” Expert Systems with Applications, vol. 252, pp. 124223, 2024. https://doi.org/10.1016/j.eswa.2024.124223.

[24] A. Mor and M. Speranza, “Vehicle Routing Problems Over Time: A Survey,” Annals of Operations Research, vol. 314, no. 1, pp. 255-275, 2022. https://doi.org/10.1007/s10479-021-04488-0.

[25] S. Taghavi, V. Ghezavati, H. Bidhandi, & S. Al-e-Hashem, “Green-Resilient Supplier Selection and Order Allocation Under Disruption by Utilizing Conditional Value at Risk: Mixed Response Strategies,” Process Integration and Optimization for Sustainability, vol. 7, no. 1-2, pp. 359-380, 2022. https://doi.org/10.1007/s41660-022-00298-4.

[26] A. Gil, E. Lalla‐Ruiz, M. Sánchez, & C. Castro, “A Review of Heuristics and Hybrid Methods for Green Vehicle Routing Problems considering Emissions,” Journal of Advanced Transportation, vol. 2022, pp. 1-38, 2022. https://doi.org/10.1155/2022/5714991.

[27] N. Dinh, C. Archetti, & L. Bertazzi, “The Inventory Routing Problem with Split Deliveries,” Networks, vol. 82, no. 4, pp. 400-413, 2023. https://doi.org/10.1002/net.22175.

[28] M. Ammouriova, E. Herrera, M. Neroni, Á. Juan, & J. Faulín, “Solving Vehicle Routing Problems under Uncertainty and in Dynamic Scenarios: From Simheuristics to Agile Optimization,” Applied Sciences, vol. 13, no. 1, pp. 101, 2022. https://doi.org/10.3390/app13010101.

[29] K. Lin, S. Musa, & H. Yap, “Vehicle Routing Optimization for Pandemic Containment: A Systematic Review on Applications and Solution Approaches,” Sustainability, vol. 14, no. 4, pp. 2053, 2022. https://doi.org/10.3390/su14042053.

[30] S. Lo and Y. Chuang, “Vehicle Routing Optimization with Cross-Docking Based on an Artificial Immune System in Logistics Management,” Mathematics, vol. 11, no. 4, pp. 811, 2023. https://doi.org/10.3390/math11040811.

[31] Z. He, M. Zhang, Q. Chen, S. Chen, & N. Pan, “Optimization of Heterogeneous Vehicle Logistics Scheduling with Multi-Objectives and Multi-Centers,” Scientific Reports, vol. 13, no. 1, 2023. https://doi.org/10.1038/s41598-023-41450-5.

[32] Y. Liu and Y. Huanzhao, “Research on Vehicle Routing Problem Based on Hybrid Immune Algorithm,” Ninth International Conference on Electromechanical Control Technology and Transportation (ICECTT 2024), pp. 66, 2024. https://doi.org/10.1117/12.3039507.

[33] B. Arisha and T. Nengsih, “Applied of Model Vehicle Sharing System with Modified Model Passive Regulation Lower Bound for Mobility Improvement,” Proceedings of the 6th International Conference of Mathematics and Mathematics Education, 2022: Innovative Research of Mathematic, 2024. https://doi.org/10.1063/5.0204594.

[34] R. Elshaer and H. Awad, “A Taxonomic Review of Metaheuristic Algorithms for Solving the Vehicle Routing Problem and its Variants,” Computers & Industrial Engineering, vol. 140, pp. 106242, 2020. https://doi.org/10.1016/j.cie.2019.106242.

[35] L. Wenyi, “Research on Vehicle Routing Problem and Application Scenarios,” Handbook of Mobility Data Mining, pp. 63-88, 2023. https://doi.org/10.1016/b978-0-323-95892-9.00006-1.

[36] F. Mar’i, H. Ubaidillah, W. Mahmudy, & A. Supianto, “Hybrid Artificial Bee Colony and Improved Simulated Annealing for the Capacitated Vehicle Routing Problem,” Knowledge Engineering and Data Science, vol. 5, no. 2, 2022. https://doi.org/10.17977/um018v5i22022p109-121.

[37] V. Leggieri and M. Haouari, “A Practical Solution Approach for the Green Vehicle Routing Problem,” Transportation Research Part E Logistics and Transportation Review, vol. 104, pp. 97-112, 2017. https://doi.org/10.1016/j.tre.2017.06.003.

[38] B. Bouvier, P. Pascal, & H. Piet-Lahanier, “Optimal Route Design for an Airship Collecting and Delivering Logs in Difficult Environmental Conditions,” Ifac-Papersonline, vol. 55, no. 22, pp. 255-260, 2022. https://doi.org/10.1016/j.ifacol.2023.03.043.

[39] A. García, “Greedy Algorithms: A Review and Open Problems,” Journal of Inequalities and Applications, vol. 2025, no. 1, 2025. https://doi.org/10.1186/s13660-025-03254-1.

[40] H. Hidayatulloh, P. Subarkah, R. Dermawan, & M. Rohman, “Optimizing the Implementation of the Greedy Algorithm to Achieve Efficiency in Garbage Transportation Routes,” JTAM (Jurnal Teori Dan Aplikasi Matematika), vol. 7, no. 4, pp. 1143, 2023. https://doi.org/10.31764/jtam.v7i4.16612.

[41] A. Almutairi, “Combined Nearest Greedy Algorithm with Randomized Iterated Greedy Algorithm to Solve Waste Collection Problem,” International Journal of Statistics and Probability, vol. 9, no. 3, pp. 66, 2020. https://doi.org/10.5539/ijsp.v9n3p66.

[42] H. Apat, B. Sahoo, V. Goswami, & R. Barik, “A Hybrid Meta-Heuristic Algorithm for Multi-Objective IoT Service Placement in Fog Computing Environments,” Decision Analytics Journal, vol. 10, pp. 100379, 2024. https://doi.org/10.1016/j.dajour.2023.100379.

[43] O. Canpolat, H. Demir, & C. Erden, “Meta-Heuristic Algorithms for Integrating Manufacturing and Supply Chain Functions,” Computers & Industrial Engineering, vol. 192, pp. 110240, 2024. https://doi.org/10.1016/j.cie.2024.110240.

[44] F. Arnold and K. Sörensen, “What Makes a VRP Solution Good? The Generation of Problem-Specific Knowledge for Heuristics,” Computers & Operations Research, vol. 106, pp. 280-288, 2019. https://doi.org/10.1016/j.cor.2018.02.007.

[45] I. Zidi, M. Al-Omani, & K. Aldhafeeri, “A New Approach Based on the Hybridization of Simulated Annealing Algorithm and Tabu Search to Solve the Static Ambulance Routing Problem,” Procedia Computer Science, vol. 159, pp. 1216-1228, 2019. https://doi.org/10.1016/j.procs.2019.09.291.

[46] V. Yu, P. Jodiawan, S. Lin, W. Nadira, A. Asih, & L. Vinh, “Using Simulated Annealing to Solve the Multi-Depot Waste Collection Vehicle Routing Problem with Time Window and Self-Delivery Option,” Mathematics, vol. 12, no. 3, pp. 501, 2024. https://doi.org/10.3390/math12030501.

[47] V. Yu, G. Aloina, H. Susanto, M. Effendi, & S. Lin, “Regional Location Routing Problem for Waste Collection Using Hybrid Genetic Algorithm-Simulated Annealing,” Mathematics, vol. 10, no. 12, pp. 2131, 2022. https://doi.org/10.3390/math10122131.

[48] V. Yu, S. Lin, L. Zhou, & R. Baldacci, “A Fast Simulated Annealing Heuristic for the Multi-Depot Two-Echelon Vehicle Routing Problem with Delivery Options,” Transportation Letters, vol. 16, no. 8, pp. 921-932, 2023. https://doi.org/10.1080/19427867.2023.2257923.

[49] D. Rossit, A. Toncovich, & M. Fermani, “Routing in Waste Collection: A Simulated Annealing Algorithm for an Argentinean Case Study,” Mathematical Biosciences and Engineering, vol. 18, no. 6, pp. 9579-9605, 2021. https://doi.org/10.3934/mbe.2021470.

[50] J. Zhang, “The Logic and Application of Greedy Algorithms,” Applied and Computational Engineering, vol. 82, no. 1, pp. 154-160, 2024. https://doi.org/10.54254/2755-2721/82/20241110.

[51] Z. Zhang, “Optimization of Multibeam Survey Measurement Based on Greedy Algorithm,” Highlights in Science Engineering and Technology, vol. 100, pp. 95-101, 2024. https://doi.org/10.54097/y5gvg089.

[52] G. Sun, R. Qi, Y. Liu, & F. Xu, “A Dynamic Traffic Signal Scheduling System based on Improved Greedy Algorithm,” Plos One, vol. 19, no. 3, pp. e0298417, 2024. https://doi.org/10.1371/journal.pone.0298417.

[53] E. Tetteh and B. Zielosko, “Greedy Algorithm for Deriving Decision Rules from Decision Tree Ensembles,” Entropy, vol. 27, no. 1, pp. 35, 2025. https://doi.org/10.3390/e27010035.

[54] D. Behera, “Optimizing Power Generation Scheduling: A Comparative Analysis of Metaheuristic Algorithms,” Journal of Electrical Systems, vol. 20, no. 2, pp. 2212-2230, 2024. https://doi.org/10.52783/jes.1989.

[55] H. Liu and H. Zhang, “Application of an Improved Simulated Annealing Algorithm in Satellite Network Routing,” Journal of Physics Conference Series, vol. 2807, no. 1, pp. 012028, 2024. https://doi.org/10.1088/1742-6596/2807/1/012028.

[56] F. Liu, Y. Zhang, B. Zhang, Y. Sun, K. Cheng, S. Jiang et al., “Urban Water Supply Dispatching based on Improved BP Neural Network and Simulated Annealing Algorithm,” Journal of Physics Conference Series, vol. 3082, no. 1, pp. 012041, 2025. https://doi.org/10.1088/1742-6596/3082/1/012041.

[57] R. Nugraha, “Application of Global Optimization Using Simulated Annealing and Artificial Bee Colony Algorithm: A Comparative Study on the 2022 Mw 5.6 Cianjur Earthquake,” IOP Conference Series Earth and Environmental Science, vol. 1458, no. 1, pp. 012028, 2025. https://doi.org/10.1088/1755-1315/1458/1/012028.