Two-stage optimization of vehicle routing problem for hazardous materials with time windows

doi:10.16265/j.cnki.issn1003-3033.2023.12.2080

Abstract

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

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.

Figures/Tables 11

Fig.1

Fig.2

Fig.3

Tab.1

Tab.2

Tab.3

Tab.4

Fig.4

Fig.5

Fig.6

Fig.7

References 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