• ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus 收录
  • 全国中文核心期刊
  • 中国科技论文统计源期刊
  • 中国科学引文数据库来源期刊

动态行驶时间取送一体化车辆路径问题

李嫚嫚 陆建 张赫

李嫚嫚, 陆建, 张赫. 动态行驶时间取送一体化车辆路径问题[J]. 西南交通大学学报, 2019, 54(5): 1104-1112. doi: 10.3969/j.issn.0258-2724.20170488
引用本文: 李嫚嫚, 陆建, 张赫. 动态行驶时间取送一体化车辆路径问题[J]. 西南交通大学学报, 2019, 54(5): 1104-1112. doi: 10.3969/j.issn.0258-2724.20170488
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

动态行驶时间取送一体化车辆路径问题

doi: 10.3969/j.issn.0258-2724.20170488
基金项目: 国家自然科学基金资助项目(51478110);江苏省自然科学基金资助项目(BY2016076-05);江苏省研究生科研与实践创新计划资助项目(KYCX18_0139)
详细信息
    作者简介:

    李嫚嫚(1991—),女,博士研究生,研究方向为交通运输管理,交通运输规划,优化理论与算法设计,E-mail:230169545@seu.edu.cn

    通讯作者:

    陆 建(1972—),男,教授,博士,研究方向为交通管理、交通安全与智能交通,E-mail:lujian_1972@seu.edu.cn

  • 中图分类号: F253.4

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

  • 摘要: 为优化真实路网下的车辆配送路径,采用优化 + 调整的两阶段求解方法. 在优化阶段,根据常发拥堵信息,采用遗传算法求解时变取送一体化车辆路径,安排车辆初始配送路径. 在调整阶段,以路段行驶时间为时间间隔,采用滚动更新策略调整车辆配送路线躲避偶发拥堵. 在针对车辆路径调整问题构建了一系列混合整数规划模型的基础上,设计了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倍.

     

  • 图 1  客户及路网信息

    Figure 1.  Customers and road network information

    图 2  求解流程

    Figure 2.  Overview of finding a solution

    图 3  2-opt算法

    Figure 3.  2-opt algorithm

    图 4  插入算法

    Figure 4.  Insertion algorithm

    图 5  测试网络及客户情况

    Figure 5.  Toy network and customers

    图 6  路段行驶时间

    Figure 6.  Link travel time

    图 7  测试网络中的初始车辆配送路线

    Figure 7.  Initial delivery routes in toy network

    图 8  不同干扰频率下的总行驶时间及更新次数

    Figure 8.  Total travel times and number of updates under different interference frequencies

    图 9  不同行驶时间增加量对应的总行驶时间及更新次数

    Figure 9.  Total travel times and number of updates under different increments of travel times

    图 10  不同影响路段数对应的总行驶时间及更新次数

    Figure 10.  Total travel times and number of updates under different numbers of affected links

    表  1  初始车辆配送路线

    Table  1.   Initial delivery routes in a simple network

    车辆编号行驶路线行驶时间/min
    10−n2P1−030
    20−n1E1−035
    下载: 导出CSV

    表  2  算法比较

    Table  2.   Algorithm comparison

    模拟
    次数
    遗传算法2-opt+insertion
    求解时间/s车辆总驶时间/min 求解时间/s车辆总驶时间/min
    1 0.44 792.00 0.10 792.00
    2 0.35 803.00 0.09 803.00
    3 0.39 803.00 0.09 803.00
    4 0.36 792.00 0.09 792.00
    5 0.34 792.00 0.09 792.00
    6 0.34 792.00 0.09 792.00
    7 0.36 800.00 0.09 800.00
    8 0.40 800.00 0.09 800.00
    平均值 0.37 796.75 0.09 796.75
    下载: 导出CSV
  • 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.
  • 加载中
图(10) / 表(2)
计量
  • 文章访问数:  369
  • HTML全文浏览量:  198
  • PDF下载量:  23
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-10-12
  • 修回日期:  2018-03-08
  • 网络出版日期:  2018-05-30
  • 刊出日期:  2019-10-01

目录

    /

    返回文章
    返回