用excel求解线性规划实验总结 王润泽，王亮刘涛

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

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

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

2.中国测绘科学研究院

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

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

摘要

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

本

文

目

录

0 引言

1 问题描述与假设

2 D-ACO算法设计

3 实例验证

4 结束语

0

引言

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

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

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

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

1 问题描述与假设

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中撤离点位置和权重为：

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

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

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

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

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

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

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

2 D-ACO算法设计

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

图1 D-ACO算法

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

2.1 交通模型

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

式中：γ、ε都是常数，γ=0.022 61，ε=0.011 27。

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

2.2 疏散模型

由于不同撤离点的车辆数不同，在疏散中每个撤离点s因时间延误会产生不同的边密度，该密度可以根据式(2)计算。例如，假设通过边e需要10 min，而撤离点s有100辆车，可知impgc(e)=600 s，w(s)=100。若没有时间延误，则边e的密度dengc(s，e)=100。然而，假设疏散者每次离开撤离点需要间隔30 s，即delay(s)=30。边的密度降低到路段实际可容纳的车量数dengc(s，e)=600/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)。

式中：cos tT，gc(eij)、cos tT，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是当前全局最优的路径成本cos tT(Ps)，只增加全局最优解路径上的信息素浓度，是一种正反馈机制。

2.4 D-ACO算法描述

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

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

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

3)While N≠0{

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

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

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

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

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

}N=N-1

}

4)输出疏散路径P。

2 实例验证

实验路网数据是从http：∥www.arcgis.com获得的圣地亚哥市街道。在GIS软件中，利用圣地亚哥的街道、转弯和路标要素构建网络数据集。首先从数据供应商HERE或TomTom获得实时流量源；然后运行地理处理工具将实时流量源生成实时流量文件，称为动态流量格式(DTF)文件，并利用网络爬虫定期更新；最后利用网络数据集从DTF文件中读取实时流量速度，并使用流量消息通道(TMC)编码把速度和边关联起来。通过为网络数据集配置实时(历史)流量数据，从而得到路网中街道的实时路况信息。文中使用圣地亚哥网络数据集作为实验数据，由40 599个节点，106 882条边和3 503个转弯限制组成。

研究区圣地亚哥市有一片绿洲巴尔博亚公园，面积超过485 hm2，被认为是天然的区域性避难所。因此本文选取了该公园作为避难所，同时选取了该市100个人员密集的POI点作为撤离点。由于该避难所的范围足够大，可以覆盖所有的撤离人员，因此没有容量限制。如图2显示了研究区域的交通状况以及撤离点，避难所位置。

图2 研究区交通状况

流量数据表示的是一天中各时间间隔的平均行驶速度，来自每天不同时间观测的车辆行驶速度，将该速度转换为畅通时段行驶速度的比例因子ε(0<ε≤1)的形式记录。畅通行驶速度是车辆在无其他流量阻碍行驶的情况下的行驶速度，一般将观测到的车辆平均速度作为畅通行驶速度。通过与路网数据的关联，即可获得每条街道“自-至”方向的速度变化过程。

文中圣地亚哥采用的是时间间隔为15 min的流量数据，表示一天中每隔15 min车辆行驶速度的变化情况。如表1所示，根据交通拥堵指数[18]对畅通行驶速度比例因子f按照交通拥挤级别划分为5个实验场景。根据交通拥挤程度的增加，对场景按升序编号。基于该表和路网数据不仅能确定道路的交通状况，还可以计算出路网畅通和变化时各边eij的通行时间impgc(eij)=L/(fVij)，其中L为该边的长度，Vij为该边的畅通行驶速度。

表1 交通拥堵级别

为了评估动态疏散路径规划方法在避免交通拥堵、减少车辆疏散时间和总疏散时间方面的潜力，在疏散中只考虑交通拥堵的变化，不考虑交通阻塞。

首先将撤离点和区域避难所的空间分布以及路网数据集和包含路网变化的属性表，导入GIS软件中进行数据预处理和分析，生成D-ACO算法所需的旅行时间矩阵。然后在疏散中利用幂模型的预测结果来局部调整疏散路线，减少局部交通拥堵，根据时变路网变化表，采用实时的旅行时间来优化全局疏散路线。

为了验证所提出的动态疏散路径规划方法D-ACO算法的有效性，还使用现有的路径规划方法(ACO-CCRP算法)来求解每个场景并作对比。对现有方法应用相同的解决方案，但缺少实时路况信息的反馈，将其称为静态疏散方案。

D-ACO算法是用Matlab软件编写的，并在一台戴尔个人电脑上执行，其运行环境配备如下：Intel(R)Xeon(R)i5 CPU，主频2.5 GHz，内存8 GB，Windows 10系统。在圣地亚哥市的路网上，针对每一个实验场景均求解10次，并求其平均值。静态疏散方案和动态疏散方案的疏散路径和疏散时间如图3所示。

图3 疏散路径

表2列出了不同场景下静态和动态疏散方案的结果。评价标准为：疏散时间(ET)，即疏散完成最后一辆车到达区域避难所的时间；总旅行时间(TT)，即全部车辆完成疏散后的旅行时间之和。从表2的实验结果可知，与静态疏散方案相比，动态疏散方案在ET和TT这两个评价标准上都有较大的改善，它分别将ET和TT平均减少了18%和11%，路网利用率平均增加了26%，但也增加了21.5%的算法运行时间。

表2 不同场景下静态和动态疏散方案的结果

从图4和图5中可以看出，两种方案的ET和TT均随着交通拥堵级别的增加而增大，但动态方案结果增加的程度远低于静态方案。

图4 疏散时间

图5 总旅行时间

从图6可以看出有3处撤离点的疏散时间突增，因为在路网中添加了2个交通拥堵区，导致该区域内车辆行驶速度降低，从而该区域内撤离点的疏散时间平均增加了2 min。

图6 有无拥堵区域时的疏散时间

4 结束语

针对在应急疏散中没有实时路况信息的反馈，将难以进行大范围的路径规划问题，本文提出将幂模型和实时路况反馈相结合的基于蚁群算法的D-ACO算法。算法能在路网变化后，最大限度地减少交通拥堵和全局疏散时间，快速更新疏散路线。实验结果表明，本文算法提高了路网利用率，减少了疏散时间和总旅行时间，特别是随着交通拥堵级别的增加，其结果越明显。但算法还存在运行时间增加的问题，可能大规模严重拥堵情况影响了算法的时效性。后续将考虑交通阻塞的情况，以提高算法的扩展性和实时性。

参考文献(略)

END

作者简介：王润泽(1996—)，男，河南商丘人，硕士研究生，主要研究方向为网络分析。

E-mail：0217713@stu.lzjtu.edu.cn

基金项目：中央科研院所基本业务费项目(AR1927)；兰州交通大学优秀平台支持项目(201806)

通信作者：王亮 研究员 E-mail：wangl@casm.ac.cn

引用格式：王润泽，王亮，刘涛，等.考虑实时路况反馈的动态路径规划算法研究[J].测绘科学，2020，45(7)：163-169.(ANG Runze，WANG Liang，LIU Tao,et al.Study on dynamic path planning algorithm considering real-time traffic feedback[J]. Science of Surveying and Mapping，2020，45(7)：163-169.)