基于最短路徑算法的艦船通道逃逸路線研究

1 引 言

艦船逃逸路線是指災(zāi)害區(qū)域及可能受到威脅區(qū)域的艦員撤離到安全地點的路線[1]，它直接關(guān)系到遇險艦員的生命安全。由于艦船通道普遍比較狹窄，而且通往露天區(qū)域的出口有限，其本身的復(fù)雜性以及災(zāi)害的蔓延對逃生通道的影響，使得選擇合理的逃逸路線往往成為一件比較棘手的工作。而一套良好的救生通道設(shè)計方案能大大減少艦員疏散撤離的時間，提高艦員獲救的幾率。因此，開展艦艇救生通道設(shè)計方面的研究不僅是必要的，而且意義重大。本文就如何采用圖論原理結(jié)合計算機技術(shù)，對逃逸路線的選擇與規(guī)劃進行了初步探索研究。

2 現(xiàn)有求解逃逸路線的方法

現(xiàn)有最佳逃逸路線的研究主要集中在對高層建筑通道疏散、礦井井巷逃生和緊急情況(如毒氣泄漏等)疏散逃生的研究上，國內(nèi)一些專家學(xué)者主要是針對火災(zāi)時的最佳逃逸路線進行研究[2-5]。以上的研究都是以圖論的最短路理論為基礎(chǔ)而展開的，其基本設(shè)計思想是求解安全且具有最短行走時間的路線。不同學(xué)者采用不同的路權(quán)來描述通道通行的難易程度。艦船通道系統(tǒng)的逃生情況與以上幾種情況類似，可以借鑒數(shù)學(xué)建模的方法指導(dǎo)艦船逃逸路線的研究。

如今有少數(shù)學(xué)者利用GIS(地理信息系統(tǒng))技術(shù)開發(fā)智能逃逸系統(tǒng)進行網(wǎng)絡(luò)分析，開發(fā)出了友好的用戶界面，已經(jīng)應(yīng)用于實際的救災(zāi)工作。

當(dāng)今艦艇及民船上經(jīng)常采用的方法主要是利用現(xiàn)有的設(shè)備幫助艦員選擇救生路線，并采用每隔一段時間的訓(xùn)練、演習(xí)、廣播等使艦員對救生通道更為熟悉，在事故發(fā)生時減少判斷錯誤的發(fā)生頻率?？梢?，常用的方法主要是經(jīng)驗的推廣，與先進的逃逸系統(tǒng)相比，無疑后者更嚴(yán)謹(jǐn)更具有發(fā)展前景[6]。作為研究的起步工作，需要將圖論等技術(shù)應(yīng)用到實際的艦船通道逃逸路線規(guī)劃中來，建立初步的研究模型。

3 艦船逃逸路線的計算方法

3.1 道路權(quán)重的確定

求解合理的逃逸線路從實質(zhì)上講是求解安全撤退的最短時間。最短距離的撤退路線不等于最短的撤退時間，這是因為通道的通行難易程度不一樣。對于艦船通道，需要考慮的影響人員通行速度和路線選擇的因素主要有：甲板層高、樓梯的坡度、障礙物的影響、有毒有害氣體濃度、高溫?zé)熈髯枞ǖ赖?。這些影響因素與民用建筑人員逃生的影響要素很相似，而不少學(xué)者通常用“當(dāng)量長度”來綜合描述建筑物中的這些影響因素。因此，本文引入“當(dāng)量長度”的概念來描述艦船通道各路段的綜合屬性，文獻[3]的研究方法將這些影響因素用通行難易程度來表示，使之與通道的實際長度相乘后得到的長度即為“當(dāng)量長度”。用當(dāng)量長度表示路權(quán)不僅考慮了通道長度和可達性，而且考慮了人員分布密度情況以及通行的難易程度。為便于比較和分析，文章分別用各路段行走時間和“當(dāng)量長度”來表示路段的通行難易程度。

第i條通道的當(dāng)量長度可用下式來表示：

(1)

式中,li——第i條通道的當(dāng)量長度值，m；

ω——煙流體積分?jǐn)?shù)懲罰系數(shù)；

c——有害氣體體積分?jǐn)?shù)；

ρ——群集密度，ρ=P/(B·lri)，P、B分別為通道人數(shù)和寬度；

lri——第i條通道的實際長度；

kt——通道類型的難易系數(shù)；

ki——不同區(qū)域的危險系數(shù)。

選擇逃逸路線時，應(yīng)首先分析各通道在災(zāi)變時是否適合人員通行；按照上述方法可以計算出通道的當(dāng)量長度(即路權(quán))，形成當(dāng)量長度的鄰接矩陣。在此基礎(chǔ)上，根據(jù)艦船通道形成的網(wǎng)絡(luò)情況，采用一定的算法選擇艦員的合理逃逸路線。

3.2 前N條最短路算法描述

圖論中經(jīng)典的最短路算法主要包括Dijkstra及Floyd算法，但它們只能求取第1最短路徑而不能求得第2， …，N最短路徑。這不能滿足疏散逃逸需要多條備選路徑的要求。由于災(zāi)變的發(fā)展有某些不可預(yù)測因素，當(dāng)?shù)?最短路徑行不通時，可選用第2、第3最短路徑，故引出求解多條救災(zāi)與逃逸路線的前N條最短路問題(也稱K最短路問題)。

本文前N條最短路算法的基本思想是:首先采用Floyd算法在原圖中求兩節(jié)點間的最短路徑(Floyd算法便于求解任意兩點間的最短路)，然后依次刪除最短路徑上的邊，每刪除一條邊生成一個子圖，再在子圖中用最短路算法求最短路，依次循環(huán)調(diào)用最短路算法，可求得前N條最短路徑[7]。

算法具體步驟和運行流程圖(圖1)如下:

1) 首先運用Floyd算法求出從源節(jié)點s到t的最短路徑r0； 將r0插入備選集Pi；

2) 依次刪除最短路徑上的邊，生成與路徑的邊相同數(shù)目的子圖，在各自得到的子圖r中調(diào)用最短路徑算法得到路徑集。標(biāo)記r為已處理。

圖1 求解前N條逃逸路線程序流程圖

3)P中的路徑數(shù)已達到或超過N值，轉(zhuǎn)步驟5)。

4) 在路徑中尋找未處理的路徑，將其標(biāo)記為當(dāng)前待處理的路徑，轉(zhuǎn)步驟2)。

5) 將路徑備選集的多條路徑返回，算法結(jié)束。

4 選擇逃逸路線的方法應(yīng)用

某艦的局部區(qū)段簡化路線示意圖如圖2所示，圖中對區(qū)段進行了網(wǎng)絡(luò)化(彎曲路線用直線表示，各路段比例不代表實際情況)，整個網(wǎng)絡(luò)共有67條分支，42個節(jié)點。上下兩個平面上縱橫交錯的直線為各層甲板的主要通道，連接兩層甲板的直線表示樓梯。由于某地發(fā)生事故或火災(zāi)，需要將事故節(jié)點所在地人員疏散到安全地點。

4.1 艦船路網(wǎng)鄰接矩陣的計算

本文使用鄰接矩陣作為路網(wǎng)的存儲方式，用一個二維數(shù)組C[i][j]表示，由于通道網(wǎng)絡(luò)為帶權(quán)圖，所以其鄰接矩陣表示為:

(2)

上式中，wij表示該路段的權(quán)值，本文分別用兩種參數(shù)來表示：各路段的行走時間和當(dāng)量長度。參考文獻[7]中的一項實測研究結(jié)果表明，當(dāng)人員密度為0.5人/m2<ρ≤1.5人/m2時，人員遷移流動呈自由流動狀態(tài)，人員平均步速為1.3 m/s；當(dāng)人員密度為1.5人/m2<ρ≤3人/m2時，人員平均步速為0.7 m/s，人員流動呈現(xiàn)滯留流動狀態(tài)；在人員密度為1.5人/m2以下時，密度的提高導(dǎo)致速度降低并不明顯，但是超過這一密度時，隨著密度的提高，速度明顯下降。同時表明，樓梯間中的人流速度約為水平人流速度的一半。

考慮建筑通道與艦船通道的區(qū)別。假定艦員疏散時，所有通道都是暢通的，門和梯口蓋完全打開；假定艦員普遍是訓(xùn)練有素的青壯年人員，艦船狹窄的通道會一定程度上影響艦員的行進速度。參考以上假設(shè)和研究，平直通道速度取為1.0 m/s；艦上樓梯比建筑樓梯要陡，取上行通過速度和下行速度的折中值為0.5 m/s；直梯上的通行速度約為0.4 m/s；而對于通道網(wǎng)絡(luò)的各路段的人員密度情況，假定在各個樓梯附近為滯留狀態(tài)，在平直通道為微滯留或自由流動狀態(tài)，在多條交叉路口為微滯留狀態(tài)，根據(jù)如上假設(shè)進行路段時間和當(dāng)量長度的計算。這些參數(shù)的取值和假設(shè)還需要通過實驗來進行進一步驗證。

圖2 通道網(wǎng)絡(luò)示意圖

4.2 運用N最短路算法求解合理逃逸路線

運用Matlab編程工具實現(xiàn)了N最短路相關(guān)算法在艦船路網(wǎng)計算上的運用，利用Matlab 6.5的圖形用戶界面編制程序的操作界面，直觀簡潔便于操作。程序啟動時，在程序界面輸入起點和終點節(jié)點號，即可得出計算機處理的3條逃逸路線及相關(guān)信息。任意指定幾個艦員位置(或遇災(zāi)區(qū)域)和逃生出口，計算機處理的逃逸路線如下(表1～表3)：

表1 節(jié)點39逃逸路線計算表

表2 節(jié)點40逃逸路線計算表

表3 當(dāng)量長度計算逃逸路徑表

通過各點間最短路徑的計算，可以為艦船逃生出口的路線分派提供依據(jù)。計算的結(jié)果不僅可以顯示各個點(或途經(jīng)各點)到各個出口的遠近，便于選擇合理的出口，而且容易看到路徑的使用情況。比如39節(jié)點到32或33出口的逃逸時間明顯比到34出口時間短，即可以引導(dǎo)途經(jīng)39節(jié)點的逃生人員優(yōu)先選擇這兩個出口逃生。

如果由于火勢蔓延等原因，導(dǎo)致某一條或幾條通道路徑堵塞，或者環(huán)境惡劣艦員無法通過，只需要將該條路段的權(quán)值設(shè)為∞或者一個很大的正整數(shù)，那么計算機在搜尋路徑的時候會自動改變可通行性條件，自動避開該條路徑。比如正常情況下，從節(jié)點40逃逸的出口首選節(jié)點33，最短路距為38.5 s，路線為：40→26→42→29→17→18→33。當(dāng)節(jié)點17附近發(fā)生較大的火災(zāi)時，假定短時間內(nèi)通道17→18或17→29被煙流嚴(yán)重污染，在實際中不可通行。這時，基于最短路線所計算出的疏散時間是不合理的。將該路段權(quán)值設(shè)為∞，重新計算可以得出節(jié)點40合理的疏散路線為：40→26→42→28→27→ 6→ 5→12→13→18→33，路距66.5 s；40→26→24→22→20→9→10→15→34，路距58.5 s；40→26→42→28→27→ 6→7→4→31， 路距60.5 s。從計算結(jié)果可看出，合理可行的疏散路線比最短路線合理。而重新計算的結(jié)果顯示，此時的逃逸首選出口變?yōu)?4和31而不是33。這樣求解的疏散路線安全性要更高，能合理地指導(dǎo)逃生艦員安全疏散出去。

通過表1、表2和表3的比較，采用路段行駛時間和當(dāng)量長度來表示路權(quán)，得出的路線結(jié)果大體一致，說明兩種方法的計算都有其合理性，但也存在差異。比如，通過兩種計算方法得到的節(jié)點40到34的計算結(jié)果就不同，這是途經(jīng)路段的人員密度不同造成的?？梢姰?dāng)量長度考慮了路段寬度和人員密度對道路通行的影響，使得不同路段的差別增大。采用當(dāng)量長度來表示路段的通行難易程度，得出的結(jié)果更貼近實際更有實用價值。

5 結(jié)論和建議

本文探討了N-最短路算法在艦船通道逃逸路線研究上的應(yīng)用。在假定災(zāi)害的前提條件下，對災(zāi)害時期通道的可通行性、通行的難易度、N最短路算法等進行了深入研究。對影響通道通行難易程度的因素進行分析，引進“當(dāng)量長度”的概念并建立了相應(yīng)的計算模型，結(jié)合N最短路算法對某艦艙段的疏散路徑進行了計算，并進行了分析總結(jié)。

盡管對該論題的研究還是初探，但對于艦上指揮員決策和總布置設(shè)計具有一定的指導(dǎo)意義，今后尚需進一步研究和解決的問題是：

1) 煙流濃度和人員分布密度是動態(tài)變化的，如何求解不同時刻的最佳疏散路線。

2) 利用GIS技術(shù)實現(xiàn)通道系統(tǒng)的可視化，能夠用圖形直觀顯示結(jié)果和路徑，使操作人員操作更方便。

3) 將“艦船事故逃逸路線系統(tǒng)”與艦艇損管系統(tǒng)的設(shè)計相結(jié)合。

[1] 付恩俊，唐安東.井下火災(zāi)期間最佳避災(zāi)路線的選擇[J].煤礦安全，2006，37(10)：32-34.

[2] 李興東.礦井火災(zāi)時期避災(zāi)路線的確定及其應(yīng)用程序[J].煤礦安全，2001，32(12)：20-22．

[3] 謝旭陽，任愛珠，周心權(quán).高層建筑火災(zāi)最佳疏散路線的確定[J].自然災(zāi)害學(xué)報，2003，12(3)：75-80.

[4] XIAO Guo-qing，WEN Li-min， CHEN Bao-zhi. Study on model of dangerous areas in poison gas leakage[C]∥Progress in safety science and technology.Beijing：Chemical Industry Press，2000:302-306.

[5] 陳金國，朱金福.礦山災(zāi)變環(huán)境下逃逸路徑優(yōu)化算法[J].煤礦安全，2005,36(11):54-56.

[6] 胡曉芳，胡勇，程劍.綜合安全評估在艦艇救生通道優(yōu)化設(shè)計中的應(yīng)用[J].艦船科學(xué)技術(shù)，2006,28(6):121-124.

[7] 柴登峰，張登榮.前N最短路徑問題的算法與應(yīng)用[J].浙江大學(xué)學(xué)報(工學(xué)版)，2002，36(5)：531-534．