带时间窗的动态车辆路径问题的局部搜索算法

刘霞; 齐欢

带时间窗的动态车辆路径问题的局部搜索算法

刘霞^{1, 2,},
齐欢¹

1.
华中科技大学控制科学与工程系, 湖北武汉 430074
2.
江汉大学物理与信息工程学院, 湖北武汉 430056

基金项目:

国家自然科学基金项目 60574025

详细信息

作者简介:
刘霞(1977-), 女, 江西星子人, 江汉大学讲师, 工学博士, 从事系统分析与集成、系统设计与优化研究

中图分类号: U492.22
计量
- 文章访问数: 236
- HTML全文浏览量: 75
- PDF下载量: 765
- 被引次数: 0
出版历程
- 收稿日期: 2008-03-26
- 刊出日期: 2008-10-25

Local search alogrithm of dynamic vehicle routing problem with time window

LIU Xia^{1, 2
,},
QI Huan¹

1.
Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China
2.
School of Physics and Information Engineering, Jianghan University, Wuhan 430056, Hubei, China

More Information

Author Bio:
LIU Xia (1977-), female, lecturer, PhD, +86-27-84226780, Ix_hust@163.com

摘要

摘要: 为有效求解带时间窗的动态车辆路径问题, 建立了该问题的数学模型, 通过计划周期分片, 将动态问题转换为一系列的静态子问题, 采用插入法构造初始解, 并将重定位法、节点交换法和2-opt*法3种线路间局部搜索方法, 以及2-opt法和Or-opt法2种线路内局部搜索方法的不同组合应用于初始解的改进, 分析了客户出现时间、地理位置分布与不同客户时间窗范围对线路选择的影响, 比较了标准算例的求解结果。结果表明: 在线路间进行局部搜索时, 重定位法的效果最好, 2-opt*法次之, 节点交换法的最差; 在线路内进行局部搜索时, 2-opt法优于Or-opt法; 当客户请求出现时间越早, 客户比较集中, 客户时间窗较宽的情况下, 使用的车辆数量较少, 整个线路的行驶距离较短, 客户延迟时间也较短。
- 交通规划 /
- 动态车辆路径问题 /
- 局部搜索 /
- 时间窗
Abstract: In order to effectively solve dynamic vehicle routing problem with time windows, the mathematical model was established, the planning period was cut into slices, and the dynamic problem was partitioned into a series of static sub-problems, the initial solutions were constructed by intertion method.Three inter-route local search approaches including relocation, exchange and 2-opt*, and two intra-route local search approaches including 2-opt and Or-opt were introduced, different approaches were combined to improve initial solutions.The influences of arrival time, distribution of geographical location and time window range on route selection were analyzed, and the solving results of standard example were compared.Result shows that relocation method is the best, 2-opt* is the second and exchange is the worst for inter-route local search, 2-opt is better than Or-opt for intra-route local search, and the vehicle number, traveling distance and delay of all routes decrease with early requests, concentrated customers and wide time windows.
- traffic planning /
- dynamic vehicle routing problem /
- local search /
- time window

HTML全文

图 1 DVRPTW的系统结构

Figure 1. System structure of DVRPTW

下载: 全尺寸图片幻灯片

图 2 重定位法

Figure 2. Relocation approach

下载: 全尺寸图片幻灯片

图 3 节点交换法

Figure 3. Exchange approach

下载: 全尺寸图片幻灯片

图 4 2-opt^*法

Figure 4. 2-opt^* approach

下载: 全尺寸图片幻灯片

图 5 2-opt法

Figure 5. 2-opt approach

下载: 全尺寸图片幻灯片

图 6 Or-opt法

Figure 6. Or-opt approach

下载: 全尺寸图片幻灯片

表 1 局部搜索方法比较

Table 1. Comparison of local search approaches

方法	m_u	d			t^de
方法	m_u	min(d)	max(d)	avg(d)	min(t^de)	max(t^de)	avg(t^de)
重定位法与2-opt法	5.00	1 454.43	1 543.55	1 508.33	0.00	0.00	0.000
重定位法与Or-opt法	5.67	1 151.00	1 506.70	1 376.10	0.00	82.84	46.790
节点交换法与2-opt法	5.67	1 529.38	1 614.63	1 571.58	0.00	167.95	55.980
节点交换法与Or-opt法	5.67	1 541.05	1 664.61	1 616.32	0.00	397.00	222.177
2-opt^*法与2-opt法	5.00	1 489.85	1 575.82	1 540.81	0.00	0.00	0.000
2-opt^*法与Or-opt法	5.33	1 419.35	1 487.79	1 454.04	26.83	109.33	65.890

下载: 导出CSV

表 2 客户请求出现时间对线路的影响

Table 2. Effects of customer arrival times on routes

α			0.1	0.3	0.5	0.7	0.9
C101	m_u		12.00	13.00	15.00	16.00	16.00
	d	min(d)	1 250.10	1 337.50	1 309.66	1 215.22	1 222.13
		max(d)	1 279.74	1 344.48	1 404.51	1 215.22	1 222.13
		avg(d)	1 259.98	1 342.15	1 357.04	1 215.22	1 222.13
	t^de	min(t^de)	0	0	0	0	0
		max(t^de)	0	0	0	0	0
		avg(t^de)	0	0	0	0	0
R101	m_u		21.33	22.67	25.00	27.67	38.00
	d	min(d)	1 922.42	1 982.94	2 012.07	2 158.3	2 477.45
		max(d)	1 956.73	2 009.11	2 036.39	2 230.59	2 477.45
		avg(d)	1 940.21	1 995.37	2 020.18	2 193.58	2 477.45
	t^de	min(t^de)	0.00	23.33	75.67	215.44	575.19
		max(t^de)	0.00	23.33	75.67	215.44	575.19
		avg(t^de)	0.00	23.33	75.67	215.44	575.19
R201	m_u		5.33	4.33	5.00	5.00	5.33
	d	min(d)	1 378.48	1 484.13	1 454.43	1 393.24	1 647.08
		max(d)	1 410.83	1 556.35	1 543.55	1 587.68	1 740.04
		avg(d)	1 399.91	1 513.18	1 508.33	1 507.05	1 695.81
	t^de	min(t^de)	0	0	0	0	0
		max(t^de)	0	0	0	0	0
		avg(t^de)	0	0	0	0	0

下载: 导出CSV

参考文献(10)

[1]	杨瑞臣, 周永付, 云庆夏. 寻找车辆最优路径的混合算法[J]. 交通运输工程学报, 2005, 5(1): 102-105. doi: 10.3321/j.issn:1671-1637.2005.01.024 YANG Rui-chen, ZHOU Yong-fu, YUN Qing-xia. Hybrid algorithm for vehicle's optimal route[J]. Journal of Trafficand Transportation Engineering, 2005, 5(1): 102-105. (in Chinese) doi: 10.3321/j.issn:1671-1637.2005.01.024
[2]	胡大伟, 朱志强, 胡勇. 车辆路径问题的模拟退火算法[J]. 中国公路学报, 2006, 19(4): 123-126. doi: 10.3321/j.issn:1001-7372.2006.04.023 HU Da-wei, ZHUZhi-qiang, HU Yong. Simulated annealing algorithmfor vehicle routing problem[J]. China Journal ofHighway and Transport, 2006, 19(4): 123-126. (in Chinese) doi: 10.3321/j.issn:1001-7372.2006.04.023
[3]	谢秉磊, 郭耀煌, 郭强. 动态车辆路径问题: 现状与展望[J]. 系统工程理论方法应用, 2002, 11(2): 116-120. https://www.cnki.com.cn/Article/CJFDTOTAL-XTGL200202005.htm XIE Bing-lei, GUO Yao-huang, GUO Qiang. Dynamic vehicle routing problem: status and prospect[J]. Systems Engineering-Theory Methodology Applications, 2002, 11(2): 116-120. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTGL200202005.htm
[4]	BI ANCHI L. Notes on dynamic vehicle routing-the state of the art[R]. Lugano: Dalle Molle Institute for Artificial Intel-ligence, 2000.
[5]	DU T C, LI E Y, CHOU D. Dynamic vehicle problem for online B2Cdelivery[J]. The International Journal of Management Science, 2005, 33(1): 33-45. https://www.sciencedirect.com/science/article/pii/S0305048304000489
[6]	LARSEN A. The dynamic vehicle routing problem[D]. Lyn-gby: Technical University of Denmark, 2001.
[7]	FABRI A, RECHT P. On dynamic pickup and delivery vehicle routing with several ti me windows and waiting ti mes[J]. Transportation Research Part B, 2006, 40(4): 335-350. https://www.sciencedirect.com/science/article/pii/S0191261505000585
[8]	MONTEMANNI R, GAMBARDELLAL M, RIZZOLI AE, et al. Ant colony system for a dynamic vehicle routing problem[J]. Combinatorial Opti mization, 2005, 10(4): 327-343. doi: 10.1007/s10878-005-4922-6
[9]	POTVI N J Y, XU Y, BENYAHI AI. Vehicle routing and scheduling with dynamic travel ti mes[J]. Computers and Operations Research, 2006, 33(4): 1129-1137. doi: 10.1016/j.cor.2004.09.015
[10]	BRAEYSYO, GENDREAU M. Vehicle routingp roblem with time windows, part i: route construction and local search algorithms[J]. Transportation Science, 2005, 39(1): 104-118. doi: 10.1287/trsc.1030.0056