趙寶強(qiáng)，劉佳銘

(1.中國艦船研究設(shè)計中心，湖北 武漢 430064；2.海軍裝備部重大專項裝備項目管理中心，北京 100071)

0 引 言

艦船通道設(shè)計[1-3]是艦船總布置設(shè)計的重要任務(wù)之一，通道直接影響人流、物流及損管等設(shè)計的合理性。通道布置設(shè)計應(yīng)能便于作戰(zhàn)行動、人員流通、物品運送和設(shè)備搬運等各種活動的進(jìn)行；流通路線應(yīng)盡量短、直而流暢，并保證所有艙室和部位都可達(dá)，這就涉及通道的設(shè)計和驗證。良好的通道設(shè)計不僅可以提高船舶人流、物流的效率，而日有助于損管工況下人員的緊急流通，使艦船及早恢復(fù)戰(zhàn)斗力和生命力。

艦船艙室、人員和部門較多，各種工況下人員部署和調(diào)度復(fù)雜。在艦船遭受導(dǎo)彈、魚雷等攻擊時，通道可能遭受損害，無法通行。針對此類問題，利用網(wǎng)絡(luò)流優(yōu)化算法開展艦船通道網(wǎng)絡(luò)完整工況和損害工況下的流量分析。網(wǎng)絡(luò)流優(yōu)化(Network Flow Optimazition)是一種尋找最優(yōu)解的成熟應(yīng)用數(shù)學(xué)方法，本文通過網(wǎng)絡(luò)流優(yōu)化搭建了包含兵艙、雷達(dá)室、指揮室和武器室等節(jié)點的簡化通道網(wǎng)絡(luò)，對此網(wǎng)絡(luò)建立數(shù)學(xué)模型并進(jìn)行戰(zhàn)斗部署下人員流動模擬。為模擬艦船通道N-1損害工況，依次對各段通道損害時的網(wǎng)絡(luò)流進(jìn)行了仿真。仿真結(jié)果對通道設(shè)計和生命力設(shè)計具有一定的參考意義。

1 網(wǎng)絡(luò)流模型

1.1 模型定義

網(wǎng)絡(luò)[4]是一個各條邊都有權(quán)值和方向的圖,網(wǎng)絡(luò)的每一條邊擁有一個最大的容量u，即該條邊可以容納的最大流量，x是流過該邊的實際流量，且總有x≤u。對于圖中每個頂點都應(yīng)滿足流出的流量和流入的流量差值為該頂點的供給/需求，即滿足能量守恒。

搭建包含兵艙、雷達(dá)室、指揮室和武器室等節(jié)點的2層甲板簡化通道網(wǎng)絡(luò)[5-6]，如圖1所示，模擬戰(zhàn)斗部署下12名士兵從兵艙前往各站位過程。簡化的通道網(wǎng)絡(luò)包含23個節(jié)點，各節(jié)點在實船位置（簡化示例）及站位設(shè)置如表1所示。由節(jié)點連接的弧如表2所示，該網(wǎng)絡(luò)包含26條弧，弧的方向為1表示為正向流，2表示為逆向流，3表示為雙向流，通道網(wǎng)絡(luò)的弧均為雙向流。所有弧的最大容量初步設(shè)置為8人。

1.2 模型求解

針對創(chuàng)建的網(wǎng)絡(luò)，以每個弧的人流量為設(shè)計變量，以各節(jié)點遵循能量守恒的連續(xù)性方程和各弧滿足容量限制為約束，以網(wǎng)絡(luò)通行總距離為優(yōu)化目標(biāo)，進(jìn)行網(wǎng)絡(luò)流優(yōu)化。具體表達(dá)式為：

圖1 簡化通道網(wǎng)節(jié)點分布圖Fig.1 Simplified channel network node distribution

表1 通道網(wǎng)節(jié)點Tab.1 Channel network nodes

表2 通道網(wǎng)弧列表Tab.2 Channel network arc list

其中：N為所有節(jié)點的集合，E為所有弧的集合，均為整數(shù)集；xij為 (i,j)弧的人流量；cij為 (i,j)弧的長度；uij為 (i,j)弧的最大流量；bi為節(jié)點i的供給量（+）/需求量（-）（見表1）。

利用分枝定界法[7-8]求解此類整數(shù)線性規(guī)劃問題，分枝定界法（branch and bound）用于求解純整數(shù)或混合的整數(shù)規(guī)劃問題。在20世紀(jì)60年代由Land Doig和Dakin等提出。這種方法靈活且便于用計算機(jī)求解，目前已經(jīng)成功運用于求解生產(chǎn)進(jìn)度問題、旅行推銷員問題、工廠選址問題、背包問題及分配問題等。

該算法對有約束條件的最優(yōu)化問題（其可行解為有限數(shù)）的所有可行解空間恰當(dāng)?shù)剡M(jìn)行系統(tǒng)搜索。通常把全部解空間反復(fù)地分割為越來越小的子集，稱為分枝，并對每個子集內(nèi)的解集計算一個目標(biāo)下界（對于最小值問題），這稱為定界。在每次分枝后，若某個已知可行解集的目標(biāo)值不能達(dá)到當(dāng)前的界限，則將這個子集舍去。這樣，許多子集不予考慮，這稱為剪枝。其思路具體如下：有最大化的整數(shù)規(guī)劃問題A，與它相應(yīng)的線性規(guī)劃問題時B。從解問題B開始，若其最優(yōu)解不符合A的整數(shù)條件，那么B的最優(yōu)目標(biāo)函數(shù)必是A的最優(yōu)目標(biāo)函數(shù)z*的上界，記作zˉ；而z的任意可行解的目標(biāo)函數(shù)值將是z的一個下界z_。分枝界定法就是把B的可行域分成子區(qū)域的方法。逐步減小zˉ和增大z_。最終求到z*。

本文在Matlab中進(jìn)行求解[9-10]，計算結(jié)果如圖2所示。圖中無流量通道硬虛線表示，有流量弧的流量通過線寬表示。

圖2 完整通道網(wǎng)絡(luò)流量圖Fig.2 Complete channel network flow chart

2 通道網(wǎng)絡(luò)損害分析

在艦船遭受打擊時，網(wǎng)絡(luò)中的節(jié)點或弧會受到損害，這里對網(wǎng)絡(luò)中一個節(jié)點或弧受到損害時（即N-1工況）的網(wǎng)絡(luò)流進(jìn)行計算，可以通過依次設(shè)置 (i,j)弧的最大流量uij為0模擬該弧損害。此處僅列出幾種典型工況（弧4，7，14，25損害工況）。通過星線表示損害弧位置，線寬表示各弧流量，虛線代表無流量通過，如圖3～圖6所示。

對于網(wǎng)絡(luò)中一個弧受到損害（即N-1工況）時各弧的最大網(wǎng)絡(luò)流如圖7所示。圖2～圖7對應(yīng)的各弧網(wǎng)絡(luò)流數(shù)值如表3所示。由于弧為雙向流，單向流最大容量8人，表3中可以看出雙向流的容量和最大為12人。

通過計算結(jié)果可以對通道設(shè)計進(jìn)行驗證和完善，如是否滿足N-X損害工況的生命力設(shè)計要求，是否含有冗余通道可以刪減等。結(jié)果顯示，本文提出的通道網(wǎng)絡(luò)可以滿足N-1損害工況下的生命力設(shè)計，各弧最大網(wǎng)絡(luò)流均大于0，無冗余弧，通道的容量可以參照計算結(jié)果開展相關(guān)設(shè)計，以降低通行距離和總體資源。

圖3 通道網(wǎng)絡(luò)N-弧4流量圖Fig.3 Channel network N-arc4 flow chart

圖4 通道網(wǎng)絡(luò)N-弧7流量圖Fig.4 Channel network N-arc7 flow chart

圖5 通道網(wǎng)絡(luò)N-弧14流量圖Fig.5 Channel network N-arc14 flow chart

圖6 通道網(wǎng)絡(luò)N-弧25流量圖Fig.6 Channel network N-arc25 flow chart

圖7 通道網(wǎng)N-1工況最大網(wǎng)絡(luò)流Fig.7 Channel network N-1 maximum network flow

3 結(jié) 語

本文在艦船簡化通道網(wǎng)的基礎(chǔ)上，建立以通行距離最小為目標(biāo)的網(wǎng)絡(luò)流模型，利用分枝定界法開展網(wǎng)絡(luò)流優(yōu)化。依次對完整網(wǎng)絡(luò)和N-1損害工況下網(wǎng)絡(luò)進(jìn)行了優(yōu)化求解，結(jié)果顯示，本文的模型和算法能夠快速、良好地反映通道網(wǎng)絡(luò)流量分布，可為通道網(wǎng)的設(shè)計、驗證和完善提供依據(jù)，可對網(wǎng)絡(luò)N-1損害工況進(jìn)行求解，計算結(jié)果可為通道網(wǎng)生命力設(shè)計和損管決策和操作提供依據(jù)。

表3 各典型工況網(wǎng)絡(luò)流Tab.3 Network flow of each typical working condition