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

DUAN Zhengyu; LEI Zengxiang; SUN Shuo; YANG Dongyuan

doi:10.3969/j.issn.0258-2724.20170617

Volume 54 Issue 3

Jun. 2019

Turn off MathJax

Article Contents

Abstract

References

Journal of Southwest Jiaotong University > 2019 > 54(3): 565-572.

WANG Yonghong, SANG Songkui, LIU Xueying, ZHANG Mingyi, BAI Xiaoyu. Numerical Simulation of Particle Flow Characteristics of Jacked Pile Penetration in Laminated Clay Soil[J]. Journal of Southwest Jiaotong University, 2021, 56(6): 1250-1259. doi: 10.3969/j.issn.0258-2724.20200072

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

Citation:

PDF( 655 KB)

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

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.
- vehicle routing problem,
- stochastic time-dependent network,
- robust optimisation,
- multi-objective optimisation,
- ant colony optimisation algorithm

FullText(HTML)

References(26)

References

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

[1]	WANG Jiayong, XIAO Chengzhi, HE Chenxi. Numerical Analysis of Effect of Jacked Pile on Performance of Buried Pipes[J]. Journal of Southwest Jiaotong University, 2018, 53(2): 322-329. doi: 10.3969/j.issn.0258-2724.2018.02.014
[2]	HUANG Qiang, YE Bin, HUANG Hongwei, ZHANG Dongmei, ZHANG Feng. Comparison of 2D and 3D Dynamic Responses of Saturated Soft Soil due to Metro Train Load[J]. Journal of Southwest Jiaotong University, 2017, 30(6): 1121-1129. doi: 10.3969/j.issn.0258-2724.2017.06.012
[3]	XIAO Yongjie, CHEN Fuquan, DONG Yizhi. Model Test and Numerical Simulation of Penetration Process of Sleeve for Cast-in-Place Piles Driven by Vibratory Hammers[J]. Journal of Southwest Jiaotong University, 2017, 30(4): 705-714. doi: 10.3969/j.issn.0258-2724.2017.04.008
[4]	DENG Weili, XIAO Nan, YONG Yuan. Numerical Simulation of Monitoring Wheel-Rail Contact Conditions Using Ultrasonic Technology[J]. Journal of Southwest Jiaotong University, 2014, 27(6): 1073-1077. doi: 10.3969/j.issn.0258-2724.2014.06.020
[5]	WANG Weihua, LIAO Haili, LI Mingshui. Numerical Simulation of Wind-Induced Roof Snow Distributions Based on Time Variable Boundary[J]. Journal of Southwest Jiaotong University, 2013, 26(5): 851-856,967. doi: 10.3969/j.issn.0258-2724.2013.05.011
[6]	GUO Liqun, WANG Lei, CHEN Fuquan. Soil Plugging Effect of Sleeves Driven by High Frequency Hammers[J]. Journal of Southwest Jiaotong University, 2013, 26(1): 47-54. doi: 10.3969/j.issn.0258-2724.2013.01.008
[7]	CHEN Xiao'an, SHANG Fujun, SONG Shuncheng. Numerical Simulation of Temperature Distribution of Induction Plasma Torch in Preparation of Superfine Powder[J]. Journal of Southwest Jiaotong University, 2011, 24(2): 271-276. doi: 10.3969/j.issn.0258-2724.2011.02.016
[8]	CHENG Zhi-Jiang, BARRIERE T, LIU Bao-Sheng, GELIN J C. Experiment and Numerical Simulation of Micro-injection Moulding[J]. Journal of Southwest Jiaotong University, 2010, 23(4): 635-638. doi: 10. 3969/ j. issn. 0258-2724.
[9]	CAO Jixing, CHEN Qiu, ZHANG Jiping. Simulation of SHPB Test on Concrete and Uniformity of Stresses[J]. Journal of Southwest Jiaotong University, 2008, 21(1): 67-70.
[10]	WANG Heshun, CHEN Cichang, WANG Jinnuo. Numerical Simulation of Face Flow Field for Dry Gas Seal[J]. Journal of Southwest Jiaotong University, 2007, 20(5): 568-573.
[11]	CAO Xiaojun, ZHANG Jichun, LU Helin, GUO Jianqun. Numerical Simulation of Ground Vibration Effects in Shallow Tunneling Blasting[J]. Journal of Southwest Jiaotong University, 2006, 19(6): 680-684.
[12]	WUBo, GAO Bo, LUOJian-jun. Numerical Simulation of Reinforcing Effect of Horizontal Drilling Jet-Grouting Pegs on Shenzhen Metro Tunnel between Stations[J]. Journal of Southwest Jiaotong University, 2004, 17(5): 605-608.
[13]	TONG Bing, ZHU Bing, ZHOU Ben-kuan. Numerical Simulation of Velocity Field of Flow Around Square Cylinder[J]. Journal of Southwest Jiaotong University, 2002, 15(2): 121-124.
[14]	CHENG Qian-gong, HUHou-tian. Discrete Element Simulation of Full-Course Kinematics of Rocky High-Speed Landslide[J]. Journal of Southwest Jiaotong University, 2000, 13(1): 18-22.
[15]	Lei Bo　, Liu Yingqing. Simulation of Pressure on Overline Bridge Due to High-Speed Train Passage[J]. Journal of Southwest Jiaotong University, 1999, 12(3): 259-263.
[17]	Zhu Bing, Guan Baoshu, ZhengDaofang. Numerical Simulation of Longitudinal Ventilation of Long Highway Tunnel[J]. Journal of Southwest Jiaotong University, 1999, 12(2): 133-137.

Supplements(0)

Cited By

Cited by

Periodical cited type(6)

1.	施静怡，吴能森，刘强. 静压桩在成层地基中挤土效应的可视化研究. 河南城建学院学报. 2024(02): 20-26 .
2.	马登辉，韩迅，蔡正银，关云飞. 静压桩的桩侧土压力分布规律数值分析. 岩土力学. 2024(06): 1863-1872 .
3.	时静. 水库施工静压桩挤土效应数值模拟分析. 海河水利. 2023(01): 100-102 .
4.	管鸣睿. 基于离散元颗粒接触模型的桩网复合地基土体力学改良影响研究. 地下水. 2023(03): 143-146 .
5.	卫少波. 软土地基中静压桩沉桩的力学特性研究. 价值工程. 2023(21): 90-92 .
6.	许永亮，吴泽坤. 层状地基静压PHC管桩连续贯入有限元模拟. 科技和产业. 2023(18): 226-231 .

Other cited types(11)

Proportional views

Proportional views

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

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

Figures(1) / Tables(3)

Get Citation

PDF

XML

Article views(659) PDF downloads(56)