时间依赖型多时间窗车辆路径问题研究

doi:10.16182/j.issn1004731x.joss.21-0244

摘要/Abstract

摘要：

针对一类考虑城市交通拥堵情况的时间依赖型多时间窗车辆路径问题(time-dependent vehicle routing problem with multiple time windows，TD_VRPMTW)，提出一种混合离散灰狼算法(hybrid discrete grey wolf optimizer，HDGWO)进行求解。在HDGWO中，设计了新的灰狼个体更新公式，采用基于客户排列的整数编码方式，使算法可直接在离散问题解空间中执行基于标准灰狼算法个体更新机理的全局搜索；设计了基于问题性质的种群初始化策略，用于生成具有高质量和多样性的初始种群；引入头狼信息交流公式，用于探索头狼形成的优质解空间；构造具有多种局部搜索操作的自适应变邻域局部搜索策略，用于增强算法的局部搜索能力。结果表明：HDGWO可有效求解TD_VRPMTW。

关键词: 灰狼算法, 多时间窗, 车辆路径问题, 时间依赖, 离散, 局部搜索

Abstract:

Aiming at the time-dependent vehicle routing problem with multiple time windows (TD_VRPMTW) that considers urban traffic congestion, a hybrid discrete gray wolf optimizer (HDGWO) is proposed. In the HDGWO, a new grey wolf individual updating formula is designed, and the integer coding method based on customer permutation is adopted, so that the algorithm can directly perform the global search based on GWO individual updating mechanism in the discrete problem solution space.A population initialization strategy based on the nature of the problem is designed to generate the initial population with high quality and diversity.The information exchange formula of the head wolf is introduced to explore the high-quality solution space formed by the head wolf. An adaptive variable neighborhood local search strategy with multiple local search operators is constructed to enhance the local search ability of the algorithm. Results show that HDGWO can effectively solve TD_VRPMTW.

Key words: GWO, multiple time windows, vehicle routing problem, time-dependent, discrete, local search

中图分类号:

TP391.9

李楠, 胡蓉, 钱斌, 金怀平, 于乃康. 时间依赖型多时间窗车辆路径问题研究[J]. 系统仿真学报, 2022, 34(8): 1775-1788.

Nan Li, Rong Hu, Bin Qian, Huaiping Jin, Naikang Yu. Research on Time-dependent Vehicle Routing Problem with Multiple Time Windows[J]. Journal of System Simulation, 2022, 34(8): 1775-1788.

图/表 8

图1

图2

图3

图4

图5

表1

表2

表3

参考文献 28

1	Bell W J, Dalberto L M, Fisher M L, et al. Improving the Distribution of Industrial Gases with an On-Line Computerized Routing and Scheduling Optimizer[J]. Interfaces (S0092-2102), 1983, 13(6): 4-23.
2	Rancourt M E, Cordeau J F, Laporte G. Long-haul Vehicle Routing and Scheduling with Working Hour Rules[J]. Transportation Science (S0041-1655), 2013, 47(1): 81-107.
3	Souffriau W, Vansteenwegen P, Berghe G V, et al. The Multiconstraint Team Orienteering Problem with Multiple Time Windows[J]. Transportation Science (S0041-1655), 2013, 47(1): 53-63.
4	Ichoua Soumia, Gendreau Michel, Jean Yves Potvin. Vehicle Dispatching with Time-Dependent Travel Times[J]. European Journal of Operational Research (S0377-2217), 2003, 144(2): 379-396.
5	Favaretto D, Moretti E, Pellegrini P. Ant Colony System for a VRP with Multiple Time Windows and Multiple Visits[J]. Journal of Interdisciplinary Mathematics (S0972-0502), 2007, 10(2): 263-284.
6	Belhaiza Slim, Hansen Pierre, Laporte Gilbert. A Hybrid Variable Neighborhood Tabu Search Heuristic for the Vehicle Routing Problem with Multiple Time Windows[J]. Computers & Operations Research (S0305-0548), 2014, 52: 269-281.
7	Beheshti A K, Hejazi S R, Alinaghian M. The Vehicle Routing Problem with Multiple Prioritized Time Windows: a Case Study[J]. Computers & Industrial Engineering (S0360-8352), 2015, 90: 402-413.
8	Huggo Silva Ferreira, Eduardo Theodoro Bogue, Noronha Thiago F, et al. Variable Neighborhood Search for Vehicle Routing Problem with Multiple Time Windows[J]. Electronic Notes in Discrete Mathematics (S1571-0653), 2018, 66: 207-214.
9	Belhaiza Slim, M'Hallah Rym, Ghassen Ben Brahim, et al. Three Multi-Start Data-Driven Evolutionary Heuristics for the Vehicle Routing Problem with Multiple Time Windows[J]. Journal of Heuristics (S1381-1231), 2019, 25(3): 485-515.
10	Baradaran Vahid, Shafaei Amir, Amir Hossein Hosseinian. Stochastic Vehicle Routing Problem with Heterogeneous Vehicles and Multiple Prioritized Time Windows: Mathematical Modeling and Solution Approach[J]. Computers & Industrial Engineering (S0360-8352), 2019, 131: 187-199.
11	Li Jiliu, Qin Hu, Roberto Baldacci, et al. Branch-and-Price-and-Cut for the Synchronized Vehicle Routing Problem with Split Delivery, Proportional Service Time and Multiple Time Windows[J]. Transportation Research Part E (S1366-5545), 2020, 140: 101955.
12	Bogue E T, Ferreira H S, Noronha T F, et al. A Column Generation and a Post Optimization VNS Heuristic for the Vehicle Routing Problem with Multiple Time Windows[J]. Optimization Letters (S1862-4472), 2022, 16(6): 79-95.
13	Hoogeboom M, Dullaert W, Lai D, et al. Efficient Neighborhood Evaluations for the Vehicle Routing Problem with Multiple Time Windows[J]. Transportation Science (S0041-1655), 2020, 54(2): 400-416.
14	Malandraki Chryssi, Daskin Mark S. Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms[J]. Transportation Science (S0041-1655), 1992, 26(3): 185-200.
15	Miguel Andres Figliozzi. The Time Dependent Vehicle Routing Problem with Time Windows: Benchmark Problems, an Efficient Solution Algorithm, and Solution Characteristics[J]. Transportation Research Part E (S1366-5545), 2012, 48(3): 616-636.
16	穆东, 王超, 王胜春, 等. 基于并行模拟退火算法求解时间依赖型车辆路径问题[J]. 计算机集成制造系统, 2015, 21(6): 1626-1636.
	Mu Dong, Wang Chao, Wang Shengchun, et al. Solving Time Dependent Vehicle Routing Problem Based on Parallel Simulated Annealing Algorithm [J]. Computer Integrated Manufacturing System, 2015, 21(6): 1626-1636.
17	Sun Peng, Veelenturf Lucas P, Mike Hewitt, et al. The Time-Dependent Pickup and Delivery Problem with Time Windows[J]. Transportation Research Part B(S0191-2615), 2018, 116: 1-24.
18	Visser Thomas R, Spliet Remy. Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems[J]. Transportation Science (S0041-1655), 2020, 54(4): 1091-1112.
19	张景玲, 刘金龙, 赵燕伟, 等. 时间依赖型同时取送货VRP及超启发式算法[J]. 计算机集成制造系统, 2020, 26(7): 1905-1917.
	Zhang Jingling, Liu Jinlong, Zhao Yanwei, et al. Time Dependent Simultaneous Delivery VRP and Super Heuristic Algorithm [J]. Computer Integrated Manufacturing System, 2020, 26(7): 1905-1917.
20	Mirjalili S, Mirjalili S M, Lewis A. Grey Wolf Optimizer[J]. Advances in Engineering Software (S0965-9978), 2014, 69(3): 46-61.
21	Daniel Ebenezer, Anitha J, Gnanaraj J. Optimum Laplacian Wavelet Mask Based Medical Image Using Hybrid Cuckoo Search-Grey Wolf Optimization Algorithm[J]. Knowledge-Based Systems (S0950-7051), 2017, 131: 58-69.
22	Pritam Keshavdas Gujarathi, Shah Varsha A, Lokhande Makarand M. Grey Wolf Algorithm for Multidimensional Engine Optimization of Converted Plug-In Hybrid Electric Vehicle[J]. Transportation Research Part D (S1361-9209), 2018, 63: 632-648.
23	Hemeida A M, Alkhalaf S, Mady A, et al. Implementation of Nature-Inspired Optimization Algorithms in Some Data Mining Tasks[J]. Ain Shams Engineering Journal (S2090-4479), 2020, 11(2): 309-318.
24	黄戈文, 蔡延光, 戚远航, 等. 自适应遗传灰狼优化算法求解带容量约束的车辆路径问题[J]. 电子学报, 2019, 47(12): 2602-2610.
	Huang Gewen, Cai Yanguang, Qi Yuanhang, et al. Adaptive Genetic Gray Wolf Optimization Algorithm for Vehicle Routing Problem with Capacity Constraint [J]. Acta electronica Sinica, 2019, 47(12): 2602-2610.
25	Abed alguni B H, Alawad N A. Distributed Grey Wolf Optimizer for Scheduling of Workflow Applications in Cloud Environments[J]. Applied Soft Computing (S1568-4946), 2021(102): 107113.
26	顾九春, 姜天华, 朱惠琦. 多目标离散灰狼优化算法求解作业车间节能调度问题[J/OL]. 计算机集成制造系: 1-18[2021-03-11]. .
	Gu Jiuchun, Jiang Tianhua, Zhu Huiqi. Multi Objective Discrete Grey Wolf Optimization Algorithm for Job Shop Energy Saving Scheduling Problem[J/OL]. Computer Integrated Manufacturing System: 1-18 [2021-03-11] .
27	胡蓉, 李洋, 钱斌, 等. 结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题[J/OL]. 自动化学报.[2021-03-13]. .
	Hu Rong, Li Yang, Qian Bin, et al. Solving Complex Green Vehicle Routing Problem with Enhanced Ant Colony Algorithm Based on Clustering Decomposition [J/OL]. Journal of Automation. [2021-03-13] .
28	Montgomery D C. Design and Analysis of Experiments [M]. Hoboken: John Wiley and Sons, 2005.

算例	GWO_V1		GWO_V2		HDGWO_V1		HDGWO_V2		HDGWO
算例	BST	AVG	BST	AVG	BST	AVG	BST	AVG	BST	AVG
rm101	8 752.0	9 086.1	8 029.8	9 065.6	7 435.0	7 933.7	5 357.6	5 569.1	4 453.5	4 529.6
rm103	9 540.1	9 798.1	9 174.0	9 933.7	8 050.3	8 602.0	6 199.8	6 439.5	4 912.0	5 223.7
rm105	10 439.7	10 873.0	9 338.5	10 120.5	8 845.3	9 335.4	6 071.8	6 347.8	5 492.5	5 737.2
rm201	10 613.1	11 359.9	10 427.9	11 762.4	8 259.7	8 880.0	5 277.4	5 386.1	5 144.5	5 276.0
rm203	16 425.3	17 672.8	14 695.5	16 913.6	11 418.2	12 858.4	7 008.8	7 173.6	6 369.0	6 581.9
rm205	22 648.9	25 069.1	18 614.1	21 045.3	14 166.5	17 606.6	9 000.5	9 234.5	6 917.7	7 140.3
cm101	6 641.8	7 220.9	7 313.1	8 205.3	6 410.7	6 755.8	5 518.3	5 702.3	4 736.3	5 077.0
cm103	7 571.5	8 026.2	7 820.8	8 239.4	6 924.7	7 337.6	5 859.9	5 989.7	5 467.0	5 691.3
cm105	8 179.0	8 585.2	8 227.1	8 787.2	7 476.0	7 687.0	6 443.4	6 718.6	5 337.7	5 721.0
cm201	9 043.6	9 961.2	8 531.9	9 694.1	7 178.0	8 156.2	5 557.9	5 803.4	4 987.9	5 216.1
cm203	11 233.9	12 269.9	10 844.7	12 137.4	9 145.2	10 028.0	6 176.8	6 322.5	5 499.5	5 856.1
cm205	12 518.8	13 821.2	11 267.4	13 259.4	9 985.5	10 863.7	6 312.4	6 987.9	5 656.0	5 971.8
rcm101	11 107.8	11 616.8	10 449.5	11 397.3	8 981.9	10 108.2	7 473.5	7 807.7	5 468.9	5 782.7
rcm103	11 420.4	12 010.1	10 867.9	11 867.7	9 711.1	10 458.8	7 450.3	7 604.8	5 774.8	6 024.5
rcm105	11 620.9	12 470.3	11 223.9	12 049.4	10 213.8	10 811.9	7 906.0	8 180.7	5 428.3	5 984.5
rcm201	13 400.6	13 763.6	12 080.1	14 124.6	9 825.9	10 914.8	5 399.0	5 906.9	5 238.4	5 799.6
rcm203	17 727.4	18 722.6	16 887.3	18 826.4	12 809.9	14 301.9	7 383.0	7 642.0	6 771.0	6 994.2
rcm205	17 036.2	18 507.4	15 402.5	17 651.3	11 831.9	13 416.0	7 259.9	7 487.3	6 442.8	6 591.7

算例	TD3a						TD3b
	HAVNTS		AVNS		HDGWO		HAVNTS		AVNS		HDGWO
	BST	AVG	BST	AVG	BST	AVG	BST	AVG	BST	AVG	BST	AVG
rm101	5 063.5	5 479.8	4 890.2	5 187.2	4 713.4	4 952.0	4 904.3	5 513.1	4 535.7	4 939.3	4 439.0	4 572.1
rm103	5 616.2	5 804.5	4 983.8	5 475.2	5 035.0	5 367.6	5 595.1	5 969.4	5 106.6	5 428.3	4 855.9	5 300.8
rm105	5 716.4	5 999.8	5 403.4	5 885.0	5 502.9	5 690.3	6 123.3	6 455.7	5 470.4	6 017.7	5 541.2	5 930.9
rm201	7 189.5	7 371.9	6 024.2	7 054.0	4 862.6	5 091.2	7 581.0	7 893.3	6 395.5	7 439.5	5 236.5	5 305.1
rm203	7 541.9	8 067.7	7 306.9	7 719.3	5 219.5	6 430.3	7 851.8	8 496.3	7 443.4	7 876.1	6 507.9	6 654.3
rm205	8 272.7	9 560.2	9 072.1	9 393.7	8 031.8	8 346.6	8 184.6	9 161.8	8 016.9	9 066.1	7 055.8	7 267.8
cm101	5 059.9	5 276.8	4 947.6	5 093.3	4 887.6	5 119.5	5 237.1	5 513.8	4 881.2	5 099.2	4 810.5	5 157.4
cm103	5 434.7	5 702.4	5 241.8	5 458.3	5 159.7	5 414.5	5 893.3	6 149.7	5 630.9	5 873.2	5 520.5	5 687.7
cm105	5 547.7	5 739.8	5 273.8	5 563.5	5 383.5	5 560.1	5 933.8	6 197.8	5 339.7	5 752.7	5 458.2	5 645.5
cm201	4 778.8	5 032.9	4 379.5	4 647.0	4 718.7	4 937.1	5 447.8	5 694.8	4 920.3	5 245.1	5 133.6	5 336.6
cm203	5 063.6	5 505.1	4 714.5	5 209.0	4 966.1	5 111.9	5 715.1	6 367.3	5 282.6	5 754.8	5 716.9	5 954.6
cm205	5 228.5	5 686.5	4 907.6	5 337.1	5 051.9	5 665.2	5 819.4	6 259.7	5 332.1	5 818.4	5 776.4	6 067.1
rcm101	6 078.8	6 505.6	5 982.3	6 422.0	5 788.2	6 209.8	6 193.9	6 504.5	5 675.2	6 046.6	5 378.6	5 752.3
rcm103	6 014.7	6 566.7	6 007.0	6 597.4	5 820.4	6 225.9	6 207.4	6 702.6	5 856.1	6 320.4	5 830.2	6 106.2
rcm105	6 358.1	6 876.3	6 387.4	6 806.1	6 163.5	6 483.5	5 857.2	6 633.7	5 784.1	6 306.6	5 762.6	6 078.1
rcm201	7 288.1	8 641.2	7 177.7	8 199.1	4 869.9	5 099.9	8 078.6	9 401.7	7 683.4	8 629.0	5 375.2	5 673.9
rcm203	8 669.9	9 340.7	8 395.6	9 214.8	6 497.2	6 799.4	9 110.5	9 713.5	7 549.7	9 205.5	6 922.2	7 071.0
rcm205	8 887.1	9 586.2	8 576.6	9 018.9	6 400.6	6 736.9	8 916.2	9 579.6	7 501.8	8 938.1	6 496.8	6 676.1

算例	TD3c						TD3d
	HAVNTS		AVNS		HDGWO		HAVNTS		AVNS		HDGWO
	BST	AVG	BST	AVG	BST	AVG	BST	AVG	BST	AVG	BST	AVG
rm101	5 302.8	5 552.0	5 130.8	5 354.9	4 540.7	4 767.5	4 884.3	5 318.2	4 476.1	5 007.6	4 521.8	4 759.4
rm103	5 435.8	6 011.0	5 300.6	5 756.8	4 944.7	5 256.1	5 257.1	5 887.5	5 157.0	5 534.0	4 879.9	5 241.4
rm105	5 625.6	5 995.9	5 259.2	5 820.4	5 375.0	5 572.0	6 000.7	6 314.2	5 676.5	6 120.0	5 636.7	5 909.4
rm201	6 056.5	7 112.1	6 563.6	6 752.9	4 741.5	4 945.6	6 446.5	7 618.0	6 248.2	7 248.2	4 059.9	5 095.6
rm203	7 034.6	7 487.4	6 887.3	7 266.0	6 099.4	6 314.3	7 841.5	8 482.7	7 797.0	8 401.4	5 735.7	6 687.2
rm205	7 786.6	8 740.1	7 645.2	8 452.4	6 925.0	7 787.7	9 544.9	10 149.9	8 327.3	9 615.0	8 349.7	9 136.3
cm101	4 549.1	4 739.3	4 403.9	4 566.7	4 381.1	4 600.5	5 737.2	5 993.5	5 531.4	5 835.3	5 449.4	5 790.3
cm103	5 336.0	5 521.1	5 158.1	5 402.9	5 090.4	5 358.4	5 941.0	6 192.0	5 781.9	6 039.7	5 706.3	5 872.2
cm105	5 176.8	5 355.6	5 012.4	5 160.6	5 001.7	5 186.0	6 202.2	6 412.2	5 997.4	6 280.9	5 929.2	6 196.2
cm201	4 343.6	4 530.1	4 184.1	4 307.0	4 287.1	4 507.2	6 048.1	6 974.5	5 481.4	6 543.3	5 432.9	5 642.3
cm203	4 849.2	5 038.3	4 568.5	4 808.2	4 670.1	4 825.2	7 060.4	7 469.0	6 924.4	7 203.8	6 283.7	7 129.0
cm205	4 726.3	5 043.1	4 703.0	4 847.0	4 740.3	4 825.9	6 465.7	7 534.3	6 134.6	7 411.1	6 364.6	7 398.3
rcm101	6 226.8	6 552.2	5 948.1	6 407.6	5 688.1	6 094.1	6 014.0	6 511.0	6 014.3	6 357.5	5 688.2	6 018.0
rcm103	6 320.6	6 793.5	6 161.1	6 617.0	5 843.5	6 078.4	6 403.9	6 601.8	6 070.7	6 608.0	6 014.9	6 187.0
rcm105	6 489.1	6 939.3	6 485.7	6 851.5	6 287.4	6 518.2	6 051.7	6 537.8	6 029.9	6 427.2	6 049.5	6 327.9
rcm201	7 357.8	8 425.3	6 899.9	8 176.6	5 005.0	5 141.2	7 879.1	9 253.9	7 684.7	8 859.0	5 314.5	6 263.9
rcm203	8 207.1	9 098.1	7 914.7	8 433.2	6 310.0	6 458.3	8 235.5	9 823.0	9 042.6	9 548.2	7 044.3	7 164.2
rcm205	8 192.1	8 558.9	6 845.0	8 190.9	6 177.4	6 332.5	9 120.1	9 779.9	6 594.1	9 001.6	5 371.0	6 526.8

[1]	胡蓉, 江文, 钱斌, 于乃康. 两阶段优化算法求解绿色装箱车辆路径问题[J]. 系统仿真学报, 2022, 34(7): 1490-1505.
[2]	付建林, 丁国富, 张剑, 江海凡, 郭沛佩. 基于响应面和NSGA-II的AGV系统多目标优化配置[J]. 系统仿真学报, 2022, 34(5): 994-1002.
[3]	林清泉, 杨佳然, 张和明. 一种基于离散事件系统规范的复杂产品行为模型描述方法[J]. 系统仿真学报, 2022, 34(4): 661-669.
[4]	冯开团, 袁杰. 基于改进注水算法的离散车间任务分配问题研究[J]. 系统仿真学报, 2022, 34(4): 768-776.
[5]	宁涛, 苟涛, 刘向东. 考虑低碳约束的生鲜农产品冷链物流策略仿真研究[J]. 系统仿真学报, 2022, 34(4): 797-805.
[6]	陈魁, 毕利, 王文雅. 柔性作业车间AGV与机器双资源集成调度研究[J]. 系统仿真学报, 2022, 34(3): 461-469.
[7]	刘闽东, 吴龙军, 汤明超, 孟梅. 项目型制造过程信息流集成建模仿真研究[J]. 系统仿真学报, 2022, 34(3): 555-563.
[8]	王伟权, 丁鼎, 颜林莎. 线性充电策略下多车型电动车辆路径模型研究[J]. 系统仿真学报, 2022, 34(3): 614-623.
[9]	王霄汉, 张霖, 赖李媛君, 谢堃钰, 胡听春. 基于DEVS原子模型的智能体离散仿真构建方法[J]. 系统仿真学报, 2022, 34(2): 191-200.
[10]	赵梓安, 周泓, 雷颖健. 基于改进狼群算法与仿真的单元调度优化[J]. 系统仿真学报, 2022, 34(2): 201-211.
[11]	李珍萍, 杨光, 韩倩倩. 考虑工作量均衡的成品油二次配送车辆路径问题[J]. 系统仿真学报, 2022, 34(2): 221-233.
[12]	齐晓龙, 杨旭光. 离散异构多自主体系统时变输出编队跟踪控制[J]. 系统仿真学报, 2022, 34(1): 36-44.
[13]	胡蓉, 陈文博, 钱斌, 郭宁, 向凤红. 学习型蚁群算法求解绿色多车场车辆路径问题[J]. 系统仿真学报, 2021, 33(9): 2095-2108.
[14]	闫飞, 甘斌, 陈招迪, 马文娟, 李路遥, 张柯. 离散事件仿真中实体被动式空间感知交互机制设计[J]. 系统仿真学报, 2021, 33(9): 2234-2242.
[15]	李志华, 江德, 沈汉武, 樊志华. 基于量化状态的混合系统仿真方法[J]. 系统仿真学报, 2021, 33(8): 1775-1783.