K则最优路径在矿井水害避灾中的应用研究

成韶辉 张雪英 李凤莲 李 芸

(太原理工大学信息工程学院，山西 太原 030024)

K则最优路径在矿井水害避灾中的应用研究

成韶辉 张雪英 李凤莲 李 芸

(太原理工大学信息工程学院，山西 太原 030024)

矿井水害发生时会严重影响井下人员的生命安全，应在水灾发生初期尽可能以最快速度转移到安全区域。基于此，以改进的Dijkstra最优路径算法为基础，考虑巷道的可靠性因子、通行效率及实际当量长度等因素，建立了最优避灾路径的数学模型，并提出了其求取方法，同时说明了K则最优避灾路径的获得方法。详细描述了模型的设计思想和实现过程,结合矿井具体实例，利用C#编程语言，实现了对2种路径的准确获取及界面显示。

数学模型 等价权因子 当量长度 最优路径K则最优路径

近年来，随着煤矿安全受到社会各界的广泛关注，矿井安全工作日益得到完善，但是煤矿事故时有发生。目前在矿井数量不断增多，煤炭产量持续增长的情况下，矿井的安全形势仍不容乐观。矿井水害作为矿山安全生产建设的主要灾害之一，给人们的生命财产安全带来了严重的威胁。当井下发生突水事故时，随着时间推移，涌水量会不断加大，水流很难遏制，会迅速蔓延多个巷道，影响井下人员的逃生，因此突水初期是逃生的最佳时期[1]，应以最快速度撤到安全区域，减少人员伤亡和财产损失。在发生突水时，由于井下环境特殊，巷道错综复杂，有时最优避灾路径可能会被破坏，或者不再适合人员逃生，所以为了防患于未然，通常选择多条逃生路线，也就是所谓的K则最优避灾路径。因此研究井下人员在突水发生时的K则最优避灾路线具有重要的意义。

1 K则最优避灾路径的机理及建模研究

1.1 K则最优避灾路径

所谓K则最优路径，就是寻找起点和终点间所有可达路径中耗费最小、次小、直至第K小的路径,得到多个备选优化路径形成最优路径组[2],最大程度地满足用户在矿井突水发生时对不同路径的选择需求。

求解K则最优路径的传统算法是以单源单标准的Dijkstra算法为基础的去边算法[3]，该算法在求得最优路径后,舍弃所得路径中的任意1条边并重新计算得到次优路径，依此类推得到K则最优路径。该算法计算复杂，实现较困难。

矿井水害时，获得K则最优路径，使得井下人员通过K则最优避灾路径迅速撤离，可以有效减少人员伤亡，降低财产损失。

1.2 最优避灾路径的建模研究

求解最优路径算法中采用的数学模型，一般以理想状态下的路径长短作为权重因子来求解网络中2点之间的最短路径。井下避灾路线是指从人员所在点到安全区的最短路径，因突水发生时其波及范围会影响路径的安全性及通行效率，使巷道的通行难易程度不一样，所以最短通行距离并不等于最短通行时间。因此在求解最优避灾路径时，建立的数学模型应考虑突水时影响巷道的各种因素，满足路径安全性好和撤退时间短的条件。

1.2.1 基于改进的Dijkstra算法的最优避灾路径的数学模型的建立

Dijkstra算法是一种基于贪心策略的最短路径算法，可以求解起止点到所有节点的最短距离。其基本思想是首先求出从起点到与其直接连接顶点最短的一条路径，然后以此为参照求出长度次短的一条最短路径，依此类推，直到目标终点为止[4]。改进的Dijkstra算法所求解的最优避灾路径是指从起止点到达具体终节点之间经过的权值最短的路径[5]，而权值的大小一般是由路径的长短决定的，其数学模型如(1)式：

(1)

式中，vj为井下巷道网络中的巷道节点；dj为井下巷道网络中起始巷道节点v1到节点vj的最短路径；E为井下巷道网络中相邻节点之间弧段的集合；K为井下巷道网络中从巷道节点vi到节点vj的第K条巷道；pK为第K条巷道的等价权因子；wij为井下巷道网络中相邻节点vi到vj之间弧段的权值，即巷道的当量长度。

等价权因子的计算方法如(2)式：

(2)

式中，ki为第i条巷道的可靠性因子；ti为第i条路径的通行效率。

1.2.2 最优避灾路径的数学模型中的影响因子

(1)可靠性因子k。巷道可靠性因子k指在发生突水事故时井下人员通过的巷道的安全程度[6]。它是一种巷道安全通行的数字指标，取值可以根据实时获取的安全监测信息模糊评价得出[7]。其值为0或1,0表示井下巷道不能通行或通行危险，1表示井下巷道安全可以通行。

(2)巷道通行效率t。在避险时，井下人员通过巷道会遇到多种情况[8]：当巷道高度较标准巷道偏低时，逃生人员必须放慢速度弯腰前行；当发生突水时，巷道内有积水会影响逃生效率；人员在巷道中行走时会逐渐适应黑暗环境，通行速度会受影响。表1中列出了人员在不同避难情况下的通行效率，其中通行效率大小是个相对比值，无量纲。在实际应用中，可以根据巷道的实际情况选择统一标准，如以弯腰状态为计算标准1时，爬行的通行效率为2，自由行走为0.5，没膝水中的通行效率为1。

表1 相同路径长度下井下人员的通行效率Table 1 Miners' efficiency of passage at the same length of path

(3)巷道的当量长度wij。井下巷道网络中相邻节点的权值一般用巷道的长度来表示。因各种因素的影响，即使对于同样长的巷道，其实际巷道长度也有所不同，所以应将影响因素考虑进去。将巷道的实际长度乘以各种影响系数，就得到了巷道的当量长度wij[9]：

(3)

式中，aij、aw、ap、af和av分别表示巷道高度、宽度、坡度、泥泞程度和风速的影响系数，其取值可以通过矿井的实际数据信息获得经验值；lij为巷道的实际长度，n为局部障碍物的个数，lm为局部障碍物的当量长度。

2 K则最优避灾路径的求解

井下发生突水时，需要考虑多条避灾线路，即找到从人员所在起止点到安全点的可达路径中耗费最小、次小直至第K小的线路，从而提高逃生效率。基于式(1)建立的数学模型，提出了一种便于求解矿井突水时K则最优避灾路径的方法，具体如下。

2.1 构建一个带权有向图

矿井避灾路线图的表现形式一般为数字化的矢量地图，需对其进行预处理，转换成由顶点和弧组成的网络图的形式。首先将实际矿井避灾线路图(.dwg格式)转换成矢量地图(.shp格式)，提取出线类图元数据中的巷道信息，存入相应的巷道文件；然后对巷道进行拓扑检查、剪断处理，对打断后的路段进行节点、中途点位置坐标及其属性特征的定义，将处理过的路段和节点分别存入路段数据集和节点数据集中。因井下巷道地理位置比较复杂，1条巷道可能与若干条巷道相交或相连，因此以巷道的交叉点为结点进行分割，将巷道交叉点作为网络图的顶点，路段为网络的弧；最后采用十字链表的数据结构[10]生成有向图G=(V，E，W)，V表示巷道节点，E表示弧段，W表示弧段上对应的巷道当量长度。

2.2 K则最优避灾路径的具体实现

在带权有向图G=(V，E，W)中，V={v0,v1,v2,…，vn}，W={wi0,wi1,wi2,…，win}(i=0，1，2，…，n且i≠j)，若i=j或vi到vj无边，wij=0。则v0到vn的K则最优路径的实现如下所示。

(1)基于式(1)，构造n+1阶矩阵A=[aij]，其中aij=pkwij(pk为第k条巷道的等价权因子)，S={v0}，T=V-S，Don=0。

(2)当i=0时，依次寻找满足a0j>0的值，其中vj∈T，令a0k取第f次满足a0j>0的值(f为v0到vn的搜索路径的循环次数，即路径条数，此时f取1)，(j=1,2,…,n)，S={v0，vk}，D0n=D0n+a0k。

(3)同理，当i=k时，依次寻找满足akj>0的值，同样取akm为第f次满足akj>0的值，S={v0，vk，vm}，D0n=D0n+akm。

(4)按照步骤(2)和(3)的思路，当i=r时，依次寻找满足arj>0，若arj=0，则该条路线不存在，若始终可以满足arj>0，直到vn∈S，则S就是v0到vn的第f条路径，D0n就是该条路径的长度。

(5)循环执行步骤(2)和(4)可以依次取得v0到vn的所有路径，即一共f条路径。将所求得的f条路径排序，这样就可以找出K条最优路径。

3 应用实例

以斜沟煤矿的实际巷道通风系统图为基础数据，利用C#程序设计语言实现K则最优避灾路径的选择，便于指导井下人员的逃生。

根据矿井巷道的实际参数，结合式(2)和式(3)可以得出各个巷道的当量长度wij及其对应系数pkwij，见表2。

表2 各巷道当量长度Table 2 The equivalent lengths of all tunnels

利用C#程序，通过Windows窗体应用程序实现最优避灾路线分析系统的界面显示，有以下优点：

(1)利用了基于改进的Dijkstra建立的最优避灾路线的数学模型，使得计算结果直观显示。

(2)输入任意2点可以求得其最短路径，便于井下人员快速安全的撤离。

图1 最短路径在网络图中的显示

Fig.1 The display of the optimal path in the network diagram

4 结 论

K则最优水害避灾路线的研究在保证矿井安全高效的工作中具有重要意义。本研究基于改进的Dijkstra算法，结合矿井突水时的实际情况，引入了巷道的等价权因子，建立了最优避灾路径的数学模型，并利用C#语言,通过窗体界面得到直观有效的实现。当发生突水时，井下人员可以通过专业的小灵通设备获得最优避灾路线，便于安全撤离。但是由于井下突水时实际参数会动态变化，如何将动态的参数实时准确地考虑进去并及时通知井下人员，是需要进一步深入解决的问题。

[1] 汪金花，张亚静，朱令起，等.井下避险最优路径机理与数学建模研究[J].金属矿山，2013(5):128-130. Wang Jinhua，Zhang Yajing，Zhu Lingqi.Study on the mathematical modeling and mechanism of optimal path of underground hedge[J].Metal Mine，2013(5):128-130.

[2] Hoffman W，Pavley R.A method of solution of theNth bestpath problem[J].Joural of the ACM,1959(6):506-514.

[3] 高 松，陆 峰，段滢滢.一种基于双向搜索的K则最优路径算法[J].武汉大学学报：信息科学版，2008，33(4):418-421. Gao Song，Lu Feng，Duan Yinyin.AKth shortest path algorithm implemented with bi-directional search[J].Journul of Wuhan University：Information Science Edition，2008，33(4):418-421.

[4] 计会凤，徐爱功，隋达嵬．Dijkstra算法的设计与实现[J]．辽宁工程技术大学学报:自然科学版，2008，27(S1):222-223． Ji Huifeng，Xu Aigong，Sui Dawei.Design and implementation of Dijkstra algorithm[J].Journal of Liaoning Technical University：Natural Science Edition，2008，27(S1):222-223．

[5] 冯欣欣．Dijkstra算法在嵌入式GIS中的优化实现[J]．北京理工大学学报，2009，29(10):873-876. Feng Xinxin.Efficient implementation of Dijkstra algorithm in embedded GIS[J].Transactions of Beijing Institute of Technology，2009，29(10):873-876.

[6] 汪金花,张亚静,朱令起,等.井下避险路线的GIS数学模型与水灾仿真实验[J].中国煤炭，2013(3):97-101. Wang Jinhua，Zhang Yajing，Zhu Lingqi，et al.The GIS mathematical model and flood simulation of underground emergency route[J].China Coal，2013(3):97-101.

[7] 杨义辉，冯仁俊，李明建，等．基于 GIS 的矿井应急救援系统的研究及应用[J]． 矿业安全与环保，2009，36：64-67． Yang Yihui，Feng Renjun，Li Mingjian.Research and application of mine emergency rescue system based on GIS[J].Mining Safety & Environmental Protection，2009，36：64-67．

[8] 盛 武，高明中，杨 力，等.煤矿紧急避险体系构建与应急救援模型研究[J].中国安全科学学报，2011，21(4):171-175. Sheng Wu，Gao Mingzhong，Yang Li.Study on coal mine emergency refuge system construction and rescue model[J].China Safety Science Journal，2011，21(4):171-175.

[9] 卢国菊，王 飞．矿井火灾时期K则最优避灾路径研究[J]．煤矿安全，2013(4):35-37． Lu Guoju，Wang Fei.Research onKshortest avoid disaster path during mine fire period[J].Safety in Coal Mines，2013(4):35-37．

[10] 王海梅，周献中.网络系统中的最短路径分析及其应用研究[J].兵工学报，2006,27(3):515-518. Wang Haimei，Zhou Xianzhong.Shortest path analysis and its application in network systems[J].Acta Armamentarii，2006,27(3):515-518.

(责任编辑 徐志宏)

Application ofKShortest Path Algorithm in Avoiding from Mine Water Disaster

Cheng Shaohui Zhang Xueying Li Fenglian Li Yun

(CollegeofInformationEngineering,TaiyuanUniversityofTechnology，Taiyuan030024,China)

Mine water disaster seriously affects the life safety of the miners，so the miners should flee to safety site at the beginning of the water disaster as quickly as possible.Based on this，a mathematical model of optimal escape routes was conducted based on the improved Dijkstra algorithm，considering such influence factors as reliability factor，efficiency of passage，actual equivalent length of the tunnel etc..Then its solution was given，and the method of obtainingKshortest path was illustrated.The designing idea for the model and its implementing process were described in detail.As well，the accurate access to two routes and its interface display were realized combining with specific examples of the mine and using C# programming language.

Mathematical model，The equivalent weight factor，Equivalent length，Optimal path，Kshortest path algorithm

2013-11-01

山西省科技重大专项(编号20121101004)，中国博士后科学基金第53批面上项目(编号：2013M530896)，山西省科技攻关项目(编号：20130321004-01)。

成韶辉(1989—)，女，硕士研究生。

TD745+.2

A

1001-1250(2014)-01-137-04