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

LI Manman; LU Jian; ZHANG He

doi:10.3969/j.issn.0258-2724.20170488

Volume 54 Issue 5

Oct. 2019

Turn off MathJax

Article Contents

Abstract

References

Journal of Southwest Jiaotong University > 2019 > 54(5): 1104-1112.

LI Manman, LU Jian, ZHANG He. Vehicle Routing Problem with Pick-up and Delivery under Dynamic Travel Times[J]. Journal of Southwest Jiaotong University, 2019, 54(5): 1104-1112. doi: 10.3969/j.issn.0258-2724.20170488

Citation:

LI Manman, LU Jian, ZHANG He. Vehicle Routing Problem with Pick-up and Delivery under Dynamic Travel Times[J]. Journal of Southwest Jiaotong University, 2019, 54(5): 1104-1112. doi: 10.3969/j.issn.0258-2724.20170488

Citation:

PDF( 1315 KB)

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

doi: 10.3969/j.issn.0258-2724.20170488

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

Received Date: 12 Oct 2017
Rev Recd Date: 08 Mar 2018

Available Online: 30 May 2018

Publish Date: 01 Oct 2019

Abstract

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

FullText(HTML)

References(17)

References

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.

Relative Articles

[1]	JIAO Yuling, ZHANG Linjing, XING Xiaocui. LIRP Joint Collaborative Optimization under Stochastic Demand and Time Constraints[J]. Journal of Southwest Jiaotong University, 2020, 55(5): 963-970. doi: 10.3969/j.issn.0258-2724.20190463
[2]	HUANG Minghua, QU Hezhou, LIU Xiaobo, TANG Youhua. Transfer-Oriented Dispatching Optimization of Rail Transit Network[J]. Journal of Southwest Jiaotong University, 2017, 30(2): 326-333. doi: 10.3969/j.issn.0258-2724.2017.02.016
[3]	CHEN Qingshan, XU Yang, HE Xingxing. Heuristic Complete Algorithm for SAT Problem by Using Logical Deduction[J]. Journal of Southwest Jiaotong University, 2017, 30(6): 1224-1232. doi: 10.3969/j.issn.0258-2724.2017.06.025
[4]	CHEN Hao, WANG Wenxian, LI Xueqin. Routing Optimization Model and Algorithm for Out-of-Gauge Freights in Multiple Flow Railway Network[J]. Journal of Southwest Jiaotong University, 2016, 29(1): 145-151. doi: 10.3969/j.issn.0258-2724.2016.01.021
[5]	GUO Rui, GUO Jin, SU Yuebin, MA Liang. Model and Approximation Algorithm for Dynamic Wagon-Flow Allocation Based on Greedy Strategy[J]. Journal of Southwest Jiaotong University, 2014, 27(4): 712-719. doi: 10.3969/j.issn.0258-2724.2014.04.024
[6]	HE Dong, ZHU Jianmei. Building Modes of Integrative Passenger Rail Transit System[J]. Journal of Southwest Jiaotong University, 2012, 25(2): 279-284. doi: 10.3969/j.issn.0258-2724.2012.02.018
[7]	YANG Qiu-Beng, XIE Xin-Lian, FEI Guang-Dan. Modeling and Simulation of Fleet Planning for Liner Shipping[J]. Journal of Southwest Jiaotong University, 2011, 24(6): 1046-1054. doi: 10.3969/j.issn.0258-2724.2011.06.026
[8]	ZOU Shurong, HUANG Xiaobin, ZHANG Hongwei. Multi-Objective Genetic Algorithm for Solving Capacitated Vehicle Routing Problems[J]. Journal of Southwest Jiaotong University, 2009, 22(5): 782-786.
[9]	CHEN Jingrong, YU Jianning, LI Yinzhen. Adaptive Path Selection in Stochastic and Time-Dependent Traffic Networks[J]. Journal of Southwest Jiaotong University, 2009, 22(4): 523-529.
[10]	ZHANG Jianyong, LI Jun, GUO Yaohuang. Insertion Heuristic Algorithm for Dynamic Vehicle Routing Problem with Fuzzy Due-Time[J]. Journal of Southwest Jiaotong University, 2008, 21(1): 107-113.
[11]	HE Di, YAN Yusong, GUO Shoujing, HAO Guang. Optimal Routing Algorithm for Public Traffic Network Based on Matrix Analysis[J]. Journal of Southwest Jiaotong University, 2007, 20(3): 315-319.
[12]	LI Hao, LUO Xia, YAO Chen. Vehicle Routing Based on Floating Car Data[J]. Journal of Southwest Jiaotong University, 2007, 20(6): 748-752,757.
[13]	YIN Chuanzhong, BU Lei, PU Yun, ZHAO Yi. Model and Algorithm for Vehicle Routing Problem with Backhauls and Time Windows[J]. Journal of Southwest Jiaotong University, 2006, 19(3): 290-295.
[14]	ZHANG Jin, MA Xiao-lai, DU Wen. Nonlinear Programming Model and Algorithm of Two-Layer Distribution Network Based on Integrated Transit-Inventory Concept[J]. Journal of Southwest Jiaotong University, 2004, 17(3): 301-305.
[15]	LIBing, YEHuai-zhen. A Heuristic Layout Restriction Algorithm for Solving Two-Dimensional Rectangular Layout Loading Problems[J]. Journal of Southwest Jiaotong University, 2002, 15(4): 443-447.
[16]	YEHUAI-zhen, ZHOUXIAN-wei, CHENCHANG-he. AnAssignmentModelofDynamieTransPortation NetworkFlowsforSystemOPtimization[J]. Journal of Southwest Jiaotong University, 2001, 14(4): 396-400.
[17]	DU Wen, LIN Shu-rong, ZΗΟUXian-wei. Batch Parallel Algorithm of Assignment Problem of Dynamic Transportation Network Flows for System Optimization[J]. Journal of Southwest Jiaotong University, 2001, 14(5): 453-456.
[18]	XIEBing-lei, LIJun, LIUJian-xin. A Heuristic Genetic Algorithm for the Travelling Salesman Problem with Time Restraints[J]. Journal of Southwest Jiaotong University, 2001, 14(2): 211-213.

Supplements(0)

Cited By

Cited by

Periodical cited type(3)

1.	郭方明，孟祥虎，唐静，李浩，黄文. 多商品分批次取送货的异构绿色车辆路径问题研究. 安徽工业大学学报(自然科学版). 2025(02): 159-168 .
2.	何美玲，魏志秀，武晓晖，彭永涛. 基于改进蚁群算法求解带软时间窗的车辆路径问题. 计算机集成制造系统. 2023(03): 1029-1039 .
3.	王冰怡. 资源共享下城市快递网点模式及布局研究综述. 综合运输. 2020(05): 99-103 .

Other cited types(24)

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(10) / Tables(2)

Get Citation

PDF

XML

Article views(460) PDF downloads(33)