第7期 詹子娜等：基于避险设施的火灾救援及避灾路线算法 ·969· 间最短路径的最基本和使用最广泛的算法，传统D- 内燃烧状况，使部分巷道通行能力发生改变，造成了 jkstra算法是贪心的搜索解算；但由于矿井系统网络 高温和有毒气体环境。计算机根据火灾污染的情 的复杂性，导致解算重复度较高和时间较长。依据 况，通过对巷道通行安全性和通行效率的计算，得到 井下最佳路径的选择原则，对Dijkstra算法进行改 巷道灾后权重k=b/a,并对最短路径长度进行修正 进，进行无向有权求解。改进思路和方法为：①计算 d=min(d+0,Cm),救援系统仿真模拟结果如图3 时只考虑从矿工位置到避险设施或出井口之间的最 所示。利用ArcGIS的Weh服务和分析技术，实现 短路径：②将最短路径问题分解为始末两节点同时 火灾污染范围和最佳避灾路线的动态可视化显示功 进行求解；③利用数据结构“堆”的特性和方法， 能，并在数秒内可同时实现某时刻下不同位置人员 简化节点和分支的标记，优化求解步骤，降低其计算 基于避险设施的最佳避灾路线。通过GS图层的关 重复度以提高计算速度，可将其复杂度降为O((m 联性设定，可实现矿工有序正确的基于救生舱或避 +n)lgn)2。基于堆结构的算法改进，可大大避免 难酮室的避灾路线的选择。救援系统的开发在一定 全网络分支的搜索标记，可实现计算机Wb在线的 程度上为矿上井下救援和避险提供了动态实时的情 快速解算及最佳路线的动态显示。 景再现，给救援避险和决策指挥提供科学的依据。 采取面向对象的方法通过对网络分析所用到的 具体解算过程以位置7人员的逃生路线为例， 地理实体属性进行面向对象封装以实现Dijkstra算 N3采区井巷网络如图4和图5所示。虚线表示火 法的运算和最短路径的可视化显示。 灾后受到高温和有毒有害气体影响而无法通行的巷 给定带权无向网络图D,n个节点，m条边，C 道；带括号的数字为巷道通行效率。 表示i与j两节点间的路径长度。当节点i=j,C,= 2) 0;若i与j不相连时，C=,用d,表示i与j两节点 ④0) ⑤ 间的最短路径。特定源点v和终点u,求v到u的最 ① (1) ⑦ 短路径。构建堆矩阵heap,和heap2,及索引矩阵in- 6 dex,最短路径树SPTree。算法主要步骤如下： 2 ①输入最短路径的起始节点u和终结点v。 O ②初始化堆结构heap,和heap2,其元素分别为 ⑥05 ⑧ ① ④ 起点v和终点w的相连接点，并按照其d的大小依 次堆栈排序，主要根据二维节点数组的权值C], 图4井下N3采区灾前井巷网络 Fig.4 Pre-disaster roadway network in the mine 调用Heap-insert方法实现初始化操作。 ③判断heap,和heap2的堆顶元素是否相同，若 (2) ④ 相同转到⑥：否则，转到④。 ④取heap,和heap2内堆顶元素i和j,调用De- ① crease-Key方法将其从栈内删除，分别对heap,和 ⑩ ⑨ )6 heap2堆内其他元素heap1(x)和heap2(y)进行修正， ③ 满足da=min(Ca'dn.+Ca），d=min(C,d+ 心 / 0.58 ⑦ C)。 ④ (6) ⑤利用堆顶元素i和j对其相连的非堆内元素s 图5井下N3采区灾后井巷网络 和t进行修正，取de.=min(Ces,dn.+Ct),dn=min Fig.5 Disaster roadway network in the mine (Ca'd,+Cg),通过Heap-insert方法将其分别加入 到heap,和heap,堆结构内，并按照d.和d,的大小 设井下人员从2号出发，需到达16号处的避险 对堆内元素依此排序，转到③。 设施，按照避灾路线选择原则和改进的dijkstra算法 ⑥若i=j,则v到w的最短路径为d=min 进行仿真运算，如表2所示。N3永久避险设施的构 (Cw,d.+C,),输出最短路径树SPTree,并退出。 建，增加了回风巷内监测人员通行回风巷进入避难 酮硐室而避险几率，在无火灾下，回风大巷2中的监测 3仿真模拟分析与应用 人员可直接通过下风向的大巷而进入避难硐室内， 通过常村煤矿N3采区的火灾模拟，模拟节点 此状态下路径长度最短，但引入通行安全效率权重 11下方向分支（胶带运输机巷道）50m胶带20min 后，巷道的通行时间较长，通过优化后，位置7的监第 7 期 詹子娜等: 基于避险设施的火灾救援及避灾路线算法 间最短路径的最基本和使用最广泛的算法，传统 Di￾jkstra 算法是贪心的搜索解算; 但由于矿井系统网络 的复杂性，导致解算重复度较高和时间较长。依据 井下最佳路径的选择原则，对 Dijkstra 算法进行改 进，进行无向有权求解。改进思路和方法为: ①计算 时只考虑从矿工位置到避险设施或出井口之间的最 短路径; ②将最短路径问题分解为始末两节点同时 进行求解; ③利用数据结构“堆”的特性和方法［17］， 简化节点和分支的标记，优化求解步骤，降低其计算 重复度以提高计算速度，可将其复杂度降为 O( ( m + n) lgn) /2。基于堆结构的算法改进，可大大避免 全网络分支的搜索标记，可实现计算机 Web 在线的 快速解算及最佳路线的动态显示。 采取面向对象的方法通过对网络分析所用到的 地理实体属性进行面向对象封装以实现 Dijkstra 算 法的运算和最短路径的可视化显示。 给定带权无向网络图 D，n 个节点，m 条边，Cij 表示 i 与 j 两节点间的路径长度。当节点 i = j，Cij = 0; 若 i 与 j 不相连时，Cij = ∞ ，用 dij表示 i 与 j 两节点 间的最短路径。特定源点 v 和终点 u，求 v 到 u 的最 短路径。构建堆矩阵 heap1和 heap2，及索引矩阵 in￾dex，最短路径树 SPTree。算法主要步骤如下: ①输入最短路径的起始节点 u 和终结点 v。 ②初始化堆结构 heap1和 heap2，其元素分别为 起点 v 和终点 w 的相连接点，并按照其 dij的大小依 次堆栈排序，主要根据二维节点数组的权值 C［i］， 调用 Heap-insert 方法实现初始化操作。 ③判断 heap1和 heap2的堆顶元素是否相同，若 相同转到⑥; 否则，转到④。 ④取 heap1和 heap2内堆顶元素 i 和 j，调用 De￾crease-Key 方法将其从栈内删除，分别对 heap1 和 heap2堆内其他元素 heap1 ( x) 和 heap2 ( y) 进行修正， 满足 dvx = min( Cvx，dvi + Cxi ) ，dwy = min( Cwy，dvj + Cyj) 。 ⑤利用堆顶元素 i 和 j 对其相连的非堆内元素 s 和 t 进行修正，取 dvs = min( Cvs，dvi + Csi ) ，dwt = min ( Cwt，dvj + Ctj) ，通过 Heap-insert 方法将其分别加入 到 heap1和 heap2堆结构内，并按照 dvx和 dwy的大小 对堆内元素依此排序，转到③。 ⑥若 i = j，则 v 到 w 的最短路径为 dvw = min ( Cvw，dvi + Cvj) ，输出最短路径树 SPTree，并退出。 3 仿真模拟分析与应用 通过常村煤矿 N3 采区的火灾模拟，模拟节点 11 下方向分支( 胶带运输机巷道) 50 m 胶带 20 min 内燃烧状况，使部分巷道通行能力发生改变，造成了 高温和有毒气体环境。计算机根据火灾污染的情 况，通过对巷道通行安全性和通行效率的计算，得到 巷道灾后权重 k = b / a，并对最短路径长度进行修正 d = min( dvw + wijCvw ) ，救援系统仿真模拟结果如图 3 所示。利用 ArcGIS 的 Web 服务和分析技术，实现 火灾污染范围和最佳避灾路线的动态可视化显示功 能，并在数秒内可同时实现某时刻下不同位置人员 基于避险设施的最佳避灾路线。通过 GIS 图层的关 联性设定，可实现矿工有序正确的基于救生舱或避 难硐室的避灾路线的选择。救援系统的开发在一定 程度上为矿上井下救援和避险提供了动态实时的情 景再现，给救援避险和决策指挥提供科学的依据。 具体解算过程以位置 7 人员的逃生路线为例， N3 采区井巷网络如图 4 和图 5 所示。虚线表示火 灾后受到高温和有毒有害气体影响而无法通行的巷 道; 带括号的数字为巷道通行效率。 图 4 井下 N3 采区灾前井巷网络 Fig． 4 Pre-disaster roadway network in the mine 图 5 井下 N3 采区灾后井巷网络 Fig． 5 Disaster roadway network in the mine 设井下人员从 2 号出发，需到达 16 号处的避险 设施，按照避灾路线选择原则和改进的 dijkstra 算法 进行仿真运算，如表 2 所示。N3 永久避险设施的构 建，增加了回风巷内监测人员通行回风巷进入避难 硐室而避险几率，在无火灾下，回风大巷 2 中的监测 人员可直接通过下风向的大巷而进入避难硐室内， 此状态下路径长度最短，但引入通行安全效率权重 后，巷道的通行时间较长，通过优化后，位置 7 的监 · 969 ·