城市动态灾害环境下多种类多目标路径优化算法

doi:10.16265/j.cnki.issn1003-3033.2024.09.1544

中国安全科学学报 ›› 2024, Vol. 34 ›› Issue (9): 217-224.doi: 10.16265/j.cnki.issn1003-3033.2024.09.1544

城市动态灾害环境下多种类多目标路径优化算法

张盈斐¹^,²(), 李航¹^,², 齐玉亮³, 王伟明³, 张海林⁴, 胡小兵¹^,²

¹ 中国民航大学安全科学与工程学院,天津 300300
² 中国民航大学体系安全与智能决策实验室,天津 300300
³ 河北省高速公路京雄筹建处,河北保定 071000
⁴ 北京交科公路勘察设计研究院,北京 100191

收稿日期:2024-03-14 修回日期:2024-06-20 出版日期:2024-09-28
作者简介:
张盈斐 (1995—),女,河南禹州人,博士研究生,主要研究方向为应急管理、智能计算。E-mail: zhangyf9507@163.com。
胡小兵，教授
基金资助:
中央高校基本科研业务费专项资金(3122023034); 中央高校基本科研业务费专项资金(3122019057); 河北省交通运输厅科技项目(JX-202002)

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

ZHANG Yingfei¹^,²(), LI Hang¹^,², QI Yuliang³, WANG Weiming³, ZHANG Hailin⁴, HU Xiaobing¹^,²

¹ College of Safety Science and Engineering, Civil Aviation University of China, Tianjin 300300, China
² Laboratory of System Safety and Intelligent Decisions, Civil Aviation University of China, Tianjin 300300, China
³ Hebei Province Highway Jingxiong Preparatory Office, Baoding Hebei 071000, China
⁴ Jiaoke Transport Consultants Ltd., Beijing 100191, China

Received:2024-03-14 Revised:2024-06-20 Published:2024-09-28

摘要/Abstract

摘要：

为提高城市应对动态灾害的响应能力,针对动态灾害环境中应急车辆行驶路线的规划问题,考虑路径安全度为乘法权重,车辆行驶路径长度和通行时间为加法权重,首先,提出一种动态环境下可同时计算乘法与加法权重的多种类多目标路径优化问题(MCMPOP)的求解模型;其次,通过改进涟漪扩散算法(RSA)求解MCMPOP;然后,为验证算法的有效性,通过510组仿真试验,对比MCMPOP下非支配排序遗传算法(NSGA)-Ⅱ与改进RSA的计算时间与解的质量;最后,选取“7·20”郑州特大暴雨事件数据进行实例验证。结果表明:与NSGA-II相比,改进的RSA可以求解出完整的Pareto最优路径集合,有效保证算法的计算效率和Pareto最优解的质量;可在应急车辆可接受的安全范围内,筛选出行驶路线长度和时间成本较小的Pareto最优路径,为应急车辆提供更多可靠的行驶路线,提高城市的应急管理能力。

关键词: 动态灾害环境, 多种类多目标路径优化问题(MCMPOP), 涟漪扩散算法(RSA), 路线规划, Pareto前沿

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

中图分类号:

张盈斐, 李航, 齐玉亮, 王伟明, 张海林, 胡小兵. 城市动态灾害环境下多种类多目标路径优化算法[J]. 中国安全科学学报, 2024, 34(9): 217-224.

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.

图/表 10

图1

表1

图2

图3

图4

图5

表2

图6

表3

图7

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

城市动态灾害环境下多种类多目标路径优化算法

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 17

相关文章 2

编辑推荐

Metrics

本文评价

[1]	胡小兵, 李佳茹, 刘骋越, 李航, 周航. 一种评估网络结点和链接重要性的改进介数[J]. 中国安全科学学报, 2022, 32(3): 33-40.
[2]	张明空, 胡小兵, 王静爱. 考虑火灾动态扩散过程的高层建筑疏散路径研究[J]. 中国安全科学学报, 2019, 29(3): 32-38.