基于圖論的艦船通道路線優(yōu)化

1 引 言

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

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

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

2 最短路徑問(wèn)題的圖論描述

2.1 圖論及其相關(guān)概念

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

G=(V，E，W)

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

2.2 路網(wǎng)結(jié)構(gòu)的建立分析

路線優(yōu)化技術(shù)通常采用圖論中的“圖”來(lái)表示路網(wǎng)，船舶通道路網(wǎng)與圖論的路網(wǎng)對(duì)應(yīng)關(guān)系為：

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

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

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

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

3 道路權(quán)重的標(biāo)定確定路阻鄰接矩陣

3.1 人員遷移流動(dòng)的特性

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

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

表1 人的行動(dòng)速度

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

根據(jù)參考文獻(xiàn)[3]中，國(guó)外的一項(xiàng)實(shí)測(cè)研究結(jié)果表明，人流密度對(duì)疏散速度的影響從定量來(lái)講，人群疏散受步幅限制，并得出結(jié)論如下：

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

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

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

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

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

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

表2 人行速度、密度與流量關(guān)系

3.2 路權(quán)的確定

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

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

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

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

4 算法的實(shí)現(xiàn)和應(yīng)用

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

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

4.1 圖的建立

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

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

按照?qǐng)D的定義建立如下所示的賦權(quán)圖，見(jiàn)圖2。

圖2 賦權(quán)圖

4.2 確定路阻矩陣

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

則有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 運(yùn)用Floyd算法確定最短路徑

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

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

運(yùn)用Matlab編程工具編寫(xiě)的程序，其核心代碼如下：

……

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);%修改長(zhǎng)度

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

end

end

end

……

選取任意兩點(diǎn)輸入Matlab程序運(yùn)行，可得到兩點(diǎn)間最短路徑。舉幾個(gè)實(shí)例見(jiàn)表3。

表3 計(jì)算結(jié)果

5 總結(jié)與設(shè)想

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

本文的研究是建立在簡(jiǎn)化模型的基礎(chǔ)上，實(shí)際的情況可能更復(fù)雜，未來(lái)還有許多值得研究和探討的問(wèn)題，比如：

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

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

3) 對(duì)甲板層數(shù)多或者路線復(fù)雜的通道網(wǎng)絡(luò)，如果采用人工標(biāo)點(diǎn)來(lái)建立網(wǎng)絡(luò)，這會(huì)是一個(gè)非常煩瑣的工作，而且如果網(wǎng)絡(luò)過(guò)于復(fù)雜，經(jīng)典的圖論算法就需要作一些改進(jìn)；

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

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

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

[3] 謝灼利，等.地鐵車站站臺(tái)火災(zāi)中人員的安全疏散[J].中國(guó)安全科學(xué)學(xué)報(bào)，2004，14(7)：21.

[4] 建筑防火設(shè)計(jì)與應(yīng)用[M].中國(guó)建筑學(xué)會(huì)防火綜合技術(shù)委員會(huì).北京:海洋出版社,1991.

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

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