首页 | 本学科首页   官方微博 | 高级检索  
     

动态行驶时间取送一体化车辆路径问题
引用本文:李嫚嫚,陆建,张赫. 动态行驶时间取送一体化车辆路径问题[J]. 西南交通大学学报, 2019, 54(5): 1104-1112. DOI: 10.3969/j.issn.0258-2724.20170488
作者姓名:李嫚嫚  陆建  张赫
基金项目:国家自然科学基金资助项目(51478110);江苏省自然科学基金资助项目(BY2016076-05);江苏省研究生科研与实践创新计划资助项目(KYCX18_0139)
摘    要:为优化真实路网下的车辆配送路径,采用优化 + 调整的两阶段求解方法. 在优化阶段,根据常发拥堵信息,采用遗传算法求解时变取送一体化车辆路径,安排车辆初始配送路径. 在调整阶段,以路段行驶时间为时间间隔,采用滚动更新策略调整车辆配送路线躲避偶发拥堵. 在针对车辆路径调整问题构建了一系列混合整数规划模型的基础上,设计了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倍. 

关 键 词:货物运输   交通网络   车辆路径   取送一体化   动态行驶时间   启发式算法
收稿时间:2017-10-12

Vehicle Routing Problem with Pick-up and Delivery under Dynamic Travel Times
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
Authors:LI Manman  LU Jian  ZHANG He
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. 
Keywords:
点击此处可从《西南交通大学学报》浏览原始摘要信息
点击此处可从《西南交通大学学报》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号