艦艇編隊多補給艦海上補給路徑規(guī)劃*

魏振堃，趙素麗，李陽超，郭 湛

（陸軍勤務學院，重慶 401331）

0 引言

隨著國際局勢的變化，我國受到來自海上的安全挑戰(zhàn)日益增多，海上軍事斗爭準備日益艱巨，突破島鏈束縛，走向遠洋，為我國海外利益提供戰(zhàn)略支撐成為當前我海軍的重要使命任務。伴隨保障是拓展艦艇編隊行動半徑的有效途徑，是海軍走向深藍的重要舉措。因此，研究艦艇編隊海上補給路徑規(guī)劃問題，提高伴隨保障效率，對于提高艦艇編隊遠洋伴隨保障能力具有一定意義。

目前，國內外對艦艇編隊海上補給路徑規(guī)劃問題進行了大量有益探索，主要將其視為旅行商問題（Traveling Salesman Problem，TSP）或者車輛路徑問題（Vehicle Routing Problem，VRP）［1-7］。在TSP 模型或VRP 模型中，艦艇編隊補給方式主要有3 種［8］，即送報男孩（Delivery Boy，DB）方式、加油站（Gas Station，GS）方式，巡回牧師（Circuit Rider，CR）方式。DB 方式為補給艦到各個作戰(zhàn)艦艇海域實施補給的方式；GS 方式為各個作戰(zhàn)艦艇輪流到補給艦海域實施補給的方式；CR 方式為補給艦與作戰(zhàn)艦艇共同到達某個海域實施補給的方式，3 種補給方式的示意圖如圖1 所示。

圖1 艦艇編隊補給策略

其中，GS 方式將所有作戰(zhàn)艦艇集中于一處補給，目標相對集中，易受敵攻擊；CR 方式同時調整補給艦和作戰(zhàn)艦艇位置，艦船航行距離增加，模型復雜度增加，提高了運算成本。根據文獻［6］，采用DB 方式能最大限度地保證編隊的基本作戰(zhàn)陣型，隨時可以進入戰(zhàn)斗狀態(tài)，同時在求解補給時間和規(guī)劃方案的結果上更具有優(yōu)勢，因此，本文只考慮DB方式。

3 種方式均將單補給艦補給總時間最短作為唯一目標函數，對于大型艦艇編隊往往存在多補給艦的情況，此時目標函數需要調整為在少用補給時間的情況下少用補給艦，此時模型變?yōu)殡p目標函數模型，即補給時間最短和參與補給任務的補給艦最少。國內對艦艇編隊海上補給線路規(guī)劃雙目標函數模型比較少，其求解方式為設置函數權重后求和，從而轉化成單一目標函數求解［2］，這種求解方式主觀性太強，結果往往不準確。從本質上講，艦艇編隊海上補給線路規(guī)劃雙目標函數模型是復雜多旅行商問題的衍生模型，難以求得精確解，采用啟發(fā)式算法仍是求解該模型的最優(yōu)策略。基于此，本文提出了一種基于改進GA 算法的艦艇編隊多補給艦海上補給路徑規(guī)劃模型。

1 艦艇編隊多補給艦海上補給路徑規(guī)劃模型

假設k 艘補給艦和n 艘作戰(zhàn)艦艇組成的艦艇編隊執(zhí)行海上任務時，補給艦位于編隊內部，在得到補給命令時，作戰(zhàn)艦艇位置不動，補給艦按照一定順序前往作戰(zhàn)艦艇實施補給任務。

1.1 模型假設條件

抽象出的數學模型與艦艇編隊海上補給實際情況略有不同，需要對相關細節(jié)進行合理假設，以方便建模求解。

1）艦艇編隊中，k 艘補給艦對n 艘作戰(zhàn)艦艇實施伴隨補給；

2）補給艦從初始位置出發(fā)，按照一定順序對所有作戰(zhàn)艦艇實施補給后再回到初始位置；

3）每艘作戰(zhàn)艦艇只補給一次；

4）補給艦船抵達作戰(zhàn)艦艇補給海域，即刻就能補給，忽略補給準備時間，補給結束后即刻就能出發(fā)前往下一作戰(zhàn)艦艇補給海域，忽略補給裝備撤收時間；5）補給艦勻速航行；6）作戰(zhàn)艦位置不動。

1.2 符號定義

N={1，2，…，n}：所有待補給作戰(zhàn)艦艇的集合

K={1，2，…，k}：所有補給艦的集合

dij：補給艦從作戰(zhàn)艦艇i 到作戰(zhàn)艦艇j 所用的時間

ti：作戰(zhàn)艦艇i 需要補給的時間

決策變量：

1.3 數學模型

綜合考慮艦艇編隊海上補給路徑規(guī)劃問題，在參與補給行動的補給艦數量盡量少的前提下，追求補給總時間最少。因此，艦艇編隊海上補給路徑規(guī)劃模型為雙目標函數模型［9］，具體如下：

目標函數：

式（1）和式（2）分別表示補給艦數量最少和補給時間最短目標函數；式（3）和式（4）約束了一艘作戰(zhàn)艦只能由一艘補給艦沿一條補給路線進行補給；式（5）約束了補給艦在補給完作戰(zhàn)艦i 后，又從作戰(zhàn)艦i 所在海域出發(fā)，保證線路的連續(xù)性；式（6）和式（7）約束了補給艦從初始位置出發(fā)并返回初始位置；式（8）參與補給行動的補給艦數量應不多于補給艦總數。

2 求解艦艇編隊多補給艦海上補給路徑規(guī)劃模型的改進GA 算法

GA 算法是一種模擬生物界中遺傳與進化的算法，通過染色體編碼構建解空間、選擇運算淘汰劣質父代、交叉運算產生優(yōu)質子代、變異運算跳出局部最優(yōu)，從而實現函數全局尋優(yōu)。傳統(tǒng)GA 算法只能進行單目標函數的最值尋優(yōu)，不符合艦艇編隊多補給艦海上補給路徑規(guī)劃模型的要求。本文在研究了艦艇編隊多補給艦海上補給路徑規(guī)劃問題求解的具體特征后，在傳統(tǒng)GA 算法的基礎上增加了多目標函數尋優(yōu)策略、采用了近時初始化方式構建初始解、改進了交叉和變異運算的運算規(guī)則，對問題的解空間進行充分搜索，并利用高效的選擇機制，使種群不停向最優(yōu)解空間聚集，達到快速尋優(yōu)的目的，算法流程見圖2［10］。

2.1 種群初始化

本文采用近時矩陣初始化方法構建初始解，近時矩陣定義如下。

近時矩陣，neartime（i，p）=j 表示艦艇j 是從艦艇i 出發(fā)用時第p 短的艦艇，記艦艇i 到自身的時間最長，即neartime（i，n+1）=i。若neartime（1，1）=3，則表明補給艦1 到作戰(zhàn)艦艇3 的用時最短。

對于規(guī)模為M 的種群，初始化的具體步驟如下：

步驟1：對個體i（i≤M），置染色體X={1}，迭代次數t=1；

步驟2：根據近時矩陣，在未被訪問的艦艇集中選擇到上一個訪問艦艇用時最短的艦艇a 作為下一個補給艦艇，并更新X=X∪{a}和t=t+1；

步驟3：若t

步驟4：隨機產生k-1 初始斷點；

步驟5：若i

圖2 改進的GA 算法流程圖

圖3 染色體編碼

2.2 染色體編碼

本文采用單染色體編碼，染色體上的每一個基因表示一個作戰(zhàn)艦艇所在位置，用補給艦和作戰(zhàn)艦艇所在位置的編號對每個基因進行編碼。以8 艘待補給作戰(zhàn)艦為例，圖3 中2～9 分別為各作戰(zhàn)艦艇的位置，1 為補給艦所在位置。當有2 艘補給艦時，會自動生成一個斷點位置，若斷點位置為3，則第1艘補給艦的補給路徑為1→4→2→1，第2 艘補給艦的補給路徑為1→5→7→9→6→3→8→1；當有3艘補給艦時，會自動生成兩個斷點位置，若斷點位置為3、7，則第1 艘補給艦的補給路徑為1→4→2→1，第2 艘補給艦的補給路徑為1→5→7→9→6→1，第3 艘補給艦的補給路徑為1→3→8→1。

2.3 適應度函數

在遺傳算法中，通過適應度大小來區(qū)分種群中個體的優(yōu)劣，故設計合理的適應度函數尤為重要。在求解艦艇編隊多補給艦海上補給路徑規(guī)劃模型的改進GA 算法中，適應度函數為補給總時間，優(yōu)化的目標就是選擇能夠使適應度函數盡可能小的染色體。

2.4 選擇運算

在進行選擇運算時，采用保留精英策略，將父代種群中適應度函數最小的染色體復制到下一代種群中，剩余染色體按照輪盤賭的方式選擇，這樣能夠保證遺傳算法的收斂，使其向最優(yōu)化方向進化。

2.5 交叉運算

交叉運算采用部分匹配交叉運算，選擇進行交叉的父代，根據交叉概率確定是否進行染色體配對，交叉后的染色體作為子代染色體。隨機選取兩個父代染色體上的兩個交叉位置，從而確定一段匹配基因，根據兩個交叉位置之間的中間段給出的匹配關系生成兩個子代染色體。例如：

對于下面兩個父代染色體，隨機地選擇兩個交叉位置“|”。

兩個交叉位置之間的基因進行交換，得到

其中，x 代表暫未定義艦艇基因，得到匹配基因段的關系為：

9?3，8?4?6，7?5

然后將未選定的作戰(zhàn)艦艇基因2 保留，于是得到

對于S1 中第7 個艦艇基因x，可以由7?5，可得為5；對于S1 中第8 個艦艇基因x，可以由8?4?6 可得為4 或6，當x=4 時出現重復，于是x=6；對于S1 中第9 個艦艇基因x，可以由9?3，可得為3；S2 同理，結果如下：

2.6 變異運算

為提高全局搜索的能力，避免過早陷入局部最優(yōu)解，本文設置了兩種變異算子。

一種是普通變異算子，染色體內除1 號基因外任意兩個基因片段相互交換，實現基因序列倒位，從而實現作戰(zhàn)艦艇補給順序的調整，例如染色體“123456789”，假設隨機交換第2 位和第7 位，則有

另一種是反轉變異算子，染色體上任意選擇兩個基因位置，兩基因位置中間的所有基因進行逆序排列，例如染色體“123456789”反轉位置為2 和5，則有

2.7 動態(tài)斷點調整

隨機動態(tài)調整斷點位置，從而實現對每艘補給艦補給作戰(zhàn)艦艇數量的調整。

2.8 補給艦數量控制規(guī)則

補給艦數量從k 開始循環(huán)，依次減少1，當補給艦數量由m（m∈K）減少到m-1，而最小補給總時間沒有變化時，補給艦數量確定為m-1；補給艦數量為m-1 時的最優(yōu)染色體即為最優(yōu)補給方案。

3 實例分析

運用電腦模擬生成了一組艦隊編成，包括3 艘補給艦和17 艘作戰(zhàn)艦艇，并以此為例進行艦艇編隊多補給艦海上補給路徑規(guī)劃，對所提出的模型與方法進行驗證。

3.1 原始數據輸入和相關參數設置

3.1.1 原始數據輸入

下頁表1 為模擬生成的各補給艦和作戰(zhàn)艦艇的相對位置，為方便計算，將3 艘補給艦均置于坐標原點，編隊中3 艘補給艦位置為1，作戰(zhàn)艦艇按照2～18 依次編號。

表1 艦艇編隊基本情況統(tǒng)計表

3.1.2 參數設置

1）補給艦平均航速20 節(jié)（n mile/h）；

2）改進GA 算法的相關參數設置：種群大小M=80，最大迭代次數T=5 000，交叉概率Pc=0.85，變異概率Pm=0.15。

3.2 艦艇編隊多補給艦海上補給路徑規(guī)劃結果

運用改進GA 算法對艦艇編隊多補給艦海上補給路徑進行40 次MATLAB 實例仿真，選取仿真結果中的一個較好結果，其最優(yōu)補給路徑規(guī)劃方案如表2。

各艦艇的相對位置和3 艘補給艦的海上補給路徑結果見52 頁圖4 所示。

3.3 艦艇編隊多補給艦海上補給路徑規(guī)劃結果對比

運用傳統(tǒng)GA 算法對艦艇編隊多補給艦海上補給路徑進行40 次MATLAB 實例仿真，選取仿真結果中的一個較好結果，其最優(yōu)補給路徑規(guī)劃方案如52 頁表3。

表2 艦艇編隊多補給艦海上補給路徑規(guī)劃方案

由表2 和表3，兩種方案均需要調用3 艘補給艦，但是利用改進GA 算法規(guī)劃的補給路徑方案在補給時間上具有明顯優(yōu)勢。

4 結論

本文研究了艦艇編隊多補給艦海上補給路徑規(guī)劃問題，通過模型分析和實例驗證，所提模型能夠較好地為艦艇編隊中補給艦實施補給任務規(guī)劃路線，實現最短補給時間和最少補給艦參與補給的雙重目標。本文研究結論可為艦艇編隊海上補給行為提供決策基礎依據，具有較強的實用性和針對性。

圖4 艦艇編隊多補給艦海上補給路徑規(guī)劃圖

表3 艦艇編隊多補給艦海上補給路徑規(guī)劃方案