Research on Time-dependent Vehicle Routing Problem with Multiple Time Windows

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

Abstract

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

CLC Number:

TP391.9

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.

Figures/Tables 8

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Table 1

Table 2

Table 3

References 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]	Rong Hu, Wen Jiang, Bin Qian, Naikang Yu. Two Stage Optimization Algorithm to Solve the Green Packing Vehicle Routing Problem [J]. Journal of System Simulation, 2022, 34(7): 1490-1505.
[2]	Jianlin Fu, Guofu Ding, Jian Zhang, Haifan Jiang, Peipei Guo. Multi-Objective Optimization Configuration of AGV System Based on Response Surface and NSGA-II [J]. Journal of System Simulation, 2022, 34(5): 994-1002.
[3]	Qingquan Lin, Jiaran Yang, Heming Zhang. A DEVS-based Formal Description Method for Complex Product Behavior Models [J]. Journal of System Simulation, 2022, 34(4): 661-669.
[4]	Weiquan Wang, Ding Ding, Shuyan Cao. Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem [J]. Journal of System Simulation, 2022, 34(4): 910-919.
[5]	Kaituan Feng, Jie Yuan. Research on Discrete Workshop Task Assignment Based on Improved Water Filling Algorithm [J]. Journal of System Simulation, 2022, 34(4): 768-776.
[6]	Tao Ning, Tao Gou, Xiangdong Liu. Simulation on Cold Chain Distribution Path of Fresh Agricultural Products Under Low-carbon Constraints [J]. Journal of System Simulation, 2022, 34(4): 797-805.
[7]	Kui Chen, Li Bi, Wenya Wang. Research on Integrated Scheduling of AGV and Machine in Flexible Job Shop [J]. Journal of System Simulation, 2022, 34(3): 461-469.
[8]	Mindong Liu, Longjun Wu, Mingchao Tang, Mei Meng. Research on Information Flow Integrated M&S Method for Project Type Manufacturing Process [J]. Journal of System Simulation, 2022, 34(3): 555-563.
[9]	Weiquan Wang, Ding Ding, Linsha Yan. Path-Based Model for the Heterogeneous-Fleet Electric Vehicle Routing Problem with Partial Linear Recharging [J]. Journal of System Simulation, 2022, 34(3): 614-623.
[10]	Xiaohan Wang, Lin Zhang, Yuanjun Laili, Kunyu Xie, Tingchun Hu. Constructing the Agent Discrete Simulation Based on DEVS Atomic Model [J]. Journal of System Simulation, 2022, 34(2): 191-200.
[11]	Zi'an Zhao, Hong Zhou, Yingjian Lei. Modeling and Optimization for Manufacturing Cell Scheduling Based on Improved Wolf Pack Algorithm and Simulation [J]. Journal of System Simulation, 2022, 34(2): 201-211.
[12]	Zhenping Li, Guang Yang, Qianqian Han. Vehicle Routing Problem with Refined Oil Secondary Distribution Considering Workload Balance [J]. Journal of System Simulation, 2022, 34(2): 221-233.
[13]	Qi Xiaolong, Yang Xuguang. Time-varying Output Formation Tracking Control of Discrete-time Heterogeneous Multi-agent Systems [J]. Journal of System Simulation, 2022, 34(1): 36-44.
[14]	Hu Rong, Chen Wenbo, Qian Bin, Guo Ning, Xiang Fenghong. Learning Ant Colony Algorithm for Green Multi-depot Vehicle Routing Problem [J]. Journal of System Simulation, 2021, 33(9): 2095-2108.
[15]	Yan Fei, Gan Bin, Chen Zhaodi, Ma Wenjuan, Li Luyao, Zhang Ke. Mechanism Design for Entities' Passive Dimensional Sensing Interaction in Discrete Event Simulations [J]. Journal of System Simulation, 2021, 33(9): 2234-2242.