帶時間窗的航母編隊多補給船海上補給路徑規劃?

王城超 鄒 強 賈汝娜

1 引言

海上補給路徑規劃是一個NP-Hard難題，是海上補給規劃的研究重點。在航母編隊海上補給過程中，由于編隊內作戰艦艇數量較多，各作戰艦艇所處的位置相對分散且距離較遠，作戰時各艦艇的位置可根據作戰需要而變動，補給策略多樣，這些都使得航母編隊海上補給路徑規劃問題趨于復雜化［1］。目前，國外對海上補給路徑進行了大量研究，將其視標準TSP問題、廣義TSP問題或廣義定向問題［2～6］，Williams［7］將海上補給路徑規劃將其視為車間調度問題（VRP）。國內對航母編隊海上補給路徑規劃研究較晚，主要是針對編隊單補給船海上補給路徑規劃［8～10］方面的相關研究，大多是將TSP問題的基本思想進行適當改進，應用到單補給船海上補給路徑規劃中去。針對編隊多補給船海上補給路徑規劃，國內難以查到研究該問題的文獻。從航母編隊的發展趨勢來看，航母編隊單補給船海上補給路徑規劃難以滿足航母編隊的海上補給保障需求。航母編隊補給船補給模式主要有三種，即送報男孩（delivery boy）模式，加油站（gas station）模式，巡回牧師（circuit rider）模式，考慮到本文篇幅有限，故本文只研究送報男孩模式下的航母編隊多補給船海上補給路徑規劃?；诖?，本文研究送報男孩模式下帶有時間窗的航母編隊多補給船海上補給路徑規劃（Undeyway Replenishment Routing Scheduling Problem with Time Windows，URRSPTW），可為航母編隊伴隨補給保障提供策略支持。

2 VRPTW問題與URRSPTW問題的聯系與區別

URRSPTW問題與VRPTW問題之間既存在相同之處，也存在部分區別。因此在對URRSPTW問題進行描述與求解時，一方面，要充分吸取VRPTW問題中可以運用的成功經驗；另一方面，要充分考慮URRSPTW問題的獨特屬性。此外，URRSPTW問題是基于編隊作戰條件下的補給路徑規劃問題，所以求解URRSPTW問題的考慮的因素和求解過程的復雜性更高。所以URRSPTW問題的求解思路是在URRSPTW問題與VRPTW問題共性的基礎上，結合URRSPTW問題作戰等獨特因素的影響來求解該問題。

兩者的相同之處：URRSPTW問題與VRPTW問題都屬于復雜化的優化問題；都是采用圖論中頂點和賦權的邊方法對其進行描述；圖中每個定點都只能被訪問一次。

兩者的不同之處：1）圖方面，對于VRPTW問題，其圖論中描述的頂點表示固定的被服務點，而對于URRSPTW問題來說，其圖論中描述的頂點是作戰艦艇補給時所處的位置。2）目標函數的選擇方面，VRPTW模型的目標函數一般為單目標（補給總時間、補給總距離或補給總成本等最小），而URRSPTW問題的目標函數與作戰等因素密切相關，一般為多重目標（如補給船選擇數量盡量少、最小化編隊補給總時間、因補給而生成的編隊作戰效能最大等），根據作戰實際情況，目標函數可選擇其中的一個或多個。3）配送車輛或伴隨補給船數量限制方面，VRPTW問題的配送車輛數量一般未進行限制，最大限度地滿足客戶的配送需求，但在優化目標中設置配送車輛數量盡可能少；而URRSPTW問題伴隨補給船的數量一般受到嚴格的限制，在極短情況下（比如同一段時間出現較多作戰艦艇的補給需求），很可能會出現伴隨補給船不能滿足全部作戰艦艇的補給時間窗要求的情況，此時優先選擇因補給而生成作戰效能最大的作戰艦艇進行補給。4）時間窗方面，VRPTW問題時間窗是客戶給定的，URRSPTW問題的時間窗是通過預測得到的。

3 URRSPTW問題的數學描述

3.1 補給模式描述

假設航母編隊作戰時，補給船位于航母編隊的內部，并時刻受航母編隊的保護。在該補給模式下，編隊內作戰艦艇位置不變，根據編隊內各作戰艦艇的彈藥補給需求，若干艘補給船離開其初始位置，以一定的順序對各作戰艦艇進行彈藥補給。由于在補給船補給過程中，編隊內作戰艦艇在原有位置，最大程度地保證了編隊陣形的完整性，此情況對航母編隊作戰最為有益，但是該補給模式也存在一定的缺陷，比如補給船不能同時對兩艘作戰艦艇進行彈藥補給。下面以10艘待補作戰艦艇和2艘補給船為例，該補給模式下的補給路徑規劃示意圖如下。

3.2 模型假設條件

在航母編隊實際作戰中，URRSPTW問題涉及的因素較多，在建立數學模型對其進行求解時，建立的數學模型肯定與真實情況下的URRSPTW問題有部分差異。所以為了能夠準確地對URRSPTW問題進行建模，必須根據實際情況對模型做出一定的假設，基本假設如下：

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

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

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

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

5）每艘作戰艦艇只補給一次；

6）每艘待補作戰艦艇的補給時間窗已知，可表示為[ ]ETi，LTi。只要補給船對該作戰艦艇的開始補給時間在時間窗[ETi，LTi]內，即稱補給滿足時間窗約束。

3.3 符號定義

本文用圖論的方法來描述編隊多補給船補給路徑規劃問題。定義無向圖G=(V ，A) ，點集V={0 ，1，…，n} ，其中{0}表示補給船的初始位置，V{0}表示待補作戰艦艇的位置集合；弧線集合A={( i ， j)|i，j∈V，i≠j} 表示連接2個待補作戰艦艇之間的航行路線的集合，當i或j的值為0時，表示處于補給船的初始位置。

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

3.4 模型建立

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

目標函數：

流程約束條件

時間窗約束條件：

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

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

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

4 改進GA的設計

GA最早是由美國J.Holland教授提出的，是一種模擬生物界中遺傳和進化的算法［11～12］。GA具有較強的全局搜索能力，同時解的表示方法也很直觀清楚，但是也存在容易陷入局部最優等缺點，所以本文采用改進GA來求解URRSPTW問題。改進GA的基本流程如下圖。

下面對改進GA的設計步驟進行詳細闡述。

1）染色體結構設計

設計染色體結構包括染色體編碼方式和編碼長度的確定。

本文采用的染色體編碼方式是較為直觀的自然數編碼，該方法的優點是占用計算機內存較小，同時解的表示方法直觀清楚。假設待補作戰艦艇的數量為m，補給船數量為k，該編碼方法首先是隨機生成一種由0和1～m之間不重復自然數組成排列的補給方案，該排列就代表了問題的一個解。假設“0”表示補給船的初始位置，“1，2，…，m ”表示m艘作戰艦艇的補給需求點集合。以染色體“0421078906530”為例，該染色體表示補給船補給路徑規劃方案，即表示3艘補給船從原始位置出發，對9艘作戰艦艇補給需求點進行補給作業。補給路徑規劃方案具體如下：

第一艘補給船補給路徑：補給船初始位置→需求點4→需求點2→需求點1→補給船初始位置。

第二艘補給船補給路徑：補給船初始位置→需求點7→需求點8→需求點9→補給船初始位置。

第三艘補給船補給路徑：補給船初始位置→需求點6→需求點5→需求點3→補給船初始位置。

染色體長度=補給船總數+需求點數+1。

2）適應度函數

在遺傳算法中，通過適應度大小來區分種群中個體的優劣，故設計合理的適應度函數尤其重要。一般可根據模型中目標函數設計相應的適應度函數，假設 f(x)表示目標函數，F(x)表示適應度函數，則將 f(x)轉化為F(x)的過程定義為標定［13］（Scaling）。本文采用的標定方式是動態線性標定，具體如下：

其中k表示待定參數，且k的取值一般較大；x表示種群中的某個個體，f()x表示種群個體x的目標函數；通過對目標函數進行上述標定，得到的適應度函數F()

x能夠較好地均衡GA的全局搜索與局部搜索。

對于目標函數 f()x有必要做進一步闡述。由于GA在求解編隊補給船路徑規劃時不能直接處理模型中的約束條件，故必須把相關約束條件做進一步轉化，并轉移到目標函數中去。

考慮到URRSPTW模型中時間窗約束的重要性，基于GA的原理，設計的目標函數 f()x具體如下

其中Tis表示補給船對作戰艦艇i的補給開始時間。目標函數 f(x) 中 p1、p2、A、B均為常數，目標函數f(x)是一種組合化的目標，常數 p1、p2、A、B的取值直接關系到GA中適應度值的準確度。目標函數f(x)中包括三重組合化目標，第一目標為時間窗約束目標，第二目標為最小化補給船的使用數量，第三目標為編隊最小化補給航行時間，所以常數 p1、p2、A、B的取值應滿足以下條件：

例如 p1、p2、A、B的取值可以為 A=1000，B=1000，p1=100，p2=10。

3）選擇操作

本文采用的選擇策略是Proportional Selection，假設種群數量為n，種群中個體i被選擇的概率計算公式如下：

其中Pi表示個體i被選中的概率；Fi表示種群中個體 i的適應度值表示種群中所有個體的適應度值總和。

在Pi確定之后，本文采用的選擇操作方法是Roulette Wheel（輪盤賭法）。記 PP0=0，假設有個圓形輪盤，根據PPi(i =1，2，…，n)將整個輪盤分為n份，則圓形輪盤中第i個扇形的角度數為2πPPi。隨機生成一個隨機數r∈U(0 ，1) ，若 PPi-1≤r＜PPi時，則選擇個體i，該選擇操作中共生成n個隨機數。很顯然，Pi較大的個體i的在圓形輪盤中占用的面積較大，該個體被選擇的概率也較大，被遺傳到下一代的概率也越大。

因目前不少高校開設了國外合作辦學專業，可采取國內高校-國外高校-企業三方合作模式，共同訂制人才培養方案，并與企業需求相對接，同時完成教學、實踐任務。在國外、國內都給學生提供企業實習機會，豐富學生職業實踐經歷，提高意識，幫助他們不斷修正和評估自我，完善職業規劃。

4）遺傳算子的設計

（1）交叉算子設計

本文中交叉算子的設計可以避免GA陷入局部最優。交叉操作可分兩步進行，第一步是將上述選擇操作中選出的染色體進行兩兩配對，然后再根據交叉率來決定該對染色體是否進行交叉操作；第二步是設置配對染色體中的交叉點，并進行交叉互換。

OX是在傳統PartiallyMatched Crossover（PMX）的基礎上改進得到的，在求解URRSPTW模型中有較大的優勢。OX的步驟如圖3所示。

OX運算示意圖如下。

本文采用順序交叉法（簡稱OX）和改進OX來對染色體中基因進行交叉互換。若被選出待交叉的兩個個體不同，則采用上述OX進行交叉操作；若被選出待交叉的兩個個體染色體完全一樣，則采用改進OX進行交叉操作（即將這兩個個體中一個個體被選中將進行交叉的基因移入該染色體的首位，而將另一個體將進行交叉的基因移到該染色體的末尾）。

變異算子的實質是對補給船的補給路徑規劃線路中的部分可行解進行局部尋優。設置變異算子的作用是加速GA的收斂速度和避免早熟現象發生。變異操作包括兩個步驟：首先依據變異率來決定是否進行變異操作；如果確定進行變異操作，則通過特定的變異操作方法來完全變異操作。

本文采用的變異操作方法是交換變異法（亦可稱為對稱變異法），該方法是指隨機選擇基因片段中排列的兩艘作戰艦艇，交換兩者的位置。例如個體“87654321”，假設隨機交換第2位和第7位，則有87654321→82654371。

（3）終止條件

本文將改進GA的終止條件設置為最大進化代數M。

5 實例分析

本文以一種典型雙航母編隊的海上補給路徑規劃為例，編隊構成包括2艘航母母艦、3艘伴隨補給船、15艘編隊附屬水面艦艇，對所提出的的模型與方法進行驗證。

表1 輸入初始數據

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

1）初始輸入數據

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

2）相關參數設置

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

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

5.2 航母編隊多補給船補給路徑規劃結果

采用改進GA對航母編隊多補給船海上補給路徑進行10次實例仿真，選取仿真結果中的一個較好結果，其最優航母編隊多補給船海上補給路徑規劃方案如表2。

表2中的航母編隊多補給船海上補給路徑規劃方案由三艘補給船的補給路徑組成，其中1號補給船在t=0h時刻就從該補給船的初始位置出發，并開始補給作業，該補給船完成該補給船所在路徑上全部補給任務所花的時間是22h；2號補給船在t=2.5h時刻從該補給船的初始位置出發，并開始補給作業，該補給船完成該補給船所在路徑上全部補給任務所花的時間是24.1h；3號補給船在t=3.7h時刻從該補給船的初始位置出發，并開始補給作業，該補給船完成該補給船所在路徑上全部補給任務所花的時間是24.9h。編隊補給總時間表示編隊內伴隨補給船完成航母編隊多補給船海上補給路徑規劃中全部作戰艦艇的補給作業所花費的時間，即為3條路徑補給時間中的最長者（24.9h）。

表2 航母編隊多補給補給路徑規劃方案

在該航母編隊多補給船海上補給路徑規劃方案下，航母編隊多補給船海上補給路徑規劃圖如下所示。

航母編隊多補給船海上補給路徑規劃圖由三艘補給船的補給路徑組成，為了圖中補給路徑清晰可見，分別采用不同的線條對三艘補給船的補給路徑進行了標記。

在該航母編隊多補給船海上補給路徑規劃方案下，補給船對各作戰艦艇進行補給作業的實際到達時刻、等待時間、開始補給時刻和補給結束后的實際離開時刻等時間情況如表3所示。

表3 航母編隊多補給船海上補給路徑規劃的相關時間情況表

6 結語

本文研究帶時間窗的航母編隊多補給船海上補給路徑規劃問題。首先將URRSPTW問題和VRPTW問題進行了對比，分析了兩者的區別與聯系。在此基礎上，建立了URRSPTW問題的數學模型，并提出了改進GA來求解模型，該方法能夠避免陷入局部最優。最后選取了一種典型航母編隊多補給船海上補給路徑為案例，進行了實例分析，得到了多補給船補給路徑規劃方案和補給路徑規劃圖，計算結果驗證了該模型與方法的合理性，可為航母編隊伴隨補給保障提供策略支持。

［1］Conley T E.Analysis of pacific fleet underway replenishment data［D］.Montery：Naval Postgraduate School，1988：14-25.

［2］Dunn J S.Scheduling underway replenishment as a generalized orienteering problem［D］.California：Naval Postgraduate School，1992：25-40.

［3］Wu，Tzu-Li.Optimization Models for Underway Replenishment of A Dispersed carrier Battle Group［D］.California：Naval Postgraduate School，1992：1-15.

［4］Hardgrave S W.Determining the feasibility of replenishment a dispersed carrier battle group［D］.California：Naval Postgraduate School，1989：6-21.

［5］Zabarouskas M W.Scheduling underway replenishment using delivery boy and circuit rider tactics，an asymmetric generalized TSP［D］. California：NavalPostgraduate School，1992：10-29.

［6］DeGrange W C.Optimizing global combat logistics force support for sea base operations［D］.California：Naval Postgraduate School，2005：3-15.

［7］Williams T M.Heuristic scheduling of ship replenishment at sea［J］.Journal of the Operational Research，1992，（43）：11-18，5-21.

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

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

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

［11］韓慶田，曹文靜，蘇濤.基于遺傳算法的艦載機保障流程研究［J］. 科學技術與工程，2012，12（35）：9784-9787.

［12］史峰，王輝，郁磊，等.Matlab智能算法30個案例分析［M］.2版.北京：北京航空航天大學出版社，2015：108-117.

［13］汪定偉，王俊偉等.智能優化方法［M］.北京：高等教育出版社，2007：63-64.