Synergistic design for VRPTW: A competitive swarm optimizer guided by path diversity index and adaptive neighborhood search

i

This article has been updated. A Correction to this article was published on .

i

The Original Article was published on

i

The Original Article was published on

i

This article has been updated

i

This article was retracted on

i

This article has been updated

Abstract

The vehicle routing problem with time windows (VRPTW) is a classical NP-hard combinatorial optimization problem, where NP denotes nondeterministic polynomial time, and it plays a critical role in modern logistics and transportation systems. Although competitive swarm optimization (CSO) algorithms have demonstrated strong performance in continuous optimization, their effective application to discrete combinatorial problems such as VRPTW remains challenging. In this paper, a hybrid competitive swarm optimization and tabu search algorithm (CSO-TS) is proposed to solve the VRPTW. To enhance the search capability of the CSO framework, a tabu search mechanism with an adaptive neighborhood operation strategy is integrated. Moreover, to achieve a better balance between exploration and exploitation, a path diversity index is introduced to quantitatively evaluate solution diversity based on four distinct indices. The proposed CSO-TS algorithm is tested on 56 Solomon benchmark instances and obtains 23 optimal solutions. Extensive computational experiments and comparative analyses demonstrate that CSO-TS outperforms or is competitive with nine state-of-the-art algorithms in terms of solution quality.

Keywords

VRPTW / competitive swarm optimizer / tabu search algorithm / large scale optimization

CHANGE HISTORY

A Correction to this paper has been published:
https://doi.org

The Retraction Note was updated to reflect reception of statements of disagreement from all authors.

This article has been retracted.Please see the Retraction Notice for more detail:
https://doi.org

References

[1] W. Li, Z. Ma, N. Liu, Design of reverse logistics system for B2C e-commerce based on management logic of internet of things, Int. J. Ship. Transport Logist., 13 (2021), 484-497. https://doi.org/10.1504/IJSTL.2021.117274

[2] G. B. Dantzig, J. H. Ramser, The truck dispatching problem, Manage. Sci., 6 (1959), 80-91. https://doi.org/10.1287/mnsc.6.1.80

[3] R. Ojeda, H. Brenner, C. Eduardo, Metaheuristic approaches for the stochastic capacitated multi-depot vehicle routing problem with pickup and delivery, Expert Syst. Appl., 290 (2025), 128258. https://doi.org/j.eswa.2025.128258

[4] H. Y. Jeong, B. D. Song, Optimizing urban logistics: Vehicle routing problem with underground transportation, IEEE Trans. Intell. Transp. Syst., 26 (2025), 6393-6413. https://doi.org/10.1109/TITS.2025.3533477

[5] C. Hua, Solving the problem of vehicle routing problem with time window via dual adaptive genetic algorithm, IEEE Access, 13 (2025), 96535-96543. https://doi.org/10.1109/ACCESS.2025.3575459

[6] R. Baldacci, A. Mingozzi, R. Roberti, Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints, Eur. J. Oper. Res., 218 (2012), 1-6. https://doi.org/10.1016/j.ejor.2011.07.037

[7] B. Kallehauge, Formulations and exact algorithms for the vehicle routing problem with time windows, Comput. Oper. Res., 35 (2008), 2307-2330. https://doi.org/10.1016/j.cor.2006.11.006

[8] C. Yang, X. Ning, D. Yu, H. Sun, G. Kang, H. Wang, A divide-and-conquer strategy for integer programming problems, Electron. Res. Arch., 33 (2025), 3950-3967. httpss://doi.org/10.3934/era.2025175

[9] M. Alinaghian, E. B. Tirkolaee, An augmented Tabu search algorithm for the green inventory-routing problem with time windows, Swarm Evol. Comput., 60 (2021), 100802. https://doi.org/10.1016/j.swevo.2020.100802

[10] B. Yu, Z. Z. Yang, B. Z. Yao, A hybrid algorithm for vehicle routing problem with time windows, Expert Syst. Appl., 38 (2011), 435-441. https://doi.org/10.1016/j.eswa.2010.06.082

[11] Y. J. Gong, J. Zhang, O. Liu, R. Z. Huang, H. S. H. Chung, Optimizing the vehicle routing problem with time windows: A discrete particle swarm optimization approach, IEEE Trans. Syst. Man Cybern. Part C Appl. Rev., 42 (2012), 254-267. https://doi.org/10.1109/TSMCC.2011.2148712

[12] T. S. Khoo, B. B. Mohammad, A two-phase distributed ruin-and-recreate genetic algorithm for solving the vehicle routing problem with time windows, IEEE Access, 8 (2020), 169851-169871. https://doi.org/10.1109/ACCESS.2020.3023741

[13] Y. Zou, P. Xu, H. Dai, Swarm optimization with intra- and inter-hierarchical competition for large-scale berth allocation and crane assignment, IEEE Trans. Emerging Top. Comput. Intell., 9 (2025), 1307-1321. https://doi.org/10.1109/TETCI.2025.3529876

[14] Q. Yang, W. N. Chen, J. D. Deng, A level-based learning swarm optimizer for large-scale optimization, IEEE Trans. Evol. Comput., 22 (2018), 578-594. https://doi.org/10.1109/TEVC.2017.2743016

[15] Q. Yang, W. N. Chen, T. Gu, Segment-based predominant learning swarm optimizer for large-scale optimization, IEEE Trans. Cybern., 47 (2017), 2896-2910. https://doi.org/10.1109/TCYB.2016.2616170

[16] N. Zeng, Z. Wang, W. Liu, H. Zhang, K. Hone, X. Liu, A dynamic neighborhood-based switching particle swarm optimization algorithm, IEEE Trans. Cybern., 52 (2022), 9290-9301. https://doi.org/10.1109/TCYB.2020.3029748

[17] B. Yu, Z. Z. Yang, B. Z. Yao, A hybrid algorithm for vehicle routing problem with time windows, Expert Syst. Appl., 38 (2011), 435-441. https://doi.org/10.1016/j.eswa.2010.06.082

[18] Y. Wang, L. Wang, Z. P. Peng, A multi ant system based hybrid heuristic algorithm for vehicle routing problem with service time customization, Swarm Evol. Comput., 50 (2019), 100563. https://doi.org/10.1016/j.swevo.2019.100563

[19] A. Gupta, S. Saini, An enhanced ant colony optimization algorithm for vehicle routing problem with time windows, in 2017 Ninth International Conference on Advanced Computing (ICoAC), Chennai, India, (2017), 267-274. https://doi.org/10.1109/ICoAC.2017.8441175

[20] H. Z. Zhang, L. Ma, Z. Y. Zhang, Y. Liu, A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows, Inf. Sci., 490 (2019), 166-190. https://doi.org/10.1016/j.ins.2019.03.070

[21] W. Q. Zhang, D. J. Yang, G. H. Zhang, M. Gen, Hybrid multiobjective evolutionary algorithm with fast sampling strategy-based global search and route sequence difference-based local search for VRPTW, Expert Syst. Appl., 145 (2020), 113151. https://doi.org/10.1016/j.eswa.2019.113151

[22] S. Reong, H. M. Wee, Y. L. Hsiao, 20 years of particle swarm optimization strategies for the vehicle routing problem: a bibliometric analysis, Mathematics, 10 (2022), 3669. https://doi.org/10.3390/math10193669

[23] P. Saksuriya, C. Likasiri, Hybrid heuristic for vehicle routing problem with time windows and compatibility constraints in home healthcare system, Appl. Sci., 12 (2020), 6486. https://doi.org/10.3390/app12136486

[24] M. S. Sarbijan, J. Behnamian, Real-time collaborative feeder vehicle routing problem with flexible time windows, Swarm Evol. Comput., 75 (2022), 101201. https://doi.org/10.1016/j.swevo.2022.101201

[25] N. Ding, J. Yang, Z. Han, J. Hao, Electric-vehicle routing planning based on the law of electric energy consumption, Mathematics, 10 (2022), 3099. https://doi.org/10.3390/math10173099

[26] R. Liu, Z. B. Jiang, A hybrid large-neighborhood search algorithm for the cumulative capacitated vehicle routing problem with time-window constraints, Appl. Soft Comput., 80 (2019), 18-30. https://doi.org/10.1016/j.asoc.2019.03.008

[27] P. G. Luan, N. T. Thinh, Hybrid genetic algorithm based smooth global-path planning for a mobile robot, Mech. Based Des. Struct. Mach., 51 (2023), 1758-1774. https://doi.org/10.1080/15397734.2021.1876569

[28] D. B. Blumenthal, N. Boria, J. Gamper, S. Bougleux, L. Brun, Comparing heuristics for graph edit distance computation, VLDB J., 29 (2020), 419-458. https://doi.org/10.1007/s00778-019-00544-1

[29] P. Z. Du, N. Liu, H. F. Zhang, J. F. Lu, An improved ant colony optimization based on an adaptive heuristic factor for the traveling salesman problem, J. Adv. Transp., 2021 (2021), 6642009. httpss://doi.org/10.1155/2021/6642009

[30] Z. H. Luo, L. Li, M. X. Zhang, Diversified top-k route planning in road network, Proc. VLDB Endow., 15 (2022), 3199-3212. https://doi.org/10.14778/3551793.3551863

[31] J. Kennedy, Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance, in Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), Washington, DC, USA, 3 (1999), 1931-1938. https://doi.org/10.1109/CEC.1999.785509

[32] Q. C. Wu, X. W. Xia, A neighborhood comprehensive learning particle swarm optimization for the vehicle routing problem with time windows, Swarm Evol. Comput., 84 (2024), 101425. https://doi.org/10.1016/j.swevo.2023.101425

[33] J. N. Liu, L. Tong, X. W. Xia, A genetic algorithm for vehicle routing problems with time windows based on cluster of geographic positions and time windows, Appl. Soft Comput., 169 (2025), 112593. https://doi.org/10.1016/j.asoc.2024.112593

[34] M. M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper. Res., 35 (1987), 254-265. https://doi.org/10.1287/opre.35.2.254

[35] G. D. Konstantakopoulos, S. P. Gayialis, E. P. Kechagias, A multiobjective large neighborhood search metaheuristic for the vehicle routing problem with time windows, Algorithms, 13 (2020), 243. https://doi.org/10.3390/a13100243

[36] D. F. Zhang, S. F. Cai, F. R. Ye, Y. W. Si, T. T. Nguyen, A hybrid algorithm for a vehicle routing problem with realistic constraints, Inf. Sci., 394-395 (2017), 167-182. https://doi.org/10.1016/j.ins.2017.02.028

[37] T. S. Khoo, B. B. Mohammad, The parallelization of a two-phase distributed hybrid ruin-and-recreate genetic algorithm for solving multi-objective vehicle routing problem with time windows, Expert Syst. Appl., 168 (2021), 114408. https://doi.org/10.1016/j.eswa.2020.114408

[38] Y. Shen, M. Liu, J. Yang, Y. Shi, M. Middendorf, A hybrid swarm intelligence algorithm for vehicle routing problem with time windows, IEEE Access, 8 (2020), 93882-93893. https://doi.org/10.1109/ACCESS.2020.2984660

[39] Y. L. Lan, F. Liu, W. W. Y. Ng, Decomposition based multi-objective variable neighborhood descent algorithm for logistics dispatching, IEEE Trans. Emerging Top. Comput. Intell., 5 (2021), 826-839. https://doi.org/10.1109/TETCI.2020.3002228

[40] Z. X. He, K. Zhou, H. Shu, X. Chen, X. Y. Lyu, Multi-objective algorithm based on tissue P system for solving tri-objective optimization problems, Evol. Intell., 16 (2023), 1-16. https://doi.org/10.1007/s12065-021-00658-y

[41] W. B. Dong, K. Zhou, H. Q. Qi, A tissue P system based evolutionary algorithm for multi-objective VRPTW, Swarm Evol. Comput., 39 (2018), 310-322. https://doi.org/10.1016/j.swevo.2017.11.001

[42] Y. Rochat, E. D. Taillard, Probabilistic diversification and intensification in local search for vehicle routing, J. Heuristics, 1 (1995), 147-167. https://doi.org/10.1007/BF02430370

[43] K. C. Tan, Y. H. Chew, L. H. Lee, A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows, Comput. Optim. Appl., 34 (2006), 115-151. https://doi.org/10.1007/s10589-005-3070-3

[44] H. B. Li, A. Lim, Local search with annealing-like restarts to solve the VRPTW, Eur. J. Oper. Res., 150 (2003), 115-127. https://doi.org/10.1016/S0377-2217(02)00486-1

[45] D. Mester, An evolutionary strategies algorithm for large scale vehicle routing problem with capacitate and time windows restrictions, in Proceedings of the Conference on Mathematical and Population Genetics, University of Haifa, Israel, 2002.

[46] P. Shaw, A new local search algorithm providing high quality solutions to vehicle routing problems, in APES Group, Dept of Computer Science, University of Strathclyde, Glasgow, Scotland, UK, 46 (1997).

[47] J. Berger, M. Barkaoui, O. Bräysy, A route-directed hybrid genetic approach for the vehicle routing problem with time windows, INFOR: Inf. Syst. Oper. Res., 41 (2003), 179-194. https://doi.org/10.1080/03155986.2003.11732675

[48] J. Homberger, H. Gehring, Two evolutionary metaheuristics for the vehicle routing problem with time windows, INFOR: Inf. Syst. Oper. Res., 37 (1999), 297-318. https://doi.org/10.1080/03155986.1999.11732386

[49] L. M. Rousseau, M. Gendreau, G. Pesant, Using constraint-based operators to solve the vehicle routing problem with time windows, J. Heuristics, 1 (2002), 43-58. https://doi.org/10.1023/A:1013661617536

[50] L. M. Gambardella, É. Taillard, G Agazzi, MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows, Istituto Dalle Molle Di Studi Sull Intelligenza Artificiale, 1999.

[51] R. Bent, H. V. Hentenryck, A two-stage hybrid local search for the vehicle routing problem with time windows, Transp. Sci., 38 (2004), 515-530. https://doi.org/10.1287/trsc.1030.0049

[52] G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt, Record breaking optimization results using the ruin and recreate principle, J. Comput. Phys., 159 (2000), 139-171. https://doi.org/10.1006/jcph.1999.6413

[53] A. L. Bouthillier, T. G. Crainic, A cooperative parallel meta-heuristic for the vehicle routing problem with time windows, Comput. Oper. Res., 32 (2005), 1685-1708. https://doi.org/10.1016/j.cor.2003.11.023

[54] J. Homberger, Eine verteilt-parallele Metaheuristik, in Verteilt-parallele Metaheuristiken zur Touren-planung: Lösungsverfahren für das Standardproblem mit Zeitfensterrestriktionen, (2000), 139-165. https://doi.org/10.1007/978-3-322-97815-84

[55] K. Ghoseiri, S. F. Ghannadpour, Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm, Appl. Soft Comput., 10 (2010), 1096-1107. https://doi.org/10.1016/j.asoc.2010.04.001

[56] Z. Fu, R. Eglese, L. Y. O. Li, A unified tabu search algorithm for vehicle routing problems with soft time windows, J. Oper. Res. Soc., 59 (2008), 663-673. https://doi.org/10.1057/palgrave.jors.2602371

[57] Z. J. Czech, P. Czarnas, Parallel simulated annealing for the vehicle routing problem with time windows, in Proceedings 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, 19 (2002), 376-383. https://doi.org/10.1109/EMPDP.2002.994313

[58] T. Ibaraki, S. Imahori, M. Kubo, T. Masuda, T. Uno, M. Yagiura, Effective local search algorithms for routing and scheduling problems with general time-window constraints, Transp. Sci., 39 (2005), 206-232. https://doi.org/10.1287/trsc.1030.0085

[59] Y. Shen, M. Liu, J. Yang, A hybrid swarm intelligence algorithm for vehicle routing problem with time windows, IEEE Access, 8 (2020), 93882-93893. https://doi.org/10.1109/ACCESS.2020.2984660