王城超 鄒 強(qiáng) 賈汝娜

（海軍航空大學(xué) 煙臺 264001）

1 引言

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

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

2 數(shù)學(xué)模型的建立

2.1 模型假設(shè)條件

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

1）航母編隊有k艘伴隨補(bǔ)給船對編隊中作戰(zhàn)艦艇進(jìn)行伴隨彈藥補(bǔ)給，k艘伴隨補(bǔ)給船沒有航行距離限制；

2）補(bǔ)給船從初始位置出發(fā)，依次對各待補(bǔ)作戰(zhàn)艦艇進(jìn)行彈藥補(bǔ)給，補(bǔ)給結(jié)束后補(bǔ)給船回到初始位置，該段時間也被稱為編隊補(bǔ)給時間；

3）補(bǔ)給船的彈藥儲備量可滿足編隊作戰(zhàn)艦艇的所有補(bǔ)給需求；

4）補(bǔ)給船的對每艘待補(bǔ)作戰(zhàn)艦艇的開始補(bǔ)給時間滿足時間窗口約束；

5）伴隨補(bǔ)給船可在戰(zhàn)斗中隨時對編隊內(nèi)待補(bǔ)作戰(zhàn)艦艇進(jìn)行彈藥補(bǔ)給；

6）每艘作戰(zhàn)艦艇只補(bǔ)給一次。

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

2.2 符號定義

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

數(shù)學(xué)模型中的參數(shù)含義及決策變量如下。

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

2.3 模型建立

在滿足流程約束、時間窗約束和整數(shù)性與非負(fù)性約束等條件下，建立以完成編隊作戰(zhàn)艦艇彈藥補(bǔ)給的最小化補(bǔ)給船數(shù)量和最小化補(bǔ)給航行時間為目標(biāo)的數(shù)學(xué)模型。

目標(biāo)函數(shù)：

流程約束條件

時間窗約束條件：

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

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

式（7）～（8）為時間窗約束條件。式（7）表示補(bǔ)給船到達(dá)作戰(zhàn)艦艇的時間約束，保證了補(bǔ)給時間的連續(xù)性。式（8）表示補(bǔ)給時間窗約束，補(bǔ)給船對待補(bǔ)作戰(zhàn)艦艇i的最早開始補(bǔ)給時間滿足作戰(zhàn)艦艇i的補(bǔ)給時間窗

3 DRRSPTW模型求解策略設(shè)計

3.1 兩階段求解策略

將DRRSPTW模型求解策略概述為兩階段求解策略，即預(yù)期補(bǔ)給路徑規(guī)劃階段和動態(tài)局部補(bǔ)給路徑規(guī)劃階段。DRRSPTW模型的兩階段求解策略流程圖如圖1。

3.2 動態(tài)局部補(bǔ)給路徑規(guī)劃求解策略

由于預(yù)期補(bǔ)給路徑規(guī)劃是一種比較傳統(tǒng)的靜態(tài)補(bǔ)給路徑優(yōu)化問題，求解過程比較簡單，在這不再過多贅述，下面重點(diǎn)對動態(tài)局部補(bǔ)給路徑規(guī)劃進(jìn)行重點(diǎn)闡述。

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

用基于時間的分批處理策略來求解動態(tài)補(bǔ)給時間段路徑優(yōu)化問題的基本思路如下：

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

2）采用最晚指派策略，將動態(tài)補(bǔ)給轉(zhuǎn)換為瞬時靜態(tài)補(bǔ)給。在每個時間片段結(jié)束之前只接受動態(tài)信息但不進(jìn)行處理，補(bǔ)給船依舊按照原補(bǔ)給路徑規(guī)劃方案執(zhí)行補(bǔ)給任務(wù)，直到每個時間段的末尾時刻，即t=T，對該時間片段內(nèi)的動態(tài)信息進(jìn)行一次性批量處理。

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

將DRRSPTW轉(zhuǎn)化為瞬時靜態(tài)補(bǔ)給路徑規(guī)劃問題之后，根據(jù)補(bǔ)給船補(bǔ)給過程中的實(shí)時動態(tài)信息，判斷作戰(zhàn)艦艇補(bǔ)給需求類型，可分為原作戰(zhàn)艦艇補(bǔ)給需求取消、原作戰(zhàn)艦艇補(bǔ)給時間窗變更和新增作戰(zhàn)艦艇補(bǔ)給需求三種類型，設(shè)計相應(yīng)的補(bǔ)給子策略。

下面分別對三種情況下作戰(zhàn)艦艇補(bǔ)給時間窗變動后的補(bǔ)給子策略進(jìn)行相關(guān)闡述。

1）原作戰(zhàn)艦艇補(bǔ)給需求取消

假設(shè)航母編隊內(nèi)所有補(bǔ)給船的出發(fā)時間是使得補(bǔ)給船航行至第一艘作戰(zhàn)艦艇的時刻剛好就是第一艘作戰(zhàn)艦艇補(bǔ)給時間窗的開啟時間。

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

（1）取消補(bǔ)給需求的是某艘補(bǔ)給船補(bǔ)給路徑規(guī)劃的起始作戰(zhàn)艦艇

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

（2）取消補(bǔ)給需求的是某艘補(bǔ)給船補(bǔ)給路徑規(guī)劃的中間作戰(zhàn)艦艇

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

（3）取消補(bǔ)給需求的是某艘補(bǔ)給船補(bǔ)給路徑規(guī)劃的末端作戰(zhàn)艦艇

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

2）原作戰(zhàn)艦艇補(bǔ)給時間窗需求變更（延遲或提前）

假設(shè)當(dāng)出現(xiàn)原作戰(zhàn)艦艇補(bǔ)給時間窗需求變動的情況，可能會影響該補(bǔ)給船所規(guī)劃的補(bǔ)給路徑，但是不會影響其他補(bǔ)給船的補(bǔ)給路徑規(guī)劃。原作戰(zhàn)艦艇補(bǔ)給時間窗需求變更策略如圖2。

圖2 原作戰(zhàn)艦艇補(bǔ)給時間窗變更策略流程圖

方案1：當(dāng)原作戰(zhàn)艦艇補(bǔ)給時間窗需要變更時，在補(bǔ)給調(diào)度中心查看該作戰(zhàn)艦艇所屬補(bǔ)給船的補(bǔ)給路徑規(guī)劃情況，在不改變其他補(bǔ)給船所規(guī)劃補(bǔ)給路徑的前提下，以該時刻該補(bǔ)給船所在位置為起點(diǎn)，按照余下未補(bǔ)給作戰(zhàn)艦艇變更后的補(bǔ)給時間窗進(jìn)行補(bǔ)給路徑的局部優(yōu)化。如果該補(bǔ)給船出現(xiàn)多艘作戰(zhàn)艦艇的補(bǔ)給時間窗沖突情況，則需做進(jìn)一步判斷分析。

方案2：從補(bǔ)給船初始位置調(diào)用閑置補(bǔ)給船對該作戰(zhàn)艦艇進(jìn)行補(bǔ)給。如果補(bǔ)給船初始位置無閑置補(bǔ)給船可調(diào)用，則轉(zhuǎn)入方案3。

方案3：調(diào)用穿梭補(bǔ)給船來對該作戰(zhàn)艦艇進(jìn)行彈藥補(bǔ)給作業(yè)。

3）新作戰(zhàn)艦艇補(bǔ)給需求

新增作戰(zhàn)艦艇補(bǔ)給需求的動態(tài)補(bǔ)給策略流程圖如圖3。

圖3 新增作戰(zhàn)艦艇補(bǔ)給需求的動態(tài)補(bǔ)給策略流程圖

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

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

4 改進(jìn)C-W算法

在動態(tài)局部補(bǔ)給路徑規(guī)劃階段，瞬時靜態(tài)補(bǔ)給路徑規(guī)劃問題的實(shí)質(zhì)是基于時間窗的TSP。由于傳統(tǒng)C-W算法［11～12］不能直接用于求解帶有時間窗的TSP，所以本文采用改進(jìn)C-W算法來對該補(bǔ)給船余下作戰(zhàn)艦艇彈藥補(bǔ)給路徑進(jìn)行重新優(yōu)化。

4.1 改進(jìn)C-W算法的基本原理

對于帶有時間窗的TSP，在連接兩點(diǎn)時檢驗連接后是否滿足時間窗條件，構(gòu)造能求解該問題的啟發(fā)式算法（簡稱改進(jìn)C-W算法）。傳統(tǒng)C-W算法中節(jié)約值一般是距離的節(jié)約值，而改進(jìn)C-W算法中節(jié)約值表示時間的節(jié)約值，故本文討論的是滿足時間窗條件下的補(bǔ)給船最小化補(bǔ)給航行時間的補(bǔ)給路徑優(yōu)化問題。

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

EFj=Ri+Ti+tij-Rj

其中，Ri表示補(bǔ)給船到達(dá)處于補(bǔ)給需求點(diǎn)i的待補(bǔ)作戰(zhàn)艦艇的時間，Rj表示連接前補(bǔ)給船到達(dá)處于補(bǔ)給需求點(diǎn)j的待補(bǔ)作戰(zhàn)艦艇的時間，Ti表示補(bǔ)給船對處于補(bǔ)給需求點(diǎn)i的作戰(zhàn)艦艇進(jìn)行彈藥補(bǔ)給的時間，tij表示補(bǔ)給船從一艘作戰(zhàn)艦艇的補(bǔ)給需求點(diǎn)i航行至另一艘作戰(zhàn)艦艇的補(bǔ)給需求點(diǎn)j的所花費(fèi)的時間。

若EFj＞0，則表示連接點(diǎn)i和j之后，補(bǔ)給船到達(dá)作戰(zhàn)艦艇補(bǔ)給需求點(diǎn)j的時間推遲。

若EFj=0，則表示連接點(diǎn)i和j之后，補(bǔ)給船到達(dá)作戰(zhàn)艦艇補(bǔ)給需求點(diǎn)j的時間不變。

若EFj＜0，則表示連接點(diǎn)i和j之后，補(bǔ)給船到達(dá)作戰(zhàn)艦艇補(bǔ)給需求點(diǎn)j的時間提前。

假設(shè)TBj表示連接i和j點(diǎn)之后，j點(diǎn)和j點(diǎn)后面作戰(zhàn)艦艇補(bǔ)給需求點(diǎn)允許到達(dá)的最大提前時間；TAj表示連接i和j點(diǎn)之后，j點(diǎn)和j點(diǎn)后面作戰(zhàn)艦艇補(bǔ)給需求點(diǎn)允許到達(dá)的最大推遲時間，則有如下公式

其中r表示補(bǔ)給需求點(diǎn)j和j點(diǎn)后面作戰(zhàn)艦艇補(bǔ)給需求點(diǎn)，作戰(zhàn)艦艇補(bǔ)給需求點(diǎn)r的補(bǔ)給時間窗為[E Tr，LTr]。

當(dāng) EFj＜0，且 | EFj|≤TBj時，則有連接后補(bǔ)給船到達(dá)作戰(zhàn)艦艇補(bǔ)給需求點(diǎn)r的時間不會早于ETr，即連接后到達(dá)作戰(zhàn)艦艇補(bǔ)給需求點(diǎn)r的時間滿足時間窗上限要求。

當(dāng) EFj＞0 ，且 EFj≤TAj時，則有連接后補(bǔ)給船到達(dá)作戰(zhàn)艦艇補(bǔ)給需求點(diǎn)r的時間不會晚于LTr，即連接后到達(dá)作戰(zhàn)艦艇補(bǔ)給需求點(diǎn)r的時間滿足時間窗下限要求。

4.2 改進(jìn)C-W算法流程

圖4 改進(jìn)C-W算法流程

下面對圖4中改進(jìn)C-W算法的部分重點(diǎn)步驟進(jìn)行詳細(xì)闡述。

Step1：初始解的確定，并計算該初始解的總航行時間。初始解設(shè)置為派出K艘補(bǔ)給船分別對K艘作戰(zhàn)艦艇進(jìn)行補(bǔ)給，補(bǔ)給結(jié)束后分別回到初始位置的路徑規(guī)劃，即K條o→i→o的補(bǔ)給路徑，初始解的總航行時間如下：

其中doi表示補(bǔ)給船從初始位置航行至作戰(zhàn)艦艇補(bǔ)給需求點(diǎn)i的時間；dio表示補(bǔ)給船補(bǔ)給結(jié)束，從補(bǔ)給需求點(diǎn)i返回初始位置的航行時間。

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

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

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

1）作戰(zhàn)艦艇補(bǔ)給需求點(diǎn)i和j都不在已構(gòu)成的補(bǔ)給路徑上，即存在補(bǔ)給回路 o→i→o和o→j→o，此時則將補(bǔ)給路徑 o→i→j→o作為候選連接補(bǔ)給路徑。

2）作戰(zhàn)艦艇補(bǔ)給需求點(diǎn)i和j中的一個點(diǎn)在已構(gòu)成的補(bǔ)給路徑上，且該補(bǔ)給需求點(diǎn)與o點(diǎn)相連，而另外一個補(bǔ)給需求點(diǎn)不在已構(gòu)成的補(bǔ)給路徑上。假設(shè)補(bǔ)給需求點(diǎn)i在已構(gòu)成的補(bǔ)給路徑上（即存在補(bǔ)給回路o→i→…o或o…→i→o），補(bǔ)給需求點(diǎn)j不在已構(gòu)成的補(bǔ)給路徑上（即存在補(bǔ)給回路 o→j→o）。此時則把補(bǔ)給回路o→j→i→…o或 o…→i→j→o作為候選連接補(bǔ)給路徑回路。

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

Step5：假設(shè)作戰(zhàn)艦艇補(bǔ)給需求點(diǎn)j位于補(bǔ)給路徑上i補(bǔ)給需求點(diǎn)之后，分別計算EFj、TBj和TAj，然后再根據(jù)EFj、TBj和TAj三個值作進(jìn)一步判斷。

5 實(shí)例分析

本文以一種典型雙航母編隊的海上補(bǔ)給路徑規(guī)劃為例，編隊構(gòu)成包括2艘航母母艦、3艘伴隨補(bǔ)給船、15艘編隊附屬水面艦艇，對所提出的求解航母編隊補(bǔ)給船動態(tài)補(bǔ)給路徑規(guī)劃的模型與方法進(jìn)行驗證。由于論文篇幅有限，故只給出新增作戰(zhàn)艦艇補(bǔ)給需求情況下的實(shí)例結(jié)果。

5.1 初始輸入數(shù)據(jù)和相關(guān)參數(shù)設(shè)置

1）初始輸入數(shù)據(jù)

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

表1 輸入初始數(shù)據(jù)

（2）相關(guān)參數(shù)設(shè)置

1）補(bǔ)給船的平均航速v=25節(jié)（海里/小時）；

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

5.2 初始補(bǔ)給路徑規(guī)劃結(jié)果

表2 預(yù)期補(bǔ)給路徑規(guī)劃方案

圖5 補(bǔ)給船預(yù)期補(bǔ)給路徑規(guī)劃圖

5.3 新增作戰(zhàn)艦艇補(bǔ)給需求后的補(bǔ)給船補(bǔ)給路徑規(guī)劃結(jié)果

新增作戰(zhàn)艦艇補(bǔ)給需求相關(guān)信息如表3。

表3 新增作戰(zhàn)艦艇補(bǔ)給需求相關(guān)信息表

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

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

圖6 補(bǔ)給船t=19h時刻補(bǔ)給路徑圖

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

表4 新增作戰(zhàn)艦艇后補(bǔ)給船補(bǔ)給路徑規(guī)劃方案

圖7 新增作戰(zhàn)艦艇后補(bǔ)給船補(bǔ)給路徑修正圖

6 結(jié)語

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

［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］余鵬，何學(xué)軍.基于蟻群算法的艦艇編隊海上補(bǔ)給路徑規(guī)劃方法［J］.海軍工程大學(xué)學(xué)報，2014，26（2）：108-112.

［9］周曉光，趙厚仁，王述運(yùn)，等.航母編隊補(bǔ)給船海上補(bǔ)給航路規(guī)劃［J］.系統(tǒng)工程與電子技術(shù)，2014，36（9）：1756-1760.

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

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

［12］崔宏志，龔加安.帶時間窗車輛路徑問題的改進(jìn)節(jié)約算法［J］. 純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2011，27（5）：688-693.