|
|
Dynamic pick-up and delivery problem considering dynamic events in real-world environment |
Bao-feng SUN(),Yue YANG,Jun-yan SHI,Li-li ZHENG*() |
School of Transportation, Jilin University, Changchun 220104, China |
|
|
Abstract Real-time city distribution strategies are highly dependent on dynamic environments, requiring timely responses to changes of demand and environment due to various dynamic events that take place in the distribution system. A dynamic vehicle routing model based on a dynamic pick-up and delivery problem considering multiple dynamic events in a real-world environment (DPDP-MDE) was established, considering the influence of four kinds of real-time information on vehicle routing and vehicle scheduling, including new requests arriving gradually, old requests being modified or canceled, traffic congestion and vehicle breakdowns. A dynamic algorithm framework is designed to solve this model. The execution rules and calculation rules of static subproblems within scheduled time horizon are given. The constructive heuristic algorithm is used to generate the initial feasible solution for the exact static subproblems. Two intelligent optimization algorithms, tabu search algorithm and adaptive large-scale neighborhood search algorithm, are adopted to improve the quality of those initial feasible solution. The dynamic insertion method is adopted to solve the synchronization problem of unfixed requests and new requests when updating the routing. Experimental results show that the model and dynamic algorithm framework proposed can effectively solve the dynamic pick-up and delivery problem with time windows (DPDP-TW).
|
Received: 18 July 2019
Published: 28 August 2020
|
|
Corresponding Authors:
Li-li ZHENG
E-mail: sunbf@jlu.edu.cn;lilizheng@jlu.edu.cn
|
考虑真实场景动态事件的动态取送货问题
实时城市配送决策高度依赖于环境的变化,须及时处理配送系统中由各种动态事件带来的需求和环境变化. 综合考虑新请求逐渐出现、旧请求修改或取消、交通拥堵状况和车辆抛锚4种动态事件对车辆路径规划和配送服务的影响,重新建立考虑实时场景多项动态事件的取送货(DPDP-MDE)动态车辆路径规划模型. 设计动态算法框架求解该模型,给出调度时域内静态子问题执行规则和计算规则;针对具体静态子问题,采用构造型启发式算法生成初始可行解,分别采用禁忌搜索算法和自适应大规模邻域搜索算法2种智能优化算法,改善初始可行解质量;在更新路径规划方案时,运用未固定动态插入法,解决处于规划中的未固定请求和新请求同步处理问题. 数值实验表明,所提出的模型及设计的动态算法框架能有效解决带时间窗的动态取送货问题(DPDP-TW).
关键词:
动态取送货问题,
动态算法框架,
构造型算法,
禁忌搜索算法,
自适应大规模邻域搜索算法
|
|
[1] |
FRANCESCO F, STEFAN B Real-time control of express pickup and delivery processes in a dynamic environment[J]. Transportation Research Part B, 2014, (63): 1- 14
|
|
|
[2] |
FABRI A, RECHT P On dynamic pickup and delivery vehicle routing with several time windows and waiting times[J]. Transportation Research Part B: Methodological, 2006, 40 (4): 335- 350
doi: 10.1016/j.trb.2005.04.002
|
|
|
[3] |
MITROVIC′-MINIC′ S, LAPORTE G Waiting strategies for the dynamic pickup and delivery problem with time windows[J]. Transportation Research Part B: Methodological, 2004, (38): 635- 655
|
|
|
[4] |
BRANKE J, MIDDENDORF M, NOETH G, et al Waiting strategies for dynamic vehicle routing[J]. Transportation Science, 2005, 39 (3): 298- 312
doi: 10.1287/trsc.1040.0095
|
|
|
[5] |
SNEZANA M, RAMESH K, GILBERT L Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows[J]. Transportation Research Part B: Methodological, 2004, 38 (8): 669- 685
doi: 10.1016/j.trb.2003.09.001
|
|
|
[6] |
ICHOUA S, GENDREAU M, POTVIN J-Y Exploiting knowledge about future demands for real-time vehicle dispatching[J]. Transportation Science, 2006, 40 (2): 211- 225
doi: 10.1287/trsc.1050.0114
|
|
|
[7] |
LI H, LIM A A metaheuristic for the pickup and delivery problem with time windows[J]. International Journal on Artificial Intelligence Tools, 2003, 12 (2): 173- 186
|
|
|
[8] |
PUREZA V, LAPORTE G Waiting and buffering strategies for the dynamic pickup and delivery problem with time windows[J]. INFOR: Information Systems and Operational Research, 2008, 46 (3): 165- 176
|
|
|
[9] |
KOK A L, HANS E W, SCHUTTEN J M J Vehicle routing under time-dependent travel times: the impact of congestion avoidance[J]. Computers and Operations Research, 2012, 39 (5): 910- 918
doi: 10.1016/j.cor.2011.05.027
|
|
|
[10] |
SUN P, VEELENTURF L P, HEWITT M, et al The time-dependent pickup and delivery problem with time windows[J]. Transportation Research Part B: Methodological, 2018, 116: 1- 24
|
|
|
[11] |
MAMASIS K, MINIS I, DIKAS G Managing vehicle breakdown incidents during urban distribution of a common product[J]. Journal of the Operational Research Society, 2013, 64 (6): 925- 937
doi: 10.1057/jors.2012.93
|
|
|
[12] |
GOLDEN B L, RAGHAVAN S, WASIL E A. The vehicle routing problem [M]// Latest advances and new challenges. Berlin: Springer, 2008.
|
|
|
[13] |
KRITZINGER S, DOERNER K F, HARTL R F Using traffic information for time-dependent vehicle routing[J]. Procedia-Social and Behavioral Sciences, 2012, 39: 217- 229
doi: 10.1016/j.sbspro.2012.03.103
|
|
|
[14] |
GERARDO B, JEAN-FRAN?OIS C, GILBERT L Dynamic pickup and delivery problems[J]. European Journal of Operational Research, 2010, 202 (1): 8- 15
doi: 10.1016/j.ejor.2009.04.024
|
|
|
[15] |
MICHEL G, FRANCOIS G, JEAN-YVES P, et al Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries[J]. Transportation Research Part C: Emerging Technologies, 2006, 14 (3): 157- 174
doi: 10.1016/j.trc.2006.03.002
|
|
|
[16] |
MONTEMANNI R, GAMBARDELLA L M, RIZZOLI A E, et al Ant colony system for a dynamic vehicle routing problem[J]. Journal of Combinatorial Optimization, 2005, 10 (4): 327- 343
doi: 10.1007/s10878-005-4922-6
|
|
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|