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

1 引言

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

2 VRPTW問題與URRSPTW問題的聯(lián)系與區(qū)別

URRSPTW問題與VRPTW問題之間既存在相同之處，也存在部分區(qū)別。因此在對URRSPTW問題進(jìn)行描述與求解時(shí)，一方面，要充分吸取VRPTW問題中可以運(yùn)用的成功經(jīng)驗(yàn)；另一方面，要充分考慮URRSPTW問題的獨(dú)特屬性。此外，URRSPTW問題是基于編隊(duì)作戰(zhàn)條件下的補(bǔ)給路徑規(guī)劃問題，所以求解URRSPTW問題的考慮的因素和求解過程的復(fù)雜性更高。所以URRSPTW問題的求解思路是在URRSPTW問題與VRPTW問題共性的基礎(chǔ)上，結(jié)合URRSPTW問題作戰(zhàn)等獨(dú)特因素的影響來求解該問題。

兩者的相同之處：URRSPTW問題與VRPTW問題都屬于復(fù)雜化的優(yōu)化問題；都是采用圖論中頂點(diǎn)和賦權(quán)的邊方法對其進(jìn)行描述；圖中每個(gè)定點(diǎn)都只能被訪問一次。

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

3 URRSPTW問題的數(shù)學(xué)描述

3.1 補(bǔ)給模式描述

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

3.2 模型假設(shè)條件

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

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

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

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

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

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

6）每艘待補(bǔ)作戰(zhàn)艦艇的補(bǔ)給時(shí)間窗已知，可表示為[ ]ETi，LTi。只要補(bǔ)給船對該作戰(zhàn)艦艇的開始補(bǔ)給時(shí)間在時(shí)間窗[ETi，LTi]內(nèi)，即稱補(bǔ)給滿足時(shí)間窗約束。

3.3 符號定義

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

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

3.4 模型建立

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

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

流程約束條件

時(shí)間窗約束條件：

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

式（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）為時(shí)間窗約束條件。式（7）表示補(bǔ)給船到達(dá)作戰(zhàn)艦艇的時(shí)間約束，保證了補(bǔ)給時(shí)間的連續(xù)性。式（8）表示補(bǔ)給時(shí)間窗約束，補(bǔ)給船對待補(bǔ)作戰(zhàn)艦艇i的最早開始補(bǔ)給時(shí)間滿足作戰(zhàn)艦艇i的補(bǔ)給時(shí)間窗[ETi，LTi。]

4 改進(jìn)GA的設(shè)計(jì)

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

下面對改進(jìn)GA的設(shè)計(jì)步驟進(jìn)行詳細(xì)闡述。

1）染色體結(jié)構(gòu)設(shè)計(jì)

設(shè)計(jì)染色體結(jié)構(gòu)包括染色體編碼方式和編碼長度的確定。

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

第一艘補(bǔ)給船補(bǔ)給路徑：補(bǔ)給船初始位置→需求點(diǎn)4→需求點(diǎn)2→需求點(diǎn)1→補(bǔ)給船初始位置。

第二艘補(bǔ)給船補(bǔ)給路徑：補(bǔ)給船初始位置→需求點(diǎn)7→需求點(diǎn)8→需求點(diǎn)9→補(bǔ)給船初始位置。

第三艘補(bǔ)給船補(bǔ)給路徑：補(bǔ)給船初始位置→需求點(diǎn)6→需求點(diǎn)5→需求點(diǎn)3→補(bǔ)給船初始位置。

染色體長度=補(bǔ)給船總數(shù)+需求點(diǎn)數(shù)+1。

2）適應(yīng)度函數(shù)

在遺傳算法中，通過適應(yīng)度大小來區(qū)分種群中個(gè)體的優(yōu)劣，故設(shè)計(jì)合理的適應(yīng)度函數(shù)尤其重要。一般可根據(jù)模型中目標(biāo)函數(shù)設(shè)計(jì)相應(yīng)的適應(yīng)度函數(shù)，假設(shè) f(x)表示目標(biāo)函數(shù)，F(xiàn)(x)表示適應(yīng)度函數(shù)，則將 f(x)轉(zhuǎn)化為F(x)的過程定義為標(biāo)定［13］（Scaling）。本文采用的標(biāo)定方式是動(dòng)態(tài)線性標(biāo)定，具體如下：

其中k表示待定參數(shù)，且k的取值一般較大；x表示種群中的某個(gè)個(gè)體，f()x表示種群個(gè)體x的目標(biāo)函數(shù)；通過對目標(biāo)函數(shù)進(jìn)行上述標(biāo)定，得到的適應(yīng)度函數(shù)F()

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

對于目標(biāo)函數(shù) f()x有必要做進(jìn)一步闡述。由于GA在求解編隊(duì)補(bǔ)給船路徑規(guī)劃時(shí)不能直接處理模型中的約束條件，故必須把相關(guān)約束條件做進(jìn)一步轉(zhuǎn)化，并轉(zhuǎn)移到目標(biāo)函數(shù)中去。

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

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

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

3）選擇操作

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

其中Pi表示個(gè)體i被選中的概率；Fi表示種群中個(gè)體 i的適應(yīng)度值表示種群中所有個(gè)體的適應(yīng)度值總和。

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

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

4）遺傳算子的設(shè)計(jì)

（1）交叉算子設(shè)計(jì)

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

OX是在傳統(tǒng)PartiallyMatched Crossover（PMX）的基礎(chǔ)上改進(jìn)得到的，在求解URRSPTW模型中有較大的優(yōu)勢。OX的步驟如圖3所示。

OX運(yùn)算示意圖如下。

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

變異算子的實(shí)質(zhì)是對補(bǔ)給船的補(bǔ)給路徑規(guī)劃線路中的部分可行解進(jìn)行局部尋優(yōu)。設(shè)置變異算子的作用是加速GA的收斂速度和避免早熟現(xiàn)象發(fā)生。變異操作包括兩個(gè)步驟：首先依據(jù)變異率來決定是否進(jìn)行變異操作；如果確定進(jìn)行變異操作，則通過特定的變異操作方法來完全變異操作。

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

（3）終止條件

本文將改進(jìn)GA的終止條件設(shè)置為最大進(jìn)化代數(shù)M。

5 實(shí)例分析

本文以一種典型雙航母編隊(duì)的海上補(bǔ)給路徑規(guī)劃為例，編隊(duì)構(gòu)成包括2艘航母母艦、3艘伴隨補(bǔ)給船、15艘編隊(duì)附屬水面艦艇，對所提出的的模型與方法進(jìn)行驗(yàn)證。

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

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

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

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

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

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

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

5.2 航母編隊(duì)多補(bǔ)給船補(bǔ)給路徑規(guī)劃結(jié)果

采用改進(jìn)GA對航母編隊(duì)多補(bǔ)給船海上補(bǔ)給路徑進(jìn)行10次實(shí)例仿真，選取仿真結(jié)果中的一個(gè)較好結(jié)果，其最優(yōu)航母編隊(duì)多補(bǔ)給船海上補(bǔ)給路徑規(guī)劃方案如表2。

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

表2 航母編隊(duì)多補(bǔ)給補(bǔ)給路徑規(guī)劃方案

在該航母編隊(duì)多補(bǔ)給船海上補(bǔ)給路徑規(guī)劃方案下，航母編隊(duì)多補(bǔ)給船海上補(bǔ)給路徑規(guī)劃圖如下所示。

航母編隊(duì)多補(bǔ)給船海上補(bǔ)給路徑規(guī)劃圖由三艘補(bǔ)給船的補(bǔ)給路徑組成，為了圖中補(bǔ)給路徑清晰可見，分別采用不同的線條對三艘補(bǔ)給船的補(bǔ)給路徑進(jìn)行了標(biāo)記。

在該航母編隊(duì)多補(bǔ)給船海上補(bǔ)給路徑規(guī)劃方案下，補(bǔ)給船對各作戰(zhàn)艦艇進(jìn)行補(bǔ)給作業(yè)的實(shí)際到達(dá)時(shí)刻、等待時(shí)間、開始補(bǔ)給時(shí)刻和補(bǔ)給結(jié)束后的實(shí)際離開時(shí)刻等時(shí)間情況如表3所示。

表3 航母編隊(duì)多補(bǔ)給船海上補(bǔ)給路徑規(guī)劃的相關(guān)時(shí)間情況表

6 結(jié)語

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

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

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

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

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

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

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