A Hybrid Approach for Solving the Capacitated Vehicle Routing Problem

Year 2025, Volume: 9 Issue: 2, 249 - 258, 30.06.2025

Amel Mounia Djebbar , Kemmar Amina

https://doi.org/10.30939/ijastech..1663305

Cited By: 1

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] Christopher PM. Logistics and Supply Chain Management. FT Publishing International; 2016. https://doi.org/10.1057/9781137541253_6
• [2] Fender M, Pimor Y. Logistique & Supply chain. Dunod paris; 2016. https://doi.org/10.3917/ems.lavas.2016.01.0305
• [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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] Buontempo F. Genetic Algorithms and Machine Learning for Programmers: Create AI Models and Evolve Solutions. Pragmatic Bookshelf; 2019.  978‑1680506204
• [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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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
• [47] Brindle A. Genetic algorithms for function optimization [PhD dissertation]. University of Alberta, Edmonton; 1980. https://dx.doi.org/10.7939/R3FB4WS2W
• [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.
• [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
• [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