Multi-Objective Robust Optimisation Method for Stochastic Time-Dependent Vehicle Routing Problem
DUAN Zhengyu1, LEI Zengxiang1, SUN Shuo2, YANG Dongyuan1
1. Key Laboratory of Road and Traffic Engineering of the Ministry of Education, Tongji University, Shanghai 201804, China; 2. Shanghai Urban Planning and Design Research Institute, Shanghai 200040, China
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.
HALL R W. The fastest path through a network with random time-dependent travel times[J]. Transportation Science, 1986, 20(3):182-188
[2]
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
[3]
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
[4]
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
[5]
SIM M. Robust optimization[D]. Cambridge:Massachusetts Institute of Technology,2004
[6]
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
[7]
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
[8]
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
[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
[10]
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
[11]
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
[12]
何承,朱扬勇. 城市交通大数据[M]. 上海:上海科学技术出版社,2015:285-300
[13]
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
[14]
谭艳艳. 几种改进的分解类多目标进化算法及其应用[D]. 西安:西安电子科技大学,2013
[15]
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
[16]
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
[17]
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
[18]
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
[19]
段征宇,杨东援,王上. 时间依赖型车辆路径问题的一种改进蚁群算法[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
[20]
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
[21]
SCHAFFER J D. Some experiments in machine learning using vector evaluated genetic algorithms[R]. Nashville:Vanderbilt University,1985
[22]
高媛. 非支配排序遗传算法(NSGA)的研究与应用[D]. 杭州:浙江大学,2006
[23]
万旭,林健良,杨晓伟. 改进的最大-最小蚂蚁算法在有时间窗车辆路径问题中的应用[J]. 计算机集成制造系统,2005,4(4):572-576 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
