A Hybrid Approach for Solving the Capacitated Vehicle Routing Problem

Abstract

Industrial transportation problems, such as the distribution of petroleum products, industrial gases, merchandise, and waste management, are critical challenges in operations research. These issues often involve high costs and complex logistics, making efficient solutions essential for businesses. The routing problem, a well-known optimization challenge, focuses on minimizing transportation costs while satisfying vehicle capacity. In this research, we propose an innovative approach Hybrid Artificial Bee Colony (HABC), which combines the Artificial Bee Colony (ABC) algorithm with the Genetic Algorithm (GA). The ABC algorithm is recognized for its rapid convergence, whereas GA is effective at diversifying the search space through genetic operators such as crossover and mutation. By integrating these two metaheuristics, HABC aims to exploit their complementary strengths, thereby improving both solution quality and computational performance. In addition, we introduce a heuristic for random population initialization, which ensure a balance between quality and diversity in the initial solutions. This strategy helps avoid premature convergence and explores a broader solution space. Simulation results demonstrate that HABC achieves significant improvement in solution quality, outperforming existing methods in several instances of the CVRP. This approach not only reduces trans-portation costs but also offers a scalable and efficient framework for solving complex industrial logistics problems. By optimizing routes and resource allocation, HABC contributes to more sustainable and cost-effective operations, offering tangible benefits to industries that depend on reliable transportation systems. The proposed method underscores the potential of hybrid AI techniques in addressing real-world operational challenges.

Keywords

• Artificial Intelligence
• Genetic operators
• Random initialization
• Transport

References

1. [1] Christopher PM. Logistics and Supply Chain Management. FT Publishing International; 2016. https://doi.org/10.1057/9781137541253_6
2. [2] Fender M, Pimor Y. Logistique & Supply chain. Dunod paris; 2016. https://doi.org/10.3917/ems.lavas.2016.01.0305
3. [3] Ma Z, Wu G, Suganthan PN, Song A, Luo Q. Performance assessment and exhaustive listing of 500+ nature-inspired metaheuristic algorithms. Swarm and Evolutionary Computation. 2023; 77: 101-248. http://dx.doi.org/10.1016/j.swevo.2023.101248
4. [4] Karaboga D, Basturk B. Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems. Foundations of Fuzzy Logic and Soft Computing; 2007; Cancun, Mexico. https://doi.org/10.1007/978-3-540-72950-1_77
5. [5] Karaboga D, Akay B. A comparative study of Artificial Bee Colony algorithm, Applied Mathematics and Computation. 2009; 214(1):108–132. http://dx.doi.org/10.1016/j.amc.2009.03.090
6. [6] Karaboga N. A new design method based on artificial bee colony algorithm for digital IIR filters. Journal of the Franklin Institute. 2009; 346(4):328–348. http://dx.doi.org/10.1016/j.jfranklin.2008.11.003
7. [7] Dokeroglu T, Sevinc E, Cosar A. Artificial bee colony optimization for the quadratic assignment problem. Applied Soft Comp Computing. 2019; 76:595–606 http://dx.doi.org/10.1016/j.asoc.2019.01.001
8. [8] Gao W, Liu S. Improved artificial bee colony algorithm for global optimization. Information Processing Letters. 2011; 111(17): 871–882. http://dx.doi.org/10.1016/j.ipl.2011.06.002

9. [9] Muriyatmoko D, Djunaidy A, Muklason A. Heuristics and Metaheuristics for Solving Capacitated Vehicle Routing Problem: An Algorithm Comparison. Procedia Computer Science. 2024; 234:494:501. https://doi.org/10.1016/j.procs.2024.03.032
10. [10] Berger J, Barkaoui M. A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Computers and Operations Research. 2004; 31:2037–2053. http://dx.doi.org/10.1016/S0305-0548(03)00163-1
11. [11] Mohammed MA, Abd Ghani MK, Hamed RI, Mostafa SA, Ahmad MS, Ibrahim DA. Solving vehicle routing problem by using mp roved genetic algorithm for optimal solution. Journal of Computational Science. 2017; 21:255–262. http://dx.doi.org/ 10.1016/j.jocs.2017.04.003
12. [12] Shekhar S., Xiong H., Zhou X. Vehicle Routing Problem, in Encyclopedia of GIS. Springer International Publishing; 2017. http://dx.doi.org/10.1007/978-3-319-17885-1_1147
13. [13] Altabeeb AM, Mohsen AM, Ghallab A. An improved hybrid firefly algorithm for capacitated vehicle routing problem. Applied Soft Computing. 2019; 84(c):105728. http://dx.doi.org/10.1016/j.asoc.2019.105728
14. [14] Nayyar A, Le DN, Nguyen NG. Advances in Swarm Intelligence for Optimizing Problems in Computer Science. Chapman and Hall/CRC; 2018. https://doi.org/10.1201/9780429445927
15. [15] Buontempo F. Genetic Algorithms and Machine Learning for Programmers: Create AI Models and Evolve Solutions. Pragmatic Bookshelf; 2019.  978‑1680506204
16. [16] Zhang JL, Zhao YW, Peng DJ, Wang WL. A Hybrid Quantum-Inspired Evolutionary Algorithm for Capacitated Vehicle Routing Problem. Fourth International Conference on Intelligent Computing. 2008; Shanghai, China. https://doi.org/10.1007/978-3-540-87442-3_5
17. [17] Yu B., Yang ZZ, Yao B. An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research. 2009; 196(1):71–176. https://doi.org/10.1016/j.ejor.2008.02.028
18. [18] Zhao Y, Leng L, Qian Z, Wang W. A Discrete Hybrid Invasive Weed Optimization Algorithm for the Capacitated Vehicle Routing Problem. Procedia Computer Science. 2016;91: 978–987. https://doi.org/10.1016/j.procs.2016.07.127
19. [19] Goel R, Maini R. A hybrid of ant colony and firefly algorithms (HAFA) for solving vehicle routing problems. Journal of Computational Science. 2018; 25:28–37. https://doi.org/10.1016/j.jocs.2017.12.012
20. [20] Thammano A, Rungwachira P. Hybrid modified ant system with sweep algorithm and path relinking for the capacitated vehicle routing problem. Heliyon. 2021;7(9):08029. https://doi.org/10.1016/j.heliyon.2021.e08029
21. [21] Dalbah LM, Al-Betar MA, Awadallah MA, Zitar RA. A modified coronavirus herd immunity optimizer for capacitated vehicle routing problem. Journal of King Saud University - Computer and Information Sciences. 2022;34(8):4782–4795. https://doi.org/ 10.1016/j.jksuci.2021.06.013
22. [22] Kalatzantonakis P, Sifaleras A, Samaras N. A reinforcement learning-Variable neighborhood search method for the capacitated Vehicle Routing Problem. Expert Systems with Applications. 2023; 213:118812. https://doi.org/10.1016/j.eswa.2022.118812
23. [23] Souza IP, Boeres MCS, Moraes REN. A robust algorithm based on Differential Evolution with local search for the Capacitated Vehicle Routing Problem. Swarm and Evolutionary Computation. 2023; 77:101245. https://doi.org/10.1016/j.swevo.2023.101245
24. [24] Tiwari KV, Sharma SK. An optimization model for vehicle routing problem in last-mile delivery. Expert Systems with Applications. 2023:222(c):19789. https://doi.org/10.1016/j.eswa.2023.119789
25. [25] Zhang X, Geng K, Li Y. Hybrid Artificial Bee Colony Algorithm with Variable Neighborhood Search for Capacitated Vehicle Routing Problem. Journal of Electrical Systems. 2024;20(2): 584-597. https://doi.org/10.52783/jes.1213
26. [26] Di JYL. Adaptive Hybrid Ant Colony Optimization for Capacitated Vehicle Routing Problem. Journal of Northeastern University (Natural Science). 2024;44(12):1686. https://doi.org/10.12068/j.issn.1005-3026.2023.12.003
27. [27] Elshaer R, Awad H. A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants. Computers & Industrial Engineering. 2020; 140:106242. http://dx.doi: 10.1016/j.cie.2019.106242
28. [28] Boğar E, Beyhan S, A hybrid genetic algorithm for mobile robot shortest path problem. International Journal of Intelligent Systems and Applications in Engineering. 2016; 4(1): 264–267. http://dx.doi: 10.18201/ijisae.2016si12473
29. [29] Altabeeb AM, Mohsen AM. Abualigah L, Ghallab A. Solving capacitated vehicle routing problem using cooperative firefly algorithm. Applied Soft Computing. 2021; 108:107403. http://dx.doi: 10.1016/j.asoc.2021.107403
30. [30] Tan SY and Yeh WC. The vehicle routing problem: State-of-the-art classification and review. Applied Sciences. 2021; 11(21):10295. http://dx.doi: 10.3390/app112110295
31. [31] Djebbar AM, Djebbar B. A hybrid discrete artificial bee colony for the green pickup and delivery problem with time windows. Informatica. 2020; 44(4):507-519. http://dx.doi.org/10.31449/inf.v44i4.3000
32. [32] Sadati MEH, Çatay B. A hybrid variable neighborhood search approach for the multi-depot green vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review. 2021;149:102293. http://dx.doi.org/10.1016/j.tre.2021.102293
33. [33] Wen M, Sun W, Yu Y, Tang J, Ikou K. An adaptive large neighborhood search for the larger-scale multi depot green vehicle routing problem with time windows. Journal of Cleaner Production. 2022;374:133916.http://dx.doi.org/10.1016/j.jclepro.2022.133916
34. [34] Pham DT, Ghanbarzadeh A, Koç E, Otri S, Rahim S, Zaidi M. The Bees Algorithm — A Novel Tool for Complex Optimisation Problems. Elsevier Science & Technology; 2006. http://dx.doi.org/10.1016//B978-008045157-2/50081-X
35. [35] Yang XS. Engineering Optimizations via Nature-Inspired Virtual Bee Algorithms. Artificial Intelligence and Knowledge Engineering Applications: A Bioinspired Approach.2005; Canary Islands, Spain. http://dx.doi.org/10.1007/11499305_33
36. [36] Huo J, L. Liu L. An Improved Multi-Objective Artificial Bee Colony Optimization Algorithm with Regulation Operators. Information. 2017;8(1):1-21. http://dx.doi.org/10.3390/info8010018
37. [37] Panniem A, Puphasuk P. A Modified Artificial Bee Colony Algorithm with Firefly Algorithm Strategy for Continuous Optimization Problems. Journal of Applied Mathematics. 2018; 2018:1-9. https://dx.doi.org/10.1155/2018/1237823
38. [38] Li G, Sun M, Li P. Quantum-Inspired Bee Colony Algorithm. Open Journal of Optimization. 2015; 04:51–60. https://dx.doi.org/10.4236/ojop.2015.43007
39. [39] Xin Z, Chen G. Artificial Bee Colony Algorithm Based on Adaptive Cauchy Mutation. DEStech Transactions on Engineering and Technology Research. 2016;0:16. https://dx.doi.org/10.12783/dtetr/iect2016/3727
40. [40] Drezner Z, Drezner TD. Biologically Inspired Parent Selection in Genetic Algorithms. Ann Oper Res. 2020;287(1):161–183. https://dx.doi.org/10.1007/s10479-019-03343-7
41. [41] Krishnanand KR, Nayak SK, Panigrahi BK, Rout PK. Comparative study of five bio-inspired evolutionary optimization techniques. World Congress on Nature & Biologically Inspired Computing (NaBIC). 2009; Coimbatore, India. https://dx.doi.org/10.1109/NABIC.2009.5393750
42. [42] Sahli A, Behiri W, Belmokhtar B, Chu C. An effective and robust genetic algorithm for urban freight transport scheduling using passenger rail network. Computers & Industrial Engineering. 2022; 173:108645. https://dx.doi.org/10.1016/j.cie.2022.108645
43. [43] Reddy MJ, Kumar N. Computational algorithms inspired by biological processes and evolution. Current Science. 2013;103 (4):1–11. https://repository.ias.ac.in/126221
44. [44] Karakatič S, Podgorelec V. A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing. 2015; 27:519–532. https://dx.doi.org/10.1016/j.asoc.2014.11.005
45. [45] Bye R, Gribbestad M, Chandra R, Osen O. A Comparison of GA Crossover and Mutation Methods for the Traveling Salesman Problem. Advances in Intelligent Systems and Computing. 2021;529–542. https://dx.doi.org/10.1007/978-981-15-6067-5_60 [46] Holland JH. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. The MIT Press; 1992. https://dx.doi.org/10.7551/mitpress/1090.001.0001
46. [47] Brindle A. Genetic algorithms for function optimization [PhD dissertation]. University of Alberta, Edmonton; 1980. https://dx.doi.org/10.7939/R3FB4WS2W
47. [48] Augerat P., Belenguer J.M., Benavent E., Corberán A., Naddef D. & Rinaldi G. Computational results with a branch and cut code for the capacitated vehicle routing problem. Institute of Systems Analysis and Computer Science, National Research Council. 1995; Roma, Italy.
48. [49] Wang Z, Li J, Zhou M, Fan J. Research in capacitated vehicle routing problem based on modified hybrid particle swarm optimization. IEEE International Conference on Intelligent Computing and Intelligent Systems. 2009; New Jersey, United States. https://dx.doi.org/10.1109/ICICISYS.2009.5358182
49. [50] Pham VHS, Dang NTN, Nguyen VN. Advanced vehicle routing in cement distribution: a discrete Salp Swarm Algorithm approach. International Journal of Management Science and Engineering Management. 2025;1(1):1–13. https://dx.doi.org/10.1080/17509653.2024.2324172