Please wait a minute...
Journal of ZheJiang University (Engineering Science)  2020, Vol. 54 Issue (8): 1604-1612    DOI: 10.3785/j.issn.1008-973X.2020.08.020
    
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
Download: HTML     PDF(942KB) HTML
Export: BibTeX | EndNote (RIS)      

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).



Key wordsdynamic pick-up and delivery problem      dynamic algorithm framework      constructive algorithm      tabu search algorithms      adaptive large neighborhood search algorithm     
Received: 18 July 2019      Published: 28 August 2020
CLC:  U 492.3  
Corresponding Authors: Li-li ZHENG     E-mail: sunbf@jlu.edu.cn;lilizheng@jlu.edu.cn
Cite this article:

Bao-feng SUN,Yue YANG,Jun-yan SHI,Li-li ZHENG. Dynamic pick-up and delivery problem considering dynamic events in real-world environment. Journal of ZheJiang University (Engineering Science), 2020, 54(8): 1604-1612.

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2020.08.020     OR     http://www.zjujournals.com/eng/Y2020/V54/I8/1604


考虑真实场景动态事件的动态取送货问题

实时城市配送决策高度依赖于环境的变化,须及时处理配送系统中由各种动态事件带来的需求和环境变化. 综合考虑新请求逐渐出现、旧请求修改或取消、交通拥堵状况和车辆抛锚4种动态事件对车辆路径规划和配送服务的影响,重新建立考虑实时场景多项动态事件的取送货(DPDP-MDE)动态车辆路径规划模型. 设计动态算法框架求解该模型,给出调度时域内静态子问题执行规则和计算规则;针对具体静态子问题,采用构造型启发式算法生成初始可行解,分别采用禁忌搜索算法和自适应大规模邻域搜索算法2种智能优化算法,改善初始可行解质量;在更新路径规划方案时,运用未固定动态插入法,解决处于规划中的未固定请求和新请求同步处理问题. 数值实验表明,所提出的模型及设计的动态算法框架能有效解决带时间窗的动态取送货问题(DPDP-TW).


关键词: 动态取送货问题,  动态算法框架,  构造型算法,  禁忌搜索算法,  自适应大规模邻域搜索算法 
Fig.1 Flow chart of dynamic algorithm
Fig.2 Shift operator and tabu object
Fig.3 Dynamic insertion procedure
Fig.4 Arrival of new requests
Fig.5 Degree of improvement of TS and ALNS at different scheduling time horizon
Fig.6 Comparison of improvement degree of solution of two algorithms under different urgency degrees
Fig.7 Comparison of computation time of two algorithms under different urgency degrees
请求规模 数据来源 初始解 改善解 改善程度/% 计算时间/s
TS ALNS TS ALNS TS ALNS
50 lc101 13499.29 12685.16 10765.53 6.03 20.25 0.72 8.87
50 lr101 5334.35 4463.41 4405.10 16.33 17.42 12.72 66.74
50 lrc101 5690.40 5170.15 4953.49 9.14 12.95 23.47 93.83
100 LC1_2_1 28761.62 27062.05 25699.91 5.91 10.65 4.01 741.44
100 LR1_2_1 17411.13 15640.55 14755.93 10.17 15.25 5.74 633.92
100 LRC1_2_1 18524.11 16154.23 15645.90 12.79 15.54 12.26 1026.40
200 LC1_4_1 17411.13 15640.55 15003.17 10.17 13.83 10.16 1218.88
200 LR1_4_1 18524.11 16154.23 15856.64 12.79 14.40 15.46 4711.36
200 LRC1_4_1 43170.27 40406.39 38145.25 6.40 11.64 68.78 12203.84
300 LC1_6_1 77561.53 73369.65 ? 5.40 ? 19.39 ?
300 LR1_6_1 90873.69 83317.97 ? 8.31 ? 46.48 ?
300 LRC1_6_1 48895.00 43278.83 ? 11.49 ? 58.03 ?
Tab.1 Comparisonbetween two intelligent algorithms under different request sizes
[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
No related articles found!