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

成韶輝 張雪英 李鳳蓮 李 蕓

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

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

成韶輝 張雪英 李鳳蓮 李 蕓

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

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

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

(2)巷道通行效率t。在避險時，井下人員通過巷道會遇到多種情況[8]：當巷道高度較標準巷道偏低時，逃生人員必須放慢速度彎腰前行；當發(fā)生突水時，巷道內(nèi)有積水會影響逃生效率；人員在巷道中行走時會逐漸適應(yīng)黑暗環(huán)境，通行速度會受影響。表1中列出了人員在不同避難情況下的通行效率，其中通行效率大小是個相對比值，無量綱。在實際應(yīng)用中，可以根據(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)絡(luò)中相鄰節(jié)點的權(quán)值一般用巷道的長度來表示。因各種因素的影響，即使對于同樣長的巷道，其實際巷道長度也有所不同，所以應(yīng)將影響因素考慮進去。將巷道的實際長度乘以各種影響系數(shù)，就得到了巷道的當量長度wij[9]：

(3)

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

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

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

2.1 構(gòu)建一個帶權(quán)有向圖

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

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

在帶權(quá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)，構(gòu)造n+1階矩陣A=[aij]，其中aij=pkwij(pk為第k條巷道的等價權(quán)因子)，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 應(yīng)用實例

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

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

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

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

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

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

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

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

4 結(jié) 論

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

[1] 汪金花，張亞靜，朱令起，等.井下避險最優(yōu)路徑機理與數(shù)學(xué)建模研究[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].武漢大學(xué)學(xué)報：信息科學(xué)版，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算法的設(shè)計與實現(xiàn)[J]．遼寧工程技術(shù)大學(xué)學(xué)報:自然科學(xué)版，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]．北京理工大學(xué)學(xué)報，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ù)學(xué)模型與水災(zāi)仿真實驗[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 的礦井應(yīng)急救援系統(tǒng)的研究及應(yī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] 盛 武，高明中，楊 力，等.煤礦緊急避險體系構(gòu)建與應(yīng)急救援模型研究[J].中國安全科學(xué)學(xué)報，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] 盧國菊，王 飛．礦井火災(zāi)時期K則最優(yōu)避災(zāi)路徑研究[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)絡(luò)系統(tǒng)中的最短路徑分析及其應(yīng)用研究[J].兵工學(xué)報，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)，中國博士后科學(xué)基金第53批面上項目(編號：2013M530896)，山西省科技攻關(guān)項目(編號：20130321004-01)。

成韶輝(1989—)，女，碩士研究生。

TD745+.2

A

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