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

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

摘要/Abstract

摘要：

本文研究了时间依赖型多配送中心带时间窗的开放式车辆路径问题，基于道路通行情况，建立车辆行驶速度时间函数；考虑车辆载重、里程限制与客户点服务时间窗的约束，建立混合整数规划模型，目标函数为最小化车辆总成本，具体包括车辆行驶时间成本和车辆固定发车成本；提出了一种二维编码方式的混合遗传算法，针对混合遗传算法设计了多分区段单点交叉策略、动态插入算子及局部搜索策略；最后，基于Solomon VRPTW基准数据集生成27个测试算例，使用混合遗传算法进行求解。数值实验结果表明，考虑道路通行情况，选择合理的出发时间，避免拥堵时段进行配送服务，能明显减少车辆的总行驶时间，且验证了混合遗传算法能够获得问题的满意解。

关键词: 时间依赖, 多配送中心, 时间窗, 车辆路径问题, 混合遗传算法

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

中图分类号:

C931

张歆悦,靳鹏,胡笑旋,朱默宁. 时间依赖型多配送中心带时间窗的开放式车辆路径问题研究[J]. 中国管理科学, 2024, 32(1): 146-157.

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.

图/表 14

图1

图2

图3

图4

图5

图6

表1

表2

表3

表4

图7

表5

图8

表6

算法参数表"

算例规模

_算例

N p

P c r

I t e r a

0.7

100

0.7

160

表6

参考文献 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