安全疏散路线规划算法

本文重点研究紧急情况下的智能疏散路线规划问题，包括自然和人力资源灾难以及流行病灾难，例如COVID-19大流行。

本研究的目的是快速为社区生成一条疏散路线，以便受害者尽快疏散到安全地区。 疏散路线规划问题需要确定合适的路线，并为每条路线分配特定数量的受害者。 本文将问题表述为最大流量问题，并提出基于最大流量算法的二分搜索算法，是一种社区智能优化疏散路线规划算法。

此外，该公式是一个非线性优化问题，因为每条路线的建议疏散时间是分配给该路线的受害者数量的凸非线性函数。 最后，数值算例和Matlab仿真不仅证明了算法的有效性，而且算法复杂度低、精度高。 该研究结果为疏散路线规划的非线性模型提供了实用的解决方案，将广泛应用于人类社会和机器人路径规划方案。

1、简介

疏散是应急管理响应阶段的重点工作。 对于任何公共安全事件，特别是在全球防控COVID-19的过程中，将受害者和潜在受害者从受害地点疏散至安全区域已成为当务之急[1]。 在人员疏散过程中，人们需要做出决策或处理一系列子问题作为应急响应阶段的关键策略，包括预测灾害影响演变、划分疏散区域、发布疏散指令、估算疏散交通需求、 并确定疏散计划。 然后，必须引导疏散人员到邻近的疏散路线，并且必须更新交通信号以有效疏散交通[2]。 人们根据实际情况确定疏散方案。 也就是说，根据交通状况选择合适的交通方式，将疏散人数分配到各条疏散路线上，是疏散问题的核心问题。 有效的疏散计划可以减少灾害损失，特别是大规模人员伤亡的发生[3]。

疏散计划的目的是为社区建立有序和协调的疏散路线程序。 这可以适用于可能需要从家中疏散到避难所或隔离区的不同类型的紧急情况。 对于台风、洪水、火山、海啸、龙卷风、家庭火灾等自然和人力资源灾难紧急情况，可以应用疏散预案将人员从家中疏散到避难所。 对于诸如COVID-19之类的流行病灾难，可以应用拟议的计划将受影响的人及时从家中疏散到隔离区。 对于不同的社区，有必要识别可能发生的常见危险并确定适当的疏散路线。

区域疏散是指在一定时间内将人员从危险地区转移到安全地区的过程。 区域疏散研究涉及疏散区域的划分、疏散交通需求的估算以及疏散计划的制定[4,5,6]。 社区疏散是指将社区人口从危险区域疏散到安全区域的问题，是区域性疏散的一种。 随着人力资源的增加和自然灾害的增加，政府建立了许多避难所以应对各种灾害。 主要目的是在突发事件发生时，将受灾地区的灾民迅速转移至避难场所，减少灾害造成的损失[7]。 在本文中，我们将基于社区的疏散路线规划问题表述为最大流量问题，这是一个经典的网络流量问题。 该方案将确定从社区到避难所的最佳疏散路线，并为每条路线分配具体数量的受害者，以便所有受害者都可以转移到目的地区域。 我们的模型与经典最大流量公式的主要区别在于，我们的模型是非线性模型，其中每条路线的建议疏散时间是分配给该路线的受害者数量的凸非线性函数。 这种非线性给求解模型带来了挑战。 我们提出了一种基于经典最大流求解方法的二分搜索算法，它可以快速为所提出的模型生成解决方案。

紧急疏散研究最早出现于20世纪60年代，以提出和讨论紧急疏散的概念和框架的形式[8]。 随后，紧急疏散问题引起了众多研究者的关注。 主要研究方法分为微观模型研究和宏观模型研究。 微观模型关注疏散个体的行为、心理和相互影响。 分析了这些因素对疏散路径选择和疏散效果评价的影响。 主要的微观模型有概率模型、元胞自动机模型、社会力模型、疏散模拟模型等。 宏观模型将疏散人群视为一个群体，利用优化模型方法求解疏散路径规划问题的疏散时间下界，从宏观角度规划整个疏散路线和方案。

本文基于宏模型算法对应急疏散路径规划进行研究。 假设不同路径不交叉，考虑人群密度与疏散速度的非线性关系，建立非线性模型，给出多项式时间逼近算法。 论文的主要贡献如下。 (1) 我们将疏散人员视为一个群体，并将问题表述为优化模型。 (2) 我们假设任意两条道路之间不存在相互影响； 一条道路上的交通状况不会影响另一条道路上的交通状况。 给出了基于网络流的近似算法来求解模型。 (3)从理论上分析了所提算法的复杂度，并通过仿真实验证明了算法的有效性。

2、相关工作

2.1. 疏散路径问题的宏观模型

宏观模型研究可以研究疏散路径规划的模型和算法。 一个好的疏散路径规划模型和算法可以给出更好的疏散规划方案，有效缩短疏散时间。 Hamacher [9]详细回顾了疏散问题的宏观模型，并介绍了几种基于网络流的模型。 例如，利用最小闸门成本动态网络流模型来估计每个疏散个体的平均疏散时间； 采用最大动态流量和通用最大动态流量模型计算给定时限内的最大疏散人数； 最快流法（QFM）用于估计疏散一定数量人员的最短时间[10]。 大多数这些模型都假设行程时间是一个固定常数。 如果考虑人群密度与疏散时间之间的非线性关系，模型的复杂度将大大增加[11]。 本文处理非线性关系的方法是用近似线性函数代替非线性关系。

从宏观疏散模型的求解方法和算法来看，可分为基于线性规划求解最优疏散方案的多项式算法和基于非线性规划的各种启发式算法[12,13,14,15] ]。 第一种方法主要利用网络流法，特别是动态网络流法，给出各种疏散问题的多项式算法。 动态网络[16]定义在有向图G=(V,E)上，其中顶点集V包含源点source、端点汇和中间点集。 每条弧(x,y)∈E都有一个非负的容量uxy和一个非负的传输时间uxy。 两个经典的动态网络流问题是最大动态流问题（MDFP）和快速流问题（QFP）。 MDFP是指在给定时间限制T下，汇点到端点的动态流量。QFP是指将预定量的流量从源点移动到端点[17]。 Burkard [18]提出了第一个针对单源点和单端点情况下的 QFP 问题的强多项式算法。 Hoppe 和 Tardos [19] 针对具有固定数量的源点和端点的疏散问题给出了多项式算法。 对于多源点、多端点的QFP疏散问题，他们首先使用二分搜索法给出最优时间T的上界，然后给出了通过多源多端汇的QFP多项式算法： 椭球法[20]。

除了动态网络流方法外，许多研究还利用经典的网络流方法，如最小短路算法、最小成本流算法、最大流算法来解决疏散路径优化问题。 Dunn和Newton[21]采用最大流量法来解决疏散路径分配问题，旨在将疏散人群从危险区到安全区的路网容量范围内尽可能转移到最优路径上。 Yamada[22]应用最小成本流问题来分配疏散交通路径，并提出最短疏散计划（SEP），旨在最小化所有人员疏散到指定避难所的总行程。 因此，根据这个优化目标，交通网络中的每辆车都会选择距离它最近的区域的出口进行疏散。 然而，在复杂的交通网络中，这样的分配规则很容易造成交通拥堵。 在Cova[23]提出的基于车道的疏散网络流模型中，建立了扩展的最小成本流模型，以防止交叉口冲突并限制交叉口，同时最小化总行驶距离。 最后，模型输出每个路口可能的路线图。

综上所述，大多数研究者将疏散问题描述为具有容量约束的节点和边的网络流图G(V,E)，其中一些节点称为源点，每个源点都有一定数量的疏散人员； 有些节点称为端点，每个端点可以容纳一定数量的疏散人员。 图中的边缘代表疏散通道。 疏散问题是通过在每条疏散路径上分配合理数量的人员，使总疏散时间最小化，将所有人员疏散到目的地。 利用网络流理论解决问题的优点在于将疏散问题转化为经典的网络流问题，可以利用成熟的多项式网络流算法进行求解，方便有效。 然而网络流问题一般只能解决线性规划问题。 上述文章只能解决线性问题； 即模型中无法考虑人群密度与疏散时间之间可能存在的非线性关系。 因此，该模型无法反映一些疏散交通现象，例如因交通拥堵而减速等。

2.2. 非线性疏散规划

疏散问题的非线性规划主要考虑人群密度与疏散速度之间的非线性关系。 目前，还没有解决疏散问题非线性规划的多项式算法，只有各种启发式算法。 Pursals [24]考虑了当人群移动速度受到人群密度影响时的建筑物疏散。 首先，参考Nelson和McLennan对紧急情况下人群运动速度的分析，给出了人群疏散时间与每个出口人群数量之间的凸函数关系[25]。 该函数与出口的长度和宽度、进入出口前人群所占据的面积以及正常情况下人群的行走速度有关。 那么，反函数就是疏散特定人数所需时间的函数。 本文对所有出口的疏散函数的反函数进行求和，得到疏散总数与疏散时间的函数关系。 因此，给定疏散总人数K，可以通过函数M求出疏散所需的时间。同时，Carey[26]使用分段线性函数来近似疏散时间与疏散人数之间的非线性关系。 人们并建立了一个线性模型来解决它。

如前所述，文献中有两种解决疏散问题的方法。 一是将问题建模为非线性规划，并设计启发式算法来解决它。 另一种是将问题建模为网络流问题。 第一类方法一般得到近似解，近似率不能保证。 第二种方法的优点是将疏散问题转化为经典的网络流问题，可以利用成熟的多项式网络流算法来求解，方便有效。 本文采用第二种方法，模型中考虑了疏散时间相对于人群密度的非线性。

3、材料与方法

3.1 社区疏散问题

问题是如何在有限的交通网络内尽快将需要疏散的所有人转移到指定避难所[27]。 人群运动速度与人群密度之间存在非线性函数关系。 此外，由于人群运动速度会随着密度的增加而减慢，因此人群运动速度与人群密度之间的函数关系是凸函数[28,29]。

综上所述，该问题可以描述为将M个社区的人口疏散到N个避难所，如图1所示。问题包括每个社区需要疏散的人数、每个避难所的容量限制、非线性函数 疏散时间和每条路径上的疏散人数，以及从社区到避难所的每条路径上的参数值（例如道路长度、道路宽度和交叉口面积）。 最快的疏散计划是将社区内所有疏散人员转移到避难所——即每条道路分配的疏散人数。 我们的目标是尽量减少将所有社区疏散到紧急避难所所需的时间。

集合 I={1, 2, …, m}和 J={1, 2, …, n}分别用于表示社区和避难所的集合。 bI 代表社区 i 的人数。 cj 代表社区 j 的容量。 pij 代表社区 i 和庇护所 j 之间的路径。 xij 是决策变量，代表分配给路径 pij 的疏散人员数量。 那么这条路上对应的疏散时间就是一个凸函数，用 gij(xij)表示。 由于不同数量的分配疏散人员将对应不同的疏散时间，因此函数 gij(xij) 必须是一对一映射。 该模型可以写成以下凸程序：

假设任意两条道路之间不存在相互影响； 一条道路上的交通状况不会影响另一条道路上的交通状况。 该问题可以用二分图G=(I1,J1)来描述，其中顶点集I1和顶点集J1分别对应社区集I和庇护所集J。 仅当社区 i 和庇护所 j 之间存在路径时，顶点 i ∈ I 1 和顶点 j ∈ J 1 之间才存在边连接。

3.2 基于网络流的逼近算法

• 网络流图结构构建

网络流图构建在二分图G=(I1,J1)上，如图2所示。对于任意给定参数t，顶点集V={s0,t0,I,J}，其中s0是超 源点，t0 是过闭点。 弧集A包括以下三种类型：

• 当(s0,i),∀i∈I时，对应的容量为bi。
• 当(j,t0),∀j∈J时，对应的容量为cj。
• 在I和J之间的弧中，单个人i到j转移到网络所需的时间小于参数t的弧的集合被并入网络。 也就是说，如果 ∀i∈I,∀j∈J,(i,j)∈A 并且仅当 gij(1)≤t，则该弧上的容量极限为 ⌊g−1ij(t)⌋，其中 ⌊ g−1ij(t)⌋ 表示 gij 的反函数，⌊⌋ 表示相同但向下舍入。 由于函数 gij(xij) 是一对一映射，因此其反函数 g−1ij 必定存在。

当问题描述为图2所示的网络流图时，一旦给出了需要疏散的人数和每条路径上的时间的函数关系gij(t)，就可以用反函数求出疏散人数的容量 t 限制下的每条路径； 然后，它构成了所有参数已知的网络流图。 最大流问题是一个经典的网络流问题。 有关此问题的更多详细信息，可以参考 Schrijver [30]。 解决最大流量问题最流行的算法是 Ford-Fulkerson 算法。 当在图上使用这个最大流量算法来求网络上的最大流量值时，这个最大流量值就是参数t下网络中能够疏散的最大人数。 如果疏散总人数等于待疏散总人数，那么所有人都可以在时间t内疏散到安全区域。 但我们要求用最短的疏散时间将所有人群疏散到避难所，所以t不一定是最短的疏散时间。 接下来，我们用一个较大的时限T作为初始解，取[0,T]中间的值，T/2，计算该时限下的最大流量。 然后根据计算结果，采用二分查找的方法逐步搜索，将最佳疏散时间逐渐缩小到一个较小的时间间隔。 当区间长度小于某个小数ε时，我们可以高精度地得到一个近似最优的疏散时间t，并相应地得到疏散时间t下的具体疏散方案。

• 基于网络流的二分查找算法

针对网络流图给出了该问题的近似算法。 需要强调的是，下面提出的算法并不是直接计算分配到每条路径的人数来最小化疏散时间，而是以网络流图上的参数t作为决策变量，并以足够大的常数T作为初始值 价值。 通过逐步搜索最优疏散时间t*，在网络流图N(t*)上采用最大流算法，得到每条路径上分配的疏散人数。

定理1：
算法1的精度可以为t/t*≤(1+ε)，其中t指问题的最优解。

算法一：基于网络流的二分查找算法

定理1的证明。

假设每条路径上的疏散时间是路径上分配的疏散人数的凸函数[24]； 即，g−1ij(t) 是凸函数。 这样就保证了k次迭代找到的局部最优就是全局最优。 假设第K次迭代的时间间隔为[t′,t′′]； 则t=t′+t′′2，且由于t在[t′,t′′]区间内，所以t≥t′。

因此，算法1的精度为：tt*=t′+t′′2t*。 否则，因为 t′′−t′t′≤2ε，t′′≤2εt′+t′，tt*=t′+t′′2t*≤2εt′+t′+t′2t′=1+ε 。

定理2：
算法1的复杂度为：

定理2的证明。

对于算法 1 中的每次迭代，[t',t''] 区间的长度减少到前一次迭代的一半。 然后，在网络N(t′+t′′2)上，利用标记算法计算网络上的最大流量值。

标记算法的复杂度为n3+n4[31]，因此每次迭代生成的复杂度为n3+n4。

从初始值T开始，假设经过k次算法迭代，参数t的精度可以达到tt≤(1+ε)，即t=O((1+ε)⋅t) =O(ε·t*); 那么，T2k=O(ε·t*)。

当迭代次数k为：

由于n是有向图G上的顶点数，算法1的复杂度可由下式获得：

• 理论比较

本文建立了非线性模型，假设不同路径不交叉，考虑人群密度与疏散速度的非线性关系，给出了多项式时间逼近算法。 从理论上证明了算法的复杂性和准确性，并通过算例验证了方法的有效性。 经典疏散模型只需满足道路和避难场所的容量限制，但疏散时间与疏散人数之间是非线性凸函数的关系[32]。 本文的创新点在于提出了一种具有很好的复杂度和精度的近似算法，为疏散路径规划的非线性模型提供了有效的解决方案。

相比于现有的网络流算法一般只能解决线性规划问题，我们在模型中考虑疏散时间相对于人群密度的非线性，首先将问题表述为非线性网络流模型。 它是基于经典最大流算法（即Ford-Fulkerson算法）的二分搜索模型，并且准确率保证在预先定义的数字（例如0.05%）内。 现有文献中的方法要么无法保证准确率，要么无法处理模型中的非线性函数。

理论上，本研究在定理1中证明了算法的精确度在任何预先定义的小数之内，并且在定理2中我们也证明了算法的复杂度是多项式的。这两个定理表明了算法具有高精度和多项式性。 计算复杂度。

4、散路线规划问题的实证研究

以当地社区地震疏散为例。 该小区共有16栋楼房； 共有北门、正门、南门3个出口，如图3所示。社区人口分为三部分，通过3个门疏散，如图1所示。

疏散出口分配表。

金融街共有7个开放避难所，各避难所的容量如表2所示。

疏散速度与人群密度的函数关系采用Pursals[24]提出的疏散速度与人群密度的函数关系，如下：

式中，v为人群疏散速度，λij为Pij道路上的平均步行速度，单位为m/s。 ρij 为能够进入道路的人群密度，单位为人/m2。 将式（1）转化为时间与人群数量的函数关系：

xij,I=0.5382aij 和 xij,S=3.5aij 分别指分配给道路 Pij 的疏散人数的下限和上限。 tij(xij) 表示在路径 Pij 上分配 xij 人数所花费的时间。 lij 表示道路 Pij 的长度。 wij 是道路 Pij 的宽度。 aij 表示疏散人员到达 Pij 路口时分配给 Pij 路的占用面积。 λij 表示 Pij 上的正常行走速度。 当λij=1.4 m/s时，分析表明，疏散时间随着人数的增加而增加，因此疏散时间与疏散人数之间呈凸函数关系，如图4所示。

tij(xij) 的反函数是路径上的疏散时间和分配给该路径的疏散人员数量的函数。

其中 tij,I 和 tij,S 分别指密度为 0.5382 人/m2 和 3.5 人/m2 时一定数量的人员疏散至目的地所需的时间长度，如图 5 所示，为凹形 功能。 另外，利用谷歌地图测量了每条路径的参数值，包括道路长度、道路宽度和交叉口面积，如表3所示。从3个疏散点到7个避难所共有21条路径。

5、实证研究的计算结果

使用Matlab软件对算法1进行了仿真。 算法的准确率设置为小于0.05%，即ε=0.05%。 我们计算了上述例子的最优疏散方案，包括每条路径的疏散分配、人群疏散速度和时间。 结果如表4所示。

总疏散时间和算法精度如表5所示:

结果表明，经过13次迭代运算，该算法获得的最优目标值的精度达到0.0005。 总疏散时间约为 24.92 分钟。 第 13 次迭代的上限和下限差距为 0.041%。 这表明位于上限和下限之间的最佳疏散时间必须与最佳值的偏差在0.04%以内，低于预定义的精度水平0.005。 最终得到的网络流程图如图6所示。

结果分析与讨论

在本次对风汇园社区的实证研究中，我们使用算法1，在秒级内得到了路由结果。 获得的疏散结果准确度达到0.05%。 理论和实践结果表明，该算法具有四个优点。 首先，该算法简单、直观，易于用编程语言实现。 其次，为求解非线性疏散问题提供了一种有效的方法，精度高、复杂度低、计算速度快。 第三，无论疏散人数与疏散时间之间的具体非线性函数关系有多复杂，只要函数可逆，都可以用算法来求解。 因此，适用范围广泛。 第四，精度高，可以达到任意预设值的精度。

表4和图6的结果显示了本次实证研究的地震突发事件的详细疏散方案。 我们发现24.92分钟内疏散了4129人，这是一个可执行的应急预案。 在此疏散计划中，网络中使用了 6 条路径。 最大疏散流量发生在路径(4,5)上，有998人，而最小流量瓶颈发生在路径(4,7)上，只有27人。 因此，我们可能需要提高路径（4,7）上的容量，以便可以在该路径上共享更多流量，从而减少其他路径上的流量。 相应地，疏散时间也可以减少。 使用算法1，我们可以快速获取社区的疏散计划，并提供提高计划效率的建议，使其成为相关部门或管理者决策的宝贵工具。

6、结束语

研究了社区疏散智能路径规划的非线性模型构建。 非线性模型反映了疏散时间与疏散人数之间的非线性关系； 即随着人数的增加，疏散速度会减慢，疏散时间会增加。 为了解决社区疏散问题中疏散路线规划的非线性模型，提出了一种基于网络流法内最大流算法的二分搜索方法来求解非线性模型。 最后对丰汇园社区地震疏散进行实证研究。 我们提出的算法提供了高效且高度准确的结果。

简而言之，本文设计的算法为解决疏散问题，特别是非线性疏散问题提供了巧妙的思路。 该算法避免从问题本身出发，而是间接启动，以疏散时间作为解变量。 最大流算法通过逐步搜索最佳疏散时间，求出在确定的疏散时间下每条路径上分配的疏散人数。

然而，所提出的算法有一些局限性。 目前仅适用于疏散通道之间没有交叉点的情况。 对于道路交叉的情况，模型和算法的复杂度会增加。 因此，在路况较为复杂的情况下，算法需要进一步扩展和进一步分析。

原文链接：Intelligent Evacuation Route Planning Algorithm Based on Maximum Flow

BimAnt翻译整理，转载请标明出处