Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (6): 1897-1904.DOI: 10.11772/j.issn.1001-9081.2023060760
Special Issue: 先进计算
• Advanced computing • Previous Articles Next Articles
Yan LI1,2, Dazhi PAN1,2(), Siqing ZHENG1
Received:
2023-06-14
Revised:
2023-09-16
Accepted:
2023-09-20
Online:
2023-10-07
Published:
2024-06-10
Contact:
Dazhi PAN
About author:
LI Yan, born in 1997, M. S. candidate. His research interests include intelligent computing, combinatorial optimization.Supported by:
通讯作者:
潘大志
作者简介:
李焱(1997—),男(苗族),四川泸州人,硕士研究生,主要研究方向:智能计算、组合优化基金资助:
CLC Number:
Yan LI, Dazhi PAN, Siqing ZHENG. Improved adaptive large neighborhood search algorithm for multi-depot vehicle routing problem with time window[J]. Journal of Computer Applications, 2024, 44(6): 1897-1904.
李焱, 潘大志, 郑思情. 多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1897-1904.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2023060760
算子类型 | Avg.gap/% | Fails | Times/s |
---|---|---|---|
遗憾-1 | 36.2 | 4 | 0.02 |
遗憾-2 | 29.3 | 3 | 0.02 |
遗憾-3 | 27.6 | 3 | 0.02 |
遗憾-4 | 26.4 | 3 | 0.02 |
遗憾-5 | 25.7 | 2 | 0.02 |
遗憾-m | 27.8 | 0 | 0.03 |
Tab. 1 Performance of regret-k repair operator
算子类型 | Avg.gap/% | Fails | Times/s |
---|---|---|---|
遗憾-1 | 36.2 | 4 | 0.02 |
遗憾-2 | 29.3 | 3 | 0.02 |
遗憾-3 | 27.6 | 3 | 0.02 |
遗憾-4 | 26.4 | 3 | 0.02 |
遗憾-5 | 25.7 | 2 | 0.02 |
遗憾-m | 27.8 | 0 | 0.03 |
ξ | Avg.gap/% | LOT | ξ | Avg.gap/% | LOT |
---|---|---|---|---|---|
0.1 | 22.4 | 14 | 0.6 | 17.2 | 10 |
0.2 | 16.8 | 11 | 0.7 | 19.3 | 11 |
0.3 | 12.6 | 7 | 0.8 | 18.0 | 10 |
0.4 | 5.2 | 4 | 0.9 | 24.3 | 16 |
0.5 | 13.5 | 5 |
Tab. 2 Test results of weight response coefficient ξ
ξ | Avg.gap/% | LOT | ξ | Avg.gap/% | LOT |
---|---|---|---|---|---|
0.1 | 22.4 | 14 | 0.6 | 17.2 | 10 |
0.2 | 16.8 | 11 | 0.7 | 19.3 | 11 |
0.3 | 12.6 | 7 | 0.8 | 18.0 | 10 |
0.4 | 5.2 | 4 | 0.9 | 24.3 | 16 |
0.5 | 13.5 | 5 |
Instance | TS | VNS | MPMSFLA | IALNS | |||||||
---|---|---|---|---|---|---|---|---|---|---|---|
name | N | D | KBS | TIME/min | AVE | TIME/min | AVE | TIME/min | AVE | TIME/min | GAP/% |
pr01 | 48 | 4 | 1 074.12 | 28 | 1 074.12 | 9.49 | 1 074.34 | 0.45 | 1 074.28 | 0.39 | 0.01 |
pr02 | 96 | 4 | 1 762.48 | 79 | 1 763.66 | 27.63 | 1 768.23 | 1.42 | 1 766.41 | 0.68 | 0.16 |
pr03 | 144 | 4 | 2 397.06 | 115 | 2 388.73 | 75.88 | 2 378.23 | 2.96 | 2 399.52 | 3.15 | 0.45 |
pr04 | 192 | 4 | 2 865.71 | 144 | 2 847.56 | 93.53 | 2 858.35 | 4.21 | 2 852.41 | 3.26 | 0.17 |
pr05 | 240 | 4 | 3 050.80 | 181 | 3 015.27 | 89.36 | 3 021.56 | 4.89 | 3 027.97 | 3.95 | 0.42 |
pr06 | 288 | 4 | 3 670.13 | 221 | 3 674.60 | 96.63 | 3 685.28 | 6.33 | 3 686.14 | 6.85 | 0.31 |
pr07 | 72 | 6 | 1 418.22 | 53 | 1 418.22 | 7.66 | 1 418.78 | 1.89 | 1 421.21 | 1.72 | 0.21 |
pr08 | 144 | 6 | 2 118.50 | 102 | 2 103.21 | 54.92 | 2 111.47 | 3.07 | 2 110.36 | 2.87 | 0.34 |
pr09 | 216 | 6 | 2 760.46 | 160 | 2 753.61 | 69.11 | 2 770.61 | 3.85 | 2 760.23 | 2.96 | 0.24 |
pr10 | 288 | 6 | 3 507.26 | 227 | 3 541.01 | 65.70 | 3 555.86 | 6.97 | 3 534.27 | 6.38 | -0.19 |
pr11 | 48 | 4 | 1 016.59 | 32 | 1 011.65 | 18.30 | 1 009.70 | 0.48 | 1 019.35 | 0.35 | 0.76 |
pr12 | 96 | 4 | 1 486.26 | 81 | 1 488.32 | 89.40 | 1 489.11 | 1.90 | 1 487.15 | 1.36 | -0.08 |
pr13 | 144 | 4 | 2 028.85 | 143 | 2 012.37 | 82.30 | 2 026.47 | 3.25 | 2 025.65 | 2.59 | 0.66 |
pr14 | 192 | 4 | 2 228.64 | 188 | 2 239.02 | 106.51 | 2 242.89 | 4.16 | 2 251.23 | 3.29 | 0.55 |
pr15 | 240 | 4 | 2 527.60 | 227 | 2 498.85 | 89.39 | 2 508.28 | 4.88 | 2 503.14 | 3.15 | 0.17 |
pr16 | 288 | 4 | 2 960.93 | 261 | 2 909.45 | 99.69 | 2 930.14 | 6.86 | 2 918.35 | 6.92 | 0.31 |
pr17 | 72 | 6 | 1 241.25 | 61 | 1 247.51 | 62.15 | 1 240.19 | 1.60 | 1 251.31 | 1.36 | 0.30 |
pr18 | 144 | 6 | 1 823.24 | 146 | 1 809.25 | 99.24 | 1 815.74 | 3.07 | 1 814.35 | 2.56 | 0.28 |
pr19 | 216 | 6 | 2 288.38 | 262 | 2 294.19 | 90.84 | 2 300.65 | 4.29 | 2 310.12 | 3.88 | 0.69 |
pr20 | 288 | 6 | 3 120.32 | 263 | 3 093.51 | 86.38 | 3 109.12 | 6.64 | 3 107.25 | 6.12 | 0.44 |
Tab. 3 Comparison of experimental results between IALNS and other algorithms
Instance | TS | VNS | MPMSFLA | IALNS | |||||||
---|---|---|---|---|---|---|---|---|---|---|---|
name | N | D | KBS | TIME/min | AVE | TIME/min | AVE | TIME/min | AVE | TIME/min | GAP/% |
pr01 | 48 | 4 | 1 074.12 | 28 | 1 074.12 | 9.49 | 1 074.34 | 0.45 | 1 074.28 | 0.39 | 0.01 |
pr02 | 96 | 4 | 1 762.48 | 79 | 1 763.66 | 27.63 | 1 768.23 | 1.42 | 1 766.41 | 0.68 | 0.16 |
pr03 | 144 | 4 | 2 397.06 | 115 | 2 388.73 | 75.88 | 2 378.23 | 2.96 | 2 399.52 | 3.15 | 0.45 |
pr04 | 192 | 4 | 2 865.71 | 144 | 2 847.56 | 93.53 | 2 858.35 | 4.21 | 2 852.41 | 3.26 | 0.17 |
pr05 | 240 | 4 | 3 050.80 | 181 | 3 015.27 | 89.36 | 3 021.56 | 4.89 | 3 027.97 | 3.95 | 0.42 |
pr06 | 288 | 4 | 3 670.13 | 221 | 3 674.60 | 96.63 | 3 685.28 | 6.33 | 3 686.14 | 6.85 | 0.31 |
pr07 | 72 | 6 | 1 418.22 | 53 | 1 418.22 | 7.66 | 1 418.78 | 1.89 | 1 421.21 | 1.72 | 0.21 |
pr08 | 144 | 6 | 2 118.50 | 102 | 2 103.21 | 54.92 | 2 111.47 | 3.07 | 2 110.36 | 2.87 | 0.34 |
pr09 | 216 | 6 | 2 760.46 | 160 | 2 753.61 | 69.11 | 2 770.61 | 3.85 | 2 760.23 | 2.96 | 0.24 |
pr10 | 288 | 6 | 3 507.26 | 227 | 3 541.01 | 65.70 | 3 555.86 | 6.97 | 3 534.27 | 6.38 | -0.19 |
pr11 | 48 | 4 | 1 016.59 | 32 | 1 011.65 | 18.30 | 1 009.70 | 0.48 | 1 019.35 | 0.35 | 0.76 |
pr12 | 96 | 4 | 1 486.26 | 81 | 1 488.32 | 89.40 | 1 489.11 | 1.90 | 1 487.15 | 1.36 | -0.08 |
pr13 | 144 | 4 | 2 028.85 | 143 | 2 012.37 | 82.30 | 2 026.47 | 3.25 | 2 025.65 | 2.59 | 0.66 |
pr14 | 192 | 4 | 2 228.64 | 188 | 2 239.02 | 106.51 | 2 242.89 | 4.16 | 2 251.23 | 3.29 | 0.55 |
pr15 | 240 | 4 | 2 527.60 | 227 | 2 498.85 | 89.39 | 2 508.28 | 4.88 | 2 503.14 | 3.15 | 0.17 |
pr16 | 288 | 4 | 2 960.93 | 261 | 2 909.45 | 99.69 | 2 930.14 | 6.86 | 2 918.35 | 6.92 | 0.31 |
pr17 | 72 | 6 | 1 241.25 | 61 | 1 247.51 | 62.15 | 1 240.19 | 1.60 | 1 251.31 | 1.36 | 0.30 |
pr18 | 144 | 6 | 1 823.24 | 146 | 1 809.25 | 99.24 | 1 815.74 | 3.07 | 1 814.35 | 2.56 | 0.28 |
pr19 | 216 | 6 | 2 288.38 | 262 | 2 294.19 | 90.84 | 2 300.65 | 4.29 | 2 310.12 | 3.88 | 0.69 |
pr20 | 288 | 6 | 3 120.32 | 263 | 3 093.51 | 86.38 | 3 109.12 | 6.64 | 3 107.25 | 6.12 | 0.44 |
1 | DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1):80-91. |
2 | J-F CORDEAU, LAPORTE G, MERCIER A, et al. A unified tabu search heuristic for vehicle routing problems with time windows [J]. Journal of the Operational Research Society, 2001, 52: 928-936. |
3 | J-F CORDEAU, LAPORTE G, MERCIER A. Improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows[J]. Journal of the Operational Research Society, 2004, 55: 542-546. |
4 | POLACEK M, HARTL R F, DOERNER K,et al. A variable neighborhood search for the multi depot vehicle routing problem with time windows [J]. Journal of Heuristics, 2004, 10: 613-627. |
5 | DONDO R, CERDÁ J. A cluster-based optimization approach for the multi- depot heterogeneous fleet vehicle routing problem with time windows[J]. European Journal of Operational Research, 2007,176:1478-1507. |
6 | 洪联系,董绍华.MDVRPTW问题多阶段迭代启发式算法[J].计算机工程与应用, 2007, 43(26): 217-222. |
HONG L X, DONG S H. Multi-phase iterative heuristic approach for MDVRPTW [J]. Computer Engineering and Applications, 2007, 43(26): 217-222. | |
7 | 王征,张俊,王旭坪.多车场带时间窗车辆路径问题的变邻域搜索算法[J].中国管理科学,2011,19(2):99-109. |
WANG Z, ZHANG J, WANG X P. A modified variable neighborhood search algorithm for the multi depot vehicle routing problem with time windows[J].Chinese Journal of Management Science, 2011,19(2):99-109. | |
8 | GENDREAU M, HERTZ A, LAPORTE G, et al. A generalized insertion heuristic for the traveling salesman problem with time windows [J]. Operations Research, 1998,46(3):330-335. |
9 | 于滨,靳鹏欢,杨忠振.两阶段启发式算法求解带时间窗的多中心车辆路径问题[J].系统工程理论与实践,2012,32(8):1793-1800. |
YU B, JIN P H, YANG Z Z. Two-stage heuristic algorithm for multi-depot vehicle routing problem with time window[J].System Engineering — Theory & Practice,2012,32(8):1793-1800. | |
10 | LUO J, CHEN M. Multi-phase modified shuffled frog leaping algorithm with extremal optimization for the MDVRP and the MDVRPTW[J]. Computers & Industrial Engineering, 2014,72:84-97. |
11 | TAMASHIRO H, NAKAMURA M, OKAZAKI T, et al. A tabu search approach combined with an extended saving method for multi-depot vehicle routing problems with time windows (TOTAL OPERATIONS MENAGEMENT)[J]. International Journal of Biomedical Soft Computing and Human Sciences: the Official Journal of the Biomedical Fuzzy Systems Association,2010,15(1):29-37. |
12 | SADATI M E H, ATAY B, AKSEN D. An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems[J]. Computers and Operations Research, 2021,133: 105269. |
13 | 刘小兰,郝志峰,汪国强,等.有时间窗的车辆路径问题的近似算法研究[J]. 计算机集成制造系统, 2004, 10(7): 825-831. |
LIU X L, HAO Z F, WANG G Q, et al. Improved large neighborhood search algorithm for vehicle routing problem with time windows[J]. Computer Integrated Manufacturing Systems, 2004, 10(7): 825-831. | |
14 | ROPKE S, PISINGER D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science, 2006, 40(4):455-472. |
15 | CHENG L. A genetic algorithm for the vehicle routing problem with time windows[D]. Wilmington, North Carolina: University of North Carolina Wilmington, 2009:105-121. |
16 | 陈小玲. 蚁群算法及其在车辆路径问题中的应用研究[D].成都:电子科技大学, 2009:16-34. |
CHEN X L. Ant colony algorithm and its application research in vehicle routing problems[D].Chengdu:University of Electronic Science and Technology of China, 2009:16-34. | |
17 | CHEN C-M, LV S, NING J, et al. A genetic algorithm for the waitable time-varying multi-depot green vehicle routing problem[J]. Symmetry, 2023,15(1): 124. |
18 | 吕垚远. 混合差分进化算法在多目标车辆路径问题中的应用[D]. 太原:太原科技大学, 2021:23-42. |
LU Y Y. Application of hybrid differential evolution algorithm in multi-objective vehicle routing problem[D]. Taiyuan: Taiyuan University of Science and Technology, 2021:23-42. | |
19 | 周蓉,沈维蕾.软硬时间窗共存装卸一体化车辆路径问题的混合离散粒子群优化算法[J].合肥工业大学学报(自然科学版),2016,39(8):1022-1026. |
ZHOU R, SHEN W L. Hybrid discrete particle swarm optimization algorithm for vehicle routing problem with simultaneous delivery and pickup under coexistence of soft and hard time windows[J]. Journal of Hefei University of Technology (Natural Science), 2016,39(8):1022-1026. | |
20 | WANG Y, WEI Y, WANG X, et al. A clustering-based extended genetic algorithm for the multidepot vehicle routing problem with time windows and three-dimensional loading constraints[J]. Applied Soft Computing, 2023,133:109922. |
21 | FAIED M, MOSTAFA A, GIRARD A. Dynamic optimal control of multiple depot vehicle routing problem with metric temporal logic[C]// Proceedings of the 2009 American Control Conference. Piscataway: IEEE, 2009: 3268-3273. |
22 | RAJMOHAN M, SHAHABUDEEN P. Metaheuristic for solving routing problem in logistics management[J]. International Journal of Operational Research, 2009, 6(2): 223-246. |
23 | 向婷,潘大志.求解需求可拆分车辆路径问题的聚类算法[J].计算机应用,2016,36(11):3141-3145. |
XIANG T, PAN D Z. Clustering algorithm for split delivery vehicle routing problem[J]. Journal of Computer Applications, 2016,36(11):3141-3145. | |
24 | MUNARI P, SAVELSBERGH M. A column generation-based heuristic for the split delivery vehicle routing problem with time windows[J]. SN Operations Research Forum, 2020, 1: 26. |
25 | FONTAINE P. The vehicle routing problem with load-dependent travel times for cargo bicycles[J]. European Journal of Operational Research, 2022,300:1005-1016. |
[1] | Yi ZHOU, Hua GAO, Yongshen TIAN. Proximal policy optimization algorithm based on clipping optimization and policy guidance [J]. Journal of Computer Applications, 2024, 44(8): 2334-2341. |
[2] | Xiuxi WEI, Maosong PENG, Huajuan HUANG. Node coverage optimization of wireless sensor network based on multi-strategy improved butterfly optimization algorithm [J]. Journal of Computer Applications, 2024, 44(4): 1009-1017. |
[3] | Yun OU, Kaiqing ZHOU, Pengfei YIN, Xuewei LIU. Improved grey wolf optimizer algorithm based on dual convergence factor strategy [J]. Journal of Computer Applications, 2023, 43(9): 2679-2685. |
[4] | Chungang HAN, Yonghui LIU. Face liveness detection algorithm based on GhostNet and feature fusion [J]. Journal of Computer Applications, 2023, 43(8): 2588-2592. |
[5] | Hao GAO, Qingke ZHANG, Xianglong BU, Junqing LI, Huaxiang ZHANG. Teaching-learning-based optimization algorithm based on cooperative mutation and Lévy flight strategy and its application [J]. Journal of Computer Applications, 2023, 43(5): 1355-1364. |
[6] | Xuesen MA, Xuemei XU, Gonghui JIANG, Yan QIAO, Tianbao ZHOU. Hybrid adaptive particle swarm optimization algorithm for workflow scheduling [J]. Journal of Computer Applications, 2023, 43(2): 474-483. |
[7] | Weikang ZHANG, Sheng LIU, Qian HUANG, Yuxin GUO. Equilibrium optimizer considering distance factor and elite evolutionary strategy [J]. Journal of Computer Applications, 2022, 42(6): 1844-1851. |
[8] | Sheng CHEN, Jun ZHOU, Xiaobing HU, Ji MA. Optimization of airport arrival procedures based on hybrid simulated annealing algorithm [J]. Journal of Computer Applications, 2022, 42(2): 606-615. |
[9] | Xiao GUO, Chunshan LI, Yuyue ZHANG, Dianhui CHU. Service integration method based on adaptive multi‑objective reinforcement learning [J]. Journal of Computer Applications, 2022, 42(11): 3500-3505. |
[10] | Zhi LI, Jianbin XUE. Task offloading and resource allocation based on simulated annealing algorithm in C-V2X internet of vehicles [J]. Journal of Computer Applications, 2022, 42(10): 3140-3147. |
[11] | FAN Xiaomao, XIONG Honglin, ZHAO Gansen. Cleaning scheduling model with constraints and its solution [J]. Journal of Computer Applications, 2021, 41(2): 577-582. |
[12] | Yongpeng SHI, Junjie ZHANG, Yujie XIA, Ya GAO, Shangwei ZHANG. Computation offloading and resource allocation strategy in NOMA-based 5G ultra-dense network [J]. Journal of Computer Applications, 2021, 41(11): 3319-3324. |
[13] | YANG Wei, LI Ran, ZHANG Kun. Task allocation optimization for automated guided vehicles based on variable neighborhood simulated annealing algorithm [J]. Journal of Computer Applications, 2021, 41(10): 3056-3062. |
[14] | WANG Bo, LIU Liansheng, HAN Shaocheng, ZHU Shixing. Hybrid multi-objective grasshopper optimization algorithm based on fusion of multiple strategies [J]. Journal of Computer Applications, 2020, 40(9): 2670-2676. |
[15] | QI Xuanxuan, HUANG Jiajun, CAO Jian'an. Path planning for unmanned vehicle based on improved A* algorithm [J]. Journal of Computer Applications, 2020, 40(7): 2021-2027. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||