带时间窗的危险货物车辆路径问题2阶段优化

doi:10.16265/j.cnki.issn1003-3033.2023.12.2080

摘要/Abstract

摘要：

为有效降低危险货物道路运输的风险和成本,针对带时间窗的危险货物车辆路径问题(HMVRPTW),设计2阶段优化方法。首先,根据特征将该问题分解为双目标最短路径问题和带时间窗双目标车辆路径问题(VRP),分别建立数学模型并设计2阶段方法求解,第1阶段采用脉冲算法初筛路径,第2阶段设计针对带时间窗双目标VRP蚁群算法;然后,以9个节点和17条边的测试为例,说明求解过程;最后,以兰州市主城区16个加油站油品配送为例,采用该方法分配运输车辆,计算平均用时为24.38 s,可获得Pareto最优解,而采用多目标遗传算法平均用时为41.05 s。结果表明:所提方法通过初筛路径能够简化问题规模,充分考虑危险货物运输风险变化及时间窗因素,引导蚂蚁在指定搜索空间中寻优,在效率方面较多目标遗传算法具有明显优势。

关键词: 时间窗, 危险货物, 车辆路径问题(VRP), 2阶段优化, 蚁群算法, Pareto最优

Abstract:

In order to effectively reduce the risks and costs of road transportation of hazardous materials, aiming at vehicle routing problem(VRP)for hazardous materials with time windows(HMVRPTW), a two-stage optimization was studied. First of all, according to its characteristics, it was divided into bi-objective shortest path problem and bi-objective VRP with time window. Secondly, the mathematical models were established and two-stage methods were designed to solve them. In the first stage, the pulse algorithm was used to filter the path to obtain the Pareto-optimal path between the distribution center and each demand node. In the second stage, an ant colony algorithm was designed for the bi-objective VRP with time window. Then, taking the test of 9 nodes and 17 edges as an example, the solution process was explained. Finally, taking the oil delivery of 16 gas stations in the main urban area of Lanzhou city as an example, this method calculated an average time of 24.38 seconds to obtain the Pareto-optimal solution for the vehicle scheduling, while using multi-objective genetic algorithm, the average time was 41.05 seconds. The results show that the proposed method simplifies the problem scale through the filtering paths, fully consider the changes in risk and the constraint of time window of hazardous materials transportation, and guides the ants to search for optimization in the specified search space. The proposed method has obvious advantages in efficiency compared to the multi-objective genetic algorithm.

Key words: time window, hazardous material vehicle routing problem(VRP) two-stage optimization, ant colony, Pareto-optimal

柴获, 何瑞春, 韩伟, 贾晓燕, 代存杰. 带时间窗的危险货物车辆路径问题2阶段优化[J]. 中国安全科学学报, 2023, 33(12): 160-166.

CHAI Huo, HE Ruichun, HAN Wei, JIA Xiaoyan, DAI Cunjie. Two-stage optimization of vehicle routing problem for hazardous materials with time windows[J]. China Safety Science Journal, 2023, 33(12): 160-166.

图/表 11

图1

图2

图3

表1

表2

表3

表4

图4

图5

图6

图7

参考文献 16

[1]	任常兴, 吴宗之. 危险品道路安全运输路径优化方法探讨[J]. 中国安全科学学报, 2006, 16(6):129-134.
	REN Changxing, WU Zongzhi. Probe into methods of optimal road transportation routing for hazardous materials[J]. China Safety Science Journal, 2006, 16(9): 129-134.
[2]	TARANTILIS C, KIRANOUDIS C. Using the vehicle routing problem for the transportation of hazardous materials[J]. Operational Research, 2001, 1(1): 67-78. doi: 10.1007/BF02936400
[3]	杨信丰, 李引珍, 何瑞春, 等. 多属性时间依赖网络的城市危险品运输路径优化[J]. 中国安全科学学报, 2012, 22(9): 103-108.
	YANG Xinfeng, LI Yinzhen, HE Ruichun, et al. Route optimization for urban hazardous material transportation in time-dependent networks with multi-attributes[J]. China Safety Science Journal, 2012, 22(9): 103-108.
[4]	ARDJMAND E, YOUNG W, WECKMAN G, et al. Applying genetic algorithm to a new bi-objective stochastic model for transportation, location, and allocation of hazardous materials[J]. Expert Systems with Applications, 2016, 51: 49-58. doi: 10.1016/j.eswa.2015.12.036
[5]	BULA G, PRODHON C, GONZALEZ F, et al. Variable neighborhood search to solve the vehicle routing problem for hazardous materials transportation[J]. Journal of Hazardous Materials, 2017, 324: 472-480. doi: S0304-3894(16)31019-6 pmid: 27876240
[6]	NOROUZI N, SADEGH-AMALNICK M, TAVAKKOLI-MOGHADDAM R. Modified particle swarm optimization in a time-dependent vehicle routing problem: minimizing fuel consumption[J]. Optimization Letters, 2017, 11(1): 121-134. doi: 10.1007/s11590-015-0996-y
[7]	柴获, 何瑞春, 苏江省, 等. 求解双目标带时间窗车辆路径问题的蚁群算法[J]. 交通运输系统工程与信息, 2018, 18(4): 156-162.
	CHAI Huo, HE Ruichun, SU Jiangsheng, et al. An ant colony optimization for the bi-objective vehicle routing problem with time windows on mutilgraph[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(4): 156-162.
[8]	ANDROUTSOPOULOS K, ZOGRAFOS K. A bi-objective time-dependent vehicle routing and scheduling problem for hazardous materials distribution[J]. Euro Journal on Transportation and Logistics, 2012, 1(1/2): 157-183. doi: 10.1007/s13676-012-0004-y
[9]	PRADHANANGA R, TANIGUCHI E, YAMADA T, et al. Bi-objective decision support system for routing and scheduling of hazardous materials[J]. Socio-Economic Planning Sciences, 2014, 48(2): 135-148. doi: 10.1016/j.seps.2014.02.003
[10]	CHAI Huo, HE Ruichun, MA Changxi, et al. Path planning and vehicle scheduling optimization for logistic distribution of hazardous materials in full container load[J]. Discrete Dynamics in Nature and Society, 2017: DOI: 10.1155/2017/9685125.
[11]	袁文燕, 王健, 吴军, 等. 危险化学品车辆路径问题的一个新模型及算法研究[J]. 系统科学与数学, 2017, 37(2): 393-406. doi: 10.12341/jssms13071
	YUAN Wenyan, WANG Jian, WU Jun, et al. A new model of hazardous material vehicle routing problem and its algorithm[J]. Journal of Systems Science and Mathematical Sciences, 2017, 37(2): 393-406. doi: 10.12341/jssms13071
[12]	HOLECZEK N. Analysis of different risk models for the hazardous materials vehicle routing problem in urban areas[J]. Cleaner Environmental Systems, 2021, 2: DOI: 10.1016/j.cesys.2021.100022.
[13]	BATTA R, CHIU S. Optimal obnoxious paths on a network: transportation of hazardous materials[J]. Operations Research, 1988, 36(1): 84-92. doi: 10.1287/opre.36.1.84
[14]	HU Hao, LI Jian, LI Xiang. A credibilistic goal programming model for inventory routing problem with hazardous materials[J]. Soft Computing, 2018, 22(17): 5803-5816. doi: 10.1007/s00500-017-2663-y
[15]	LOZANO L, MEDAGLIA A. On an exact method for the constrained shortest path problem[J]. Computers & Operations Research, 2013, 40(1): 378-384. doi: 10.1016/j.cor.2012.07.008
[16]	DUQUE D, LOZANO L, MEDAGLIA A. An exact method for the biobjective shortest path problem for large-scale road networks[J]. European Journal of Operational Research, 2015, 242(3): 788-797. doi: 10.1016/j.ejor.2014.11.003

路段	长度/km	风险	路段	长度/km	风险
(0,1)	36.56	0.045 6	(2,5)	27.95	0.022 5
(0,3)	9.85	0.021 4	(2,7)	39.18	0.025 2
(0,4)	30.29	0.015 4	(4,6)	27.16	0.018 6
(0,5)	15.82	0.028 6	(4,8)	48.89	0.006 8
(0,6)	9.26	0.005 9	(5,7)	21.26	0.054 6
(1,2)	45.16	0.021 7	(5,8)	36.35	0.003 2
(1,3)	30.36	0.002 0	(6,8)	24.15	0.045 7
(1,4)	45.47	0.008 3	(7,8)	42.65	0.002 2
(2,3)	24.26	0.023 2	—	—	—

需求点d	1	2	4	7	8
需求量 q_d/m³	4.8	6.0	1.5	3.8	7.2
时间窗 [b_d,e_d]	[08:30, 12:00]	[09:00, 13:00]	[08:00, 10:00]	[12:00, 16:00]	[10:00, 18:00]

需求点	出发路径	距离/ km	风险	返回路径	距离/ km
1	0→1	36.56	0.045 6	1→0	36.56
1	0→3→1	40.21	0.023 4	1→0	36.56
2	0→3→2	34.11	0.044 6	2→3→0	34.11
4	0→4	30.29	0.015 4	4→0	30.29
7	0→5→7	37.08	0.083 2	7→5→0	37.08
	0→3→2→7	73.29	0.069 8
	0→6→8→7	76.06	0.053 8
	0→5→8→7	94.82	0.034 0
	0→4→8→7	121.83	0.024 4
8	0→6→8	33.41	0.051 6	8→6→0	33.41
	0→5→8	52.17	0.031 8
	0→4→8	79.18	0.022 2

需求点	需求点	Pareto路径集	距离/km	风险
1	2	1→2	45.16	0.021 7
	4	1→4	45.47	0.008 3
	7	1→0→5→7	73.64	0.128 8
		1→3→0→5→7	77.29	0.106 6
		1→2→7	84.34	0.046 9
		1→4→8→7	137.01	0.017 3
	8	1→0→6→8	69.97	0.097 2
		1→3→0→6→8	73.62	0.075 0
		1→3→0→5→8	92.38	0.055 2
		1→4→8	94.36	0.015 1
2	1	2→1	45.16	0.021 7
	4	2→3→0→4	64.40	0.060 0
	4	2→1→4	90.63	0.030 0
	7	2→7	39.18	0.025 2
	8	2→5→8	64.30	0.025 7
4	1	4→1	45.47	0.008 3
	2	4→0→3→2	64.40	0.060 0
	2	4→1→2	90.63	0.030 0
	7	4→0→5→7	67.37	0.098 6
	7	4→8→7	91.54	0.009 0
	8	4→8	48.89	0.006 8
7	1	7→5→0→1	73.64	0.128 8
		7→5→0→3→1	77.29	0.106 6
		7→2→1	84.34	0.046 9
		7→8→4→1	137.01	0.017 3
	2	7→2	39.18	0.025 2
	4	7→5→0→4	67.37	0.098 6
	4	7→8→4	91.54	0.009 0
	8	7→8	42.65	0.002 2
8	1	8→6→0→1	69.97	0.097 2
		8→6→0→3→1	73.62	0.075 0
		8→5→0→3→1	92.38	0.055 2
		8→4→1	94.36	0.015 1
	2	8→5→2	64.30	0.025 7
	4	8→4	48.89	0.006 8
	7	8→7	42.65	0.002 2