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

随机时变车辆路径问题的多目标鲁棒优化方法

段征宇 雷曾翔 孙硕 杨东援

段征宇, 雷曾翔, 孙硕, 杨东援. 随机时变车辆路径问题的多目标鲁棒优化方法[J]. 西南交通大学学报, 2019, 54(3): 565-572. doi: 10.3969/j.issn.0258-2724.20170617
引用本文: 段征宇, 雷曾翔, 孙硕, 杨东援. 随机时变车辆路径问题的多目标鲁棒优化方法[J]. 西南交通大学学报, 2019, 54(3): 565-572. doi: 10.3969/j.issn.0258-2724.20170617
DUAN Zhengyu, LEI Zengxiang, SUN Shuo, YANG Dongyuan. Multi-Objective Robust Optimisation Method for Stochastic Time-Dependent Vehicle Routing Problem[J]. Journal of Southwest Jiaotong University, 2019, 54(3): 565-572. doi: 10.3969/j.issn.0258-2724.20170617
Citation: DUAN Zhengyu, LEI Zengxiang, SUN Shuo, YANG Dongyuan. Multi-Objective Robust Optimisation Method for Stochastic Time-Dependent Vehicle Routing Problem[J]. Journal of Southwest Jiaotong University, 2019, 54(3): 565-572. doi: 10.3969/j.issn.0258-2724.20170617

随机时变车辆路径问题的多目标鲁棒优化方法

doi: 10.3969/j.issn.0258-2724.20170617
基金项目: 国家自然科学基金项目(71001079)
详细信息
    作者简介:

    段征宇(1978—),男,副教授,研究方向为交通规划与管理,E-mail:d_zy@163.com

  • 中图分类号: U492.22

Multi-Objective Robust Optimisation Method for Stochastic Time-Dependent Vehicle Routing Problem

  • 摘要: 车辆路径问题 (vehicle routing problem,VRP) 是物流配送的核心问题之一,为了提高物流配送的时效性,在传统VRP模型的基础上,同时考虑了路网交通状态的时变性和随机性,基于最小最大准则,提出了一种带硬时间窗的随机时变车辆路径问题 (stochastic time-dependent vehicle routing problem,STDVRP) 的多目标鲁棒优化模型. 设计了一种非支配排序蚁群算法 (non-dominated sorting ant colony optimisation,NSACO),求解STDVRP多目标优化模型;通过测试算例,对比分析了NSACO算法与改进型非支配排序遗传算法 (non-dominated sorting genetic algorithm II,NSGA-II). 研究结果表明:对于车辆数最小的Pareto边界解,NSACO算法的平均车辆数比NSGA-II算法小3.33%;对于最坏行程时间最小的Pareto边界解,NSACO算法的平均最坏行程时间比NSGA-II算法小17.49%.

     

  • 图 1  R201算例的Pareto最优解的分布

    Figure 1.  Distribution of R201’s Pareto optimal solutions

    表  1  各类路段的行程车速

    Table  1.   Travel speed of various links

    路段类型时段
    1234
    11.003.001.202.80
    21.802.201.602.40
    31.602.401.802.20
    41.402.601.003.00
    51.202.801.402.60
    下载: 导出CSV

    表  2  STDVRP算例的计算结果

    Table  2.   Computational results of STDVRP instances

    算例算法边界解车辆数/辆最坏行程时间最坏等待时间期望行程时间期望等待时间
    C101NSGA-IIA181 319.934 007.661 271.384 040.33
    B121 482.58778.831 282.24912.98
    NSACOA12826.781 024.67703.851 083.16
    B12826.781 024.67703.851 083.16
    C201NSGA-IIA7970.188 344.81858.088 451.99
    B5999.465 415.92864.215 542.61
    NSACOA5617.235 032.93534.085 097.59
    B41 610.531 461.691 380.191 642.52
    R101NSGA-IIA201 342.001 113.831 238.721 239.63
    B161 375.66626.211 195.39778.21
    NSACOA181 267.961 060.741 096.561 192.29
    B161 350.62653.771 183.74801.94
    R201NSGA-IIA71 206.091 630.941 120.111 721.53
    B31 385.58145.181 199.96299.86
    NSACOA71 087.862 507.04956.452 597.12
    B31 387.48206.841 201.50355.61
    RC101NSGA-IIA161 334.95576.611 261.48666.44
    B141 350.06357.831 210.61470.25
    NSACOA161 337.90638.401 140.44735.28
    B141 371.84306.041 218.40403.19
    RC201NSGA-IIA81 349.752 591.401 213.292 740.82
    B41 393.53741.071 244.36864.97
    NSACOA81 132.083 102.31969.503 201.67
    B41 539.07312.021 370.44438.52
    下载: 导出CSV

    表  3  NSACO算法最优解的相对值

    Table  3.   Relative values of NSACO algorithm’s optimal solutions

    算例边界解车辆数
    相对值/%
    最坏行程时
    间相对值/%
    期望行程时
    间相对值/%
    C101A66.6762.6455.36
    B100.0055.7754.89
    C201A71.4363.6262.24
    B80.00161.14159.71
    R101A90.0094.4888.52
    B100.0098.1899.03
    R201A100.0090.2085.39
    B100.00100.14100.13
    RC101A100.00100.2290.40
    B100.00101.61100.64
    RC201A100.0083.8779.91
    B100.00110.44110.13
    平均A88.0282.5176.97
    B96.67104.55104.09
    下载: 导出CSV
  • HALL R W. The fastest path through a network with random time-dependent travel times[J]. Transportation Science, 1986, 20(3): 182-188. doi: 10.1287/trsc.20.3.182
    MILLER-HOOKS E D, MAHMASSANI H S. Least expected time paths in stochastic,time-varying transportation networks[J]. Transportation Science, 2000, 34(2): 198-215. doi: 10.1287/trsc.34.2.198.12304
    WELLMAN M P, FORD M, LARSON K. Path planning under time-dependent uncertainty[C]//Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. San Francisco: Morgan Kaufmann Publishers Inc., 1995: 532-539
    HUANG H, GAO S. Optimal paths in dynamic networks with dependent random link travel times[J]. Transportation Research Part B:Methodological, 2012, 46(5): 579-598. doi: 10.1016/j.trb.2012.01.005
    SIM M. Robust optimization[D]. Cambridge: Massachusetts Institute of Technology, 2004
    SUN Shichao, DUAN Zhengyu, SUN Shuo, et al. How to find the optimal paths in stochastic time-dependent transportation networks[C]//17th International Conference on Intelligent Transportation Systems. Qingdao: IEEE, 2014: 2348-2353
    SUN Shichao, DUAN Zhengyu, YANG Dongyuan. Optimal paths planning in dynamic transportation networks with random link travel times[J]. Journal of Central South University, 2014, 21(4): 1616-1623. doi: 10.1007/s11771-014-2103-4
    LECLUYSE C, VAN WOENSEL T, PEREMANS H. Vehicle routing with stochastic time-dependent travel times[J]. 4OR - A Quarterly Journal of Operations Research, 2009, 7(4): 363-377. doi: 10.1007/s10288-009-0097-9
    NAHUM O E, HADAS Y. Developing a model for the stochastic time-dependent vehicle-routing problem[C]// International Conference on Computers & Industrial Engineering. Troyes: IEEE, 2009: 118-123
    NAHUM O E, HADAS Y. A comparison of two algorithms for the stochastic time-dependent vehicle-routing problem[C]//Proceedings of the Transportation Research Board 89th Annual Meeting. Washington, D. C., USA: Ttansportation Research Board, 2010: 1-18
    GENDREAU M, JABALI O, REI W. 50th anniversary invited article-future research directions in stochastic vehicle routing[J]. Transportation Science, 2016, 50(4): 1163-1173. doi: 10.1287/trsc.2016.0709
    何承, 朱扬勇. 城市交通大数据[M]. 上海: 上海科学技术出版社, 2015: 285-300
    ICHOUA S, GENDREAU M, POTVIN J Y. Vehicle dispatching with time-dependent travel times[J]. European Journal of Operational Research, 2003, 144(2): 379-396. doi: 10.1016/S0377-2217(02)00147-9
    谭艳艳. 几种改进的分解类多目标进化算法及其应用[D]. 西安: 西安电子科技大学, 2013
    DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. doi: 10.1109/4235.996017
    OMBUKI B, ROSS B J, HANSHAR F. Multi-objective genetic algorithms for vehicle routing problem with time windows[J]. Applied Intelligence, 2006, 24(1): 17-30. doi: 10.1007/s10489-006-6926-z
    JEMAI J, ZEKRI M, MELLOULI K. An NSGA-II algorithm for the green vehicle routing problem[C]// European Conference on Evolutionary Computation in Combinatorial Optimization. Málaga: Springer Berlin Heidelberg, 2012: 37-48
    DONATI A V, MONTEMANNI R, CASAGRANDE N, et al. Time dependent vehicle routing problem with a multi ant colony system[J]. European Journal of Operational Research, 2008, 185(3): 1174-1191. doi: 10.1016/j.ejor.2006.06.047
    段征宇,杨东援,王上. 时间依赖型车辆路径问题的一种改进蚁群算法[J]. 控制理论与应用,2010,27(11): 1557-1563.

    DUAN Zhengyu, YANG Dongyuan, WANG Shang. Improved ant colony optimization algorithm for time-dependent vehicle routing problem[J]. Control Theory & Applications, 2010, 27(11): 1557-1563.
    ZHANG T, CHAOVALITWONGSE W A, ZHANG Y. Integrated ant colony and tabu search approach for time dependent vehicle routing problems with simultaneous pickup and delivery[J]. Journal of Combinatorial Optimization, 2014, 28(1): 288-309. doi: 10.1007/s10878-014-9741-1
    SCHAFFER J D. Some experiments in machine learning using vector evaluated genetic algorithms[R]. Nashville: Vanderbilt University, 1985
    高媛. 非支配排序遗传算法(NSGA)的研究与应用[D]. 杭州: 浙江大学, 2006
    万旭,林健良,杨晓伟. 改进的最大-最小蚂蚁算法在有时间窗车辆路径问题中的应用[J]. 计算机集成制造系统,2005,4(4): 572-576. doi: 10.3969/j.issn.1006-5911.2005.04.022

    WAN Xu, LIN Jianliang, YANG Xiaowei. Improved MMAS for vehicle routing problem with time window[J]. Computer Integrated Manufacturing Systems, 2005, 4(4): 572-576. doi: 10.3969/j.issn.1006-5911.2005.04.022
    李士勇, 陈永强, 李研. 蚁群算法及其应用[M]. 哈尔滨: 哈尔滨工业大学出版社, 2004: 26-33
    STÜTZLE T, HOOS H H. MAX-MIN ant system[J]. Future Generation Computer Systems, 2000, 16(8): 889-914. doi: 10.1016/S0167-739X(00)00043-1
    SOLOMON M M. Benchmark problems and solutions [EB/OL]. [2016-07-02]. http://w.cba.neu.edu/~msolomon/home.htm
  • 加载中
图(1) / 表(3)
计量
  • 文章访问数:  558
  • HTML全文浏览量:  270
  • PDF下载量:  50
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-08-15
  • 修回日期:  2017-10-23
  • 网络出版日期:  2019-02-23
  • 刊出日期:  2019-06-01

目录

    /

    返回文章
    返回