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

1 引 言

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

2 現有求解逃逸路線的方法

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

如今有少數學者利用GIS(地理信息系統)技術開發智能逃逸系統進行網絡分析，開發出了友好的用戶界面，已經應用于實際的救災工作。

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

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

3.1 道路權重的確定

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

第i條通道的當量長度可用下式來表示：

(1)

式中,li——第i條通道的當量長度值，m；

ω——煙流體積分數懲罰系數；

c——有害氣體體積分數；

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

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

kt——通道類型的難易系數；

ki——不同區域的危險系數。

選擇逃逸路線時，應首先分析各通道在災變時是否適合人員通行；按照上述方法可以計算出通道的當量長度(即路權)，形成當量長度的鄰接矩陣。在此基礎上，根據艦船通道形成的網絡情況，采用一定的算法選擇艦員的合理逃逸路線。

3.2 前N條最短路算法描述

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

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

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

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

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

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

3)P中的路徑數已達到或超過N值，轉步驟5)。

4) 在路徑中尋找未處理的路徑，將其標記為當前待處理的路徑，轉步驟2)。

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

4 選擇逃逸路線的方法應用

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

4.1 艦船路網鄰接矩陣的計算

本文使用鄰接矩陣作為路網的存儲方式，用一個二維數組C[i][j]表示，由于通道網絡為帶權圖，所以其鄰接矩陣表示為:

(2)

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

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

圖2 通道網絡示意圖

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

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

表1 節點39逃逸路線計算表

表2 節點40逃逸路線計算表

表3 當量長度計算逃逸路徑表

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

如果由于火勢蔓延等原因，導致某一條或幾條通道路徑堵塞，或者環境惡劣艦員無法通過，只需要將該條路段的權值設為∞或者一個很大的正整數，那么計算機在搜尋路徑的時候會自動改變可通行性條件，自動避開該條路徑。比如正常情況下，從節點40逃逸的出口首選節點33，最短路距為38.5 s，路線為：40→26→42→29→17→18→33。當節點17附近發生較大的火災時，假定短時間內通道17→18或17→29被煙流嚴重污染，在實際中不可通行。這時，基于最短路線所計算出的疏散時間是不合理的。將該路段權值設為∞，重新計算可以得出節點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。從計算結果可看出，合理可行的疏散路線比最短路線合理。而重新計算的結果顯示，此時的逃逸首選出口變為34和31而不是33。這樣求解的疏散路線安全性要更高，能合理地指導逃生艦員安全疏散出去。

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

5 結論和建議

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

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

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

2) 利用GIS技術實現通道系統的可視化，能夠用圖形直觀顯示結果和路徑，使操作人員操作更方便。

3) 將“艦船事故逃逸路線系統”與艦艇損管系統的設計相結合。

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

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

[3] 謝旭陽，任愛珠，周心權.高層建筑火災最佳疏散路線的確定[J].自然災害學報，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] 陳金國，朱金福.礦山災變環境下逃逸路徑優化算法[J].煤礦安全，2005,36(11):54-56.

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

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