1 引 言

艦船通道設計是艦船總布置設計的重要任務之一，通道設計的優(yōu)劣直接影響到總布置設計的合理性。廣義的通道布置設計包括對走道、門、艙口、梯的布置等。一般的具體要求包括應便于戰(zhàn)斗行動、人員流通、物品運送和設備搬運等各種活動的進行；流通路線應盡量短、直而流暢，并保證所有艙室和部位都可以到達等，這就涉及到線路的優(yōu)化選擇的問題。優(yōu)化的通道布置和路線設計不僅可以提高船舶人流、物流的效率，而且非常有助于對艦船上管網(wǎng)電網(wǎng)布置、逃生消防等諸多方面的設計。

在通道路線優(yōu)化設計這一問題上，一項重要的任務就是尋找兩點之間的最短路徑的問題，而最短路徑的問題是圖論理論的一個經(jīng)典問題。從圖論網(wǎng)絡模型的角度看，尋找最短路徑就是在指定網(wǎng)絡中兩結點間找一條阻礙強度最小的路徑。根據(jù)阻礙強度的不同定義，最短路徑不僅僅指一般地理意義上的距離最短，還可以引申到其它的度量，如時間、費用、線路容量等[1]。本文所研究的最短路徑就是指行程時間最短的路徑。

最短路徑算法的選擇與實現(xiàn)是通道路線設計的基礎，最短路徑算法是計算機科學與地理信息科學等領域的研究熱點，很多網(wǎng)絡相關問題均可納入最短路徑問題的范疇之中。經(jīng)典的圖論與不斷發(fā)展完善的計算機數(shù)據(jù)結構及算法的有效結合使得新的最短路徑算法不斷涌現(xiàn)。作為艦船通道路線優(yōu)化設計的一種嘗試，本文利用圖論的經(jīng)典理論和人群流量理論研究艦船人員通道路線的優(yōu)化設計及最優(yōu)線路選擇。首先介紹圖論相關理論，對船舶通道進行路網(wǎng)抽象，建立網(wǎng)絡圖，然后根據(jù)人群流動的相關理論，選取不同擁擠情況下的人員移動速度，從而確定各條路段(包括樓梯)的行程時間。以行程時間作為通道網(wǎng)絡的路權，得出路阻矩陣以選擇一對起點/終點的最短時間路線為目標，建立最短路徑問題的數(shù)學模型，利用經(jīng)典的Floyd算法確定最短路徑。將此方法應用于某艦艇多層甲板的通道網(wǎng)絡中，計算結果并進行討論，最后在此研究的基礎上對通道設計相關問題的深化和拓展進行了探討和總結，并提出設想。

2 最短路徑問題的圖論描述

2.1 圖論及其相關概念

圖論中的圖的概念與通常意義上的圖的概念是完全不同的，圖論中的圖是表明一些點及這些點之間的路線溝通情況，用點表示研究的對象，用邊表示這些對象之間的聯(lián)系。圖論中將有序三元(或多元)組稱為一幅圖，即

G=(V，E，W)

式中，V為圖中所有頂點(Node)的集合，V={v1,v2…，vn}；E為邊(Edge)的集合，E={(e1，e2…，en)}；W(Weight)為各路段的道路權值。如果給圖中的點和邊賦予具體的含義和權值，并規(guī)定了起點和終點，這樣的圖即稱為網(wǎng)絡圖。如果每條邊上有箭頭標注，稱為有向圖，如果將有向圖去掉箭頭，得到一個無向圖，稱為基礎圖。

2.2 路網(wǎng)結構的建立分析

路線優(yōu)化技術通常采用圖論中的“圖”來表示路網(wǎng)，船舶通道路網(wǎng)與圖論的路網(wǎng)對應關系為：

結點——通道的交叉口或斷頭路的終點；邊——兩結點之間的路段稱為邊，若規(guī)定了路段的方向，則稱為?。贿?弧)的權——路段某個或某些特征屬性的量化表示。

路權的標定決定了最短的路徑搜索依據(jù)，也就是搜索指標。根據(jù)不同的最優(yōu)目標，可以選擇不同的路段屬性。由于艦船上除了平面上的通道之外還有垂直方向的樓梯(或直梯)，如果以最短路程距離作為優(yōu)化目標，路線的效率未必最高(距離最短未必耗時最少)。所以，以最短行程時間作為優(yōu)化的目標，道路權重即為各路段的平均行程時間。

對于本文要研究的對象，取各條通道的起點(或終點)和交叉點為圖的頂點，各路段為邊，路權為路段行走的平均時間。尋找從起點到終點的最短時間路徑即為最優(yōu)路徑。在規(guī)定了結點、邊和權值以后，便將路網(wǎng)抽象為一個賦權無向圖或賦權有向圖，從而確定路網(wǎng)中某兩地間的最優(yōu)路線便轉化為圖論中的最短路徑問題。

可見，最短路徑問題就是一個賦權圖的優(yōu)化問題，簡單的數(shù)學描述為：P是G中從s到t的一條路(s表示起點，t表示終點)，定義路P的權為W(P)，最短路徑問題就是要在所有s到t的路徑中求出一條權最小的路徑，即求一條從s到t的路徑P0，使W(P0)=minW(P)，稱P0是從s到t的最短路徑。

3 道路權重的標定確定路阻鄰接矩陣

3.1 人員遷移流動的特性

國內外對人群流動特性的研究方興未艾，主要包括交通人流的研究和疏散人流研究的兩個方面，他們對人員遷移流動的特性的研究，都是將通道內的人群作為一個整體處理。人流包含一定數(shù)目的人員，具有一定的長度與寬度，具有一定的人員密度。不同的密度下，人流具有不同的行走速度。由于艦船的空間普遍緊張，人員分布密度較大，走道樓梯也相對狹窄，特別是在人員奔赴崗位和逃生兩種狀態(tài)下，人員的流動就表現(xiàn)為人群的流動。

與人群的流動相關的概念有：人員密度(單位面積人員的個數(shù))；人的行動速度(單位時間內人行走的距離)；人流速度(人流整體的行進速度)，其值為人流首端的行進速度。在正常狀態(tài)下， 一般人的行動速度見表1[2]。

表1 人的行動速度

研究證明，一般而言，人流流量= 人流速度×人流密度×通道寬度，而人流速度是人流密度的函數(shù)。定性地講，人流密度越大，人與人之間的距離越小，則人的步行速度越慢，人員移動越緩慢；反之密度越小，人員移動越快。人流密度過大或者過小都會影響步行速度，從而也影響到人流流量的大小。

根據(jù)參考文獻[3]中，國外的一項實測研究結果表明，人流密度對疏散速度的影響從定量來講，人群疏散受步幅限制，并得出結論如下：

1) 當疏散通道中，人流密度ρ=1.0人/m2時，則人流遷移流動呈自由流動狀態(tài),相應的遷移流動的水平速度為V=1.3 m/s；

2) 當疏散通道中，人流密度ρ=2.0 人/m2時，則人流遷移流動開始呈現(xiàn)滯留流動狀態(tài),相應的遷移流動的水平速度為V=0.7 m/s；

3) 當疏散通道中，人流密度ρ= 5.38人/m2時，則人流遷移流動完全處于停滯狀態(tài),相應的遷移流動的水平速度為V=0.0 m/s；

4) 在某一密度以下時，密度的提高，隨之而產(chǎn)生的速度降低并不明顯，但是超過某一密度時，隨著密度的提高，速度明顯下降。這里的某一密度，是指1.5人/m2左右。

而人流在樓梯中的速度，由參考文獻[4]中國外對人流在樓梯中速度的一項實測研究結果表明，一般正常人在不擁擠的樓梯中的行走速度為0.52～0.62 m/s之間；超過65歲的老人在不擁擠的樓梯中的速度為0.43 m/s，而2～5歲的小孩在不擁擠的樓梯中的速度為0.45 m/s。由此可見，樓梯中的人流速度約為水平通道人流速度的二分之一。

表2是人員的行走速度與密度之間的關系[3]。

表2 人行速度、密度與流量關系

3.2 路權的確定

參考以上的研究，考慮建筑通道與船舶通道的區(qū)別，可以得出如下啟示：

1) 艦船上人員奔赴戰(zhàn)位時，在平面上行走的密度必須保證人流呈自由流動狀態(tài)，至少為微滯留狀態(tài)，這樣才能保證行進效率，確保不發(fā)生擁堵。其速度范圍為1.0～1.4 m/s，取為1.25 m/s;

2) 艦船上樓梯比建筑樓梯要陡，所以參考表2，取上行通過速度和下行速度的折中值為0.6 m/s;

3) 直梯的速度約為0.4 m/s;

4 算法的實現(xiàn)和應用

確定路網(wǎng)表達方法、存儲結構、最優(yōu)目標、道路權值后，就可以利用賦權有向圖的最短路徑算法，求解路網(wǎng)中任意出發(fā)地到目的地之間的最優(yōu)路徑了。在求解網(wǎng)絡圖上節(jié)點間最短路徑的方法中，目前國內外一致公認的較好算法有迪杰斯特拉(Dijkstra)及弗羅伊德(Floyd)算法[5]。這兩種算法中，網(wǎng)絡被抽象為一個圖論中定義的有向或無向圖，并利用圖的節(jié)點鄰接矩陣記錄點間的關聯(lián)信息。在進行圖的遍歷以搜索最短路徑時，以該矩陣為基礎不斷進行目標值的最小性判別，直到獲得最后的優(yōu)化路徑。

Dijkstra算法是圖論中確定最短路的基本方法，也是其它算法的基礎。為了求出賦權圖中任意兩結點之間的最短路徑，通常采用兩種方法。一種方法是每次以一個結點為源點，重復執(zhí)行Dijkstra算法n次。另一種方法是由Floyd于1962年提出的Floyd算法，其時間復雜度為O(n3),雖然與重復執(zhí)行Dijkstra算法n次的時間復雜度相同，但其形式上略為簡單，且實際運算效果要好于前者。

4.1 圖的建立

首先將空間問題抽象為圖，圖1為某艦的兩層甲板的部分抽象圖，上下兩個平面上縱橫交錯的直線為各層甲板的主要通道，連接兩層甲板的直線表示樓梯，包括2個直梯和3個斜梯。每條路段上的標注(a,b)中，a表示路段實際長度或者樓梯的類型，m;b表示此路段的行程時間(即路權)，s如(40，32)。

圖1 兩層甲板的部分抽象圖

按照圖的定義建立如下所示的賦權圖，見圖2。

圖2 賦權圖

4.2 確定路阻矩陣

根據(jù)賦權圖建立路阻矩陣:

則有D=

[2]1234567891011121314151617181032in8infinfinfinfinfinfinfinfinfinfinfinfinfinf 232016inf16infinfinfinfinfinfinfinfinfinfinfinfinf 3inf16016infinfinfinfinfinf4．8infinfinfinfinfinfinf 48infinf024infinfinfinfinfinfinfinfinfinf6．25infinf 5inf16inf24016inf8infinfinfinfinfinfinfinfinfinf 6infinf16inf16016infinfinfinfinfinfinfinfinfinfinf 7infinfinfinfinf1608infinfinfinf6．3infinfinfinfinf 8infinfinfinf8infinf032infinfinfinfinfinfinf4．8inf 9infinfinfinfinfinf8320infinfinfinfinfinfinfinf4．8 10infinfinfinfinfinfinfinfinf0inf32infinfinf8infinf 11infinf4．8infinfinfinfinfinfinf016inf8infinfinfinf 12infinfinfinfinfinfinfinfinf32160infinf8infinfinf 13infinfinfinfinfinf6．25infinfinfinfinf0infinfinfinf16 14infinfinfinfinfinfinfinfinfinf8infinf016infinfinf 15infinfinfinfinfinfinfinfinfinfinf8inf1602416inf 16infinfinf6．25infinfinfinfinf8infinfinfinf240infinf 17infinfinfinfinfinfinf4．8infinfinfinfinfinf16inf032 18infinfinfinfinfinfinfinf4．8infinfinf16infinfinf320

4.3 運用Floyd算法確定最短路徑

Floyd算法的功能是通過一個圖的路權矩陣求出每兩點之間的最短距離，這種算法的優(yōu)點是容易理解，可以算出任意兩點間的最短路徑；缺點是其復雜度為三次方，不適合大量的數(shù)據(jù)處理。

Floyd算法的基本原理和實現(xiàn)方法為：如果一個矩陣D=[dij],其中dij>0表示i與j間的距離，若i與j間無路可通，則dij為無窮大。i與j間的最短距離存在經(jīng)過i與j間的k和不經(jīng)過k兩種情況，所以可以令k=1，2, 3，……，n(n為節(jié)點數(shù))。檢查dij與dik+dkj的值，在此，dik與dkj分別為目前所知的i到k與k到j的最短距離，因此，dik+dkj就是i到j經(jīng)過k的最短距離。所以，若有dij>dik+dkj,就表示從i出發(fā)經(jīng)k再到j的距離要比原來的i到j距離短，自然把i到j的dij重寫成dik+dkj。每當一個k搜索完，dij就是目前i到j的最短距離。重復這一過程，最后當查完所有k時，dij就為i到j的最短距離。

運用Matlab編程工具編寫的程序，其核心代碼如下：

……

for k=1:n

for i=1:n

for j=1:n

if D(i,k)+D(k,j)

D(i,j)=D(i,k)+D(k,j);%修改長度

path(i,j)=path(i,k);%修改路徑

end

end

end

……

選取任意兩點輸入Matlab程序運行，可得到兩點間最短路徑。舉幾個實例見表3。

表3 計算結果

5 總結與設想

運用經(jīng)典的圖論算法確定最短路徑的這種方法，是艦船通道線路優(yōu)化設計的基礎，本文提取簡化的艦船通道線路模型，參考流量理論建立賦權圖，運用合適的算法能夠求得網(wǎng)絡圖中任意兩點間的最優(yōu)路徑。對于船舶特別是對大型艦船，或者甲板層數(shù)多、路線復雜并且人員密度大的艦船，合理的路線設計具有重要的現(xiàn)實意義，本文的方法對艦船通道設計路線優(yōu)化技術的研究起到了基礎性的作用。

本文的研究是建立在簡化模型的基礎上，實際的情況可能更復雜，未來還有許多值得研究和探討的問題，比如：

1) 流動的人群在移動的過程中表現(xiàn)為具有相互聯(lián)系的三種狀態(tài):集結、流動、滯留狀態(tài)。而滯留常常發(fā)生在艙室的開口部位，如房間的出口、樓梯的入口等位置。本文假設所有的人群都是自由流動的，這與實際情況并不完全符合。所以，在最短行程時間路徑的確立上能否考慮滯留時間，或者能否預測滯留地點，或者提出帶流量控制權值或考慮道路通行能力的圖論方法，建立一個多目標優(yōu)化的數(shù)學模型；

2) 最短路徑也許并不是最優(yōu)路徑，在許多點上的人群一起移動時，最短路徑的某些地段可能出現(xiàn)擁堵，這樣就必須考慮選擇次優(yōu)路徑的問題；

3) 對甲板層數(shù)多或者路線復雜的通道網(wǎng)絡，如果采用人工標點來建立網(wǎng)絡，這會是一個非常煩瑣的工作，而且如果網(wǎng)絡過于復雜，經(jīng)典的圖論算法就需要作一些改進；

4) 能否借鑒智能交通系統(tǒng)(比如地理信息系統(tǒng)(GIS)和智能運輸系統(tǒng)(ITS))對交通實時誘導的相關理論，建立船舶道路系統(tǒng)的數(shù)據(jù)庫和路網(wǎng)結構，在此基礎上實現(xiàn)智能搜索最優(yōu)及次優(yōu)路徑，這些都是以后需要研究的問題[6]。

[1] 戴文舟.交通網(wǎng)絡中最短路徑算法的研究[D].重慶大學碩士學位論文，2004.

[2] PROUHX G.Evacuation time and movement in apartment buildings[J]. Fire Safety Journal,1995(24):229-246.

[3] 謝灼利，等.地鐵車站站臺火災中人員的安全疏散[J].中國安全科學學報，2004，14(7)：21.

[4] 建筑防火設計與應用[M].中國建筑學會防火綜合技術委員會.北京:海洋出版社,1991.

[5] 王平.大型公共建筑人員疏散性能化評估軟件的開發(fā).武漢大學碩士學位論文[D]，2005.

[6] 榮瑋.基于道路網(wǎng)的最短路徑算法的研究與實現(xiàn).武漢理工大學碩士學位論文[D]，2005.