中国安全科学学报

路径编号	路径	目标函数值 (路径长度，路径安全度)	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)	否

路径编号	路径	目标函数值 (路径长度，路径安全度)	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

积水量/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	路径安全度
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
3	—	4 457	—	297.13	—	1
III	460— 444	4	5 614	5 614	374.27	399.37	1	0.9
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
10	—	12 215	—	814.33	—	1
VI	312— 243	11	3 361	3 361	224.07	295.83	1	0.9
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
18	—	5 545	—	369.67	—	1
IX	230— 97	19	3 519	3 519	234.60	242.63	1	0.9
20	—	4 714	—	314.27	—	1
X	464— 117	21	13 496	13 496	899.73	911.4	1	0.9
22	—	13 716	—	914.4	—	1

序号	起终点	路线序号	路径长度/m	行驶时间/s	路径安全度
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
3	—	4 457	—	297.13	—	1
III	460— 444	4	5 614	5 614	374.27	399.37	1	0.9
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
10	—	12 215	—	814.33	—	1
VI	312— 243	11	3 361	3 361	224.07	295.83	1	0.9
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
18	—	5 545	—	369.67	—	1
IX	230— 97	19	3 519	3 519	234.60	242.63	1	0.9
20	—	4 714	—	314.27	—	1
X	464— 117	21	13 496	13 496	899.73	911.4	1	0.9
22	—	13 716	—	914.4	—	1

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

PDF下载

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

中国安全科学学报 | 防灾减灾技术与工程 2024,34(9): 217-224

收起

中国安全科学学报 | 防灾减灾技术与工程 2024, 34(9): 217-224

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

全屏

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

作者信息

¹ 中国民航大学安全科学与工程学院，天津 300300

² 中国民航大学体系安全与智能决策实验室，天津 300300

³ 河北省高速公路京雄筹建处，河北保定 071000

⁴ 北京交科公路勘察设计研究院，北京 100191

张盈斐 (1995—)，女，河南禹州人，博士研究生，主要研究方向为应急管理、智能计算。E-mail：zhangyf9507@163.com。

胡小兵，教授

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

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

Affiliations

¹ 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

出版时间: 2024-09-28 doi: 10.16265/j.cnki.issn1003-3033.2024.09.1544

文章导航

摘要

收起

为提高城市应对动态灾害的响应能力，针对动态灾害环境中应急车辆行驶路线的规划问题，考虑路径安全度为乘法权重，车辆行驶路径长度和通行时间为加法权重，首先，提出一种动态环境下可同时计算乘法与加法权重的多种类多目标路径优化问题(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

引用本文

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

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

正文

收起

0 引言

收起

城市灾害是指由自然、人为因素或两者共同引发的对城市居民生活或城市社会发展造成暂时或长期不良影响的灾害，如火灾、洪水、暴雨和台风等。这些灾害通常具有明显的动态变化特征，包括灾害扩散范围、转移位置和破坏程度等^[1]。当路网环境安全性随灾害影响动态变化时，规划通行时耗短、安全度高的应急车辆的行驶路线十分必要。现阶段，通常结合智能优化算法解决多需求应急车辆的多目标路径优化问题(Multi-objective Path Optimization Problem，MPOP)。例如：Dijkstra算法等智能优化算法^[2-3]等多以加法型权重目标函数解决路线安全度和行驶时间的MPOP，其本质上是单目标路径优化，且多是静态规划，如遇外界动态环境变化需重新规划路线。为提高算法在动态环境的适应性，动态MPOP(Dynamic MPOP，DMPOP)逐渐成为许多研究人员的重点研究对象^[4]。由于DMPOP的目标函数、约束条件或参数都可能会随时间变化而改变，要求算法必须能够及时跟踪变化的Pareto最优前沿。因此，基于预测的方法是求解DMPOP的主流方法^[5]。由于时间扩充图所需存储量较大，故粒子群算法、A^*算法、非支配排序遗传算法(Non-dominated Sorting Genetic Algorithm-II，NSGA-II)等其他启发式算法被引入^[6-7]。为尽可能多地找到分布在Pareto前沿的最优解，需要不断调整非确定性方法的参数^[8-9]。通常这类算法只能求出Pareto非占优解或找到部分Pareto前沿，而非完整的Pareto最优前沿，也无法保证路线的最优性^[10]。

涟漪扩散算法(Ripple Spreading Algorithm，RSA)是一种确定性算法，可以求得一对一MPOP的完整Pareto前沿。与传统智能算法相比，RSA具有良好的扩展性。将其扩展到多对多的DMPOP问题时，不需要进行一对一的循环式计算，实现运算一次即可得到所有起点到终点的最优路径^[11]。鉴于此，笔者拟假设每一时刻的动态灾害数据由其他专业灾害演化模型模拟所得，以寻找完整的Pareto前沿为重点，考虑路径长度和行驶时间为加法权目标函数的同时，增加路径安全度为乘法权目标函数，提出一种解决动态环境下多对多的多种类MPOP(Multi-category MPOP，MCMPOP)的算法，以期为动态灾害环境中应急车辆的行进路线提供合理方案。

1 MCMPOP问题描述

收起

1.1 MCMPOP数学模型

假设在路网G(V，E)中，V为N个结点的集合，E为L条链接的集合，在邻接矩阵A(i，j)中，A(i，j) >0表示结点i和结点j之间存在链接，A(i，j)=0表示结点间不存在链接。现实中对目标函数的要求可归为相乘型目标和相加型目标2类。对于G中的每条链接都有n_p个乘法权

m i j 1

，

m i j 2

，…，

m i j n p

(m_ij∈[0，1])，有n_q个非负加法权

c i j 1

，

c i j 2

，…，

c i j n q

。对于G中的起点s和终点d，那么，MCMPOP的数学模型可描述为：

m i n A (i ， j) · [c i j 1 ， c i j 2 ， … ， c i j n q ， - l n (m i j 1) ，

- l n (m i j 2) ， … ， - l n (m i j n p)]

满 足 ∑ j = 1 N A (i ， j) - ∑ j = 1 N A (j ， i) = 1 ， i = s 0 ， 其 他 - 1 ， i = d

(1)

A (i ， j) ∈ {0，1} ， ∀ i ， j ∈ V

假设第k条路径P_k=[1，2，…，h]含有h个结点，表示从起点1到结点h的路径，对于路径P_k上结点i，t时刻路径P_k的目标函数值可由下式计算：

(2) $\begin{array}{c} f\left(P_{k}，t\right)=\left[\left.\sum_{i=1}^{h-1} c_{i(i+1)}^{1}\right|_{t}，\left.\sum_{i=1}^{h-1} c_{i(i+1)}^{2}\right|_{t}，\cdots，\left.\sum_{i=1}^{h-1} c_{i(i+1)}^{n_{q}}\right|_{t}\right. \\ \left.\left.\prod_{i=1}^{h-1} m_{i(i+1)}^{1}\right|_{t}，\left.\prod_{i=1}^{h-1} m_{i(i+1)}^{2}\right|_{t}，\cdots，\left.\prod_{i=1}^{h-1} m_{i(i+1)}^{n_{p}}\right|_{t}\right] \end{array}$

1.2 目标函数

考虑随时间变化的外部动态灾害环境对路径规划的影响，以路长、行驶时间、路径安全度为优化目标，对路网中起点到终点的路径进行多种类多目标路径规划。

1.2.1 路径长度

路段长度

c i (i + 1) 1

一般不随时间变化(一条路径由多条路段组成)。考虑动态环境对路网链接通达性的影响，路径P_k的长度可由路径长度函数f₁计算得到：

(3)

f 1 (P k ， t) = ∑ i = 1 h - 1 A (i ， i + 1) c i (i + 1) 1

1.2.2 行驶时间

由于外部动态环境的影响，在t时刻，车辆行驶速度受到路段积水量

c i (i + 1) 2

|_t的影响，其通过路径P_k的行驶时间可由行驶时间函数f₂计算得到：

(4)

f 2 (P k ， t) = ∑ i = 1 h - 1 A t (i ， i + 1) c i (i + 1) 1 c i (i + 1) 2 t v t ， A t ≠ 0 f 2 (P k ， t - 1) + W k ， A t = 0

式中：v_t为车辆在路段[i，i+1]的行驶速度；W_k为车辆在路径P_k行驶过程中需要等待的时间。

1.2.3 路径安全度

由于外界动态灾害的影响，路径安全度会随时间而变化。t时刻，降水量对路径P_k中路段[i，i+1]的路段安全度

m i (i + 1) t

会随着积水量上升而减小，整条路径P_k的路径安全度等同各路段安全度的乘积，由路径安全度函数f₃计算得到：

(5)

f 3 (P k ， t) = ∏ i = 1 h - 1 A t (i ， i + 1) × m i (i + 1) t

t时刻路网的通达状态由动力学环境f_D给出：

(6)

A t (i ， i + 1) ， c i (i + 1) 2 ， m i (i + 1) t = f D (P k ， t)

图1为动态环境中某一时刻MCMPOP的应急车辆路线规划场景。结点1是救援点(起点)，结点6是需求点(终点)。以最小化路径长度和最大化路径安全度为目标，那么从起点1到终点6的所有路径见表1，经过筛选，路径1和5是该路网在相加型和相乘型目标函数下的Pareto最优解。

2 MCMPOP算法设计

收起

2.1 RSA算法原理

RSA是一种通过模拟自然涟漪扩散的形式来模拟路径搜索和求解过程。由于涟漪在所有方向上的扩散速度相同，因此，涟漪总是最先到达离它最近的结点^[12]。在初始路网中激活一个起点的涟漪，涟漪以相同速度向四周扩散，并激活相邻结点的涟漪。设置结点的状态S_R(i)有未激活、激活和锁定3种(即S_R(i)=0，1，2)，链接的状态有通达和不通达2种。链接的通达性受外部动态灾害环境影响，当灾害影响路段通行时，该链接状态为不通达。当与某个结点相连的链接状态为通达时，该结点可被激活并产生新的涟漪；当其链接状态为不通达时，该结点处于锁定状态；如果此时其他涟漪已经到达该结点，需等待链接通达后该结点涟漪方可扩散；当结点未被任何涟漪激活但其所在的链接状态通达时，结点为未激活状态。

2.2 基于RSA的MCMPOP

为更好地求解MCMPOP，首先，将一对一RSA的MPOP算法改进为一对多RSA的MCMPOP，然后将其改进为多对多RSA的MCMPOP。令所有起点涟漪在路网中并行扩散，增加判断当前路径Pareto占优的条件，并相应改变涟漪激活和算法终止条件。基于多对多RSA的MCMPOP，只需运算一次就可以得到所有起点到所有终点的Pareto最优路径，得到完整的Pareto前沿。

基于Pareto支配的概念，这里给出非支配涟漪(Pareto Non-Dominated Ripple，PNDR)的表述：

定义1:假设t时刻结点i的涟漪r记录了从起点扩散到结点i的路径P_r，该路径的第n个目标函数为f_n(P_r)，n=1，2，…，n_p+n_q。假设涟漪R(i)在没有到达结点i时已有k个涟漪已经到达(即，结点i已搜索到k条路径)，那么对于结点i来说，如果P_r和P_k(k∈R)不满足Pareto支配的概念，则称涟漪r为一个PNDR，有P_r∈Ω_PNDR。

在路网G(V，E)中，对于起点s和终点d，结点初始状态为S_R(s)=0，S_R(d)=0。R(s)为起点s的涟漪半径；v为涟漪扩散速度，涟漪在整个路网中的扩散过程为：①路网初始化。设置路网中的起点、终点以及涟漪扩散速度。②激活所有起点s，使每一个起点以恒定的速度向四周扩散。记录起点的第k条路径信息，并存储在路径集合{P_s_，_k}中。③判断终点的PNDR数量。如果每个终点都至少获得一个PNDR，则回溯路径，得到Pareto最优路径{P_s_，_k}。否则执行下一步；④增加时间单位；⑤根据动态灾害环境的影响计算路网中各个链接的通达性；⑥对于不通达的链接，若链接上的其中一个结点的状态为S_R(i)=1，此时将该结点的状态变更为S_R(i)=2;⑦对于通达的链接，结点i的状态为S_R(i)=1，增加其涟漪半径R(i)=R(i)+v。如果

c i j 1

≤R(i)，并且结点i的涟漪r_k如果是结点j的一个PNDR，那么结点j就可被激活，产生一个半径为R(j)= R(i)-

c i j 1

的涟漪。否则，结点j不产生涟漪，更新Ω_PNDR(j)、对应的P_s_，_k以及目标函数的f_n (P_s_，_k，t)值。⑧根据定义1，删除Ω_PNDR中旧的PNDR，如果这些PNDR有后继涟漪在路网上扩散，那么锁定这些涟漪。⑨如果与结点i相邻的所有结点均已被激活，更改结点i的状态为S_R(i)=0，回到步骤 ②。图2给出了多对多RSA的MCMPOP算法的流程。

2.3 计算复杂度

在图G(V，E)中，有N个结点的集合V和L条链接的集合E，平均每个结点拥有L/N条边。假设MCMPOP含有n_p个乘法权和n_q个加法权目标函数，一个结点及其产生的涟漪需要n₁个时间单位从激活状态转换为非激活状态，计算结束后每个结点的涟漪平均数目为n₂。那么只有处于激活状态的涟漪执行以下3个运算步骤： ①在每个单位时间内，一个涟漪需要执行(2×n₁×L/N)次计算； ②目标函数值f_n (P_k，t)，n=1，2，…，n_p+n_q; ③判断结点N_i的涟漪r_k是否是结点N_j处的PNDR。只有在结点产生新涟漪时执行步骤 ②和 ③，则一个涟漪需要执行((1+n₂)×(n_p+n_q)×L/N)个计算步骤。那么，运行一次算法需要执行[2×n₁+(1+n₂)×(n_p+n_q)]×n₂×L个计算步骤。

在大规模路网中，每个结点产生的涟漪数目远大于n₁，所以算法的计算复杂度为O((n_p+n_q)×L×

n 12

)。当路网中起点个数为n₃时，算法的计算复杂度为O((n_p+n_q)×n₃×L×

n 22

)。

由于MCMPOP是NP-完全问题^[13]，随着问题规模增大，Pareto最优路径的数目也会呈现指数级增长。相较于传统多目标优化算法，虽然多对多RSA的MCMPOP算法使得路网中每个结点产生涟漪的数目相应增长，但仍能保证相对高的计算效率并求出所有的Pareto最优解。

3 MCMPOP算法及案例仿真试验

收起

3.1 算法对比试验

以非循环计算方式进行一对多的MCMPOP试验对比。以路径长度、行驶时间及路径安全度分别为加法权及乘法权目标函数，将NSGA-II^[14]的参数设置如下：种群大小为100，迭代次数为30，变异概率为0.15，交叉概率为1。由于算法的随机性，其求解结果可能会遗漏或得到错误的Pareto最优路径(即该路径由NSGA-II计算得到，但不在Pareto最优路径集合之中)。路网中结点数量分别为10²、11²、12²、13²、14²、15²、16²、17²、18²、19²、20²、25²、30²、35²、40²、45²、50²，共17种。每种结点数量给定一个随机的外界危险环境，路网有均匀和随机2种分布模式，每种模式下随机选取15组起终点数据。每种算法执行510次计算，最终对比2种算法的计算时间(Computer Time，CT)、Pareto最优解的数量(The Number of Pareto optimal Solutions，NPS)及正确Pareto最优解的数量(The Correct NPS，CNPS)。一般地，具有较好计算效率和有效性的算法，其CT值相对较小，NPS和CNPS的数量应相对较高。

取510次试验结果的均值，得到算法对比结果如图3所示，横坐标轴数值表示路网规模大小。取路网结点数量为50²的1组随机路网试验，绘制起终点编号为26—2 177的MCMPOP规划结果，如图4所示。其中，黑色圆点表示改进的RSA求解的完整的Pareto前沿，深灰色三角形表示NSGA-II求解的Pareto非占优解，灰色方形表示NAGA-II算法与RSA重合的解。分析试验结果可得如下结论： ①随着路网规模的扩大，2种算法的CT值也在相应升高。但基于RSA的MCMPOP的CT值总是小于NAGA-II，且这种差距在大规模路网中更加明显。 ②NSGA-II在部分试验中得到的NPS多于改进的RSA，但NSGA-II的解集中含有一些错误解。 ③以CNPS为比较对象，NSGA-II得到的CNPS数量总是少于改进的RSA，且随着路网规模的扩大，这种差距也更加明显。 ④与RSA能够求出所有Pareto最优解相比，NSGA-II仅能求得部分Pareto最优解或Pareto非占优解。 ⑤在所有510组对比试验中，发现NSGA-II所找到的正确Pareto最优解，都包含在RSA找到的Pareto最优解之中。

综上，通过对比2种算法在求解速度和求解质量的差异，可以看出，改进RSA的计算效率和求解的有效性方面明显优于NSGA-II。

3.2 案例仿真试验

在真实场景中，以路径长度、行驶时间以及路径安全度为目标函数，主要从以下2方面对比算法的应用效果： ①验证NSGA-II和基于RSA的MCMPOP方法在多对多路径优化问题中CNPS的解的质量差异； ②对比多对多RSA单目标与基于RSA的MCMPOP方法规划应急车辆救援路线的结果，验证后者方法规划救援路线的合理性。

根据河南省郑州市“7·20”特大暴雨事件情况设立试验，试验路网包括556个结点和971条链接。设置10个救援点(起点，编号分别为1、195、230、280、312、337、379、415、460、464)和9个需求点(终点，编号分别为85、87、97、117、234、243、251、338、444)^[15]，及85块不同程度的积水区。路网结构及其起点终点如图5所示，三角形表示起点，方形表示终点，圆形表示普通结点，不同颜色的链接表示不同积水程度的路段。根据郑州市“7·20”特大暴雨72h的降水数据，设置正常降雨(0~33)h和特大暴雨(34~72)h 这2种降水情景。为了使试验数据和真实值更接近，设置不同路段的每小时积水量有[3 10 30 50] mm共4种，暴雨场景下不同路段的每小时积水量有[30 80 200 400] mm 4种，设置每10 h路径排水80~100 mm^[16]。另外，考虑路段积水程度对车辆行驶速度的影响^[17]，设置车辆行驶速度与路段积水量的关系见表2。

图6为路网受到降水影响时，NSGA-II和基于RSA的MCMPOP在多对多应急车辆行驶路线规划的试验结果。可以看到，与NSGA-II相比，RSA的计算效率明显优于NSGA-II。与RSA计算的Pareto解的数量相比，NSGA-II计算得到的CNPS较少。试验中，应用多对多RSA的MCMPOP得到的应急车辆行驶路线不仅耗时短，而且CNPS较高。

为验证算法规划的应急车辆行驶路线在实际救援过程的应用效果，选取正常降雨场景(t=10h)、暴雨场景(t=70h)的仿真结果进行对比分析。在t=10h时，每个起点到9个终点的Pareto最优路径都只有1条，共90条路径。在路径安全度有保障的前提下，决策者一般选择路径长度值最小的路径。在t=70h时，由于各路段的安全度都有所降低，所有起点到终点的Pareto最优路径共有193条。表3对比了t=10h和t=70h时的10个起点到同一行政区或最近终点的车辆应急路线规划结果的异同。

与t=10h的救援路线相比，t=70h时算法为应急车辆规划的路线大都绕过了危险路段，或者让应急车辆依然按照原路行进，但该路线的路径安全度却比t=10h相比有所减小。具体地：

1) 由于起点1—终点35周围的路段积水量并不严重甚至无积水路段，因此，I-1-35(第I对起终点的起点1与终点35的路径的路径长度、行驶时间和路径安全度值在2个时段并未发生改变。

2) t=70h时，除终点35外其他8个终点附近均有不同程度的积水。因此，如果应急车辆仍然按照t=10h的路线行驶，虽然路径的路径长度值不变，但其行驶时间值增大、路径安全度值减小。与其他Pareto路径相比，这类路径非常容易被其他路径所支配，从而退出Pareto最优路径集合，稳定性较差。这类路线序号有2、4、6、11、17、19和21。

3) 外部动态环境变化的越剧烈，Pareto最优路径的数量也会越多。表3中序号为V和VII的起终点组合，在多目标规划过程中，在t=70h的原路径已经不在Pareto最优集合中，RSA算法为415—243和195—97规划了其他Pareto最优路径。

4) t=70h的多目标路径集合未将最短路径列入Pareto最优路径集合中。说明当路段安全度降低较快时，多数起终点之间的路线都会更改，甚至脱离Pareto最优路径集合。

起点195的多目标路线比较如图7所示，从Pareto最优解集中筛选出最适合当前灾害环境的应急车辆行驶路线。以起点195为例，它到9个终点的路径一共有18条，路径在各个目标的分值可以通过该条路径的边界距中心点的距离远近表示，此时应急决策者可以通过增设目标函数的权重进行快速抉择。

4 结论

收起

1) 基于RSA求解MCMPOP，可以同时考虑多个乘法型和加法型的目标函数，实现运行一次算法就完成多起点到多终点的路线规划。

2) 与NSGA-II相比，基于RSA的MCMPOP算法不仅可以找到完整的Pareto最优解，而且，能够有效保障算法的计算效率和有效性。

3) 针对城市暴雨情景，使用基于RSA的MCMPOP方法为动态灾害环境中的应急车辆规划救援路线，为决策者根据外部动态灾害环境的发展选择符合实际需求的救援路线提供了更多可能。

基金

收起

中央高校基本科研业务费专项资金(3122023034)
中央高校基本科研业务费专项资金(3122019057)
河北省交通运输厅科技项目(JX-202002)

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

唐少虎, 朱伟, 程光, 等. 暴雨内涝下城市道路交通系统安全韧性评估[J]. 中国安全科学学报, 2022, 32(7):143-150.

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.

[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.

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.

[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

, ENGELBRECHT

A P

. Dynamic multi-objective optimization using PSO[M]. Berlin Heidelberg: Springer, 2013: 147-188.

[8]

张宇, 郭晶, 周激流. 动态变异遗传算法[J]. 电子科技大学学报, 2002, 6(3):234-239.

ZHANG

, 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.

Weixi

. Research on the multi-objective evolutionary algorithms based on gradient crowding diversity maintenance strategy[D]. Wuhan: Wuhan University of Technology, 2008.

[10]

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]

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]

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.

[13]

SERAFINI

. Some considerations about computational complexity for multi-objective combinatorial problems[C]. Recent Advances and Historical Development of Vector Optimization, 1987: 222-232.

[14]

DEB

, PRATAP

, AGARWAL

, 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. https://www.hntv.tv/yc/article/1/1418042890119757826

[16]

郑州市水利局. 郑州都市区排水(雨水)防涝综合规划(2015—2030年)[R], 2015.

[17]

中华人民共和国国务院. 中华人民共和国道路交通安全法实施条例[L].2017-10-07.

2024年第34卷第9期

PDF下载

195

引用本文

BibTeX

文章信息

doi: 10.16265/j.cnki.issn1003-3033.2024.09.1544

接收时间：2024-03-14
首发时间：2025-07-09
出版时间：2024-09-28

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2024-03-14
修回日期：2024-06-20

基金

中央高校基本科研业务费专项资金(3122023034)

中央高校基本科研业务费专项资金(3122019057)

河北省交通运输厅科技项目(JX-202002)

作者信息

¹ 中国民航大学安全科学与工程学院，天津 300300

² 中国民航大学体系安全与智能决策实验室，天津 300300

³ 河北省高速公路京雄筹建处，河北保定 071000

⁴ 北京交科公路勘察设计研究院，北京 100191

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/zgaqkxxb/CN/10.16265/j.cnki.issn1003-3033.2024.09.1544

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT

路径编号	路径	目标函数值 (路径长度，路径安全度)	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)	否

路径
编号

路径

目标函数值
(路径长度，路径安全度)

Pareto
最优?

1-3-4-6

(7，0.480)

是

1-3-6

(8，0.360)

否

1-3-5-6

(8，0.378)

否

1-2-3-6

(9，0.420)

否

1-2-3-4-6

(8，0.560)

是

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

积水量/mm

车辆行驶速度/
(m·s^-1)

路段安
全度

[0 200)

[200 400)

0.9

[400 600)

0.8

[600 800)

0.7

[800 1000)

0.6

[1000 +∞)

序号	起终点	路线序号	路径长度/m	行驶时间/s	路径安全度
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
3	—	4 457	—	297.13	—	1
III	460— 444	4	5 614	5 614	374.27	399.37	1	0.9
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
10	—	12 215	—	814.33	—	1
VI	312— 243	11	3 361	3 361	224.07	295.83	1	0.9
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
18	—	5 545	—	369.67	—	1
IX	230— 97	19	3 519	3 519	234.60	242.63	1	0.9
20	—	4 714	—	314.27	—	1
X	464— 117	21	13 496	13 496	899.73	911.4	1	0.9
22	—	13 716	—	914.4	—	1

序
号

起
终点

路线
序号

路径长度/m

行驶时间/s

路径安全度

t=
10 h

t=
70 h

t=
10 h

t=
70 h

t=
10 h

t=
70 h

1—35

8 349

556.6

337—
338

902

60.13

90.2

0.9

—

4 457

—

297.13

—

III

460—
444

5 614

374.27

399.37

0.9

—

5 619

—

374.60

—

379—
338

5 167

344.47

366.90

0.81

—

5 168

366.90

391.77

—

0.9

—

8 532

568.80

—

415—
243

11 746

11 965

783.07

813.53

0.9

—

12 215

—

814.33

—

312—
243

3 361

224.07

295.83

0.9

—

4 791

—

319.40

—

VII

195—
97

4 400

6 466

293.33

446.67

0.9

—

6 535

—

435.67

—

6 464

—

454.57

—

0.81

—

6 530

—

443.37

—

0.9

VIII

280—
251

5 409

360.60

414.83

0.9

—

5 545

—

369.67

—

230—
97

3 519

234.60

242.63

0.9

—

4 714

—

314.27

—

464—
117

13 496

899.73

911.4

0.9

—

13 716

—

914.4

—