Evaluating Swarm-Genetics for VRPTW: Robustness Across Seeds and Fleet Efficiency On Solomon Benchmarks
DOI:
10.29303/jm.v7i4.10213Published:
2025-12-21Downloads
Abstract
The Vehicle Routing Problem with Time Windows (VRPTW) is a challenging NP-hard problem in logistics optimization. This study evaluates a Swarm-Genetics algorithm, a hybrid method combining Particle Swarm Optimization (PSO) and Genetic Algorithm (GA) with swarm regeneration and adaptive parameter control. The algorithm was tested on 57 Solomon benchmark instances (C, R, RC) under three random seeds to assess robustness. Results show that the algorithm is robust across seeds, producing stable outcomes with minimal variation. It frequently preserves fleet efficiency, often matching the Best Known Solutions (BKS) in vehicle count, particularly for clustered instances. However, routing distances remain less competitive, with average gaps of about 10% for clustered, 12–13% for random, and over 20% for mixed cases. Convergence analysis further indicates rapid early improvements but stagnation in complex distributions. Overall, Swarm-Genetics provides a robust and fleet-efficient framework, though further enhancements are needed to improve distance quality.
Keywords:
VRPTW robustness analysis fleet efficiency swarm-genetics Solomon BenchmarkReferences
Abdelmaguid, T. F., & Dessouky, M. M. (2006). A genetic algorithm approach to the integrated inventory-distribution problem. International Journal of Production Research, 44(21), 4445–4464. https://doi.org/10.1080/00207540600597138
Braekers, K., Ramaekers, K., & Nieuwenhuyse, I. Van. (2015). The Vehicle Routing Problem : State of the Art Classification and Review The Vehicle Routing Problem : State of the Art Classification and Review. COMPUTERS & INDUSTRIAL ENGINEERING. https://doi.org/10.1016/j.cie.2015.12.007
Elshaer, R., & Awad, H. (2020). Computers & Industrial Engineering A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants. Computers & Industrial Engineering, 140(December 2019), 106242. https://doi.org/10.1016/j.cie.2019.106242
Guo, H. nan, Liu, H. tao, & Wu, S. (2022). Simulation, prediction and optimization of typical heavy metals immobilization in swine manure composting by using machine learning models and genetic algorithm. Journal of Environmental Management, 323(September), 116266. https://doi.org/10.1016/j.jenvman.2022.116266
Lahyani, R., Khemakhem, M., & Semet, F. (2014). Rich Vehicle Routing Problems: From a taxonomy to a definition. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. https://doi.org/10.1016/j.ejor.2014.07.048
Li, L., Liu, F., Long, G., Guo, P., & Bie, X. (2016). Modified particle swarm optimization for BMDS interceptor resource planning. Applied Intelligence, 44(3), 471–488. https://doi.org/10.1007/s10489-015-0711-9
Liang, H., Zou, J., Zuo, K., & Khan, M. J. (2020). An improved genetic algorithm optimization fuzzy controller applied to the wellhead back pressure control system. Mechanical Systems and Signal Processing, 142, 106708. https://doi.org/10.1016/j.ymssp.2020.106708
Nguyen, M. H., Le Nguyen, P., Nguyen, K., Le, V. A., Nguyen, T. H., & Ji, Y. (2021). PM2.5 Prediction Using Genetic Algorithm-Based Feature Selection and Encoder-Decoder Model. IEEE Access, 9, 57338–57350. https://doi.org/10.1109/ACCESS.2021.3072280
Ombuki-Berman, B., & Hanshar, F. T. (2009). Using genetic algorithms for multi-depot vehicle routing. Studies in Computational Intelligence, 161, 77–99. https://doi.org/10.1007/978-3-540-85152-3_4
Pisinger, D., & Ropke, S. (2014). Large neighborhood search. September 2010. https://doi.org/10.1007/978-1-4419-1665-5
Ponis, S. T., Rokou, E., Vathis, M., & Ntalla, A. (2015). A hybrid evolutionary algorithm for the solution of the vehicle routing problem ( VRP ). June.
Prodhon, C., & Prins, C. (2016). Metaheuristics for Vehicle Routing Problems. https://doi.org/10.1007/978-3-319-45403-0
Qiao, J., Li, S., Liu, M., Yang, Z., Chen, J., & Liu, P. (2023). OPEN A modified particle swarm optimization algorithm for a vehicle scheduling problem with soft time windows. Scientific Reports, 1–18. https://doi.org/10.1038/s41598-023-45543-z
Savelsbergh, M., & Vigo, D. (2014). Vehicle Routing. January 2007.
Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems With Time Window Constraints. Operations Research, 35(2), 254–265. https://doi.org/10.1287/opre.35.2.254
Xu, K., Shen, L., & Liu, L. (2025). Enhancing column generation by reinforcement learning-based hyper-heuristic for vehicle routing and scheduling problems. Computers and Industrial Engineering, 206. https://doi.org/10.1016/j.cie.2025.111138
Yassen, E. T., Ayob, M., Zakree, M., Nazri, A., & Sabar, N. R. (2017). An Adaptive Hybrid Algorithm for Vehicle Routing Problems with Time Windows. Computers & Industrial Engineering. https://doi.org/10.1016/j.cie.2017.09.034
Yu, Y., Wang, S., Wang, J., & Huang, M. (2019). A branch-and-price algorithm for the heterogeneous fleet green vehicle routing problem with time windows. Transportation Research Part B: Methodological, 122, 511–527. https://doi.org/10.1016/j.trb.2019.03.009
Zhang, B., Xu, L., & Zhang, J. (2020). A multi-objective cellular genetic algorithm for energy-oriented balancing and sequencing problem of mixed-model assembly line. Journal of Cleaner Production, 244. https://doi.org/10.1016/j.jclepro.2019.118845
License
Copyright (c) 2025 Aprizal Resky, Zaitun Zaitun, Dhirga Tandi Teppa
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
