Vehicle Routing Problem: A Performance Comparison of Hybrid Evolutionary Algorithm with Local Search Strategies

Maria Ulfah Siregar; Thoriq Firdaus Arifin; Muhammad Javier Badruttamam; Maulida Suryaning Aisha; Ibnu Raju Humam; Muhammad Hafiz; Siti Mutmainah

doi:10.15575/join.v11i1.1539

Authors

Maria Ulfah Siregar Department of Informatics, UIN Sunan Kalijaga Yogyakarta, Indonesia https://orcid.org/0000-0001-7983-1007
Thoriq Firdaus Arifin Department of Informatics, UIN Sunan Kalijaga Yogyakarta, Indonesia
Muhammad Javier Badruttamam Department of Informatics, UIN Sunan Kalijaga Yogyakarta, Indonesia
Maulida Suryaning Aisha Department of Informatics, UIN Sunan Kalijaga Yogyakarta, Indonesia
Ibnu Raju Humam Department of Informatics, UIN Sunan Kalijaga Yogyakarta, Indonesia
Muhammad Hafiz Department of Informatics, UIN Sunan Kalijaga Yogyakarta, Indonesia
Siti Mutmainah Department of Informatics, UIN Sunan Kalijaga Yogyakarta, Indonesia https://orcid.org/0000-0001-7747-435X

DOI:

https://doi.org/10.15575/join.v11i1.1539

Keywords:

Genetic Algorithm, Local Search, Metaheuristic Hybridization, Particle Swarm Optimization, Simulated Annealing, Vehicle Routing Problem

Abstract

The Vehicle Routing Problem (VRP), one of the most challenging problems in logistics and transport, has been an area of optimization solutions to minimize costs and optimize the operational process. This study examines a hybrid of metaheuristic algorithms that are combinations of the Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Simulated Annealing (SA), and Local Search (LS) to tackle various complexities of VRP. The hybrid approach offered better exploration and exploitation by integrating global explorations with GA and PSO and local refinement with SA and LS. The performance was performed using real datasets and generated randomly with problem sizes ranging from 9 to 100 customers. PSO-LS and GA-LS are LS-based hybrids that produce lower standard deviations, showing a stable and consistent result for small to medium problems. For example, PSO-LS computed 3.31 for 9 customers and 5.76 for 50 customers. However, SA-based hybrids, such as PSO-SA and GA-SA, presented more variability, with SA-GA reaching 100 customers as much as 7.83. These findings highlight key trade-offs while optimizing VRP between stability, efficiency, and problem scale.

References

[1] A. Seyyedabbasi, W. Z. Tareq Tareq, and N. Bacanin, “An Effective Hybrid Metaheuristic Algorithm for Solving Global Optimization Algorithms,” Multimed. Tools Appl., vol. 83, no. 37, pp. 85103–85138, May 2024, doi: 10.1007/s11042-024-19437-9.

[2] A. Bogyrbayeva, M. Meraliyev, T. Mustakhov, and B. Dauletbayev, “Machine Learning to Solve Vehicle Routing Problems: A Survey,” IEEE Trans. Intell. Transp. Syst., vol. 25, no. 6, pp. 4754–4772, 2024, doi: 10.1109/TITS.2023.3334976.

[3] G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Manage. Sci., vol. 6, no. 1, pp. 80–91, 1959, [Online]. Available: https://www.jstor.org/stable/2627477

[4] M. Drexl, “Synchronization in Vehicle Routing—A Survey of VRPs with Multiple Synchronization Constraints,” Transp. Sci., vol. 46, no. 3, pp. 297–316, Aug. 2012, doi: 10.1287/trsc.1110.0400.

[5] S. F. Roselli, M. Fabian, and K. Åkesson, “Conflict-free electric vehicle routing problem: an improved compositional algorithm,” Discret. Event Dyn. Syst., vol. 34, no. 1, pp. 21–51, Mar. 2024, doi: 10.1007/s10626-023-00388-6.

[6] M. Oliveira Machado, E. F. Gouvea Goldbarg, M. Cesar Goldbarg, G. De Araujo Sabry, I. F. Costa Fernandes, and T. Soares Marques, “Heuristic Hybridization for CaRSP, a multilevel decision problem,” in 2021 IEEE Symposium Series on Computational Intelligence (SSCI), IEEE, Dec. 2021, pp. 01–08. doi: 10.1109/SSCI50451.2021.9660015.

[7] S. Kaya, “A hybrid firefly and particle swarm optimization algorithm with local search for the problem of municipal solid waste collection: a real-life example,” Neural Comput. Appl., vol. 35, no. 9, pp. 7107–7124, 2023, doi: 10.1007/s00521-022-08173-6.

[8] L. Cai, “Decision-making of transportation vehicle routing based on particle swarm optimization algorithm in logistics distribution management,” Cluster Comput., vol. 26, no. 6, pp. 3707–3718, 2023, doi: 10.1007/s10586-022-03730-z.

[9] J. K. C. Revanna and N. Y. B. Al-Nakash, “Metaheuristic link prediction (MLP) using AI based ACO-GA optimization model for solving vehicle routing problem,” Int. J. Inf. Technol., vol. 15, no. 7, pp. 3425–3439, 2023, doi: 10.1007/s41870-023-01378-5.

[10] H. Saleh, M. Sayad, Y. Almoghathawi, A. Alghazi, and K. Al-Shareef, “A drone-based logistics network for blood supplies: a genetic algorithm based on greedy search,” Soft Comput., vol. 2, 2024, doi: 10.1007/s00500-024-10373-2.

[11] M. Abdel-Basset, L. Abdel-Fatah, and A. K. Sangaiah, Metaheuristic algorithms: A comprehensive review. Elsevier Inc., 2018. doi: 10.1016/B978-0-12-813314-9.00010-4.

[12] G. Erdoğan, “An open source Spreadsheet Solver for Vehicle Routing Problems,” Comput. Oper. Res., vol. 84, pp. 62–72, Aug. 2017, doi: 10.1016/j.cor.2017.02.022.

[13] R. Elshaer and H. Awad, “A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants,” Comput. Ind. Eng., vol. 140, p. 106242, Feb. 2020, doi: 10.1016/j.cie.2019.106242.

[14] C. Prins, “A simple and effective evolutionary algorithm for the vehicle routing problem,” Comput. Oper. Res., vol. 31, no. 12, pp. 1985–2002, 2004, doi: 10.1016/S0305-0548(03)00158-8.

[15] R. F. Syahputra and Yahfizham, “Menganalisis Konsep Dasar Algoritma Genetika,” Bhinneka J. Bintang Pendidik. dan Bhs., vol. 2, no. 1, pp. 120–132, Dec. 2024, doi: 10.59024/bhinneka.v2i1.643.

[16] A. Lambora, K. Gupta, and K. Chopra, “Genetic Algorithm- A Literature Review,” in 2019 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing (COMITCon), IEEE, Feb. 2019, pp. 380–384. doi: 10.1109/COMITCon.2019.8862255.

[17] K. S. Tang, K. F. Man, S. Kwong, and Q. He, “Genetic algorithms and their applications,” IEEE Signal Process. Mag., vol. 13, no. 6, pp. 22–37, 1996, doi: 10.1109/79.543973.

[18] F. Zhang, Y. Xie, and L. Zheng, “Application and Efficiency Analysis of Genetic Algorithm in Multi-Vehicle Path Optimisation Models Under Time Window Constraints,” in 2024 IEEE 7th International Conference on Information Systems and Computer Aided Education (ICISCAE), IEEE, Sep. 2024, pp. 938–944. doi: 10.1109/ICISCAE62304.2024.10761568.

[19] A. A. Mousa, M. A. El-Shorbagy, and W. F. Abd-El-Wahed, “Local search based hybrid particle swarm optimization algorithm for multiobjective optimization,” Swarm Evol. Comput., vol. 3, pp. 1–14, 2012, doi: 10.1016/j.swevo.2011.11.005.

[20] E. Mirsadeghi and S. Khodayifar, “Hybridizing particle swarm optimization with simulated annealing and differential evolution,” Cluster Comput., vol. 24, no. 2, pp. 1135–1163, Jun. 2021, doi: 10.1007/s10586-020-03179-y.

[21] F. Javidrad and M. Nazari, “A new hybrid particle swarm and simulated annealing stochastic optimization method,” Appl. Soft Comput., vol. 60, pp. 634–654, Nov. 2017, doi: 10.1016/j.asoc.2017.07.023.

[22] B. Fu, Y. He, Q. Guo, and J. Zhang, “An improved competitive particle swarm optimization algorithm based on de-heterogeneous information,” J. King Saud Univ. - Comput. Inf. Sci., vol. 35, no. 6, 2023, doi: 10.1016/j.jksuci.2022.12.012.

[23] L. Vanneschi and S. Silva, “Particle Swarm Optimization,” L. Vanneschi and S. Silva, Eds., Cham: Springer International Publishing, 2023, pp. 105–111. doi: 10.1007/978-3-031-17922-8_4.

[24] M. Tanha, M. H. Shirvani, and A. M. Rahmani, A hybrid meta-heuristic task scheduling algorithm based on genetic and thermodynamic simulated annealing algorithms in cloud computing environments, vol. 33, no. 24. Springer London, 2021. doi: 10.1007/s00521-021-06289-9.

[25] H. L. Shieh, C. C. Kuo, and C. M. Chiang, “Modified particle swarm optimization algorithm with simulated annealing behavior and its numerical verification,” Appl. Math. Comput., vol. 218, no. 8, pp. 4365–4383, 2011, doi: 10.1016/j.amc.2011.10.012.

[26] W. Ben-Ameur, “Computing the Initial Temperature of Simulated Annealing,” Comput. Optim. Appl., vol. 29, no. 3, pp. 369–385, Dec. 2004, doi: 10.1023/B:COAP.0000044187.23143.bd.

[27] J. J. Schneider and M. Puchta, “Investigation of acceptance simulated annealing — A simplified approach to adaptive cooling schedules,” Phys. A Stat. Mech. its Appl., vol. 389, no. 24, pp. 5822–5831, Dec. 2010, doi: 10.1016/j.physa.2010.08.045.

[28] B. Hajek, “Cooling Schedules for Optimal Annealing,” Math. Oper. Res., vol. 13, no. 2, pp. 311–329, May 1988, doi: 10.1287/moor.13.2.311.

[29] Y. Dong-mei, “A Hybrid Algorithm of Simulated Annealing and Particle Swarm Optimization,” Comput. Simul., 2008, [Online]. Available: https://api.semanticscholar.org/CorpusID:125077198

[30] P. Moradi and M. Gholampour, “A hybrid particle swarm optimization for feature subset selection by integrating a novel local search strategy,” Appl. Soft Comput. J., vol. 43, pp. 117–130, 2016, doi: 10.1016/j.asoc.2016.01.044.

[31] F. Uddin et al., “An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour,” Appl. Sci., vol. 13, no. 12, p. 7339, Jun. 2023, doi: 10.3390/app13127339.

[32] S. B. Sarathi Barma, J. Dutta, and A. Mukherjee, “A 2-opt guided discrete antlion optimization algorithm for multi-depot vehicle routing problem,” Decis. Mak. Appl. Manag. Eng., vol. 2, no. 2, Oct. 2019, doi: 10.31181/dmame1902089b.

[33] P. Aivaliotis-Apostolopoulos and D. Loukidis, “Swarming genetic algorithm: A nested fully coupled hybrid of genetic algorithm and particle swarm optimization,” PLoS One, vol. 17, no. 9, pp. 1–24, 2022, doi: 10.1371/journal.pone.0275094.

[34] S. Yin and H. Li, “GSAPSO-MQC:medical image encryption based on genetic simulated annealing particle swarm optimization and modified quantum chaos system,” Evol. Intell., vol. 14, no. 4, pp. 1817–1829, 2021, doi: 10.1007/s12065-020-00440-6.