动态行驶时间取送一体化车辆路径问题

李嫚嫚; 陆建; 张赫

doi:10.3969/j.issn.0258-2724.20170488

动态行驶时间取送一体化车辆路径问题

doi: 10.3969/j.issn.0258-2724.20170488

李嫚嫚^1,2,3,,
陆建^1,2,3, ,,
张赫⁴

基金项目: 国家自然科学基金资助项目（51478110）；江苏省自然科学基金资助项目（BY2016076-05）；江苏省研究生科研与实践创新计划资助项目（KYCX18_0139）

详细信息

作者简介:
李嫚嫚（1991—），女，博士研究生，研究方向为交通运输管理，交通运输规划，优化理论与算法设计，E-mail：230169545@seu.edu.cn

通讯作者:
陆建（1972—），男，教授，博士，研究方向为交通管理、交通安全与智能交通，E-mail：lujian_1972@seu.edu.cn

中图分类号: F253.4
计量
- 文章访问数: 401
- HTML全文浏览量: 219
- PDF下载量: 32
- 被引次数: 0
出版历程
- 收稿日期: 2017-10-12
- 修回日期: 2018-03-08
- 网络出版日期: 2018-05-30
- 刊出日期: 2019-10-01

Vehicle Routing Problem with Pick-up and Delivery under Dynamic Travel Times

LI Manman^{1,2,3
,},
LU Jian^{1,2,3
, ,},
ZHANG He⁴

摘要

摘要: 为优化真实路网下的车辆配送路径，采用优化 + 调整的两阶段求解方法. 在优化阶段，根据常发拥堵信息，采用遗传算法求解时变取送一体化车辆路径，安排车辆初始配送路径. 在调整阶段，以路段行驶时间为时间间隔，采用滚动更新策略调整车辆配送路线躲避偶发拥堵. 在针对车辆路径调整问题构建了一系列混合整数规划模型的基础上，设计了2-opt + insertion启发式算法求解模型，并结合Dijkstra算法求解到的客户点间最短行驶路线，将车辆配送路径转化成了真实路网中的车辆配送路线. 数值实验测试结果表明：滚动更新策略中，以路段行驶时间为时间间隔比以客户间行驶时间为时间间隔减少车辆行驶时间0.24～11.95 min；以路段行驶时间为时间间隔比以24 min为时间间隔减少车辆行驶时间0.08～8.06 min，比以6 min为时间间隔减少更新次数10.02～34.59次，因此，固定时间滚动更新策略中的最优时间间隔难以确定，其实用性较差. 2-opt + insertion启发式算法求解速度是遗传算法的4倍.
- 货物运输 /
- 交通网络 /
- 车辆路径 /
- 取送一体化 /
- 动态行驶时间 /
- 启发式算法
Abstract: A two-stage method of optimization and adjustment was applied to solving vehicle routing problem with pick-up and delivery under dynamic travel times in an actual urban network. In optimization stage, according to the recurrent congestion information, a genetic algorithm was used to solve time-dependent vehicle routing problem with pick-up and delivery and arrange the initial delivery routes of vehicles. In adjustment stage, the link travel time is set as the time horizon and the rolling update was adopted to adjust delivery routes and avoid non-recurrent congestion. A series of mix-integer linear programming models were formulated for routing adjustment problem and a 2-opt algorithm hybrid with insertion algorithm was designed to solve the model. According to the shortest paths between customers derived from Dijkstra algorithm, the delivery routes are converted into the ones in an actual urban network. The numerical experiments show that in the rolling update, the time horizon of the link travel time can save 0.24–11.95 min in vehicle travel time compared with the time horizon of the travel time between customers; it can also save 0.08–8.06 min compared with the time horizon of the 24 min, and can decrease 10.02–34.59 in the number of updates compared with the time horizon of 6 min. Therefore, it is difficult to determine the optimal time horizon in the rolling update with a fixed horizon and thus it has a poor practicality. And the solving speed of 2-opt algorithm hybrid with insertion algorithm is 4 times the genetic algorithm.
- freight transportation /
- urban network /
- vehicle routing /
- pick-up and delivery /
- dynamic travel times /
- heuristic algorithm

HTML全文

图 1 客户及路网信息

Figure 1. Customers and road network information

下载: 全尺寸图片幻灯片

图 2 求解流程

Figure 2. Overview of finding a solution

下载: 全尺寸图片幻灯片

图 3 2-opt算法

Figure 3. 2-opt algorithm

下载: 全尺寸图片幻灯片

图 4 插入算法

Figure 4. Insertion algorithm

下载: 全尺寸图片幻灯片

图 5 测试网络及客户情况

Figure 5. Toy network and customers

下载: 全尺寸图片幻灯片

图 6 路段行驶时间

Figure 6. Link travel time

下载: 全尺寸图片幻灯片

图 7 测试网络中的初始车辆配送路线

Figure 7. Initial delivery routes in toy network

下载: 全尺寸图片幻灯片

图 8 不同干扰频率下的总行驶时间及更新次数

Figure 8. Total travel times and number of updates under different interference frequencies

下载: 全尺寸图片幻灯片

图 9 不同行驶时间增加量对应的总行驶时间及更新次数

Figure 9. Total travel times and number of updates under different increments of travel times

下载: 全尺寸图片幻灯片

图 10 不同影响路段数对应的总行驶时间及更新次数

Figure 10. Total travel times and number of updates under different numbers of affected links

下载: 全尺寸图片幻灯片

表 1 初始车辆配送路线

Table 1. Initial delivery routes in a simple network

车辆编号	行驶路线	行驶时间/min
1	0−n₂−P₁−0	30
2	0−n₁−E₁−0	35

下载: 导出CSV

表 2 算法比较

Table 2. Algorithm comparison

模拟次数	遗传算法		2-opt+insertion
模拟次数	求解时间/s	车辆总驶时间/min	求解时间/s	车辆总驶时间/min
1	0.44	792.00	0.10	792.00
2	0.35	803.00	0.09	803.00
3	0.39	803.00	0.09	803.00
4	0.36	792.00	0.09	792.00
5	0.34	792.00	0.09	792.00
6	0.34	792.00	0.09	792.00
7	0.36	800.00	0.09	800.00
8	0.40	800.00	0.09	800.00
平均值	0.37	796.75	0.09	796.75

下载: 导出CSV

参考文献(17)

CRAINIC T G, LAPORTE G. Planning models for freight transportation[J]. European Journal of Operational Research, 1997, 97(3): 409-438. doi: 10.1016/S0377-2217(96)00298-6

DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91. doi: 10.1287/mnsc.6.1.80

KOK A L, HANS E W, SCHUTTEN J M J. Vehicle routing under time-dependent travel times:the impact of congestion avoidance[J]. Computers & Operations Research, 2012, 39(5): 910-918.

GENDREAU M, GHIANI G, GUERRIERO E. Time-dependent routing problems:a review[J]. Computers & Operations Research, 2015, 64: 189-197.

JUNG S, HAGHANI A. Genetic algorithm for the time-dependent vehicle routing problem[J]. Transportation Research Record:Journal of the Transportation Research Board, 2001, 1771(1): 164-171. doi: 10.3141/1771-21

POTVIN J Y, XU Y, BENYAHIA I. Vehicle routing and scheduling with dynamic travel times[J]. Computers & Operations Research, 2006, 38(4): 1129-1137.

TANIGUCHI E, SHIMAMOTO H. Intelligent transportation system based dynamic vehicle routing and scheduling with variable travel times[J]. Transportation Research Part C:Emerging Technologies, 2004, 12(3): 235-250.

FLEISCHMANN B, GIETZ M, GNUTZMANN S. Time-varying travel times in vehicle routing[J]. Transportation Science, 2004, 38(2): 160-173. doi: 10.1287/trsc.1030.0062

OKHRIN I, RICHTE K. Vehicle routing problem with real-time travel times[J]. International Journal of Vehicle Information and Communication Systems, 2009, 2(1/2): 59-77. doi: 10.1504/IJVICS.2009.027746

李妍峰,高自友,李军. 基于实时交通信息的城市动态网络车辆路径优化问题[J]. 系统工程理论与实践,2013,33(7): 1813-1819. doi: 10.3969/j.issn.1000-6788.2013.07.022

LI Yanfeng, GAO Ziyou, LI Jun. Vehicle routing problem in dynamic urban network with real-time traffic information[J]. Systems Engineering-Theory & Practice, 2013, 33(7): 1813-1819. doi: 10.3969/j.issn.1000-6788.2013.07.022

李妍峰,高自友,李军. 动态网络车辆路径派送问题研究[J]. 管理科学学报,2014(8): 1-9.

LI Yanfeng, GAO Ziyou, LI Jun. Dynamic vehicle routing and dispatching problem[J]. Journal of Management Sciences in China, 2014(8): 1-9.

PILLAC V, GENDREAU M, GUERET C, et al. A review of dynamic vehicle routing problems[J]. European Journal of Operational Research, 2013, 225(1): 1-11. doi: 10.1016/j.ejor.2012.08.015

BEAN J C. Genetic algorithms and random keys for sequencing and optimization[J]. ORSA Journal on Computing, 1994, 6(2): 154-160. doi: 10.1287/ijoc.6.2.154

靳志宏, 计明军. 物流实用优化技术[M]. 北京: 中国物资出版社, 2008: 1-191

饶卫振,金淳,刘锋,等. 一类动态车辆路径问题模型和两阶段算法[J]. 交通运输系统工程与信息,2015,15(1): 159-166. doi: 10.3969/j.issn.1009-6744.2015.01.027

RAO Weizhen, JIN Chun, LIU Feng, et al. Model and two-stage algorithm on dynamic vehicle routing problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2015, 15(1): 159-166. doi: 10.3969/j.issn.1009-6744.2015.01.027

张燕,周支立,翟斌. 集货送货一体化的物流配送车辆路线问题的标号算法[J]. 运筹与管理,2007,16(3): 12-19. doi: 10.3969/j.issn.1007-3221.2007.03.003

ZHANG Yan, ZHOU Zhili, ZHAI Bin. Multi-attribute label matching algorithm for vehicle routing problems with time windows and backhauls[J]. Operations Research and Management Science, 2007, 16(3): 12-19. doi: 10.3969/j.issn.1007-3221.2007.03.003

LORINI S, POTVIN J Y, ZUFFEREY N. Online vehicle routing and scheduling with dynamic travel times[J]. Computers & Operations Research, 2011, 38(7): 1086-1090.

施引文献

附加材料(0)

访问统计