An Efficient Hybrid Meta-heuristic Algorithm for Solving Capacitated Vehicle Routing Problem

Year 2025, Volume: 29 Issue: 3, 293 - 306, 26.06.2025

Emrullah Gazioğlu

https://doi.org/10.16984/saufenbilder.1631550

Abstract

Vehicle routing inside factories is one of the hard problems that researchers try to solve for many years. When planning routes, we must think about how much vehicles can carry and how factory buildings are organized. Some factories have same type vehicles while others have different types with varying capacities. Researchers made good algorithms for this problem, but these algorithms need too much computer power. In our study, we made a new algorithm that uses adaptive memory to remember good solutions and selectively explores promising regions of the solution space. When we compare with old methods, our algorithm finds the same optimal solutions but needs about 80 percent less calculations. For testing our algorithm, we used real data from a car factory with both same type vehicles and different type vehicles. We tested five different scenarios and ran each test 30 times, performing comprehensive statistical analyses. All tests showed 100 percent success rate in finding optimal solutions with remarkable computational efficiency. Test results show us something important: We don't need to look at all possible solutions to find the best one. If we look at only promising areas, we can find best solution faster. This makes our method very useful for real factory problems because factory managers need quick solutions and don't want to use too much computer power. Our method is good at finding which solution areas are promising and focuses on these areas, so it solves problems faster with less computer resources.

Keywords

Vehicle routing, Evolutionary computing, Local search, Global optimization, Meta-heuristics, Global search

References

• G. B. Dantzig, J. H. Ramser, “The truck dispatching problem,” Management Science, INFORMS, pp. 80–91, 1959.
• T. O. Ting, X.-S. Yang, S. Cheng, K. Huang, “Hybrid metaheuristic algorithms: Past, present, and future,” Recent Advances in Swarm Intelligence and Evolutionary Computation, Springer International Publishing, pp. 71–83, 2015.
• S. Kulaç, N. Kazancı, “Optimization of ın-plant logistics through a new hybrid algorithm for the capacitated vehicle routing problem with heterogeneous fleet,” Sakarya University Journal of Science, Sakarya University, pp. 1242–1260, 2024.
• P. Toth, D. Vigo, “Exact solution of the vehicle routing problem,” Fleet Management and Logistics, Springer US, pp. 1–31, 1998.
• G. Laporte, Y. Nobert, “Exact Algorithms for the vehicle routing problem*,” North-Holland Mathematics Studies, North-Holland, pp. 147–184, 1987.
• A. Mingozzi, R. Roberti, P. Toth, “An exact algorithm for the multitrip vehicle routing problem,” INFORMS Journal on Computing, INFORMS, pp. 193–207, 2013.
• M. Battarra, G. Erdoğan, D. Vigo, “Exact algorithms for the clustered vehicle routing problem,” Operations Research, INFORMS, pp. 58–71, 2014.
• V. F. Yu, H. Susanto, P. Jodiawan, T.-W. Ho, S.-W. Lin, Y.-T. Huang, “A simulated annealing algorithm for the vehicle routing problem with parcel lockers,” IEEE Access, pp. 20764–20782, 2022.
• İ. İlhan, “An improved simulated annealing algorithm with crossover operator for capacitated vehicle routing problem,” Swarm and Evolutionary Computation, p. 100911, 2021.
• E. Rodríguez-Esparza, A. D. Masegosa, D. Oliva, E. Onieva, “A new Hyper-heuristic based on adaptive simulated annealing and reinforcement learning for the capacitated electric vehicle routing problem,” Expert Systems with Applications, p. 124197, 2024.
• M. Sajid, J. Singh, R. Rajak, “Capacitated vehicle routing problem using algebraic particle swarm optimization with simulated annealing algorithm,” Artificial Intelligence in Cyber-Physical Systems, CRC Press, 2023.
• Z. Hussain Ahmed, M. Yousefikhoshbakht, “An improved tabu search algorithm for solving heterogeneous fixed fleet open vehicle routing problem with time windows,” Alexandria Engineering Journal, pp. 349–363, 2023.
• A. Mexicano, J. C. Carmona, D. Y. Alvarez, P. N. Montes, S. Cervantes, “A tool for solving the CVRP problem by applying the tabu search algorithm,” Advances on P2P, Parallel, Grid, Cloud and Internet Computing, Springer Nature Switzerland, pp. 294–304, 2024.
• J. Holliday, B. Morgan, H. Churchill, K. Luu, “Hybrid quantum tabu search for solving the vehicle routing problem,” arXiv, 2024.
• N. I. Saragih, P. Turnip, “Solving vehicle routing problem with considering traffic congestion using tabu search algorithm,” 2024 International Conference on Electrical Engineering and Informatics (ICELTICs), pp. 102–107, 2024.
• A. N. Jasim, L. Chaari Fourati, “Guided genetic algorithm for solving capacitated vehicle routing problem with unmanned-aerial-vehicles,” IEEE Access, pp. 106333–106358, 2024.
• J. Zhu, “Solving capacitated vehicle routing problem by an ımproved genetic algorithm with fuzzy c-means clustering,” Scientific Programming, p. 8514660, 2022.
• N. Mageswari, “Vehicle Routing Problem (VRP) using genetic algorithm,” Vehicle Routing Problem.
• M. Poonpanit, N. Punkong, C. Ratanavilisagul, S. Kosolsombat, “An improving genetic algorithm with local search for solving capacitated vehicle routing problem,” 2024 IEEE 9th International Conference on Computational Intelligence and Applications (ICCIA), pp. 59–63, 2024.
• J. Cai, P. Wang, S. Sun, H. Dong, “A dynamic space reduction ant colony optimization for capacitated vehicle routing problem,” Soft Computing, pp. 8745–8756, 2022.
• Z. H. Ahmed, A. S. Hameed, M. L. Mutar, H. Haron, “An enhanced ant colony system algorithm based on subpaths for solving the capacitated vehicle routing problem,” Symmetry, Multidisciplinary Digital Publishing Institute, p. 2020, 2023.
• M. Suppan, T. Hanne, R. Dornberger, “Ant colony optimization to solve the rescue problem as a vehicle routing problem with hard time windows,” Proceedings of International Joint Conference on Advances in Computational Intelligence, Springer Nature, pp. 53–65, 2022.
• P.-Y. Yin, F. Glover, M. Laguna, J.-X. Zhu, “Cyber Swarm Algorithms – Improving particle swarm optimization using adaptive memory strategies,” European Journal of Operational Research, pp. 377–389, 2010.
• É. D. Taillard, L. M. Gambardella, M. Gendreau, J.-Y. Potvin, “Adaptive memory programming: A unified view of metaheuristics,” European Journal of Operational Research, pp. 1–16, 2001.
• L. Lasdon, A. Duarte, F. Glover, M. Laguna, R. Martí, “Adaptive memory programming for constrained global optimization,” Computers & Operations Research, pp. 1500–1509, 2010.
• N. Peric, S. Begovic, V. Lesic, “Adaptive memory procedure for solving real-world vehicle routing problem,” arXiv, 2024.
• S. Farahmand-Tabar, “Memory-driven metaheuristics: Improving optimization performance,” Handbook of Formal Optimization, Springer Nature, pp. 1–26, 2023.
• A.-R. Hedar, A. E. Abdel-Hakim, W. Deabes, Y. Alotaibi, K. E. Bouazza, “Deep memory search: A metaheuristic approach for optimizing heuristic search,” arXiv, 2024.
• Y. Alotaibi, “A new meta-heuristics data clustering algorithm based on tabu search and adaptive search memory,” Symmetry, Multidisciplinary Digital Publishing Institute, p. 623, 2022.
• M. E. H. Sadati, B. Çatay, “A hybrid variable neighborhood search approach for the multi-depot green vehicle routing problem,” Transportation Research Part E: Logistics and Transportation Review, p. 102293, 2021.
• M. E. Hesam Sadati, B. Çatay, D. Aksen, “An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems,” Computers & Operations Research, p. 105269, 2021.
• C. Chen, E. Demir, Y. Huang, “An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots,” European Journal of Operational Research, pp. 1164–1180, 2021.
• X. Dong, H. Zhang, M. Xu, F. Shen, “Hybrid genetic algorithm with variable neighborhood search for multi-scale multiple bottleneck traveling salesmen problem,” Future Generation Computer Systems, pp. 229–242, 2021.
• K. Sun, D. Zheng, H. Song, Z. Cheng, X. Lang, W. Yuan, J. Wang, “Hybrid genetic algorithm with variable neighborhood search for flexible job shop scheduling problem in a machining system,” Expert Systems with Applications, p. 119359, 2023.
• J. Feng, Y. He, Y. Pan, Z. Zhou, S. Chen, W. Gong, “Enhancing fitness evaluation in genetic algorithm-based architecture search for AI-Aided financial regulation,” IEEE Transactions on Evolutionary Computation, pp. 623–637, 2024.
• O. J. Mengshoel, E. L. Flogard, T. Yu, J. Riege, “Understanding the cost of fitness evaluation for subset selection: Markov chain analysis of stochastic local search,” Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, pp. 251–259, 2022.
• S.-H. Wu, Z.-H. Zhan, J. Zhang, “SAFE: Scale-adaptive fitness evaluation method for expensive optimization problems,” IEEE Transactions on Evolutionary Computation, pp. 478–491, 2021.
• J.-F. Cordeau, M. Gendreau, G. Laporte, “A tabu search heuristic for periodic and multi-depot vehicle routing problems,” Networks, pp. 105–119, 1997.
• S. Mitchell, M. O’Sullivan, I. Dunning, “PuLP: A linear programming toolkit for python,” The University of Auckland, Auckland, New Zealand, pp. 25–37, 2011.
• A. N. Letchford, J.-J. Salazar-González, “The capacitated vehicle routing problem: Stronger bounds in pseudo-polynomial time,” European Journal of Operational Research, pp. 24–31, 2019.