考虑实时路况反馈的动态路径规划算法研究

王润泽1,2,3,4，王亮2，刘涛1,3,4，栗斌2

1.兰州交通大学测绘与地理信息学院

2.中国测绘科学研究院

3.地理国情监测技术应用国家地方联合工程研究中心

4.甘肃省地理国情监测工程实验室

针对现有的路径规划算法在应对突发事件人员车辆疏散过程中没有考虑实时交通拥堵路况反馈因素，降低了疏散路径方案的有效性问题，该文提出了一种引入实时路况的动态疏散路径规划算法。首先将动态路网中的实时路况信息建模和量化，构建实时动态的旅行时间矩阵，然后利用交通预测模型改进的动态蚁群算法求解全局疏散时间最小化、道路网利用率最大化的最优路径。采用改进的动态蚁群算法构建的动态路径规划方法，能在交通拥堵区和动态路网阻抗变化后快速更新路线，较好地平衡了疏散过程中的全局疏散时间与局部拥堵间的矛盾。实验结果表明，当交通拥堵级别增加时，相比现有的路径规划算法，本文的方法分别减少18%的平均疏散时间和11%的总旅行时间，增加26%的路网利用率。

0　引言

1　问题描述与假设

2　D-ACO算法设计

3　实例验证

4　结束语

应急疏散一般由人员疏散和救援物资配置组成，而人员疏散是营救工作中最重要的一项任务。应急疏散规划是抢险救援工作中的重要组成部分[1]。好的疏散方案不仅可以减少疏散时间，而且可以避免疏散中不必要的拥挤和二次伤害。为此，疏散路径规划的优化设计拥有重要的现实意义[2]。

相关文献[3]根据灾害的动态性[4]将路径规划方法划分为静态路径规划和动态路径规划。动态灾害是指那些行为、位置或严重性发生变化的灾害。文中将对疏散路网影响不大的灾害事故看作是静态的。静态路径规划主要为应急分析和逃生演习准备提供了理论指导，通常采用Dijkstra算法及其改良算法、K最短路径算法、Floyd算法、A*算法和动态规划。像地震、飓风、野火和洪水灾害是动态的，因为随着时间推移它们会从一个地方移动到另一个地方。因此，静态规划方法不再适应灾害或事故以及其他环境变化的动态传播。

动态路径规划是灾害应急管理中实时决策的基础，通常采用高效的启发式算法。文献[5]提出了一种用于解决地震后在交通网络的可达性和出行需求模式发生变化时导致旅行时间变化的动态疏散路径规划方法。该方法将疏散路径问题建模为车辆路径问题(vehicleroutingproblem，VRP)，利用公共交通工具将疏散者分阶段疏散，并使用启发式的模拟退火算法(simulatedannealing，SA)来求解每阶段问题。文中主要考虑了运输工具、撤离点和避难所的容量，但没有考虑疏散中撤离点延误对疏散成本的影响。文献[6]提出了具有实时交通预测的动态路线规划系统，该系统利用SCATS(sydneycoordinatedadaptivetrafficsystem)提供的实时数据构建实时的交通预测模型。该模型利用时空随机场预测未来的SCATS数据，使用高斯过程回归的方法，估算传感器未覆盖区域的交通流量。但模型的精度会受到实时数据的影响，在传感器覆盖率低的地方，如果有其他数据源的加入，将增加模型的普适性。文献[7]提出一种针对城市交通网的动态实时路径选择模型，该模型结合了实时路况信息和用户对备选路线的偏好，通过自适应学习算法及时为路网中的每辆车提供快速、准确的最优路线。文献[8]进行了实时路径规划的仿真模拟，通过实时计算来确定路网中的最短路径，利用并行计算技术加速最短路径的搜寻，与非实时计算相比，可以节省大量时间。由于现实中城市交通的不确定性和复杂性，在现实生活中微观仿真模型很难发挥实际作用。文献[9]提出自学习的动态路径规划方法，该方法是在BP神经网络初步训练的策略网络基础上，通过自学习的不断迭代构建新策略网络的方法，用于大型公共建筑的疏散。虽然BP神经网络表现良好，但相对一些先进的网络，如卷积神经网络(CNN)和递归神经网络(RNN)仍有很多不足。且近年来国内外对动态路径规划问题的研究大多采用迭代和智能算法。智能算法主要有粒子群优化算法(particleswarmoptimization，PSO)[10]、神经网络算法[11]、遗传算法(geneticalgorithm，GA)[12]、蚁群算法(antcolonyoptimization，ACO)[13]等。虽然有关动态路径规划问题的研究成果已有很多，且大多数方法将交通视为动态因素，而在应急疏散路径动态规划上的研究却很有限，面对疏散中的突发情况，在路线的动态调整和及时反馈方面并不理想，没有考虑应急疏散中撤离点本身的容量对周边道路密度的影响，也没有考虑时变路网上疏散过程中疏散路线的实际容量和密度。

针对现有方法在应急疏散上的不足，本文提出一种动态疏散路径规划方法，采用改进的动态蚁群(dynamicantcolonyoptimization，D-ACO)算法求解路网阻抗变化下的疏散路径问题。该方法在路径规划中不仅引入了与时间相关的时变路网，而且考虑了撤离点的时间延误和疏散中对路网造成的拥堵，利用蚁群算法的反馈和信息素更新机制，将疏散中的实时路况信息以信息素的形式反馈。针对算法的动态性实时性要求，结合交通预测模型估算车辆在路网中的行驶速度，实现路网阻抗变化时快速更新路径的目的。

GIS中的交通网络是一种复杂的地理对象，一般由结点和弧段组成，为了研究的需要本文用图论中点和线的集合“图”来表达交通网络。即将实际路网上的动态疏散路径规划问题建模为有向图上的路径规划问题。假设G=(V，E)是一个图，V称为顶集，V中的元素称为顶点(结点)，E称为边集，E中的元素称为边(弧段)，边有阻抗(impedance，imp)和容量(capacity，cap)两个属性。由于交通网络在疏散过程中会发生变化，所以这两个属性都不是固定的。在本文中分别表示通过这条边的通行时间和车道数量。

在实际疏散中，来自交通流量、拥堵、事故等不确定因素的影响，疏散中车辆的实际行驶速度是随时间变化的，导致路网中各路段的阻抗和容量具有时变性。为此，假设图G中边的两个属性在固定的时间间隔或时间段内不发生变化。本文用时变路网GC={gc=(t，e，imp，cap)

t≥0，e∈E}来描述其变化情况，impgc(e)，capgc(e)分别表示路网gc变化后边e的阻抗和容量。

假设图G中只有一个目的节点(区域性避难所)。因为通过添加一个连接所有目的节点的虚拟的超级源点，可以将多源多汇最短路径问题简化为单源多汇问题[14]。假设图G中撤离点位置和权重为：s∈S，SVw(s)0，其中，S表示撤离点s的集合，w(s)表示撤离点s的权重，文中w(s)代表该点的车辆数。

对动态疏散路径规划问题做以下假设。

1)假设所有疏散源点(撤离点)同时开始疏散，考虑来自同一撤离点的疏散车辆之间的延误(时间间隔)。

2)假设交通预测模型可以用数学函数的形式表达，该模型可以根据给定的车辆密度来预测路段上的交通拥堵情况。

3)假设疏散源点的车辆是不可分的，同一撤离点都选择相同的路线。

4)假设道路网的变化最初不知道，因此，算法只能在了解实时路况后进行调整。疏散过程中不会变化的是避难所的位置。

该问题有5个输入：图G、时变路网变化表、交通预测模型、撤离点位置、目的地(避难所位置)。

该问题的输出是每个撤离点到避难所的疏散路线P和预计疏散时间。

本文利用D-ACO算法来求解动态疏散路径规划问题。该算法是在实时路况信息和交通预测模型的基础上对蚁群算法的改进，其求解过程如图1所示。

图1D-ACO算法

与文献[15]中的ACO-CCRP疏散路径规划方法相比，D-ACO算法不仅考虑了实时路况信息，还引入了幂交通预测模型。在具有实时路况信息反馈的动态路网中构建旅行时间变化矩阵，通过改进蚁群算法的启发式因子和状态转移规则选择路径，利用信息素更新规则，实现在路网的阻抗发生变化时快速更新疏散路径的目标。考虑到撤离点的疏散延迟，D-ACO算法根据撤离点的时间延迟和路网中边容量，重新计算边的实际密度，并计算延迟所带来的额外成本。

2.1交通模型

为了更好地了解路网中实时交通状况，文中使用了一个名为幂模型[16]的经验交通模型，该模型可以在路网容量受限和交通流不确定情况下，根据路段限速、长度、车道数和车辆数来预测交通拥堵下的车辆速度。其数学公式是利用经验曲线拟合的成果，见式(1)。

式中：γ、ε都是常数，γ=0.，ε=0.。

该模型是基于边的容量(c)和总密度(d)两个参数来预测交通拥挤度的函数T(d，c)。该模型输出的是一个0到1的系数：T=1表示没有交通堵塞，可以畅通行驶；T=0表示非常拥堵，道路的可达性几乎为0。

2.2疏散模型

由于不同撤离点的车辆数不同，在疏散中每个撤离点s因时间延误会产生不同的边密度，该密度可以根据式(2)计算。例如，假设通过边e需要10min，而撤离点s有辆车，可知impgc(e)=s，w(s)=。若没有时间延误，则边e的密度dengc(s，e)=。然而，假设疏散者每次离开撤离点需要间隔30s，即delay(s)=30。边的密度降低到路段实际可容纳的车量数dengc(s，e)=/30=20。随着边阻抗的变化，这种密度也将从一个时间间隔变化到下一个时间间隔，见式(2)。

假设每个撤离点s只有一条路径Ps，路径Ps是一组有序的边集，它将引导撤离点处所有的疏散者到达避难所。因此，通过式(3)可知，边e上的总密度是通过e的所有路径的密度总和。

最后，通过式(4)可以计算通过该边的成本，进而可以得到其疏散路径的成本。路径成本式(5)中的第一项考虑了初始车辆延迟所带来的额外时间，第二项计算了路径本身的成本。式(4)为了计算出正确的路径成本，需要知道每个撤离人员到达每条边的时间间隔。即撤离者s通过其路径Ps到达边e的抵达时间：(s，e，Ps)∈GC。

本文的目的是最大限度地减少最终疏散时间，如式(6)所示。

目标：疏散时间最小化。

2.3改进蚁群算法

针对应急疏散中动态路径规划的需要，扩大算法的全局搜索能力，对蚁群算法的启发式因子和状态转移规则重新设计，从而改进蚁群算法。

蚁群算法中的启发式因子ηij，在进行路径选择时，会使蚂蚁因为仅受最短路径的影响，从而失去全局性，导致错误地选择下一节点，进而陷入局部最优解。因此，为了增加蚁群算法的全局搜索能力，结合实际的交通拥堵状况，利用式(4)对启发式因子改进，见式(7)。

式中：costT，gc(eij)、costT，gc(ejd)表示边eij和节点j与目标节点d间的最短旅行时间成本。

通过交通模型式(1)得到的拥挤系数T(d，c)对其状态转移规则的改进，在初始化时设定一个参数q0，q0∈[0，1]，每当进行路径选择时，通过T(d，c)与q0的比较决定的路径选择，见式(8)。

式中：p是由式(9)得出；Pkij表示路径选择概率。

通过式(8)可知信息素强度τij(t)和启发因子ηij(t)是其基础，随着路径上信息素τij(t)浓度的增加，相比启发因子ηij(t)来说，它在状态转移规则公式中的价值越高，τij(t)的更新公式将决定算法的时效性。

当一条路径上的疏散者过多时，将导致该路径的密度增加，这将影响该路径的交通状况，从而导致疏散时间增加。为此，利用局部信息素更新规则，每当蚂蚁k选择路段时，按式(10)将相应减少其所经过路段上的信息素浓度，达到局部调整的目的，降低再次选择所经过路段的概率，从而缓解该路径上的拥挤度，是一种负反馈机制。

式中：0ξ1；τ0为边的初始信息素浓度，由边的阻抗决定。

全局信息素更新规则是在算法每次迭代后，对当前最优路径上的信息素按式(11)更新。

式中：0ρ≤1是信息素挥发速率参数；Cb是当前全局最优的路径成本costT(Ps)，只增加全局最优解路径上的信息素浓度，是一种正反馈机制。

2.4D-ACO算法描述

D-ACO算法是在实时交通模型和蚁群算法基础上，求解时变路网上的动态疏散路径规划问题，其主要步骤有4步。

1)输入路网G，时变路网变化表GC，预测交通状况的幂模型：T(d，c)，撤离点s及其人数w(s)，避难所位置，疏散路线P=。

2)算法开始时，初始化算法的所有参数[17]，迭代次数N=，蚂蚁数m=，α=1，β=2，ρ=0.05，τ0=1。

3)WhileN≠0{

s∈S，w(s)0do{

随机将m只蚂蚁放置不同的撤离点，对于k∈m利用式(1)获得交通拥堵系数，并通过式(8)进行判断，然后选择下一路段。

当蚂蚁k到达目的地时，根据式(10)完成局部信息素的更新。

通过式(5)计算各蚂蚁经过的路径成本，并保存当前迭代的最优解。

当动态路网发生变化时，更新其边的容量和阻抗。

每次迭代后，按式(11)完成对疏散路径Ps上的信息素浓度的全局更新。

}N=N-1

}

4)输出疏散路径P。

实验路网数据是从