Multi-category multi-objective path optimization algorithm in urban dynamic disaster environments

doi:10.16265/j.cnki.issn1003-3033.2024.09.1544

Abstract

Abstract:

To improve urban response capabilities in dealing with dynamic disasters, a MCMPOP was proposed for planning emergency vehicle paths in dynamic disaster environments. This model considered path safety as a multiplicative weight and vehicle path length and travel time as additive weights. Then, MCMPOP was addressed by improving the RSA. To verify the effectiveness of the improved RSA in solving the MCMPOP, 510 simulation experiments were conducted comparing the computer time and solution quality of the Non-dominated Sorting Genetic Algorithm(NSGA)-Ⅱ and the improved RSA. Furthermore, "7·20" Zhengzhou rainstorm event was selected as a case study to validate the model. The results show that, compared to the NSGA-II, the improved RSA can find a complete set of Pareto optimal paths, effectively ensuring the optimality and computational efficiency of the algorithm. By using RSA to solve MCMPOP, it is possible to successfully select Pareto optimal paths with the shortest travel path lengths and the lowest time costs within the acceptable path safety range for emergency vehicles, providing more reliable routes for emergency vehicles and enhancing the urban emergency management capabilities.

Key words: dynamic disaster environment, multi-category multi-objective path optimization problem (MCMPOP), ripple spreading algorithm (RSA), path planning, Pareto front

CLC Number:

ZHANG Yingfei, LI Hang, QI Yuliang, WANG Weiming, ZHANG Hailin, HU Xiaobing. Multi-category multi-objective path optimization algorithm in urban dynamic disaster environments[J]. China Safety Science Journal, 2024, 34(9): 217-224.

Figures/Tables 10

Fig.1

Table 1

Fig.2

Fig.3

Fig.4

Fig.5

Table 2

Fig.6

Table 3

Fig.7

References 17

[1]	唐少虎, 朱伟, 程光, 等. 暴雨内涝下城市道路交通系统安全韧性评估[J]. 中国安全科学学报, 2022, 32(7):143-150. doi: 10.16265/j.cnki.issn1003-3033.2022.07.1391
	TANG Shaohu, ZHU Wei, CHENG Guang, et al. Safety resilience assessment of urban road traffic system under rainstorm waterlogging[J]. China Safety Science Journal, 2022, 32(7): 143-150. doi: 10.16265/j.cnki.issn1003-3033.2022.07.1391
[2]	孙一凡. 考虑脆弱性的应急救援路线双目标规划与优选研究[D]. 石家庄: 石家庄铁道大学, 2022.
	SUN Yifan. Research on bi-objective planning and optimization of emergency rescue route considering vulnerability[D]. Shijiazhuang: Shijiazhuang Tiedao University, 2022.
[3]	安敏, 滕明月, 安慧, 等. 农村突发公共卫生事件应急医疗设施选址研究[J]. 中国安全科学学报, 2023, 33(1):198-205. doi: 10.16265/j.cnki.issn1003-3033.2023.01.0137
	AN Min, TENG Mingyue, AN Hui, et al. Study on site selection of emergency medical facilities for rural public health emergencies[J]. China Safety Science Journal, 2023, 33(1): 198-205. doi: 10.16265/j.cnki.issn1003-3033.2023.01.0137
[4]	刘若辰, 李建霞, 刘静, 等. 动态多目标优化研究综述[J]. 计算机学报, 2020, 43(7):1246-1278.
	LIU Ruochen, LI Jianxia, LIU Jing, et al. A survey on dynamic multi-objective optimization[J]. Chinese Journal of Computers, 2020, 43(7): 1246-1278.
[5]	GUO Renyong, HUANG Haijun. A mobile lattice gas model for simulating pedestrian evacuation[J]. Physica A: Statistical Mechanics and its Applications, 2008, 387(2): 580-586.
[6]	STEWART B S, WHITE C C. Multi-objective A[J]. Journal of the ACM, 1991, 38(4): 775-814.
[7]	HELBIG M, ENGELBRECHT A P. Dynamic multi-objective optimization using PSO[M]. Berlin Heidelberg: Springer, 2013: 147-188.
[8]	张宇, 郭晶, 周激流. 动态变异遗传算法[J]. 电子科技大学学报, 2002, 6(3):234-239.
	ZHANG Yu, GUO Jing, ZHOU Jiliu. Dynamic mutation genetic algorithm[J]. Journal of University of Electronic Science and Technology of China, 2002, 6(3): 234-239.
[9]	祁薇喜. 基于梯度拥挤度的多样性保持策略的 MOEAs研究[D]. 武汉: 武汉理工大学, 2008.
	QI Weixi. Research on the multi-objective evolutionary algorithms based on gradient crowding diversity maintenance strategy[D]. Wuhan: Wuhan University of Technology, 2008.
[10]	HU Xiaobing, LI Hang, ZHOU Jun, et al. Finding all Pareto optimal paths for dynamical multi-objective path optimization problems[C]. 2018 IEEE Symposium Series on Computational Intelligence (SSCI), 2018: 965-972.
[11]	HU Xiaobing, GU Shenghao, ZHANG Chi, et al. Finding all Pareto optimal paths by simulating ripple relay race in multi-objective networks[J]. Swarm and Evolutionary Computation, 2021, 64(1): 21-31.
[12]	HU Xiaobing, WANG Ming, LEESON M S, et al. Deterministic agent-based path optimization by mimicking the spreading of ripples[J]. Evolutionary Computation, 2016, 24(2): 319-346. doi: 10.1162/EVCO_a_00156 pmid: 26066805
[13]	SERAFINI P. Some considerations about computational complexity for multi-objective combinatorial problems[C]. Recent Advances and Historical Development of Vector Optimization, 1987: 222-232.
[14]	DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2020, 6(2): 182-197.
[15]	王婷. 专家发布郑州市暴雨灾情安全隐患和居民所需救助分布图[EB/OL].(2021-07-22). https://www.hntv.tv/yc/article/1/1418042890119757826.
[16]	郑州市水利局. 郑州都市区排水(雨水)防涝综合规划(2015—2030年)[R], 2015.
[17]	中华人民共和国国务院. 中华人民共和国道路交通安全法实施条例[L].2017-10-07.

路径编号	路径	目标函数值 (路径长度,路径安全度)	Pareto 最优?
1	1-3-4-6	(7,0.480)	是
2	1-3-6	(8,0.360)	否
3	1-3-5-6	(8,0.378)	否
4	1-2-3-6	(9,0.420)	否
5	1-2-3-4-6	(8,0.560)	是
6	1-2-3-5-6	(9,0.441)	否

积水量/mm	车辆行驶速度/ (m·s^-1)	路段安全度
[0 200)	15	1
[200 400)	10	0.9
[400 600)	5	0.8
[600 800)	2	0.7
[800 1000)	1	0.6
[1000 +∞)	0	0

序号	起终点	路线序号	路径长度/m		行驶时间/s		路径安全度
序号	起终点	路线序号	t= 10 h	t= 70 h	t= 10 h	t= 70 h	t= 10 h	t= 70 h
I	1—35	1	8 349	8 349	556.6	556.6	1	1
II	337— 338	2	902	902	60.13	90.2	1	0.9
II	337— 338	3	—	4 457	—	297.13	—	1
III	460— 444	4	5 614	5 614	374.27	399.37	1	0.9
III	460— 444	5	—	5 619	—	374.60	—	1
IV	379— 338	6	5 167	5 167	344.47	366.90	1	0.81
		7	—	5 168	366.90	391.77	—	0.9
		8	—	8 532	568.80	568.80	—	1
V	415— 243	9	11 746	11 965	783.07	813.53	1	0.9
V	415— 243	10	—	12 215	—	814.33	—	1
VI	312— 243	11	3 361	3 361	224.07	295.83	1	0.9
VI	312— 243	12	—	4 791	—	319.40	—	1
VII	195— 97	13	4 400	6 466	293.33	446.67	1	0.9
		14	—	6 535	—	435.67	—	1
		15	—	6 464	—	454.57	—	0.81
		16	—	6 530	—	443.37	—	0.9
VIII	280— 251	17	5 409	5 409	360.60	414.83	1	0.9
VIII	280— 251	18	—	5 545	—	369.67	—	1
IX	230— 97	19	3 519	3 519	234.60	242.63	1	0.9
IX	230— 97	20	—	4 714	—	314.27	—	1
X	464— 117	21	13 496	13 496	899.73	911.4	1	0.9
X	464— 117	22	—	13 716	—	914.4	—	1