• ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus
  • Indexed by Core Journals of China, Chinese S&T Journal Citation Reports
  • Chinese S&T Journal Citation Reports
  • Chinese Science Citation Database
Volume 54 Issue 3
Jun.  2019
Turn off MathJax
Article Contents
Journal of Southwest Jiaotong University  > 2019  >  54(3): 565-572.
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
shu

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

doi: 10.3969/j.issn.0258-2724.20170617
  • Received Date: 15 Aug 2017
  • Rev Recd Date: 23 Oct 2017
    • Available Online: 23 Feb 2019
  • Publish Date: 01 Jun 2019
    Abstract
  • The vehicle routing problem (VRP) is a core issue of distribution logistics. In order to improve the timeliness of deliveries, a multi-objective robust optimisation model based on the minimax criterion was proposed for the stochastic time-dependent vehicle routing problem (STDVRP) with hard time windows, considering both the stochastic and time-varying nature of link travel times. A non-dominated sorting ant colony optimisation (NSACO) algorithm was designed to solve this multi-objective optimisation model for the STDVRP. The NSACO algorithm was compared with the non-dominated sorting genetic algorithm II (NSGA-II) through computational instances. The results show that for the Pareto boundary of the minimised number of vehicles, the average number of vehicles for NSACO is 3.33% less than that of NSGA-II, and for the Pareto boundary of the minimised worst travel time, the average worst travel time for NSACO is 17.49% less than that of NSGA-II.

     

    • FullText(HTML)
  • loading
    • References(26)
  • 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
    • Relative Articles
    • Supplements(0)
    • Cited By
  • 加载中

Catalog

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

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

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(1)  / Tables(3)

    Get Citation
    PDF
    XML
    Article views(573) PDF downloads(52) Cited by()
    Proportional views
    Related

    Copyright © 2009 Journal of Southwest Jiaotong University

    Address: RM449 & 451, Administrative Building, Xipu Campus, Southwest Jiaotong University Western Hi-tech Zone, Chengdu, Sichuan 611756, P. R. China

    Tel: 028-66367562Fax: 028-66366552Email: xbz@home.swjtu.edu.cn

    Supported by: Beijing Renhe Information Technology Co. Ltd  support: info@rhhz.net

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return