A Heuristic Enhancing Artificial Immune System for Three-dimensional Loading Capacitated Vehicle Routing Problem
DOI:
https://doi.org/10.37385/jaets.v6i2.6295Keywords:
Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP), Artificial Immune System, Firefly Algorithm, Metaheuristics, Bring-i-to-j Heuristic, Optimization AlgorithmsAbstract
This study addresses the Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP), a highly complex NP-hard problem that combines vehicle routing with spatially constrained three-dimensional bin packing. To tackle this challenge, we propose an enhanced Artificial Immune System (En-AIS) that integrates a novel local search heuristic called “Bring-i-to-j,” designed to improve routing feasibility and loading efficiency. The En-AIS algorithm is further refined through rigorous parameter tuning using a full factorial design and ANOVA analysis. Comparative experiments were conducted against conventional AIS and the Firefly Algorithm (FA) across 27 benchmark instances. Results demonstrate that En-AIS consistently outperforms both baseline methods in terms of solution quality, achieving an average improvement of 15–20% while maintaining competitive computational times. These findings highlight the algorithm’s robustness and its practical potential for application in logistics and supply chain optimization tasks involving joint routing and loading decisions.
Downloads
References
Altabeeb, A. M., Mohsen, A. M., Abualigah, L., & Ghallab, A. (2021). Solving capacitated vehicle routing problem using cooperative firefly algorithm. Applied Soft Computing, 108, 107403. https://doi.org/https://doi.org/10.1016/j.asoc.2021.107403
Altabeeb, A. M., Mohsen, A. M., & Ghallab, A. (2019). An improved hybrid firefly algorithm for capacitated vehicle routing problem. Applied Soft Computing, 84, 105728. https://doi.org/https://doi.org/10.1016/j.asoc.2019.105728
Aytug, H., Knouja, M., & Vergara, F. E. (2003). Use of genetic algorithms to solve production and operations management problems: a review. International Journal of Production Research, 41(17), 3955–4009. http://zerlina.ingentaselect.com/vl=776754/cl=41/nw=1/fm=docpdf/rpsv/cw/tandf/00207543/v41n17/s1/p3955
Bortfeldt, A. (2012). A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. Computers & Operations Research, 39(9), 2248-2257. https://doi.org/10.1016/j.cor.2011.11.008
Burnet, F. M. (1959). The clonal selection theory of acquired Immunity. Cambridge University Press.
Chen, C. S., Lee, S. M., & Shen, Q. S. (1995). An analytical model for the container loading problem. European Journal of Operational Research, 80(1), 68-76. https://doi.org/10.1016/0377-2217(94)00002-t
Chen, M., Huo, J., & Duan, Y. (2023). A hybrid biogeography-based optimization algorithm for three-dimensional bin size designing and packing problem. Computers & Industrial Engineering, 180, 109239. https://doi.org/https://doi.org/10.1016/j.cie.2023.109239
Chi, J., He, S., & Song, R. (2025). Solving capacitated vehicle routing problem with three-dimensional loading and relocation constraints. Computers & Operations Research, 173, 106864. https://doi.org/https://doi.org/10.1016/j.cor.2024.106864
Christensen, S. G., & Rousøe, D. M. (2009). Container loading with multi-drop constraints. International Transactions in Operational Research, 16(6), 727-743. https://doi.org/10.1111/j.1475-3995.2009.00714.x
Dasgupta, D. (2006). Advance in artificial immune systems. IEEE computational intelligence magazine, 1(4), 40-49.
Doerner, K., Fuellerer, G., Hartl, R., Gronalt, M., & Iori, M. (2007). Metaheuristics for the vehicle routing problem with loading constraints. Networks, 49, 294-307. https://doi.org/10.1002/net.20179
Engin, O., & Doyen, A. (2004a). Artificial immune systems and applications in industrial problems. G. U. Journal of Science, 17(1), 71-84.
Engin, O., & Doyen, A. (2004b). A new approach to solve hybrid flow shop scheduling problems by artificial immune system. Future Generation Computer Systems, 20(6), 1083-1095. http://www.sciencedirect.com/science/article/B6V06-4CT62DH-1/2/765bb875fea11e60b8b71a7fac507c7d
Ferreira, K. M., de Queiroz, T. A., Munari, P., & Toledo, F. M. B. (2024). A variable neighborhood search for the green vehicle routing problem with two-dimensional loading constraints and split delivery. European Journal of Operational Research, 316(2), 597-616. https://doi.org/https://doi.org/10.1016/j.ejor.2024.01.049
Freitas, A., & Timmis, J. (2003). Revisiting the foundations of artificial immune systems: A problem-oriented perspective. In J. Timmis, P. J. Bentley, & E. Hart (Eds.), Lecture Notes in Computer Science (Vol. 2787, pp. 229-241). Springer.
Fuellerer, G., Doerner, K. F., Hartl, R. F., & Iori, M. (2010). Metaheuristics for vehicle routing problems with three-dimensional loading constraints. European Journal of Operational Research, 201(3), 751-759. https://doi.org/10.1016/j.ejor.2009.03.046
Garrett, S. M. (2005). How do we evaluate artificial immune systems? Evol Comput, 13(2), 145-177. https://doi.org/10.1162/1063656054088512
Gendreau, M., Iori, M., Laporte, G., & Martello, S. (2006). A Tabu Search Algorithm for a Routing and Container Loading Problem. Transportation Science, 40(3), 342-350. https://doi.org/10.1287/trsc.1050.0145
Gimenez-Palacios, I., Alonso, M. T., Alvarez-Valdes, R., & Parreño, F. (2023). Multi-container loading problems with multidrop and split delivery conditions. Computers & Industrial Engineering, 175, 108844. https://doi.org/https://doi.org/10.1016/j.cie.2022.108844
Hart, E., & Timmis, J. (2008). Application areas of AIS: The past, the present and the future. Applied Soft Computing, 8(1), 191-201. http://www.sciencedirect.com/science/article/B6W86-4N1T1KX-2/2/9c970acc97e5f21f3167ce10f7fff74f
Jaradat, M. A. K., & Langari, R. (2009). A hybrid intelligent system for fault detection and sensor fusion. Applied Soft Computing, 9(1), 415-422. http://www.sciencedirect.com/science/article/B6W86-4SJ2WR9-1/2/f4c842db7bc71cb35de51854d5fd8853
Küçük, M., & Topaloglu Yildiz, S. (2022). Constraint programming-based solution approaches for three-dimensional loading capacitated vehicle routing problems. Computers & Industrial Engineering, 171, 108505. https://doi.org/https://doi.org/10.1016/j.cie.2022.108505
Leloup, E., Paquay, C., Pironet, T., & Oliveira, J. F. (2025). A three-phase algorithm for the three-dimensional loading vehicle routing problem with split pickups and time windows. European Journal of Operational Research, 323(1), 45-61. https://doi.org/https://doi.org/10.1016/j.ejor.2024.12.005
Meliani, Y., Hani, Y., Lissane Elhaq, S., & El Mhamedi, A. (2022). A tabu search based approach for the Heterogeneous Fleet Vehicle Routing Problem with three-dimensional loading constraints. Applied Soft Computing, 126, 109239. https://doi.org/10.1016/j.asoc.2022.109239
Placek, M. (2023). Logistics industry worldwide - statistics & facts. Retrieved 19 December from https://www.statista.com/topics/5691/logistics-industry-worldwide/
Qi, R., Li, J.-q., & Liu, X.-f. (2023). A knowledge-driven multiobjective optimization algorithm for the transportation of assembled prefabricated components with multi-frequency visits. Automation in Construction, 152, 104944. https://doi.org/https://doi.org/10.1016/j.autcon.2023.104944
Sinha, A., & Goldberg, D. (2003). A survey of hybrid genetic and evolutionary algorithms. ILLIGAL Technical Report 2003004. https://doi.org/citeulike-article-id:1460878
Timmis, J. (2007). Artificial Immune Systems - today and tomorrow. Natural Computing, 6, 1-18.
Toth, P., & Vigo, D. (2002). Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics, 123(1), 487-512. https://doi.org/https://doi.org/10.1016/S0166-218X(01)00351-1
Trachanatzi, D., Rigakis, M., Marinaki, M., & Marinakis, Y. (2020). A firefly algorithm for the environmental prize-collecting vehicle routing problem. Swarm and Evolutionary Computation, 57, 100712. https://doi.org/https://doi.org/10.1016/j.swevo.2020.100712
Wang, Y., Wei, Y., Wang, X., Wang, Z., & Wang, H. (2023). A clustering-based extended genetic algorithm for the multidepot vehicle routing problem with time windows and three-dimensional loading constraints. Applied Soft Computing, 133, 109922. https://doi.org/https://doi.org/10.1016/j.asoc.2022.109922
Wang, Y., Wei, Y., Wei, Y., Zhen, L., & Deng, S. (2025). Collaborative multidepot split delivery network design with three-dimensional loading constraints. Transportation Research Part E: Logistics and Transportation Review, 196, 104032. https://doi.org/https://doi.org/10.1016/j.tre.2025.104032
Yang, X.-S. (2008). Nature-inspired metaheuristic algorithms. Luniver press.
Yang, X.-S. (2009). Firefly Algorithms for Multimodal Optimization. Stochastic Algorithms: Foundations and Applications, Berlin, Heidelberg.
CITEDNESS IN SCOPUS
CITEDNESS IN WOS
