成韶輝 張雪英 李鳳蓮 李 蕓

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

K則最優(yōu)路徑在礦井水害避災中的應用研究

成韶輝 張雪英 李鳳蓮 李 蕓

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

礦井水害發(fā)生時會嚴重影響井下人員的生命安全，應在水災發(fā)生初期盡可能以最快速度轉移到安全區(qū)域?；诖?，以改進的Dijkstra最優(yōu)路徑算法為基礎，考慮巷道的可靠性因子、通行效率及實際當量長度等因素，建立了最優(yōu)避災路徑的數(shù)學模型，并提出了其求取方法，同時說明了K則最優(yōu)避災路徑的獲得方法。詳細描述了模型的設計思想和實現(xiàn)過程,結合礦井具體實例，利用C#編程語言，實現(xiàn)了對2種路徑的準確獲取及界面顯示。

數(shù)學模型 等價權因子 當量長度 最優(yōu)路徑K則最優(yōu)路徑

近年來，隨著煤礦安全受到社會各界的廣泛關注，礦井安全工作日益得到完善，但是煤礦事故時有發(fā)生。目前在礦井數(shù)量不斷增多，煤炭產量持續(xù)增長的情況下，礦井的安全形勢仍不容樂觀。礦井水害作為礦山安全生產建設的主要災害之一，給人們的生命財產安全帶來了嚴重的威脅。當井下發(fā)生突水事故時，隨著時間推移，涌水量會不斷加大，水流很難遏制，會迅速蔓延多個巷道，影響井下人員的逃生，因此突水初期是逃生的最佳時期[1]，應以最快速度撤到安全區(qū)域，減少人員傷亡和財產損失。在發(fā)生突水時，由于井下環(huán)境特殊，巷道錯綜復雜，有時最優(yōu)避災路徑可能會被破壞，或者不再適合人員逃生，所以為了防患于未然，通常選擇多條逃生路線，也就是所謂的K則最優(yōu)避災路徑。因此研究井下人員在突水發(fā)生時的K則最優(yōu)避災路線具有重要的意義。

1 K則最優(yōu)避災路徑的機理及建模研究

1.1 K則最優(yōu)避災路徑

所謂K則最優(yōu)路徑，就是尋找起點和終點間所有可達路徑中耗費最小、次小、直至第K小的路徑,得到多個備選優(yōu)化路徑形成最優(yōu)路徑組[2],最大程度地滿足用戶在礦井突水發(fā)生時對不同路徑的選擇需求。

求解K則最優(yōu)路徑的傳統(tǒng)算法是以單源單標準的Dijkstra算法為基礎的去邊算法[3]，該算法在求得最優(yōu)路徑后,舍棄所得路徑中的任意1條邊并重新計算得到次優(yōu)路徑，依此類推得到K則最優(yōu)路徑。該算法計算復雜，實現(xiàn)較困難。

礦井水害時，獲得K則最優(yōu)路徑，使得井下人員通過K則最優(yōu)避災路徑迅速撤離，可以有效減少人員傷亡，降低財產損失。

1.2 最優(yōu)避災路徑的建模研究

求解最優(yōu)路徑算法中采用的數(shù)學模型，一般以理想狀態(tài)下的路徑長短作為權重因子來求解網(wǎng)絡中2點之間的最短路徑。井下避災路線是指從人員所在點到安全區(qū)的最短路徑，因突水發(fā)生時其波及范圍會影響路徑的安全性及通行效率，使巷道的通行難易程度不一樣，所以最短通行距離并不等于最短通行時間。因此在求解最優(yōu)避災路徑時，建立的數(shù)學模型應考慮突水時影響巷道的各種因素，滿足路徑安全性好和撤退時間短的條件。

1.2.1 基于改進的Dijkstra算法的最優(yōu)避災路徑的數(shù)學模型的建立

Dijkstra算法是一種基于貪心策略的最短路徑算法，可以求解起止點到所有節(jié)點的最短距離。其基本思想是首先求出從起點到與其直接連接頂點最短的一條路徑，然后以此為參照求出長度次短的一條最短路徑，依此類推，直到目標終點為止[4]。改進的Dijkstra算法所求解的最優(yōu)避災路徑是指從起止點到達具體終節(jié)點之間經(jīng)過的權值最短的路徑[5]，而權值的大小一般是由路徑的長短決定的，其數(shù)學模型如(1)式：

(1)

式中，vj為井下巷道網(wǎng)絡中的巷道節(jié)點；dj為井下巷道網(wǎng)絡中起始巷道節(jié)點v1到節(jié)點vj的最短路徑；E為井下巷道網(wǎng)絡中相鄰節(jié)點之間弧段的集合；K為井下巷道網(wǎng)絡中從巷道節(jié)點vi到節(jié)點vj的第K條巷道；pK為第K條巷道的等價權因子；wij為井下巷道網(wǎng)絡中相鄰節(jié)點vi到vj之間弧段的權值，即巷道的當量長度。

等價權因子的計算方法如(2)式：

(2)

式中，ki為第i條巷道的可靠性因子；ti為第i條路徑的通行效率。

1.2.2 最優(yōu)避災路徑的數(shù)學模型中的影響因子

(1)可靠性因子k。巷道可靠性因子k指在發(fā)生突水事故時井下人員通過的巷道的安全程度[6]。它是一種巷道安全通行的數(shù)字指標，取值可以根據(jù)實時獲取的安全監(jiān)測信息模糊評價得出[7]。其值為0或1,0表示井下巷道不能通行或通行危險，1表示井下巷道安全可以通行。

(2)巷道通行效率t。在避險時，井下人員通過巷道會遇到多種情況[8]：當巷道高度較標準巷道偏低時，逃生人員必須放慢速度彎腰前行；當發(fā)生突水時，巷道內有積水會影響逃生效率；人員在巷道中行走時會逐漸適應黑暗環(huán)境，通行速度會受影響。表1中列出了人員在不同避難情況下的通行效率，其中通行效率大小是個相對比值，無量綱。在實際應用中，可以根據(jù)巷道的實際情況選擇統(tǒng)一標準，如以彎腰狀態(tài)為計算標準1時，爬行的通行效率為2，自由行走為0.5，沒膝水中的通行效率為1。

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

(3)巷道的當量長度wij。井下巷道網(wǎng)絡中相鄰節(jié)點的權值一般用巷道的長度來表示。因各種因素的影響，即使對于同樣長的巷道，其實際巷道長度也有所不同，所以應將影響因素考慮進去。將巷道的實際長度乘以各種影響系數(shù)，就得到了巷道的當量長度wij[9]：

(3)

式中，aij、aw、ap、af和av分別表示巷道高度、寬度、坡度、泥濘程度和風速的影響系數(shù)，其取值可以通過礦井的實際數(shù)據(jù)信息獲得經(jīng)驗值；lij為巷道的實際長度，n為局部障礙物的個數(shù)，lm為局部障礙物的當量長度。

2 K則最優(yōu)避災路徑的求解

井下發(fā)生突水時，需要考慮多條避災線路，即找到從人員所在起止點到安全點的可達路徑中耗費最小、次小直至第K小的線路，從而提高逃生效率?；谑?1)建立的數(shù)學模型，提出了一種便于求解礦井突水時K則最優(yōu)避災路徑的方法，具體如下。

2.1 構建一個帶權有向圖

礦井避災路線圖的表現(xiàn)形式一般為數(shù)字化的矢量地圖，需對其進行預處理，轉換成由頂點和弧組成的網(wǎng)絡圖的形式。首先將實際礦井避災線路圖(.dwg格式)轉換成矢量地圖(.shp格式)，提取出線類圖元數(shù)據(jù)中的巷道信息，存入相應的巷道文件；然后對巷道進行拓撲檢查、剪斷處理，對打斷后的路段進行節(jié)點、中途點位置坐標及其屬性特征的定義，將處理過的路段和節(jié)點分別存入路段數(shù)據(jù)集和節(jié)點數(shù)據(jù)集中。因井下巷道地理位置比較復雜，1條巷道可能與若干條巷道相交或相連，因此以巷道的交叉點為結點進行分割，將巷道交叉點作為網(wǎng)絡圖的頂點，路段為網(wǎng)絡的??；最后采用十字鏈表的數(shù)據(jù)結構[10]生成有向圖G=(V，E，W)，V表示巷道節(jié)點，E表示弧段，W表示弧段上對應的巷道當量長度。

2.2 K則最優(yōu)避災路徑的具體實現(xiàn)

在帶權有向圖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則最優(yōu)路徑的實現(xiàn)如下所示。

(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的搜索路徑的循環(huán)次數(shù)，即路徑條數(shù)，此時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)循環(huán)執(zhí)行步驟(2)和(4)可以依次取得v0到vn的所有路徑，即一共f條路徑。將所求得的f條路徑排序，這樣就可以找出K條最優(yōu)路徑。

3 應用實例

以斜溝煤礦的實際巷道通風系統(tǒng)圖為基礎數(shù)據(jù)，利用C#程序設計語言實現(xiàn)K則最優(yōu)避災路徑的選擇，便于指導井下人員的逃生。

根據(jù)礦井巷道的實際參數(shù)，結合式(2)和式(3)可以得出各個巷道的當量長度wij及其對應系數(shù)pkwij，見表2。

表2 各巷道當量長度Table 2 The equivalent lengths of all tunnels

利用C#程序，通過Windows窗體應用程序實現(xiàn)最優(yōu)避災路線分析系統(tǒng)的界面顯示，有以下優(yōu)點：

(1)利用了基于改進的Dijkstra建立的最優(yōu)避災路線的數(shù)學模型，使得計算結果直觀顯示。

(2)輸入任意2點可以求得其最短路徑，便于井下人員快速安全的撤離。

圖1 最短路徑在網(wǎng)絡圖中的顯示

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

4 結 論

K則最優(yōu)水害避災路線的研究在保證礦井安全高效的工作中具有重要意義。本研究基于改進的Dijkstra算法，結合礦井突水時的實際情況，引入了巷道的等價權因子，建立了最優(yōu)避災路徑的數(shù)學模型，并利用C#語言,通過窗體界面得到直觀有效的實現(xiàn)。當發(fā)生突水時，井下人員可以通過專業(yè)的小靈通設備獲得最優(yōu)避災路線，便于安全撤離。但是由于井下突水時實際參數(shù)會動態(tài)變化，如何將動態(tài)的參數(shù)實時準確地考慮進去并及時通知井下人員，是需要進一步深入解決的問題。

[1] 汪金花，張亞靜，朱令起，等.井下避險最優(yōu)路徑機理與數(shù)學建模研究[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則最優(yōu)路徑算法[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算法的設計與實現(xiàn)[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中的優(yōu)化實現(xiàn)[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數(shù)學模型與水災仿真實驗[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 的礦井應急救援系統(tǒng)的研究及應用[J]． 礦業(yè)安全與環(huán)保，2009，36：64-67． Yang Yihui，F(xiàn)eng 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則最優(yōu)避災路徑研究[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] 王海梅，周獻中.網(wǎng)絡系統(tǒng)中的最短路徑分析及其應用研究[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