基于优化SPFA算法的矿井突水救援模型_蔡明杰.pdf

第 47 卷 第 6 期 煤田地质与勘探 Vol. 47 No.6 2019 年 12 月 COAL GEOLOGY 2. School of Safety Engineering, North China Institute of Science and Technology, Langfang 065201, China Abstract Due to the occurrence of coal mine water inrush accidents, it is easy to cause major personnel and property losses. In order to improve the emergency rescue capability of mine water inrush disasters and reduce the water inrush hazard, a mine wa- ter inrush rescue route model was proposed. The undirected map and the adjacency list were used to describe and store the mine roadway network. According to the calculation ratio of the height of the water level and the height of underground personnel in roadway, the safety coefficient of the roadway was calculated, and then the equivalent length of the roadway was solved. Ac- cordingly, The optimized SPFA algorithm was used for search of single source route, the rescue route model for mine water in- rush was proposed and the optimized rescue route was given. The simulation analysis was carried out on the basis of the topol- ogy network structure of the roadways in Wangjialing mine. The results show that the mine water inrush rescue model based on the optimized SPFA algorithm can correctly calculate the optimized route of the single source. This considered integrally the complicate situation where the staff can’t pass through a roadway due to being blocked by water flow and collapse in the roadway, provided the reliable technical support for realizing rapid and effective emergency rescue. Keywords mine water inrush; safety coefficient of the roadway; SPFA algorithm; route planning; roadway network model; Wangjialing mine 由于煤矿开采的特殊性，在其生产过程中易发 生水、火、瓦斯、煤尘和顶板等灾害事故，煤矿突 水是煤矿建设和采矿生产中的重大灾害之一。频发 的矿井突水事故不仅易造成井下人员死亡，也严重 影响采矿企业的正常生产工作。因此，矿井必须建 立和完善科学有效的事故应急救援系统，使事故救 援与处理反应快速，提高抗灾与救灾能力[1]。合理 选择应急救援路线是应急救援技术支持体系的重要 组成部分， 不仅能指引救援人员及时到达灾害现场， 控制事故的进一步发展，而且有利于尽快展开现场 ChaoXing 第 6 期 蔡明杰等 基于优化 SPFA 算法的矿井突水救援模型 79 急救，组织被困矿工安全撤离，有效地降低事故伤 亡率并减少财产损失。 赵作鹏等[2]基于 D-K 算法提出煤矿水灾最优路 径搜索方法，该方法考虑了水灾发生时巷道中的水 位高度对救援路线选择的影响，认为巷道中积水越 深，计算路线时等效长度应越长；汪金花等[3]根据 井下实际通行情况建立了巷道通过系数量化定权的 具体方法，在改进最短路径算法基础上增添等价权 因子，构建出井下人员最优化路线算法模型；李宁 宁等[4]基于改进 Dijkstra 算法提出路线搜索算法， 一 般最多处理两点间的最优路线问题，而突水救援过 程中往往需要从多个地点出发进入事故现场，显然 多次执行 Dijkstra 算法寻找路线会极大地降低工作 效率。段凡丁提出的 SPFAShortest Path Faster Al- gorithm算法[5]是求单源最短路径的一种算法，其在 Bellman-Ford 算法基础上增加队列优化，减少冗余 的松弛操作，是一种高效的最短路线算法。这种算 法最大的优势是可以同时求源点到图中所有顶点的 最优路线，且不会因图中存在负权边而无法求解。 夏正冬等[6]对 SPFA 算法进行了分析，认为该算法实 现简单，实际运行效果较好。同时，从实际运行角度 对 SPFA 的几种改进方法进行了对比，还对 SPFA 算 法无法处理含负值有向图的问题提出了改进方案。 SPFA 算法单次执行即可计算出源点到所有节 点的路线，对突水救援的情况处理起来更有效率。 因此，本文提出基于 SPFA 路线搜索算法的矿井突 水救援路线规划模型，并对算法的松弛过程进行优 化， 使其在应对巷道网络类稀疏图时计算速度更快。 突水救援模型中采用优化的 SPFA 算法进行救援路 线搜索，可以同时搜索到达巷道中某一点的多条路 线， 且可依据途径巷道破坏程度筛选出合理的路线； 与 Dijkstra 算法相比，其效率更高，更加灵活，更 适合突水救援路线搜索。 1 矿井突水救援模型 1.1 巷道拓扑结构描述 图Graph是由顶点Vertex的有穷非空集合和 顶点之间边Edge的集合组成，通常表示为 GV,E， 其中，G 表示某图，V 是图 G 中顶点的集合，E 是 图 G 中边的集合。无向图Undirected graphs是指图 中任意两个顶点之间的边都是无向边，对于巷道拓 扑结构，可以将立体巷道映射为平面上的直线，看 作是无向图中的边；巷道交点看作是无向图中的顶 点，因此，可将由顶点和边构成的巷道拓扑结构用 无向图的数据结构高效地进行表达和存储。 无向图可以使用邻接表或邻接矩阵来进行存储 和描述。对于巷道拓扑结构类稀疏图，邻接表降低 了存储空间的浪费，提高了存取效率。根据巷道网 络的特点，本文使用两套邻接表来分别存储巷道节 点顶点和巷道段边，如表 1 和表 2 所示。节点表 包含 节点 ID、 节点坐标x, y, z、 节点邻接点 ID表 1；边的表包含边的 ID、构成边的两个节点 ID， 巷道长度表 2。巷道网络结构如图 1 所示。 图 1 巷道网络结构示意图 Fig.1 Roadway network structure 表 1 节点信息表 Table 1 Nodes ination ID x y z 连接点 ID 74 62 93 11.84 75,77 75 67 93 8.76 74,76,84 76 71 93 7.62 75 表 2 巷道信息表 Table 2 Roadways ination ID 节点1ID 节点2ID 长度/m 97 74 75 50.04 98 74 77 99.56 99 75 76 46.94 1.2 巷道安全系数 在突水灾害发生时，巷道的安全性受到多方面 因素影响。根据对矿井实际情况的监测和分析，影 响井下逃生速度的因素主要包括巷道类型、巷道 坡度、局部障碍物分布、风向风速、水位高度等， 其中，水位高度与突水的发展情况直接相关。 巷道的安全通行能力是进行路线搜索需要着重 考虑的因素，安全通行能力越强，此条路线被选为 逃生路线的概率就越大。在建立最优路线救援模型 时，巷道安全通行能力不仅要进行定性分析，还需 进行定量计算。在实际巷道中，如果水位高度达到 了人体身高的 0.9 倍时，人员的移动速度几乎为 0， 该巷道几乎无法通行；当水位高度为身高的 0.5 至 ChaoXing 80 煤田地质与勘探 第 47 卷 0.7 倍时，人员虽可以移动，但移动速度十分缓慢， 巷道依然难以通行；当水位为身高的 0.3 倍以下时， 巷道具备较好的通行能力， 可以作为救援通道通行。 综合以上分析可以看出，巷道安全通过系数与 巷道水位和矿工身高之比直接相关。因此，根据矿 工的平均身高以及巷道的水位，可以计算巷道安全 系数 P，计算式为 1 H P h   1 式中 H 为水位高度，m；h 为矿工身高，m。 以身高为 1.7 m 矿工为例，计算巷道安全系数 的结果如表 3 所示。 表 3 巷道安全系数计算结果 Table 3 Roadway safety coefficient 水位高度/m 巷道安全系数 P 通行状况 1.53 0.1 禁止通行 1.19 0.3 不建议通行 0.85 0.5 不建议通行 0.51 0.7 可以考虑通行 0.34 0.8 可以通行 0.17 0.9 可以通行 1.3 最优救援路线模型的建立 突水后巷道环境复杂，且巷道环境变化对救援 路线的选择会产生显著影响，因此，不能简单地以 救援路线长度为标准来评判某一条救援路线的优 劣。例如，某条救援路线长度虽然最短，但其中一 条巷道水位高于矿工身高的 0.9 倍，无法正常通行， 那么这条路线不应该被选为救援路线。 在评价救援路线优劣时， 应结合巷道道路特征， 同时考虑巷道的长度和水位高度，将包含水位信息 的巷道安全系数 P 作为巷道长度的系数，计算巷道 等效长度。某条巷道的等效长度同时反映了巷道安 全性和长度信息，其等效长度越小，说明巷道的通 过安全性越好，巷道长度越短。 设矿井巷道无向图中两个相邻定点 i，j 之间边 的实际长度为 Sij，在计算巷道无向图中巷道等效长 度时，巷道安全系数 P 应与等效长度成反比。设巷 道等效长度为 lij，计算公式为 1 ijij ij lS P  2 式中 Sij表示巷道无向图中某条巷道的实际长度， m； Pij表示巷道安全系数； lij代表巷道等效长度， m。 通常情况下，一条完整的救援路线由多条巷道 串联组成，救援路线等效长度应为路线中包含的所 有巷道等效长度之和，计算公式为 1 n m m LS   3 式中 Sm表示某条巷道的等效长度， m，由式2计算 得到；L 则代表整条救援路线的等效长度，m。 综上所述，在进行救援路线的搜索和选择时， 首先需根据巷道中水位情况和矿工平均身高，依据 式1计算出巷道的安全通过系数；然后结合巷道实 际长度，依据式2计算巷道的等效长度；最后根据 式3计算出救援路线的等效长度，并以此为评价标 准选取等效长度最短的路线作为救援路线。 2 SPFA 算法与矿井突水救援路线模型 2.1 SPFA 算法描述 SPFA 算法的时间复杂度与无向图顶点数量和 边数量的乘积相关，属于较高水平，但对于矿井巷 道网络类稀疏无向图来说影响较小； 而该算法可以快 速求得图中某个源顶点到其他所有顶点的最短路径， 正符合煤矿救援路线应用的场景需要。在进行救援 时， 往往需要从多个地点向人员受困点进发，或从多 条救援路线中选择较为合理的路线实施救援。 应用 SPFA 算法搜索救援路线时，可以将人员 受困地点选为算法的源顶点，再分解指定几个救援 人员出发地点作为算法的目标顶点，算法即可计算 出救援出发点到达井下人员受困点的最短路线。 使用数组 d[]记录每个顶点的最短路径估计值， 用邻接表来存储图 G。SPFA 算法使用动态逼近方 法， 建立一个先进先出的队列用来保存待优化节点。 算法运行过程中，每次取出队首顶点 u，且用 u 点 当前的最短路径估计值对离开 u 点所指向的顶点 v 进行松弛操作，如果 v 点的最短路径估计值有所调 整，且 v 点不在当前队列中，就将 v 点放入队尾； 这样不断从队列中取出顶点来进行松弛操作，当队 列为空时终止算法。 算法中的关键一步是在每个循环中进行松弛操 作每个顶点 v 均有一个 d[v]值，用来描述从源点 s 到 v 点的最短路径。一次松弛操作可以减小 d[v]， 并更新 v 的前趋域 π[v]。 算法流程如下 输入无向图 G，源点 s 输出数组 d[]存储各顶点的最短路径值，数组 path[]存储路线 ① 读入邻接表； ②初始化每个顶点是否在队列中的标识为 false； ③ 将数组 d[]初始化为最大值， 数组 path[]初始 ChaoXing 第 6 期 蔡明杰等 基于优化 SPFA 算法的矿井突水救援模型 81 化为源顶点编号； ④ 源节点 s 进入队列 Q， 修改入队标识为 true； ⑤ 当队列 Q 不为空时，从队列 Q 中取出一个 顶点 v，修改其入队标识为 false； ⑥ 判断经过 v 点到达 j 点比原来的路径 d[j]更 短后，对 j 点路径进行优化，并记录路径到 path[]， 更新数组 d[]； ⑦ 如果 j 点不在队列中，j 点进入队列，并设 置入队标识为 true； ⑧ 重复步骤⑤⑥⑦，直到队列为空即停止算法； ⑨ 输出数组 d[]，数组 path[]。 整个算法的核心操作步骤为读取队头顶点 v， 并将队头顶点 v 出队，同时消除入队标识；将与节 点 v 相连的所有节点 j 进行松弛操作，如果能更新 估计值即令 d[j]变小，那么就更新。另外，如果节 点 j 没有在队列中， 那么要将节点 j 入队， 同时修改 其入队标识；如果已经在队列中，那么就不用入队； 这样不断从队列中取出顶点来进行松弛操作。 以此循 环，直到队空为止，就完成了单源最短路径的求解。 2.2 SPFA 算法优化方法 通过对松弛点入队位置调整，来提高算法搜索 突水救援路线的效率。 目前主要的优化方法有 2 种 SLFSmall Label First和 LLLLarge Label Last[7]。 这两个改进算法的思想均基于先松弛离源点“较近” 的顶点所谓“较近”指的是 d 值较小。 SLF思路简单，原队列改为双端队列，对一 个要加入队列的点j， 如果 d[j]小于队首元素v的 d[v] 值，那么就加入到队首元素，否则加入到队尾。 LLL对每个要出队的元素 v，比较 d[v]和队列 中 d 的平均值，如果 d[v]更大，那么将其弹出放到 队尾，取队首元素再进行重复判断，直至存在 d[v] 小于平均值。 经 SLF 方法优化后的 SPFA 突水救援路线算法 流程图如图 2 所示。 本文未采用 LLL 优化方法，是因为这种优化方 法不稳定，在某些特殊图中，LLL 优化的 SPFA 算 法复杂度降低不明显， 甚至可能会变得更高； 而 SLF 优化方法，在矿井巷道类稀疏图应用场景下，一般 可达到 20左右的性能提升[7]，虽然性能没有 LLL 优化方法明显，但更加稳定，一般不会出现复杂度 指数增长的情况，更具普适性。 2.3 矿井突水救援模型实现 根据突水救援模型的设计，在突水发生后要根 据巷道中的水位信息计算出巷道的等效长度，以等 效长度最短的救援路线为搜索目标，目标函数可以 表示为 1 minmin n m m TLS    4 通过计算巷道等效长度，并利用优化 SPFA 算 法进行最优路线规划，可求得从巷道中任意位置出 发，到达指定救援位置的最优救援路线。具体流程 如图 3 所示。 图 2 SPFA 算法 SLF 优化方法流程图 Fig.2 Flow chart of optimized SPFA algorithm of SLF 图 3 矿井突水救援路线模型 Fig.3 Rescue route model of mine water inrush 在煤矿突水灾害发生后，迅速了解相关巷道淹 ChaoXing 82 煤田地质与勘探 第 47 卷 没情况和需要救援的井下位置，根据巷道的水位计 算巷道安全系数和巷道的等效长度。将需要救援的 事故发生点选为算法的源顶点，再根据巷道情况指 定几个可能的救援人员出发点， 通过使用优化 SPFA 突水救援路线算法，计算出几条从预设出发点到达 井下救援地点等效长度最短的路线。由于算法计算 时采用的路线等效长度已经将安全因素加以考虑， 求得的最短路线即为最优救援路线，因此，可筛选 出一条或几条相对安全可靠的救援路线，来对井下 受困人员进行施救，最大限度地提升救援速度，减 少突水灾害造成的人员财产损失。 3 仿真分析结果 本文以王家岭矿的巷道拓扑网络结构为基础， 对救援路线模型进行仿真分析。依据实际情况，将 王家岭矿工程开拓平面图，转化为由顶点和边组成 的巷道结构无向图来进行描述和存储，将巷道交点 标记为顶点，并将两个顶点间的巷道定义为边，分 别对标记顶点和边进行编号，共生成节点 87 个，边 108 条。将上述顶点和边的数据分别记录到顶点信 息表和巷道信息表；顶点记录下其坐标和与本顶点 存在连接关系的相邻顶点，边则记录定义边的两个 节点编号和边的长度，并将其作为巷道长度使用。 依据图 4 所示的部分巷道拓扑结构图，模拟巷道 发生突水灾害的情况。 拟定顶点 72 为需要进行救援的 地点，救援人员分别从顶点 27 处、顶点 67 处和顶点 81 处出发， 到达救援地的合理路线见表 4。 可以看出， 从顶点 27 到达顶点 72 最短路线应该为 27→26→ 12→11→69→70→71→72，但由于该条路线安全系数 较低，等效长度较长，为保证救援过程的安全，算法 选 择 了 路 线 27→26→62→61→68→75→74→73→ 71→72。经实验证明，基于优化 SPFA 算法的矿井突 水救援路线选择方法，可以正确地计算出单源最优路 线，为矿井突水井下救援路线的选择提供参考。 4 结 论 a. 采用顶点信息表和巷道信息表描述矿井巷 道网络，提出一种矿井突水救援模型，不仅节省了 存储空间，且易于巷道信息的管理与维护，并具有 灵活的扩充空间。 b. 提出了基于巷道水位和矿工身高的巷道安 全系数的计算方法，并将巷道安全系数与巷道实际 长度相结合，来计算巷道等效长度；将其作为判断 路线优劣的标准融入到路线规划算法中，使最优救 援路线同时兼顾距离因素与安全性。 图 4 王家岭矿巷道结构图 Fig.4 Topology structure map of roadway in Wangjialing mine 表 4 输出线路表 Table 4 Outlet route table 起始点 终点 路 线 27 27→26→62→61→68→75→74→73→71→72 67 67→66→69→70→71→72 81 72 81→80→79→77→74→73→71→72 c. 将 SPFA 路线搜索算法应用到矿井突水救援 路线搜索中，采用动态规划的思想，结合巷道等效 长度，求解井巷网络中任意两点间的最短路径，且 根据等效长度确定出满足实际条件的最优路线，克 服了传统最短路线算法的局限性，具有很高的灵活 性和执行效率。 d. 本文提出的方法与传统最短路线算法相比， 在 考虑路线长度的基础上考虑了巷道安全通行能力，求 得的救援路线是在确保安全基础上的最短路线，使最 终得到的救援路线更具实用价值。今后应考虑巷道类 型、巷道坡度、局部障碍物的分布、风向风速等因素 对救援路线的影响， 使求得的救援路线更加安全可靠。 参考文献 [1] 林崇德. 矿井水灾事故应急救援辅助决策系统[J]. 中国安全 ChaoXing 第 6 期 蔡明杰等 基于优化 SPFA 算法的矿井突水救援模型 83 生产科学技术，2016，12增刊 132–36. LIN Chongde. Assistant decision-making system for emergency rescue of mine water disaster[J]. Journal of Safety Science and Technology，2016，12S132–36. [2] 赵作鹏，宋国娟，宗元元，等. 基于 D–K 算法的煤矿水灾多 最优路径研究[J]. 煤炭学报，2015，402397–402. ZHAO Zuopeng，SONG Guojuan，ZONG Yuanyuan，et al. Research on the multi-optimal paths of coal mine floods based on the D-K algorithm[J]. Journal of China Coal Society，2015， 402397–402. [3] 汪金花，张亚静，朱令起，等. 基于 GIS 井下紧急避险路线 的数学建模与仿真[J]. 矿业研究与开发， 2013， 333 104–107. WANG Jinhua，ZHANG Yajing，ZHU Lingqi，et al. Mathe- matical modeling and simulation of underground emergency refuge route based on GIS[J]. Mining Research and Develop- ment，2013，333104–107. [4] 李宁宁， 刘玉树. 改进的 Dijkstra 算法在 GIS 路径规划中的应 用[J]. 计算机与现代化，2004912–14. LI Ningning，LIU Yushu. Application of modified Dijkstra al- gorithm in GIS route planning[J]. Computer and Modernization， 2004912–14. [5] 段凡丁. 关于最短路径的 SPFA 快速算法[J]. 西南交通大学学 报，1994，292207–212. DUAN Fanding. A faster algorithm for shortest-pathSPFA[J]. Journal of Southwest Jiaotong University， 1994， 292 207–212. [6] 夏正冬，卜天明，张居阳. SPFA 算法的分析及改进[J]. 计算 机科学，2014，416180–184. XIA Zhengdong，BU Tianming，ZHANG Juyang. Analysis and Improvement of SPFA algorithm[J]. Computer Science，2014， 416180–184. [7] 沈海澜， 王玉斌， 陈再良， 等. 一种基于分层图的改进 SPFA 算法[J]. 计算机工程，2012，3813251–253. SHEN Hailan，WANG Yubin，CHEN Zailiang，et al. Improved SPFA algorithm based on layered graph[J]. Computer Engineer- ing，2012，3813251–253. [8] 姜雷. A*算法在矿井灾害应急救援中的应用[J]. 煤炭技术， 2011，305109–111. JIANG Lei. Application of A* algorithm in mine emergency response and rescue[J]. Coal Technology，2011，305 109–111. [9] 孙臣良. 基于启发式搜索的矿井最佳应急救援路线确定方法[J]. 煤矿安全，2007，38137–38. SUN Liangchen. for determining the best emergency res- cue route of mine based on heuristic search[J]. Safety in Coal Mines，2007，38137–38. [10] CHERKASSKY B V，GOLDBERG A V，RADZIK T. Shortest paths algorithms Theory and experimental uation[J]. Mathematical ProgrammingSeries B，1996，732129–174. [11] 柴登峰， 张登荣. 前 N 条最短路径问题的算法及应用[J]. 浙江 大学学报工学版，2002，365531–534. CHAI Dengfeng，ZHANG Dengrong. Algorithm and its appli- cation to N shortest paths problem[J]. Journal of Zhejiang Uni- versityEngineering Science，2002，365531–534. [12] 张丽娟. 基于 OSG 的矿井突水应急虚拟仿真系统关键技术研 究[D]. 北京中国矿业大学北京，2014. [13] 周耀东，曹志国，李翠平. 基于改进 Dijkstra 算法的矿山突水 可视化仿真[J]. 金属矿山， 2010，3910123–125. ZHOU Yaodong，CAO Zhiguo，LI Cuiping. Research of the visual simulation of mine water-inrush based on improved Dijkstra algorithm[J]. Metal Mine，2010，3910123–125. [14] 白建平. 从成庄矿水患防治实践谈矿井防治水的方法[J]. 煤 炭工程，2006，38348–50. BAI Jianping. Discussion on mine prevention and control from the practice of prevention and control of water in Chengzhuang mine[J]. Coal Engineering，2006，38348–50. [15] 安凯，郑亚林，邱祖廉. 赋权有向图最短路问题的新解法 前趋法[J]. 河北师范大学学报自然科学版，2006，404 23–24. AN Kai， ZHENG Yalin， QIU Zulian. A new algorithm solution to the shortest path problem of weighting directed graph- of forward graph[J]. Journal of Hebei Normal UniversityNatural Science，2006，40423–24. [16] JALALI S E， NOROOZI M. Determination of the optimal escape routes of underground mine networks in emergency cases[J]. Safety Science，2009，4781077–1082. [17] 张志华. 矿山巷道三维网络模型的构建及其路径分析方法研 究[D]. 西安西安科技大学，2010. 责任编辑 周建军 ChaoXing