基于仿真的突发事件区域人群疏散路径规划研究

刘炎强++王坚++凌卫青

摘要：在突发事件区域人群疏散仿真的应用中，为快速准确的建立疏散区域内的路网模型，本文结合数据库与WebGIS接口技术搭建了GIS疏散路网模型。在分析了传统的Dijkstra算法的基础上，对Dijkstra算法进行了改进，并应用到已建立完成的路网模型中，为疏散人群提供路径规划。实际案例分析表明，改进后的算法符合大规模区域人群疏散要求，具有较强的适用性。

关键词：区域人群疏散；WebGIS；疏散路网模型；Dijkstra算法

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2016）01-0245-03

Route Planning of Emergency Regional Crowd Evacuation Based on Simulation

LIU Yan-qiang， WANG Jian， LING Wei-qing

（Tongji University， Shanghai 201804， China）

Abstract： In the application of emergency regional crowd evacuation simulation， to quickly and accurately build a road network model in the evacuation area， the database and webGIS interface technology is combined to establish the GIS evacuation road network model. The classic DijkStra Algorithm which can provide route planning to the crowd is improved in this paper by the basis of its analysis， and has been applied to the established road network model. The anysis of results demonstrates that the modified Dijkstra algorithm satisfies the requirements of large-scale regional crowd evacuation and has good practicability.

Key words： regional crowd evacuation； webGIS； evacuation road network model； DijkStra algorithm

随着经济社会快速发展和城市现代化水平不断提高，自然灾害和人为灾害对城市功能正常发挥的影响程度和波及范围也越来越大。面向这些灾害建立安全有效的突发事件区域人群疏散机制是一个重要研究问题，计算机仿真技术就是一种有效的研究手段[1]。只要能够建立合理的人群疏散仿真模型，就可以利用计算机仿真技术，研制突发事件区域人群疏散仿真系统，通过仿真推演的方式模拟人群的疏散过程，为城市公共安全应急管理人员提供决策参考，有效保障公众的生命财产安全。

在现实社会的实际疏散过程中，疏散者的一切运动都是在道路上进行的，所以疏散路网模型为整个人群疏散仿真过程提供了最为基础的道路数据[2]。有了准确的路网模型，就可以使用各种网络分析算法研究人群的疏散过程。本文使用的是改进的Dijkstra最短路算法，为疏散人群提供路径规划，并在GIS疏散路网模型中得到了应用。

1 GIS疏散路网模型

在突发事件人群疏散仿真系统中，疏散路网模型起到了至关重要的作用。好的路网模型不仅是对现实世界中路网的客观抽象，更真实地反映路网内部结构及关系[3]，这直接决定了人群疏散仿真的结果与实际疏散情况的偏差程度。

随着WebGIS技术发展的愈发成熟，国内的许多在线地图信息服务商如百度、腾讯、高德地图等都陆续推出了各自的地图API接口，帮助用户在网站中构建功能丰富、交互性强的地图应用。然而这些在线地图API提供的路网虽然使用方便，但是缺少路段容量、路段人群拥挤度等关键信息，很难保证以此为基础进行的人群疏散仿真结果的有效性。因此本文的疏散路网模型是通过，先使用百度地图API提供的绘图功能在地图上绘制出一个路网框架[4]，然后将绘制出的路网信息保存到数据库中得到。路网信息有以下三种：

1）节点：道路上的交叉口、拐点和终点。属性有节点ID、节点经度和节点纬度。

2）路段：两节点之间的道路。属性有路段ID、头结点ID、尾节点ID、路段长度、路段容量和路段人数。

3）路段权值：路段特征属性的量化表示，用于Dijkstra最短路算法的路径搜索指标。根据优化目标的不同可以定义相应的权值[5]，本文以人群疏散距离最短作为最优目标。

2 Dijkstra最短路算法

2.1 传统Dijkstra最短路算法

Dijkstra算法是GIS应用领域中用于求解最短路问题的经典算法，传统的Dijkstra算法用于寻求从一个固定源节点到其余各节点的最短路径，它是迪杰斯特拉（Dijkstra）于1959年提出的一个按路径长度递增的次序产生最短路径的算法[6]。设G = （V ， E ， W）是赋权无向图，式中V和E分别是G的节点集合和边集合，一条连结节点vi ， vjV的边记为[vi ， vj]（或[vj ， vi]），每一条边e = [vi ， vj]，相应地有权值w（e） = wij。当所有边的权值wij ≥ 0时，该算法是目前公认最好的最短路算法[7]。

Dijkstra算法的基本思想是从源节点vs出发，逐步地向外探寻最短路。执行过程中，每个节点都会记录下一个数称为这个节点标号，标号有两种，首先是P标号表示从vs到该节点的最短路的权值，另一种是T标号表示从vs到该节点的所有路径（这些路径中该节点的父节点必须已标注过P标号）权值的最小值。算法的每一步是去修改T标号，然后找到所有T标号最小值所标注的节点，将其改为具P标号的节点，从而使具P标号的节点数多一个。这样如果图G中存在n个节点，那么经过n-1步，就可以求出从vs到图G中所有节点的最短路[8]。

传统Dijkstra算法的具体步骤如下：

P（v）：v节点的P标号；

T（v）：v节点的T标号；

S：具有P标号节点的集合；

a（v） = m：从vs到v最短路径上，v的前一个节点是vm；

Step 1 初始化，令S = {vs}，P（vs） = 0，k = s，对每一个v ≠ vs，令T（v） = +∞。

Step 2 如果S = V，算法终止，此时vs到v最短路就是P（v），遍历a（v）即可得到最短路径；否则转入Step 3。

Step 3 考查每个使[vk ， vj] E且vjS的节点vj。如果T（vj）>P（vk）+ wkj，则令T（vj） = P（vk）+ wkj，a（vj） = k。全部考查完毕后转入Step 4。

Step 4 假设vmS且使T（vj）取最小值的节点，令P（vm） = T（vm），S = S∪{vm}，k = m。转入Step 2。

2.2改进的Dijkstra算法

从上节的算法描述中可以看出，传统Dijkstra算法的求解过程由一个大循环嵌套小循环组成，其中外循环运行n-1次，内循环为两个，第一个用来确定所有节点的T（v），第二个循环则用来找出所有T（v）的最小值，均至多运行n-1次，因此算法的时间复杂度为 O（n2）。

对于城市区域疏散路网模型来说，它的特点首先是GIS节点数量多，可能达到成百上千个，这就对算法的计算时间提出了要求。其次当发生突发事件时，人群大概率的分布在路网中的几乎所有节点上，而且为保证疏散效率，人群被引导去往的避难区或者说是安全出口肯定不止一个，也就是说这是一个多源节点多目标节点的最短路问题，如果每个源节点都运用一次Dijkstra算法，其算法的时间复杂度将上升为O（n3）。为解决上述问题必须对传统的Dijkstra算法进行改进。

我们知道，当n较大时，Dijkstra 算法的效率急剧下降，如果能有效减少n值，也就是说减少参与运算的节点数量或者是源节点的数量，那么其运行速度将大大提升，以此优化目标为出发点，考虑以下两点：

1）对于一个源节点来说，其目标节点可能是多个，以疏散路程最短为原则，只要匹配到一个目标节点，立刻退出循环，并将此路径作为疏散路径。

2）考虑到如果路径L是从vs到vt的最短路径，vi是L中的一个节点，那么从vi沿L到vt的路也是从vi到vt的最短路径。利用如上事实，再加上区域疏散路网模型源节点个数多这个特点，运算前对所有源节点到周围目标节点的直线距离从远到近进行排序，先从较远的源节点开始运算，这样做得出的路径中会大概率地包含许多其他源节点，根据结论这些源节点的最短路已经找到，不用作为输入参与后续运算，以此达到减少源节点数量的目的。

基于上述思想，改进的Dijkstra算法的具体步骤如下：

Y：源节点集合；

yi：Y中第i个集合

T：目标节点集合；

Step 1 对Y中所有源节点到T中目标节点的直线距离从远到近进行排序。

Step 2 如果Y = ?，算法终止；否则在V中匹配y1，令vs = y1，Y = Y-{y1}，转入Step 3。

Step 3 初始化，令S = {vs}，P（vs） = 0，k = s，对每一个v ≠ vs，令T（v） = +∞，P（v） = +∞。

Step 4 如果tT使得tS，转入Step 5，此时vs到t最短路就是P（v），遍历a（v）即可得到最短路径；否则转入Step 6。

Step 5 考查每个使yY且P（y） ≠ +∞的节点y，令Y = Y-{y}，此时y到t最短路就是P（y），遍历a（y）即可得到最短路径。全部考查完毕后转入Step 2。

Step 6 考查每个使[vk ， vj] E且vjS的节点vj。如果T（vj）>P（vk）+ wkj，则令T（vj） = P（vk）+ wkj，a（vj） = k。全部考查完毕后转入Step 7。

Step 7 假设vmS且使T（vj）取最小值的节点，令P（vm） = T（vm），S = S∪{vm}，k = m。转入Step 4。

改进的Dijkstra算法的路径搜索流程如图1所示。

图1 改进的Dijkstra算法流程图

3应用案例

本应用采用B/S模式，通过网页进行浏览，前端主要用HTML和JavaScript语言编写，Java语言用作后台实现了改进后的Dijkstra算法，并且采用了百度地图API技术结合MySQL数据库对包括路网模型在内的疏散模型进行建立。案例选取的事故地点为上海野生动物园，疏散路网模型见图2。模型中共建立254个节点，295条路段，在图2中红色的圆点代表节点，蓝色的线条代表路段，节点与路段的信息存于数据库中。

上海野生动物园在节假日期间遇到的最大实时客流量大约在25000人左右，案例中人流量为24340人，分布在园区内的众多热门景点上，具体的人群分布情况见图3。随后将人群分配到各个路网节点上以进行计算得到疏散路径，统计出需要疏散的源节点数量为95个。

图2 疏散路网模型

图3 人群分布热力图

图4 使用Dijkstra算法得到的疏散路径

图5 从百度地图API获取的疏散路径

图4是采用改进的Dijkstra算法得出的所有源节点的疏散路径，计算用时0.086秒，计算机配置为Intel Core 2 Quad Q8300，内存为4G。图中路段颜色用来表示疏散时该路段的拥挤程度，绿色代表畅通、橙色代表拥挤、红色代表非常拥挤，三个蓝色图标表示避难区，也就是算法中的目标节点。图5是在相同的场景下，通过百度地图API获取到的疏散路径，获取全部路径用时22.95秒。

比较图4与图5中的疏散路径可以看出，百度地图API拥有的路网模型更加的详细，但是大体上两幅图显示的路段分布和路段拥挤程度都比较相似，而且显然算法的计算速度肯定要比通过网络获取的速度要快很多，最重要的是自建疏散路网模型灵活性大、更贴近于实际情况，可以根据需要建立起更丰富、准确的路网模型属性。因此结合本文建立的GIS疏散路网模型，改进的Dijkstra算法完全可以用来进行区域人群疏散的疏散路径规划。

参考文献：

[1] 卢兆明. 基于GIS的都市应急疏散系统[J]. 中国公共安全， 2005（2）： 35-40.

[2] Yosef S， Hani M， Warren BP. A transportation net-work evacuation model[J]. Transportation Research， 1982， 16A（3）： 209-218.

[3] 曹政才， 韩丁富. 基于新型路网模型的路径寻优方法研究[J]. 电子学报， 2012， 40（4）： 756-761.

[4] 百度地图API鼠标绘制管理类参考.

http：//api.map.baidu.com/library/DrawingManager/1.4/docs/symbols/BMapLib.DrawingManager.html. 2014.3.

[5] 白尘. 交通路网中最优路径算法的道路权重选择[J]. 中国管理信息化， 2009， 12（15）： 54-56.

[6] Dijkstra E. A note two problems in connection with graphs[J]. Numerical Mathemat， 1959， 1： 269-271.

[7] 刘翠丽， 张思东. GIS应用领域中Dijkstra算法的一种改进[J]. 电信快报， 2005（5）： 46-48.

[8] 王树西， 吴政学. 改进的Dijkstra最短路径算法及其应用研究[J]. 计算机科学， 2012， 39（5）： 223-228.