航母編隊補給船動態補給路徑規劃模型及算法研究

王城超 鄒 強 賈汝娜

（海軍航空大學 煙臺 264001）

1 引言

從航母編隊作戰的實際情況來看，航母編隊作戰物資消耗很快，特別是彈藥等作戰物資，其消耗規律難以準確預測，這就導致航母編隊海上補給路徑規劃具有動態性，所以開展更符合航母編隊實戰的多補給船動態補給路徑規劃方面的研究顯得尤其重要。目前，國外對海上補給路徑規劃研究［1］較成熟，Williams［2］將海上補給路徑規劃將其視為車間調度問題（VRP）。在多補給船動態補給路徑規劃方面，雖然沒查到編隊內動態補給規劃策略方面的現成文獻，但是從美軍航母戰斗群建立的全球范圍內的多戰斗群后勤保障等建模與仿真模型［3～6］和BGLCSS［7］等后勤物資保障系統中可以看出其動態補給規劃的策略。國內對航母編隊海上補給路徑規劃研究較晚，主要是針對編隊單補給船海上補給路徑規劃［8～10］方面的相關研究，主要是將該問題視為TSP問題進行求解，在編隊多補給船動態補給路徑規劃方面難以查到相關文獻。基于此，本文開展航母編隊補給船動態補給路徑規劃方面研究。

航母編隊補給船補給模式主要有三種，即送報男孩（delivery boy）模式，加油站（gas station）模式，巡回牧師（circuit rider）模式，考慮到后兩者模式下編隊海上補給路徑規劃很難實現準時動態化，故本文只研究送報男孩模式下帶時間窗的航母編隊補給船動態補給路徑規劃，本文將該問題描述為帶有時間窗的動態補給路徑規劃問題（Dynamic Replen?ishment Routing Scheduling Problem with Time Win?dows，DRRSPTW），本文的研究可以為我軍航母編隊的后勤物資保障系統建設提供理論和策略支撐。

2 數學模型的建立

2.1 模型假設條件

在航母編隊實際作戰中，DRRSPTW問題涉及和考慮的因素較多，在建立的數學模型對其進行求解時，建立的數學模型肯定與真實情況下的DRRSPTW問題有部分差異。所以為了能夠準確地對DRRSPTW問題進行建模，必須根據實際情況對模型做出一定的假設。帶時間窗的航母編隊多補給船補給路徑規劃，對補給時機要求極為嚴格，屬于硬時間窗條件下的多補給船補給路徑規劃，基本假設如下：

1）航母編隊有k艘伴隨補給船對編隊中作戰艦艇進行伴隨彈藥補給，k艘伴隨補給船沒有航行距離限制；

2）補給船從初始位置出發，依次對各待補作戰艦艇進行彈藥補給，補給結束后補給船回到初始位置，該段時間也被稱為編隊補給時間；

3）補給船的彈藥儲備量可滿足編隊作戰艦艇的所有補給需求；

4）補給船的對每艘待補作戰艦艇的開始補給時間滿足時間窗口約束；

5）伴隨補給船可在戰斗中隨時對編隊內待補作戰艦艇進行彈藥補給；

6）每艘作戰艦艇只補給一次。

本文用圖論的方法來描述多補給船補給路徑規 規 問 題 。 定 義 無 向 圖G=(V ，A ) ，點 集V={0 ，1，…，n} ，其中{0}表示補給船的初始位置，V{0}表示待補作戰艦艇的位置集合；弧線集合窗約束。

2.2 符號定義

A={( i ， j)|i，j∈V，i≠j} 表示連接2個待補作戰艦艇之間的航行路線的集合，當i或j的值為0時，表示處于補給船的初始位置；補給船集合為k，k∈K。

數學模型中的參數含義及決策變量如下。

n表示航母編隊中待補作戰艦艇的數量；k表示補給船索引變量，k∈K={1 ，2，…，M } ；ri表示伴隨補給船對待補作戰艦艇i的補給作業時間；tsi和tei分別表示伴隨補給船對待補作戰艦艇i補給開始前的準備和撤離時間；dij表示伴隨補給船從作戰艦艇i航行至作戰艦艇（j包括補給船初始位置）的時間；Tia表示補給船到達作戰艦艇i的時間；Tis補給船對作戰艦艇i的開始補給時間；Tja補給船到達作戰艦艇j的時間；補作戰艦艇i補給的時間窗為［ETi，LTi］。

2.3 模型建立

在滿足流程約束、時間窗約束和整數性與非負性約束等條件下，建立以完成編隊作戰艦艇彈藥補給的最小化補給船數量和最小化補給航行時間為目標的數學模型。

目標函數：

流程約束條件

時間窗約束條件：

式（1）為目標函數，其中 p1、p2為整數，且有p1?p2。目標函數是一種組合化的目標函數，第一目標為最小化補給船的使用數量，第二目標為編隊最小化補給航行時間。

式（2）～（6）為流程約束條件，保證了補給船從初始位置出發，補給結束后回到初始位置。式（2）～（3）表示每艘作戰艦艇僅由一艘補給船補給彈藥，且確保了每艘作戰艦艇都能被一艘補給船補給一次。式（4）是為了確保線路的連續性，且輸入輸出弧相等。式（5）～（6）是為了確保補給船從初始位置出發，并保證補給結束后返回初始位置。

式（7）～（8）為時間窗約束條件。式（7）表示補給船到達作戰艦艇的時間約束，保證了補給時間的連續性。式（8）表示補給時間窗約束，補給船對待補作戰艦艇i的最早開始補給時間滿足作戰艦艇i的補給時間窗

3 DRRSPTW模型求解策略設計

3.1 兩階段求解策略

將DRRSPTW模型求解策略概述為兩階段求解策略，即預期補給路徑規劃階段和動態局部補給路徑規劃階段。DRRSPTW模型的兩階段求解策略流程圖如圖1。

3.2 動態局部補給路徑規劃求解策略

由于預期補給路徑規劃是一種比較傳統的靜態補給路徑優化問題，求解過程比較簡單，在這不再過多贅述，下面重點對動態局部補給路徑規劃進行重點闡述。

動態局部補給路徑規劃階段，即補給船的動態補給時間段[Ts，Tk]，研究的對象是因作戰艦艇補給時間窗不確定而引起的DRRSPTW，可以將作戰艦艇補給時間窗不確定情況分為新增作戰艦艇補給需求、原作戰艦艇補給需求取消、原作戰艦艇補給時間窗變更（延誤或提前）等三類。

用基于時間的分批處理策略來求解動態補給時間段路徑優化問題的基本思路如下：

1）首先將補給時間段[Ts，Tk] 劃分為n個時間片段T，且這n個時間片段T必須是等間隔的時間片段，可依次表示為(T1、T2、T3…Tn)。

2）采用最晚指派策略，將動態補給轉換為瞬時靜態補給。在每個時間片段結束之前只接受動態信息但不進行處理，補給船依舊按照原補給路徑規劃方案執行補給任務，直到每個時間段的末尾時刻，即t=T，對該時間片段內的動態信息進行一次性批量處理。

圖1 DRRSPTW模型的兩階段求解策略流程圖

將DRRSPTW轉化為瞬時靜態補給路徑規劃問題之后，根據補給船補給過程中的實時動態信息，判斷作戰艦艇補給需求類型，可分為原作戰艦艇補給需求取消、原作戰艦艇補給時間窗變更和新增作戰艦艇補給需求三種類型，設計相應的補給子策略。

下面分別對三種情況下作戰艦艇補給時間窗變動后的補給子策略進行相關闡述。

1）原作戰艦艇補給需求取消

假設航母編隊內所有補給船的出發時間是使得補給船航行至第一艘作戰艦艇的時刻剛好就是第一艘作戰艦艇補給時間窗的開啟時間。

在t=T時刻，對于原作戰艦艇補給需求取消的情況，可以將原作戰艦艇分三類進行分析，具體分析如下。

（1）取消補給需求的是某艘補給船補給路徑規劃的起始作戰艦艇

如果補給船還沒有離開初始位置，則補給船繼續留在初始位置；如果補給船已經離開初始位置，則以該時刻補給船所在的位置為起點；上述兩種情況都是將該補給船原計劃補給路徑規劃方案中的第二艘作戰艦艇作為下一個計劃補給的對象，補給船的出發時間以原補給路徑規劃方案中的第二艘作戰艦艇的補給時間窗約束為準。

（2）取消補給需求的是某艘補給船補給路徑規劃的中間作戰艦艇

如果該時刻該補給船的下一個計劃補給對象是該作戰艦艇，則將該時刻該補給船所在的位置為起點，并以該補給船原計劃補給路徑規劃方案中該作戰艦艇的下一艘作戰艦艇作為下一階段的補給對象。

（3）取消補給需求的是某艘補給船補給路徑規劃的末端作戰艦艇

如果該時刻該補給船的下一個計劃補給對象是該作戰艦艇，則將該時刻該補給船所在的位置為起點，該補給船直接返回其初始位置。

2）原作戰艦艇補給時間窗需求變更（延遲或提前）

假設當出現原作戰艦艇補給時間窗需求變動的情況，可能會影響該補給船所規劃的補給路徑，但是不會影響其他補給船的補給路徑規劃。原作戰艦艇補給時間窗需求變更策略如圖2。

圖2 原作戰艦艇補給時間窗變更策略流程圖

方案1：當原作戰艦艇補給時間窗需要變更時，在補給調度中心查看該作戰艦艇所屬補給船的補給路徑規劃情況，在不改變其他補給船所規劃補給路徑的前提下，以該時刻該補給船所在位置為起點，按照余下未補給作戰艦艇變更后的補給時間窗進行補給路徑的局部優化。如果該補給船出現多艘作戰艦艇的補給時間窗沖突情況，則需做進一步判斷分析。

方案2：從補給船初始位置調用閑置補給船對該作戰艦艇進行補給。如果補給船初始位置無閑置補給船可調用，則轉入方案3。

方案3：調用穿梭補給船來對該作戰艦艇進行彈藥補給作業。

3）新作戰艦艇補給需求

新增作戰艦艇補給需求的動態補給策略流程圖如圖3。

圖3 新增作戰艦艇補給需求的動態補給策略流程圖

動態補給策略流程圖中第三步中的“一定的規則”的含義如下：假設Q中有m艘補給船，分別記為k1、k2、…ki…km。 Dki表示t時刻補給船 ki所在的位置與新增作戰艦艇位置和補給船ki余下未補給的所有作戰艦艇的距離平方和，其中i=1，2…m 。

若Dku=min( )Dki，則選取補給船ku對新增作戰艦艇進行補給作業。若該補給船ku對新增和余下未補給作戰艦艇補給路徑進行規劃時，出現兩艘作戰艦艇補給時間窗沖突，則按照距離平方和Dki從小到大的順序，依次選擇補給船對新增作戰艦艇進行補給作業，直到滿足補給要求為止。

4 改進C-W算法

在動態局部補給路徑規劃階段，瞬時靜態補給路徑規劃問題的實質是基于時間窗的TSP。由于傳統C-W算法［11～12］不能直接用于求解帶有時間窗的TSP，所以本文采用改進C-W算法來對該補給船余下作戰艦艇彈藥補給路徑進行重新優化。

4.1 改進C-W算法的基本原理

對于帶有時間窗的TSP，在連接兩點時檢驗連接后是否滿足時間窗條件，構造能求解該問題的啟發式算法（簡稱改進C-W算法）。傳統C-W算法中節約值一般是距離的節約值，而改進C-W算法中節約值表示時間的節約值，故本文討論的是滿足時間窗條件下的補給船最小化補給航行時間的補給路徑優化問題。

假設s(i，j)表示連接兩個待補作戰艦艇所在位置i和（j簡稱兩個點i和j）的時間節約值（以下簡稱節約值），在連接兩點i和j后，可能會導致補給船到達后面作戰艦艇補給需求點的時間改變，即可能導致補給船到達后面待補作戰艦艇補給需求點的時間不能滿足既定時間窗要求。假設EFj表示連接i和j點前后到達j點時間變化量，具有如下公式：

EFj=Ri+Ti+tij-Rj

其中，Ri表示補給船到達處于補給需求點i的待補作戰艦艇的時間，Rj表示連接前補給船到達處于補給需求點j的待補作戰艦艇的時間，Ti表示補給船對處于補給需求點i的作戰艦艇進行彈藥補給的時間，tij表示補給船從一艘作戰艦艇的補給需求點i航行至另一艘作戰艦艇的補給需求點j的所花費的時間。

若EFj＞0，則表示連接點i和j之后，補給船到達作戰艦艇補給需求點j的時間推遲。

若EFj=0，則表示連接點i和j之后，補給船到達作戰艦艇補給需求點j的時間不變。

若EFj＜0，則表示連接點i和j之后，補給船到達作戰艦艇補給需求點j的時間提前。

假設TBj表示連接i和j點之后，j點和j點后面作戰艦艇補給需求點允許到達的最大提前時間；TAj表示連接i和j點之后，j點和j點后面作戰艦艇補給需求點允許到達的最大推遲時間，則有如下公式

其中r表示補給需求點j和j點后面作戰艦艇補給需求點，作戰艦艇補給需求點r的補給時間窗為[E Tr，LTr]。

當 EFj＜0，且 | EFj|≤TBj時，則有連接后補給船到達作戰艦艇補給需求點r的時間不會早于ETr，即連接后到達作戰艦艇補給需求點r的時間滿足時間窗上限要求。

當 EFj＞0 ，且 EFj≤TAj時，則有連接后補給船到達作戰艦艇補給需求點r的時間不會晚于LTr，即連接后到達作戰艦艇補給需求點r的時間滿足時間窗下限要求。

4.2 改進C-W算法流程

圖4 改進C-W算法流程

下面對圖4中改進C-W算法的部分重點步驟進行詳細闡述。

Step1：初始解的確定，并計算該初始解的總航行時間。初始解設置為派出K艘補給船分別對K艘作戰艦艇進行補給，補給結束后分別回到初始位置的路徑規劃，即K條o→i→o的補給路徑，初始解的總航行時間如下：

其中doi表示補給船從初始位置航行至作戰艦艇補給需求點i的時間；dio表示補給船補給結束，從補給需求點i返回初始位置的航行時間。

Step2：計算補給需求點i和j連接后的節約值s(i，j)，即計算連接后路徑o→i→j→o比原路徑o→i→o和o→j→o的節約值。

Step3：將節約值s(i，j)按照由大到小的順序進行排序，并構成集合M={s ( i，j)| s(i，j) ＞0} 。

Step4：“三個條件”依次如下。

1）作戰艦艇補給需求點i和j都不在已構成的補給路徑上，即存在補給回路 o→i→o和o→j→o，此時則將補給路徑 o→i→j→o作為候選連接補給路徑。

2）作戰艦艇補給需求點i和j中的一個點在已構成的補給路徑上，且該補給需求點與o點相連，而另外一個補給需求點不在已構成的補給路徑上。假設補給需求點i在已構成的補給路徑上（即存在補給回路o→i→…o或o…→i→o），補給需求點j不在已構成的補給路徑上（即存在補給回路 o→j→o）。此時則把補給回路o→j→i→…o或 o…→i→j→o作為候選連接補給路徑回路。

3）作戰艦艇補給需求點i和j分別在已構成的不同補給路徑上，且補給需求點j為補給路徑中的第一個補給需求點，補給需求點i為補給路徑中的最后一個補給需求點，即有 o→j→…o和o…→i→o 。 此 時 則 把 補 給 回 路o…→i→j→…o作為候選補給路徑回路。

Step5：假設作戰艦艇補給需求點j位于補給路徑上i補給需求點之后，分別計算EFj、TBj和TAj，然后再根據EFj、TBj和TAj三個值作進一步判斷。

5 實例分析

本文以一種典型雙航母編隊的海上補給路徑規劃為例，編隊構成包括2艘航母母艦、3艘伴隨補給船、15艘編隊附屬水面艦艇，對所提出的求解航母編隊補給船動態補給路徑規劃的模型與方法進行驗證。由于論文篇幅有限，故只給出新增作戰艦艇補給需求情況下的實例結果。

5.1 初始輸入數據和相關參數設置

1）初始輸入數據

假設3艘伴隨補給船的初始位置都處于坐標中心，編隊中伴隨補給船的初始位置編號1，各作戰艦艇補給需求點位置依次編號2、3、…、17。由于保密原因，本文的初始輸入位置等是人為給定的，具體如下。

表1 輸入初始數據

（2）相關參數設置

1）補給船的平均航速v=25節（海里/小時）；

2）改進GA的相關參數設置為：種群大小n=60，最大迭代次數M=200，交叉率Pc=0.9，變異率Pm=0.1。

5.2 初始補給路徑規劃結果

表2 預期補給路徑規劃方案

圖5 補給船預期補給路徑規劃圖

5.3 新增作戰艦艇補給需求后的補給船補給路徑規劃結果

新增作戰艦艇補給需求相關信息如表3。

表3 新增作戰艦艇補給需求相關信息表

從表3可看出，實時動態信息的處理時刻為t=19h，此時補給船補給路徑圖如圖6。

從圖6中可看出，t=19h時刻，1號補給船正位于圖中的0點，坐標為（-23.46，29.59），6號作戰艦艇未補給；2號補給船正位于圖中13點，坐標為（25.52，-48.38），剩下12號作戰艦艇未補給；3號補給船正位于圖中10點，坐標為（38.57，45.96），剩下9號作戰艦艇未補給；19號為新增作戰艦艇，坐標為（-2，30）。

圖6 補給船t=19h時刻補給路徑圖

通過計算可得，Dk1=854.74；Dk2=3585.41；Dk3=7937.67。故選擇1號補給船對新增19號作戰艦艇進行補給。采用改進C-W算法對1號補給船所在路徑上的新增作戰艦艇和剩余作戰艦艇補給路徑進行局部再修正，結果如下。

表4 新增作戰艦艇后補給船補給路徑規劃方案

圖7 新增作戰艦艇后補給船補給路徑修正圖

6 結語

本文研究帶時間窗的航母編隊補給船動態補給路徑規劃問題。針對戰時航母編隊海上補給路徑規劃具有動態性，建立了DRRSPTW問題的數學模型，設計了求解策略，設計了改進C-W算法來求解該模型。最后選取了一種典型航母編隊補給船動態補給路徑為案例，進行了實例分析，新增作戰艦艇補給需求后的補給路徑規劃方案和補給路徑規劃圖。計算結果驗證了該模型與方法的合理性，本文的研究可以為我軍航母編隊的后勤物資保障系統建設提供理論和策略支撐。

［1］ Conley T E，Hughes W P.Analysis of Pacific Fleet Un?derway Replenishment data［J］.Analysis of Pacific Fleet Underway Replenishment Data，1988.

［2］Williams T M.Heuristic Scheduling of Ship Replenish?ment at Sea［J］.Journal of the Operational Research Soci?ety，1992，43（1）：11-18.

［3］Schrady D A.Measures of Effectiveness in Logistics［J］.Technical Reports Collection，1989.

［4］Beveridge JD.An analytical and computer simulation ap?proach to the problem of replenishing task forces at sea［J］.1970.

［5］Brooks B C.Structured Vesus Objective-Oriented Design of Battle Group Logistics Simulation System［M］.califor?nia：Naval Postgraduate School，1970.

［6］Schrady D A.Operational Logistics：OA 3610，Introduction to Naval Logistics［M］.california：Naval Postgraduate School，1997.

［7］Hall W，Naval Postgraduate School（U.S.The Battle Group Logistics Comparative Analysis Model（BGL?CAM）：A Comparative Analysis Tool for Multi-Battle Group Logistics Support［J］.1997.

［8］余鵬，何學軍.基于蟻群算法的艦艇編隊海上補給路徑規劃方法［J］.海軍工程大學學報，2014，26（2）：108-112.

［9］周曉光，趙厚仁，王述運，等.航母編隊補給船海上補給航路規劃［J］.系統工程與電子技術，2014，36（9）：1756-1760.

［10］黃必佳，王公寶.航母編隊油料伴隨補給規劃模型及算法研究［J］.兵工自動化，2015，34（9）：78-83.

［11］鄭英，孟志青.基于節約算法的煙草物流配送線路優化［J］. 中國管理信息化，2010，13（23）：41-43.

［12］崔宏志，龔加安.帶時間窗車輛路徑問題的改進節約算法［J］. 純粹數學與應用數學，2011，27（5）：688-693.