Vehicle scheduling for hazardous materials transportation based on dissimilar paths

doi:10.16265/j.cnki.issn1003-3033.2023.09.1503

Abstract

Abstract:

In order to effectively mitigate potential risks during the simultaneous transportation of hazardous materials by multiple vehicles, this study addressed the problem of simultaneous multi-vehicle transportation on distinct paths between 2 nodes within a hazardous materials transportation network. A method for calculating safe departure time intervals of vehicles was proposed to select paths and allocate vehicles. A mathematical model was established for simultaneously scheduling multiple vehicles to travel on different paths through path selection and vehicle allocation. A multiobjective optimization algorithm based on NSGA-II was designed for solving the proposed model. Using an example of transporting 10 hazardous material vehicles in an 8-node and 13-edge hazardous materials transportation network, the proposed method yielded 13 transportation schemes satisfying single-trip risk constraints and 15 transportation schemes satisfying total risk constraints. A comparative analysis was performed on transportation risk, distance, and time under different risk constraints. The results indicate that compared with the total risk constraints, the single-trip risk constraints are more stringent, which is suitable for road authorities to select safe transportation paths, while total risk constraints are suitable for carrier enterprises to make vehicle scheduling decisions.

Key words: hazardous materials transportation, vehicle scheduling, dissimilar paths, multi-objective optimization, non-dominated sorting genetic algorithm II(NSGA-II)

CHAI Huo, HE Ruichun, JIA Xiaoyan, DAI Cunjie. Vehicle scheduling for hazardous materials transportation based on dissimilar paths[J]. China Safety Science Journal, 2023, 33(9): 181-188.

Figures/Tables 10

Fig.1

Fig.2

Fig.3

Fig.4

Tab.1

Tab.2

Fig.5

Tab.3

Fig.6

Tab.4

References 23

[1]	王艾迪, 邢莹莹, 张诗雯, 等. 基于关联规则的危险品公路运输事故风险因素研究[J]. 中国安全科学学报, 2023, 33(6):159-165. doi: 10.16265/j.cnki.issn1003-3033.2023.06.1618
	WANG Aidi, XING Yingying, ZHANG Shiwen, et al. Research on risk factors of hazardous material highway transport accidents based on association rules[J]. China Safety Science Journal, 2023, 33(6):159-165. doi: 10.16265/j.cnki.issn1003-3033.2023.06.1618
[2]	柴获, 何瑞春, 马昌喜, 等. 危险品运输车辆路径问题的多目标优化[J]. 中国安全科学学报, 2015, 25(10):84-90.
	CHAI Huo, HE Ruichun, MA Changxi, et al. Multi-objective optimization of hazardous materials transportation vehicle route problem[J]. China Safety Science Journal, 2015, 25(10):84-90.
[3]	柴获. 危险品道路运输车辆时空协调调度优化研究[D]. 兰州: 兰州交通大学, 2018.
	CHAI Huo. Research on vehicle scheduling optimization for hazardous materials road transportation on the basis of space-Time coordination[D]. Lanzhou: Lanzhou Jiaotong University, 2018.
[4]	李引珍, 何瑞春, 郭耀煌, 等. 多目标网络相异路径的Pareto解及其遗传算法[J]. 系统工程学报, 2008, 23(3):264-268.
	LI Yinzhen, HE Ruichun, GUO Yaohuang, et al. Pareto solution set and its genetic algorithm for multi-objective network dissimilar paths[J]. Journal of Systems Engineering, 2008, 23(3):264-268.
[5]	CHONDROGIANNIS T, BOUROS P, GAMPER J, et al. Finding k -dissimilar paths with minimum collective length[C]. Proceedings of the 26^th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2018:404-407.
[6]	MARTÍ R, VELARDE J, DUARTE A. Heuristics for the bi-objective path dissimilarity problem[J]. Computers & Operations Research, 2009, 36(11):2905-2912. doi: 10.1016/j.cor.2009.01.003
[7]	PUSHAK Y, HARE W, LUCET Y. Multiple-path selection for new highway alignments using discrete algorithms[J]. European Journal of Operational Research, 2016, 248(2):415-427. doi: 10.1016/j.ejor.2015.07.039
[8]	LIU Linzhong, MU Haibo, YANG Juhua. Simulated annealing based GRASP for Pareto-optimal dissimilar paths problem[J]. Soft Computing, 2017, 21(18):5457-5473. doi: 10.1007/s00500-016-2137-7
[9]	MOGHANNI A, PASCOAL M, GODINHO M. Finding shortest and dissimilar paths[J]. International Transactions in Operational Research, 2022, 29(3):1573-1601. doi: 10.1111/itor.v29.3
[10]	ZAJAC S. On a two-phase solution approach for the bi-objective k-dissimilar vehicle routing problem[J]. Journal of Heuristics, 2018, 24(3):515-550. doi: 10.1007/s10732-017-9341-1
[11]	TIKANI H, SETAK M, DEMIR E. Multi-objective periodic cash transportation problem with path dissimilarity and arrival time variation[J]. Expert Systems with Applications, 2021, 164: DOI: 10.1016/j.eswa.2020.114015.
[12]	AKGÜN V, ERKUT E, BATTA R. On finding dissimilar paths[J]. European Journal of Operational Research, 2000, 121(2):232-246. doi: 10.1016/S0377-2217(99)00214-3
[13]	ROUPHAIL N, RANJITHAN S, DESSOUKI W, et al. A decision support system for dynamic pre-trip route planning[M]. Virginia: ACSE, 1995:325-329.
[14]	LOMBARD K, CHURCH R. The gateway shortest path problem: generating alternative routes for a corridor location problem[J]. Geographical systems, 1993, 1(1):25-45.
[15]	KUBY M, XU Zhongyi, XIE Xiaodong. A minimax method for finding the k best "differentiated" paths[J]. Geographical Analysis, 1997, 29(4):298-313. doi: 10.1111/gean.1997.29.issue-4
[16]	DELL'OLMO P, GENTILI M, SCOZZARI A. On finding dissimilar Pareto-optimal paths[J]. European Journal of Operational Research, 2005, 162(1):70-82. doi: 10.1016/j.ejor.2003.10.033
[17]	KANG Yingying, BATTA R, KWON C. Generalized route planning model for hazardous material transportation with VaR and equity considerations[J]. Computers & Operations Research, 2014, 43:237-247. doi: 10.1016/j.cor.2013.09.015
[18]	TALARICO L, SÖRENSEN K, SPRINGAEL J. The k-dissimilar vehicle routing problem[J]. European Journal of Operational Research, 2015, 244(1):129-140. doi: 10.1016/j.ejor.2015.01.019
[19]	柴获, 何瑞春, 代存杰, 等. 考虑时空相异的危险品运输车辆安全调度[J]. 交通运输工程学报, 2019, 19(3):145-156.
	CHAI Huo, HE Ruichun, DAI Cunjie, et al. Safty scheduling of hazardous materials transportation vehicle considering spatio-temporal dissimilarity[J]. Journal of Traffic and Transportation Engineering, 2019, 19(3):145-156.
[20]	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
[21]	JENSEN M. Reducing the run-time complexity of multiobjective EAs: the NSGA-II and other algorithms[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(5):503-515. doi: 10.1109/TEVC.2003.817234
[22]	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
[23]	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·h^-1)	路段	运输距离/km	运输风险	行驶速度/(km·h^-1)
1→2	5.66	0.001 1	35	4→6	10.00	0.000 8	45
1→3	8.00	0.001 5	30	4→8	20.88	0.004 0	40
1→4	17.09	0.001 8	45	5→7	16.28	0.001 2	40
2→3	5.66	0.000 2	30	6→7	8.94	0.000 5	30
2→5	12.37	0.000 9	40	6→8	12.00	0.003 5	30
3→4	10.00	0.000 3	30	7→8	8.94	0.002 2	35
3→6	16.00	0.003 5	30

路径编号	路径	运输距离/km	运输风险	Δt_k/ min
1	1→2→3→4→6→7→8	49.20	0.005 1	5
2	1→2→3→4→8	42.19	0.005 6	5
3	1→2→5→7→8	43.24	0.005 4	4
4	1→3→6→8	36.00	0.008 5	5
5	1→4→6→7→8	44.98	0.005 3	5
6	1→4→8	37.97	0.005 8	4

车辆	路径	最早出发		最晚出发		车辆	路径	最早出发		最晚出发
车辆	路径	出发	到达	出发	到达	车辆	路径	出发	到达	出发	到达
1	1→2→5→7→8	09:06	10:14	10:44	11:52	6	1→4→8	09:14	10:08	10:50	11:44
2	1→2→5→7→8	09:10	10:18	10:48	11:56	7	1→4→8	09:18	10:12	10:54	11:48
3	1→2→5→7→8	09:14	10:22	10:52	12:00	8	1→4→8	09:22	10:16	10:58	11:52
4	1→4→8	09:06	10:00	10:42	11:36	9	1→4→8	09:26	10:20	11:02	11:56
5	1→4→8	09:10	10:04	10:46	11:40	10	1→4→8	09:30	10:24	11:06	12:00

车辆	路径	最早出发		最晚出发		车辆	路径	最早出发		最晚出发
车辆	路径	出发	到达	出发	到达	车辆	路径	出发	到达	出发	到达
1	1→2→5→7→8	09:06	10:14	10:44	11:52	6	1→4→8	09:10	10:04	10:50	11:44
2	1→2→5→7→8	09:10	10:18	10:48	11:56	7	1→4→8	09:14	10:08	10:54	11:48
3	1→2→5→7→8	09:14	10:22	10:52	12:00	8	1→4→8	09:18	10:12	10:58	11:52
4	1→3→6→8	09:06	10:18	10:48	12:00	9	1→4→8	09:22	10:16	11:02	11:56
5	1→4→8	09:06	10:00	10:46	11:40	10	1→4→8	09:26	10:20	11:06	12:00