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

段征宇; 雷曾翔; 孙硕; 杨东援

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
计量
- 文章访问数: 553
- HTML全文浏览量: 268
- PDF下载量: 49
- 被引次数: 0
出版历程
- 收稿日期: 2017-08-15
- 修回日期: 2017-10-23
- 网络出版日期: 2019-02-23
- 刊出日期: 2019-06-01

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%.
- 车辆路径问题 /
- 随机时变路网 /
- 鲁棒优化 /
- 多目标优化 /
- 蚁群算法
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

HTML全文

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

Figure 1. Distribution of R201’s Pareto optimal solutions

下载: 全尺寸图片幻灯片

表 1 各类路段的行程车速

Table 1. Travel speed of various links

路段类型	时段
路段类型	1	2	3	4
1	1.00	3.00	1.20	2.80
2	1.80	2.20	1.60	2.40
3	1.60	2.40	1.80	2.20
4	1.40	2.60	1.00	3.00
5	1.20	2.80	1.40	2.60

下载: 导出CSV

表 2 STDVRP算例的计算结果

Table 2. Computational results of STDVRP instances

算例	算法	边界解	车辆数/辆	最坏行程时间	最坏等待时间	期望行程时间	期望等待时间
C101	NSGA-II	A	18	1 319.93	4 007.66	1 271.38	4 040.33
	NSGA-II	B	12	1 482.58	778.83	1 282.24	912.98
	NSACO	A	12	826.78	1 024.67	703.85	1 083.16
	NSACO	B	12	826.78	1 024.67	703.85	1 083.16
C201	NSGA-II	A	7	970.18	8 344.81	858.08	8 451.99
	NSGA-II	B	5	999.46	5 415.92	864.21	5 542.61
	NSACO	A	5	617.23	5 032.93	534.08	5 097.59
	NSACO	B	4	1 610.53	1 461.69	1 380.19	1 642.52
R101	NSGA-II	A	20	1 342.00	1 113.83	1 238.72	1 239.63
	NSGA-II	B	16	1 375.66	626.21	1 195.39	778.21
	NSACO	A	18	1 267.96	1 060.74	1 096.56	1 192.29
	NSACO	B	16	1 350.62	653.77	1 183.74	801.94
R201	NSGA-II	A	7	1 206.09	1 630.94	1 120.11	1 721.53
	NSGA-II	B	3	1 385.58	145.18	1 199.96	299.86
	NSACO	A	7	1 087.86	2 507.04	956.45	2 597.12
	NSACO	B	3	1 387.48	206.84	1 201.50	355.61
RC101	NSGA-II	A	16	1 334.95	576.61	1 261.48	666.44
	NSGA-II	B	14	1 350.06	357.83	1 210.61	470.25
	NSACO	A	16	1 337.90	638.40	1 140.44	735.28
	NSACO	B	14	1 371.84	306.04	1 218.40	403.19
RC201	NSGA-II	A	8	1 349.75	2 591.40	1 213.29	2 740.82
	NSGA-II	B	4	1 393.53	741.07	1 244.36	864.97
	NSACO	A	8	1 132.08	3 102.31	969.50	3 201.67
	NSACO	B	4	1 539.07	312.02	1 370.44	438.52

下载: 导出CSV

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

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

算例	边界解	车辆数相对值/%	最坏行程时间相对值/%	期望行程时间相对值/%
C101	A	66.67	62.64	55.36
C101	B	100.00	55.77	54.89
C201	A	71.43	63.62	62.24
C201	B	80.00	161.14	159.71
R101	A	90.00	94.48	88.52
R101	B	100.00	98.18	99.03
R201	A	100.00	90.20	85.39
R201	B	100.00	100.14	100.13
RC101	A	100.00	100.22	90.40
RC101	B	100.00	101.61	100.64
RC201	A	100.00	83.87	79.91
RC201	B	100.00	110.44	110.13
平均	A	88.02	82.51	76.97
平均	B	96.67	104.55	104.09

下载: 导出CSV

参考文献(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

施引文献

附加材料(0)

访问统计