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

Fei Liang; Fei Yu; Hongrun Wu; Songbin Lan; Yingpin Chen; Xuewen Xia; Fei Liang; Fei Yu; Hongrun Wu; Songbin Lan; Yingpin Chen; Xuewen Xia

doi:10.3934/era.2026116

Electronic Research Archive

2026, Volume 34, Issue 4: 2511-2538. doi: 10.3934/era.2026116

Previous Article Next Article

Research article Special Issues

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

1.
School of Physics and Information Engineering, Minnan Normal University, Zhangzhou 363000, China
2.
Key Lab of Intelligent Optimization and Information Processing, Minnan Normal University, Zhangzhou 363000, China
3.
Key Laboratory of Light Field Manipulation and System Integration Applications in Fujian Province, Minnan Normal University, Zhangzhou 363000, China
4.
Center for China-ASEAN Regional Collaborative Development, Minnan Normal University, Zhangzhou 363000, China

Received: 10 December 2025 Revised: 02 March 2026 Accepted: 03 March 2026 Published: 23 March 2026

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.
- VRPTW,
- competitive swarm optimizer,
- tabu search algorithm,
- large scale optimization
Citation: Fei Liang, Fei Yu, Hongrun Wu, Songbin Lan, Yingpin Chen, Xuewen Xia. Synergistic design for VRPTW: A competitive swarm optimizer guided by path diversity index and adaptive neighborhood search[J]. Electronic Research Archive, 2026, 34(4): 2511-2538. doi: 10.3934/era.2026116

Related Papers:

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.

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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 10.1016/j.cor.2003.11.023
[54]	J. Homberger, Eine verteilt-parallele Metaheuristik, in Verteilt-parallele Metaheuristiken zur Tourenplanung: Lösungsverfahren für das Standardproblem mit Zeitfensterrestriktionen, (2000), 139–165. https://doi.org/10.1007/978-3-322-97815-8_4
[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 doi: 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 doi: 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 doi: 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 doi: 10.1109/ACCESS.2020.2984660

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)