Please wait a minute...
浙江大学学报(工学版)  2020, Vol. 54 Issue (8): 1604-1612    DOI: 10.3785/j.issn.1008-973X.2020.08.020
土木工程、交通工程     
考虑真实场景动态事件的动态取送货问题
孙宝凤(),杨悦,史俊妍,郑黎黎*()
吉林大学 交通学院,吉林 长春 220104
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
 全文: PDF(942 KB)   HTML
摘要:

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

关键词: 动态取送货问题动态算法框架构造型算法禁忌搜索算法自适应大规模邻域搜索算法    
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 words: dynamic pick-up and delivery problem    dynamic algorithm framework    constructive algorithm    tabu search algorithms    adaptive large neighborhood search algorithm
收稿日期: 2019-07-18 出版日期: 2020-08-28
CLC:  U 492.3  
基金资助: 国家自然科学基金资助项目(61873109,51308249);吉林省交通运输科技资助项目(20160112)
通讯作者: 郑黎黎     E-mail: sunbf@jlu.edu.cn;lilizheng@jlu.edu.cn
作者简介: 孙宝凤(1970—),女,教授,从事物流系统规划与仿真优化研究. orcid.org/0000-0002-9030-5523. E-mail: sunbf@jlu.edu.cn
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  
孙宝凤
杨悦
史俊妍
郑黎黎

引用本文:

孙宝凤,杨悦,史俊妍,郑黎黎. 考虑真实场景动态事件的动态取送货问题[J]. 浙江大学学报(工学版), 2020, 54(8): 1604-1612.

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.

链接本文:

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

图 1  动态算法流程图
图 2  邻域移动及禁忌对象
图 3  未固定请求插入法
图 4  新请求的出现
图 5  不同间隔下TS和ALNS的改善程度
图 6  不同紧迫度下2种算法的解的改善程度对比
图 7  不同紧迫度下2种算法的计算时间对比
请求规模 数据来源 初始解 改善解 改善程度/% 计算时间/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 ?
表 1  不同请求规模下2种改善算法的对比
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
[1] 李蔚, 彭浩宇, 姚利森, 等. 约束优化问题的实数制免疫-禁忌混合算法[J]. J4, 2009, 43(6): 1037-1041.
[2] 李蔚 陈坚红 盛德仁. 机组负荷优化的遗传-禁忌混合算法[J]. J4, 2007, 41(11): 1862-1865.