最短路径算法在事故应急救援中的应用*

虞 谦 高岳毅 李 俊

江苏省安全生产科学研究院

1 研究的背景与意义

在生产经营活动中，无论是在生产、运输过程中还是在储存、经营、使用环节，都可能发生重大安全生产事故，造成重大人员伤亡和财产损失。如2005年3月29日晚，在淮安境内高速公路，因交通事故诱发液氯泄漏，造成29人死亡，疏散群众1万多人。2010年7月，南京市地下丙烯管道泄漏爆燃，造成22人死亡，120多人受伤住院。当发生重大事故时，如果能及时快速组织人员疏散撤离，将会减少和避免大量人员伤亡。但要做到这一点，需要确定最短撤离路径和救援路径。

本文重点研究了疏散及救援最短路径的计算优化算法，基于单源最短路径的经典算法—迪杰斯特拉（Dijkstra）算法，通过优化算法节点，转换道路节点图层为带权有向图，运用Dijkstra优化节点算法并提出了事故疏散救援时最佳路径，同时将已确定的事故模型及最短路径的算法与地理信息系统（GIS）相结合，形成可视化最短路径结果图示化展示。

2 主要技术与方法概述

近年来，许多最短路径算法研究已被用于解决实际问题，例如，联合国救援组织在2010年的海地地震中，运用结合了最短路径算法的地理信息系统制定应急救援路线计划[1-9]。本文分析和优化基于Dijkstra最短路径的算法，提出了针对节点优化的Dijkstra最短路径算法的优化方案，并通过地理信息系统实现了最短路径优化算法的可视化问题，讨论了必要的证明和应用条件。该方案已在公路信息系统中应用，并取得了满意的效果。

2.1 节点定义

在实际运用中，首先需要根据现场道路情况，构建出道路的节点图层和道路图层。

节点：道路的交叉点。

节点图层的数据库格式为：节点ID，X，Y

节点ID：表示节点本身。在数据库中，一般只需要储存节点ID和节点坐标（如果不储存节点ID，GIS系统可以通过空间地理查询功能来获得），储存节点坐标可以在进行最短路径计算和绘制路线时提高运算速度。

在计算最短路径的初始化阶段，在储存的道路图层记录基础上，通过道路起点、终点、交叉点、道路长度和道路路况系数建立道路的邻接矩阵，以便计算最短路径。使用公式来取值：

Wij=L[i, j]×P

式中：

L[i, j]—道路节点i到道路节点j间的距离，m；

P—道路路况系数。

2.2 算法优化

Dijkstra核心算法步骤中对最小权值路径的计算需要确定节点，针对此步骤，对节点使用情况进行优化，分为已标记节点、临时标记节点和未标记节点，在计算过程中直接选择未标记节点，可以节约大量计算时间，只需要运算一次就可以按照权值对相关临时节点进行升序排列。

2.3 算法图解

如图1，以一个带权有向图来说明Dijkstra优化节点算法的计算过程。应急救援的最短路径问题，一般是解决从应急救援队出发地点到事故发生地点的最短路径问题，因此，我们把其简化为搜寻两个节点之间的最短路径问题。Dijkstra优化节点算法，需要确定一个道路节点为起点，在事故应急救援中，一般设应急救援队伍的出发点附近的道路节点为起点，设为s1；终点在事故应急救援中，一般为离事故发生地点最近的道路节点，设为s6。

初始状态：S是已计算出最短路径的顶点集合，U是未计算出最短路径的顶点的集合。

第1步：将源点s1放入S中。

此时，S={s1(0)},U={s2(∞),s3(2),s4(0),s5(6),s6(20)}。

注：s3(2)表示s3到起点s1的距离是2。

第2步：将顶点s3加入到S中。

图1 带权有向图

上一步操作之后，U中顶点s3到起点s1的距离最短；因此，将s3加入到S中，同时更新U中顶点的距离。以顶点s2为例，之前s3到s1的距离为∞；但是将s3加入到S之后，s2到s1的距离为3=(s2,s3)+(s3,s1)。

此时，S={D(0)，s3(2)},U={s2(15),s4(12),s5(6),s6(20)}。

重复以上步骤，并不断修正U集合中的路径值。最后得到：S={s1(0),s2(15),s3(2),s4(10),s5(6),s6(12)}。因此，从源点s1到终点s6的最短路径为12，见下表。

表 从s1到其余各顶点最短路径

3 最短路径展示技术

展示最短路径需要结合运用测绘、遥感、计算机模拟仿真技术、地理信息系统（GIS）等多种技术，主要包括以下内容：

3.1 三维场景数据的制作

三维场景数据库是最短路径展示技术中的基础和前提，而三维场景数据的制作是目前测绘行业先进技术的综合体现。多种类型数据的叠加形成三维场景数据，它包括矢量数据、影像数据、模型数据、地形数据等。在本项目研究的实例中，采用的是数字高程模型（Digital Elevation Modal，简称DEM）数据，其中遥感数据采用精确到1m的IKONOS卫星遥感影像数据，通过将数字高程模型、卫星影像数据、三维地形数据和三维模型数据叠加，最后生成三维场景数据从而实现对真实世界的虚拟实现。

其中，三维地形数据的加工过程，如图2。

图2 三维地形数据的制作过程

除了三维地形数据外，还需要制作三维模型数据。为了清楚表现地表上的各种建筑设施，比如道路沿路的居民区、加油站等建筑设施，需要通过三维模型数据来建立。而融合了航空遥感、地形、三维地形、三维模型数据，并且需要使用先进的数据打包技术才能够最终制作成三维场景数据。三维场景数据的制作过程，如图3。

图3 三维场景数据的制作过程

3.2 三维系统功能集成

最短路径展示技术发挥了GIS强大的空间处理能力，由传统的二维空间扩展到三维空间，使用户能够更直观的感受建筑、道路、山体等三维目标。并且实现了在三维空间中对目标物体的查询和定位。

依托GIS系统，在发生突发事故时，可以针对事故进行事故影响范围模拟，计算生成三维空间地理模型，并对事故进行应急救援最短路径方案设计。例如，在某地发生泄漏事故后，可以对泄漏地点进行定位查询、泄漏发生后影响范围在三维场景中的展现、泄漏周边应急救援物资及消防、医疗救援力量的查询定位，综合分析后自动展示出人员撤离的最短路径以及救援人员的最短救援路径。如图4展示了医疗救援最短路径（以白色线显示）。

图4 事故应急救援最短路径展示技术

4 结论

本文研究了基于Dijkstra算法的最短路径节点优化方案，提出了在危险化学品泄漏事故应急救援中应用最短路径的技术手段，并将最短路径的算法与地理信息系统相结合，通过图示化展示出最短路径。此技术手段可以有效迅速组织事故影响区域内人员的疏散撤离，为减少和避免大量人员伤亡提供了技术支持。