基于網絡流的艦船通道損害工況流量分析

趙寶強，劉佳銘

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

0 引 言

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

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

1 網絡流模型

1.1 模型定義

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

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

1.2 模型求解

針對創建的網絡，以每個弧的人流量為設計變量，以各節點遵循能量守恒的連續性方程和各弧滿足容量限制為約束，以網絡通行總距離為優化目標，進行網絡流優化。具體表達式為：

圖1 簡化通道網節點分布圖Fig.1 Simplified channel network node distribution

表1 通道網節點Tab.1 Channel network nodes

表2 通道網弧列表Tab.2 Channel network arc list

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

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

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

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

圖2 完整通道網絡流量圖Fig.2 Complete channel network flow chart

2 通道網絡損害分析

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

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

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

圖3 通道網絡N-弧4流量圖Fig.3 Channel network N-arc4 flow chart

圖4 通道網絡N-弧7流量圖Fig.4 Channel network N-arc7 flow chart

圖5 通道網絡N-弧14流量圖Fig.5 Channel network N-arc14 flow chart

圖6 通道網絡N-弧25流量圖Fig.6 Channel network N-arc25 flow chart

圖7 通道網N-1工況最大網絡流Fig.7 Channel network N-1 maximum network flow

3 結 語

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

表3 各典型工況網絡流Tab.3 Network flow of each typical working condition