时间依赖型多配送中心带时间窗的开放式车辆路径问题研究

doi:10.16381/j.cnki.issn1003-207x.2021.0203

Abstract

Abstract:

A time-dependent multi-depot open vehicle routing problem with time windows is studied. Based on the traffic conditions， the travel speed function is established. Considering the constraints of vehicle capacity， the distance of vehicles and customer time windows， a mixed integer programming model is established. The objective function is to minimize total cost which includes vehicle travel time cost and vehicle fixed departure cost. A hybrid genetic algorithm （HGA） with two-dimensional coding method is proposed， for which a multi-segment single point crossover strategy， dynamic insertion operator and local search strategy are designed. Finally， 27 test cases are generated based on the Solomon VRPTW benchmark dataset， and the hybrid genetic algorithm is used to solve them. The numerical experimental results indicate that the proposed model has not only a significant impact on the total travel time of vehicles by considering the traffic conditions， choosing a reasonable departure time and avoiding the congestion period， but also the HGA is capable to obtain a satisfying solution.

Key words: time-dependent, multi-depot, time windows, vehicle routing problem, hybrid genetic algorithm

CLC Number:

C931

Xinyue Zhang,Peng Jin,Xiaoxuan Hu,Moning Zhu. Research on the Time-dependent Multi-depot Open Vehicle Routing Problem with Time Windows[J]. Chinese Journal of Management Science, 2024, 32(1): 146-157.

Figures/Tables 14

算例规模

_算例

N p

P c r

I t e r a

0.7

100

0.7

160

References 26

1	中冷联盟官网.5000亿，7322 万吨！数字的背后是冷链物流巨大的市场潜力［EB/OL］.（2021-831）［2021-11-21］..
	China Cold Union official website.500 billion， 73.22 million tons！Behind the figures is the huge market potential of cold chain logistics［EB/OL］ .（2021-831）［2021-11-21］..
2	马艳芳，应斌，周晓阳，等. 基于冲突合作关系的生鲜选址－路径多主体优化模型与算法［J］.系统工程理论与实践，2020，40（12）：3194-3209.
	Ma Y F， Ying B， Zhou X Y， et al.Multi-agent optimization model and algorithm for perishable food location： routing problem with conflict and coordination［J］. Systems Engineering-Theory & Practice， 2020，40（12）：3194-3209.
3	Wen L， Eglese R. Minimum cost VRP with time-dependent speed data and congestion charge［J］. Computers & Operations Research， 2015，56： 41-50.
4	丁秋雷，胡祥培，姜洋，等. 考虑新鲜度的农产品冷链物流配送受扰恢复模型［J］. 系统工程理论与实践， 2021， 41（3）： 667-677.
	Ding Q L， Hu X P， Jiang Y， et al.Arecory model for cold chain delivery of agricultural products by considering freshness［J］. Systems Engineering-Theory & Practice， 2021， 41（3）： 667-677.
5	Li J， Li Y， Pardalos P M. Multi-depot vehicle routing problem with time windows under shared depot resources［J］. Journal of Combinatorial Optimization， 2014，31（2）： 515-532.
6	Afshar-Nadjafi B， Afshar-Nadjafi A. A constructive heuristic for time-dependent multi-depot vehicle routing problem with time-windows and heterogeneous fleet［J］. Journal of King Saud University - Engineering Sciences，2017， 29（1）： 29-34.
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 Managent Science， 2011，19（2）： 99-109.
8	刘家利，马祖军. 存在车辆租赁及共享且有时间窗的多配送中心开环VRP［J］. 系统工程理论与实践，2013， 33（3）： 666-675.
	Liu J L， Ma Z J.Multi-depot open vehicle routing problem with time windows based on vehicle leasing and sharing［J］. Systems Engineering - Theory & Practice，2013， 33（3）： 666-675.
9	Mirabi M， Shokrib N， Sadeghieh A. Modeling and solving the multi-depot vehicle routing problem with time［J］. International Journal of Supply and Operations Management，2016， 3（3）： 1373-1390.
10	Dabia S， Ropke S， van Woensel T， et al. Branch and price for the time-dependent vehicle routing problem with time windows［J］. Transportation Science， 2013，47（3）： 380-396.
11	Fleischmann B， Gietz M， Gnutzmann S. Time-varying travel times in vehicle routing［J］. Transportation Science，2004， 38（2）： 160-173.
12	Malandraki C， Daskin M S. Time dependent vehicle routing problems： formulations， properties and heuristic algorithms［J］. Transportation Science， 1992，26（3）： 185-200.
13	Ichoua S， Gendreau M， Potvin J Y. Vehicle dispatching with time-dependent travel times［J］. European Journal of Operational Research， 2003，144（2）： 379-396.
14	Balseiro S R， Loiseau I， Ramonet J. An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows［J］. Computers & Operations Research，2011， 38（6）： 954-966.
15	Dabia S， Ropke S， van Woensel T， et al. Branch and price for the time-dependent vehicle routing problem with time windows［J］. Transportation Science， 2013，47（3）： 380-396.
16	Zhao X， Goncalves G， Dupas R. A genetic approach to solving the vehicle routing problem with time-dependent travel times［J］. Institute of Electrical and Electronics Engineers， 2008： 413-418.
17	周鲜成，刘长石，周开军，等. 时间依赖型绿色车辆路径模型及改进蚁群算法［J］. 管理科学学报， 2019，22（5）： 57-68.
	Zhou X C， Liu C S， Zhou K J，et al.Improved ant colony algorithm and modelling of time-dependent green vehicle routing problem［J］. Journal of Management Science in China， 2019，22（5）：57-68.
18	周鲜成，吕阳，贺彩虹，等. 考虑时变速度的多车场绿色车辆路径模型及优化算法研究［J］. 控制与决策.2021，37（2）：473-482.
	Zhou X C， Lv Y， He C H，et al.Research on multi-depot green vehicle routing model and its optimization algorithm with time-varying speed［J］.Control and Decision.2021，37（2）：473-482.
19	Rincon-Garcia N， Waterson B， Cherrett T J， et al. A metaheuristic for the time-dependent vehicle routing problem considering driving hours regulations-An application in city logistics［J］. Transportation Research Part A： Policy and Practice， 2020，137： 429-446.
20	Tarantilis C D， Kiranoudis C T. Distribution of fresh meat［J］. Journal of Food Engineering， 2002，51（1）： 85-91.
21	Liu R， Jiang Z B， Geng N. A hybrid genetic algorithm for the multi-depot open vehicle routing problem［J］. OR Spectrum， 2012，36（2）： 401-421.
22	张江华，李进，高敏刚. 同时集散货物的开放式车辆路径问题研究［J］. 中国管理科学， 2013，21（4）： 188-192.
	Zhang J H， Li J， Gao M G.Research on the open vehicle routing problem of with simultaneous deliveries and pickups［J］. Chinese Journal of Management Science，2013，21（4）：188-192.
23	杨海强. 基于出租车GPS数据的城市常发性交通拥堵演变研究［D］. 哈尔滨：哈尔滨工业大学， 2018.
	Yang H Q.Research of urban recurrent congestion evolution based on taxi GPS data ［D］. Harbin： Harbin Institute of Technology，2018.
24	Kim Y K， Park K， Ko J. A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling［J］. Computers & Operations Research， 2003，30（8）： 1151-1171.
25	Kohl N， Desrosiers J， Madsen O B G， et al. 2-Path cuts for the vehicle routing problem with time windows［J］. Transportation Science， 1999，33（1）： 101-116.
26	Figliozzi M A. The time dependent vehicle routing problem with time windows：benchmark problems， an efficient solution algorithm， and solution characteristics［J］.Transporation Research Part E，2012，48（3）：619-636.

算例	n	Best known solution			HGA best solution
算例	n	vehicles	B_best	B_time	vehicles	R_best	Gap(%)	CPU_time
C101	25	3	191.3	0.56	3	191.81	0.27	0.28
C102	25	3	190.3	1.94	3	190.74	0.23	0.19
C103	25	3	190.3	4.03	3	190.74	0.23	0.18
C104	25	3	186.9	8.45	3	186.90	0.00	0.65
C105	25	3	191.3	0.64	3	191.81	0.27	0.33
C106	25	3	191.3	0.62	3	191.81	0.27	0.63
C107	25	3	191.3	0.61	3	191.81	0.27	0.39
C108	25	3	191.3	0.64	3	191.81	0.27	0.23
C109	25	3	191.3	0.87	3	191.81	0.27	0.26
C101	50	5	362.4	2.48	5	363.25	0.23	1.85
C102	50	5	361.4	13.99	5	361.40	0.00	2.94
C103	50	5	361.4	33.78	5	361.49	0.02	3.11
C104	50	5	358	884.46	5	363.18	1.45	5.81
C105	50	5	362.4	5.83	5	363.25	0.23	9.89
C106	50	5	362.4	1.25	5	363.25	0.23	70.39
C107	50	5	362.4	3.85	5	363.25	0.23	13.27
C108	50	5	362.4	8.21	5	363.25	0.23	3.93
C109	50	5	362.4	5.34	5	363.25	0.23	1.38
C101	100	10	827.3	5.86	10	828.94	0.20	9.67
C102	100	10	827.3	111.35	10	841.36	1.70	11.45
C103	100	10	826.3	679.69	10	838.03	1.42	7.17
C104	100	10	822.9	1216.04	10	824.46	0.19	12.22
C105	100	10	827.3	33.21	10	827.72	0.05	11.33
C106	100	10	827.3	23.7	10	827.45	0.02	11.45
C107	100	10	827.3	36.92	10	828.94	0.20	12.21
C108	100	10	827.3	42.2	10	828.92	0.20	10.95
C109	100	10	827.3	72.9	10	831.56	0.51	15.28

算例	n	Best known solution			HGA best solution
算例	n	vehicles	T_best	vehicles	T_min	absolute value	CPU_avg
C101	25	3	91.84	3	79.51	12.33	0.33
C102	25	3	91.36	3	74.64	16.72	0.29
C103	25	3	91.36	3	73.12	18.24	0.28
C104	25	3	89.72	3	79.34	10.38	3.37
C105	25	3	91.84	3	80.35	11.49	1.17
C106	25	3	91.84	3	78.89	12.95	0.44
C107	25	3	91.84	3	84.07	7.77	0.26
C108	25	3	91.84	3	83.33	8.51	0.48
C109	25	3	91.84	3	77.99	13.85	0.50
C101	50	5	173.97	5	149.91	24.06	1.96
C102	50	5	173.49	5	154.92	18.57	5.99
C103	50	5	173.49	5	162.81	10.68	3.12
C104	50	5	171.86	5	159.45	12.41	2.54
C105	50	5	173.97	5	150.01	23.96	3.88
C106	50	5	173.97	5	149.50	24.47	1.29
C107	50	5	173.97	5	166.07	7.90	1.80
C108	50	5	173.97	5	145.38	28.59	1.15
C109	50	5	173.97	5	152.88	21.09	1.63
C101	100	10	397.16	10	383.18	13.98	3.87
C102	100	10	397.15	10	374.67	22.48	9.89
C103	100	10	396.68	10	383.23	13.45	5.99
C104	100	10	395.04	10	353.80	41.24	4.43
C105	100	10	397.16	10	372.98	24.18	7.27
C106	100	10	397.16	10	357.47	39.69	8.15
C107	100	10	397.16	10	374.80	22.36	6.25
C108	100	10	397.16	10	371.05	26.11	6.51
C109	100	10	397.16	10	355.95	41.21	8.22

Travel time distribution	Best known solution			HGA best solution			Gap₁	Gap₂
Travel time distribution	vehicles	T_avg	D_avg	vehicles	T’_avg	D’_avg	Gap₁	Gap₂
TD1a	10.00	729	879	10.00	650	892	12.13	-1.46
TD2a	10.00	644	864	10.00	562	884	14.53	-2.26
TD3a	10.00	608	880	10.00	513	882	18.46	-0.23
TD1b	10.00	732	892	10.00	650	892	12.59	0.00
TD2b	10.00	650	883	10.00	562	884	15.6	-0.11
TD3b	10.00	584	866	10.00	513	882	13.79	-1.81
TD1c	10.00	697	865	10.00	650	892	7.211	-3.03
TD2c	10.00	618	863	10.00	562	884	9.91	-2.38
TD3c	10.00	565	862	10.00	513	882	10.08	-2.27
TD1d	10.00	731	872	10.00	650	892	12.44	-2.24
TD2d	10.00	652	856	10.00	562	884	15.96	-3.17
TD3d	10.00	612	867	10.00	513	882	19.24	-1.70

算例	Basic GA			HGA							Gap
算例	vehicles	S_basic	CPU_time	vehicles	S_max	S_avg	S_min	Gap₁	Gap₂	CPU_avg	B~H(%)
C3-101	6	101.14	0.32	3	86.33	84.85	82.45	1.74	-2.83	0.34	22.67
C3-102	5	117.42	0.31	5	107.78	106.83	105.68	0.89	-1.08	0.32	11.11
C3-103	5	113.3	0.30	5	108.57	105.96	101.39	2.46	-4.31	0.32	11.75
C3-104	6	108.63	0.31	4	94.04	93.33	92.56	0.76	-0.83	0.35	17.36
C3-105	4	126.36	0.32	6	121.61	119.26	114.89	1.97	-3.66	0.33	9.97
C3-106	6	121.31	0.31	5	104.84	103.96	102.9	0.85	-1.02	0.32	17.89
C3-107	4	109.47	0.31	5	114.28	111.86	106.9	2.16	-4.44	0.35	2.41
C3-108	6	120.83	0.31	6	117.61	114.71	110.11	2.53	-4.01	0.35	9.73
C3-109	5	117.14	0.42	4	106.17	102.72	98.24	3.35	-4.37	0.47	19.24
C5-101	10	238.95	2.05	8	211.12	207.24	201.28	1.87	-2.88	2.28	18.72
C5-102	10	280.61	6.05	10	254.4	250.16	245.91	1.7	-1.7	6.75	14.11
C5-103	10	280.55	3.11	9	242.82	237.73	235.73	2.14	-0.84	3.71	19.01
C5-104	10	250.1	1.04	9	223.81	220.99	216.31	1.28	-2.12	1.25	15.62
C5-105	9	218.99	2.10	8	201.04	197.82	191.84	1.63	-3.02	2.71	14.15
C5-106	10	237.57	10.51	9	210.94	207.46	202.55	1.68	-2.37	11.21	17.29
C5-107	10	256.02	2.19	10	234.79	231.13	225.09	1.58	-2.61	2.14	13.74
C5-108	9	236.7	1.86	7	196.38	193.45	188.59	1.51	-2.51	2.06	25.51
C5-109	10	249.41	1.38	10	233.33	230.58	222.08	1.19	-3.69	1.68	12.31
C7-101	17	478.8	60.18	17	449.72	449.15	448.8	0.13	-0.08	62.18	6.68
C7-102	17	580.43	50.28	17	567.52	564.21	560.43	0.59	-0.67	51.48	3.57
C7-103	18	595.45	20.10	18	574.71	570.08	575.45	0.81	0.94	21.3	3.48
C7-104	13	529.35	7.23	18	520.82	517.26	512.41	0.69	-0.94	7.83	3.30
C7-105	10	399.12	74.51	11	388.34	388.34	388.34	0.00	0.00	75.51	2.78
C7-106	15	534.71	66.00	20	526.49	521.19	515.44	1.02	-1.1	66.66	3.74
C7-107	10	428.9	79.95	12	416.26	414.36	413.42	0.46	-0.23	74.56	3.74
C7-108	10	391.28	58.13	10	380.75	376.53	373.22	1.12	-0.88	60.13	4.84
C7-109	10	473.55	47.64	11	465.13	463.4	461.14	0.37	-0.49	46.28	2.69
Avg								1.35	-1.92		11.39

算例	TDMDVRPTW				TDMDOVRPTW
算例	vehicles	R_best	C_best	CPU_time	vehicles	R'_best	C'_best	CPU_time	Gap₁	Gap₂
C3-101	3	60.05	90.05	0.33	3	52.45	82.45	0.34	14.49	9.22
C3-102	5	69.84	119.84	0.28	5	55.68	105.68	0.32	25.43	13.40
C3-103	5	61.39	111.39	0.29	5	51.39	101.39	0.32	19.46	9.86
C3-104	4	59.32	99.32	0.23	4	52.56	92.56	0.35	12.86	7.30
C3-105	6	58.25	118.25	0.74	6	54.89	114.89	0.33	6.11	2.92
C3-106	6	56.63	116.63	0.76	5	52.90	102.90	0.32	7.05	13.34
C3-107	5	64.02	114.02	0.76	5	56.90	106.90	0.35	12.52	6.66
C3-108	6	51.14	111.14	0.43	6	50.11	110.11	0.35	2.05	0.93
C3-109	4	60.59	100.59	0.48	4	58.24	98.24	0.47	4.04	2.39
C5-101	8	133.67	213.67	2.92	8	121.28	201.28	2.28	10.22	6.16
C5-102	10	159.06	259.06	1.61	10	145.91	245.91	6.75	9.01	5.35
C5-103	10	150.06	250.06	1.16	9	145.73	235.73	3.71	2.97	6.08
C5-104	10	137.23	237.23	0.78	9	126.31	216.31	1.25	8.65	9.67
C5-105	8	115.03	195.03	3.42	8	111.84	191.84	2.71	2.85	1.66
C5-106	9	118.31	208.31	4.56	9	112.55	202.55	11.21	5.12	2.84
C5-107	10	140.64	240.67	4.29	10	125.09	225.09	2.14	12.43	6.92
C5-108	8	128.38	208.38	3.02	7	118.59	188.59	2.06	8.25	10.49
C5-109	10	139.54	239.54	2.16	10	122.08	222.08	1.68	14.30	7.86
C7-101	17	291.01	461.01	28.21	17	278.80	448.80	62.18	4.38	2.72
C7-102	17	396.67	566.67	24.72	17	390.43	560.43	51.48	1.60	1.11
C7-103	19	390.53	580.16	19.61	18	385.45	575.45	21.30	1.32	0.82
C7-104	19	341.71	531.71	7.36	18	332.41	512.41	7.83	2.80	3.77
C7-105	13	309.93	439.93	49.22	11	278.34	388.34	75.51	11.35	13.28
C7-106	20	333.19	533.19	65.85	20	315.44	515.44	66.66	5.63	3.44
C7-107	15	303.86	453.86	56.02	12	293.42	413.42	74.56	3.56	9.78
C7-108	12	300.79	420.79	40.91	10	273.22	373.22	60.13	10.09	12.75
C7-109	12	356.29	476.29	29.73	11	351.14	461.14	46.28	1.47	3.29
Avg									8.15	6.45

Research on the Time-dependent Multi-depot Open Vehicle Routing Problem with Time Windows

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 26

Related Articles 15

Metrics

Comments

Recommended 0

[1]	HE Pei-yang, LI Kun-peng, TIAN Qian-nan. The Integrated Production and Transportation Scheduling Problem Based on 3D Printing Technology [J]. Chinese Journal of Management Science, 2023, 31(4): 239-249.
[2]	Xian-cheng ZHOU,Tao-ying JIANG,Cai-hong HE,Li WANG,Yang LV. Green Vehicle Routing Model and Its Solution Algorithm in Cold-chain Logistics Distribution [J]. Chinese Journal of Management Science, 2023, 31(12): 203-214.
[3]	GE Xian-long, WEN Peng-zhe, XUE Gui-qin. Two-echelon Dynamic Vehicle Routing Problem with Request Forecasting [J]. Chinese Journal of Management Science, 2022, 30(8): 210-220.
[4]	LI Yang, FAN Hou-ming, ZHANG Xiao-nan. A Periodic Optimization Model and Solution for Capacitated Vehicle Routing Problem with Dynamic Requests [J]. Chinese Journal of Management Science, 2022, 30(8): 254-266.
[5]	YAN Rui, CHEN Li-shuang, ZHU Xiao-ning, TIAN Hao-tong, WEN Ya, ZHANG Qun. Research on Vehicle Routing Problem with Truck and Drone Considering Regional Restriction [J]. Chinese Journal of Management Science, 2022, 30(5): 144-155.
[6]	LIU Ming, XU Xi-fen, NING Jing, CAO Jie. Modeling and Optimizing Method for Rebalancing the Dock-less Bicycles based on Order Data Analysis [J]. Chinese Journal of Management Science, 2022, 30(4): 275-286.
[7]	PU Xu-jin, LI Xiu-feng. Multi-objective Low Carbon MDVRP Optimization Based on E-commerce Commitment Delivery Mechanism [J]. Chinese Journal of Management Science, 2021, 29(8): 57-66.
[8]	TANG Hui-ling, TANG Heng-shu, ZHU Xing-liang. Research on Low-carbon Vehicle Routing Problem Based on Modified Ant Colony Algorithm [J]. Chinese Journal of Management Science, 2021, 29(7): 118-127.
[9]	XU Dong-yang, LI Kun-peng, CUI Li-gang, TIAN Qian-nan. Multi-commodity Unpaired Supply-demandand Split Pickup and Delivery Vehicle Routing Problem with Multi-depot and Multi-type Trucks [J]. Chinese Journal of Management Science, 2021, 29(1): 127-137.
[10]	GUO Dong-wei, DING Gen-hong, LIU Wei. Improved Multi-Strategy Grouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows [J]. Chinese Journal of Management Science, 2020, 28(7): 204-211.
[11]	GUO Fang, YANG Jun, YANG Chao. Study on Heterogeneous Electric Vehicle Routing and Batterycharging Problem with the Consideration of Differentiated Service Cost [J]. Chinese Journal of Management Science, 2019, 27(8): 118-128.
[12]	FANG Wen-ting, AI Shi-zhong, WANG Qing, FAN Jun-bo. Research on Cold Chain Logistics Distribution Path Optimization Based on Hybrid Ant Colony Algorithm [J]. Chinese Journal of Management Science, 2019, 27(11): 107-115.
[13]	PAN Wen-wen, GUO Hai-xiang, DU Tian-song, LIU Xiao, WANG De-yun. The Vehicle Routing Problem with the Recycling of Oil Pipelines and Oil Casings and the Differential Evolution Algorithm based on Niching Clearing [J]. Chinese Journal of Management Science, 2018, 26(5): 118-128.
[14]	YAN Rui, ZHU Xiao-ning, ZHANG Qun, QI Yao-yuan, LIN Yu-zheng. Research ofthe Model and Algorithm for Two-dimensional Multi-depots Capacitated Vehicle Routing Problem with Time Window Constrain [J]. Chinese Journal of Management Science, 2017, 25(7): 67-77.
[15]	FU Zhuo, LIU Wen, QIU Meng. A Tabu Search Algorithm for the Vehicle Routing Problem with Soft Time Windows and Split Deliveries by Order [J]. Chinese Journal of Management Science, 2017, 25(5): 78-86.