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

（陸軍勤務(wù)學(xué)院，重慶 401331）

0 引言

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

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

圖1 艦艇編隊(duì)補(bǔ)給策略

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

3 種方式均將單補(bǔ)給艦補(bǔ)給總時(shí)間最短作為唯一目標(biāo)函數(shù)，對(duì)于大型艦艇編隊(duì)往往存在多補(bǔ)給艦的情況，此時(shí)目標(biāo)函數(shù)需要調(diào)整為在少用補(bǔ)給時(shí)間的情況下少用補(bǔ)給艦，此時(shí)模型變?yōu)殡p目標(biāo)函數(shù)模型，即補(bǔ)給時(shí)間最短和參與補(bǔ)給任務(wù)的補(bǔ)給艦最少。國內(nèi)對(duì)艦艇編隊(duì)海上補(bǔ)給線路規(guī)劃雙目標(biāo)函數(shù)模型比較少，其求解方式為設(shè)置函數(shù)權(quán)重后求和，從而轉(zhuǎn)化成單一目標(biāo)函數(shù)求解［2］，這種求解方式主觀性太強(qiáng)，結(jié)果往往不準(zhǔn)確。從本質(zhì)上講，艦艇編隊(duì)海上補(bǔ)給線路規(guī)劃雙目標(biāo)函數(shù)模型是復(fù)雜多旅行商問題的衍生模型，難以求得精確解，采用啟發(fā)式算法仍是求解該模型的最優(yōu)策略?；诖耍疚奶岢隽艘环N基于改進(jìn)GA 算法的艦艇編隊(duì)多補(bǔ)給艦海上補(bǔ)給路徑規(guī)劃模型。

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

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

1.1 模型假設(shè)條件

抽象出的數(shù)學(xué)模型與艦艇編隊(duì)海上補(bǔ)給實(shí)際情況略有不同，需要對(duì)相關(guān)細(xì)節(jié)進(jìn)行合理假設(shè)，以方便建模求解。

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

2）補(bǔ)給艦從初始位置出發(fā)，按照一定順序?qū)λ凶鲬?zhàn)艦艇實(shí)施補(bǔ)給后再回到初始位置；

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

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

1.2 符號(hào)定義

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

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

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

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

決策變量：

1.3 數(shù)學(xué)模型

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

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

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

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

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

2.1 種群初始化

本文采用近時(shí)矩陣初始化方法構(gòu)建初始解，近時(shí)矩陣定義如下。

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

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

步驟1：對(duì)個(gè)體i（i≤M），置染色體X={1}，迭代次數(shù)t=1；

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

步驟3：若t

步驟4：隨機(jī)產(chǎn)生k-1 初始斷點(diǎn)；

步驟5：若i

圖2 改進(jìn)的GA 算法流程圖

圖3 染色體編碼

2.2 染色體編碼

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

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

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

2.4 選擇運(yùn)算

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

2.5 交叉運(yùn)算

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

對(duì)于下面兩個(gè)父代染色體，隨機(jī)地選擇兩個(gè)交叉位置“|”。

兩個(gè)交叉位置之間的基因進(jìn)行交換，得到

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

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

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

對(duì)于S1 中第7 個(gè)艦艇基因x，可以由7?5，可得為5；對(duì)于S1 中第8 個(gè)艦艇基因x，可以由8?4?6 可得為4 或6，當(dāng)x=4 時(shí)出現(xiàn)重復(fù)，于是x=6；對(duì)于S1 中第9 個(gè)艦艇基因x，可以由9?3，可得為3；S2 同理，結(jié)果如下：

2.6 變異運(yùn)算

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

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

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

2.7 動(dòng)態(tài)斷點(diǎn)調(diào)整

隨機(jī)動(dòng)態(tài)調(diào)整斷點(diǎn)位置，從而實(shí)現(xiàn)對(duì)每艘補(bǔ)給艦補(bǔ)給作戰(zhàn)艦艇數(shù)量的調(diào)整。

2.8 補(bǔ)給艦數(shù)量控制規(guī)則

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

3 實(shí)例分析

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

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

3.1.1 原始數(shù)據(jù)輸入

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

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

3.1.2 參數(shù)設(shè)置

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

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

3.2 艦艇編隊(duì)多補(bǔ)給艦海上補(bǔ)給路徑規(guī)劃結(jié)果

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

各艦艇的相對(duì)位置和3 艘補(bǔ)給艦的海上補(bǔ)給路徑結(jié)果見52 頁圖4 所示。

3.3 艦艇編隊(duì)多補(bǔ)給艦海上補(bǔ)給路徑規(guī)劃結(jié)果對(duì)比

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

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

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

4 結(jié)論

本文研究了艦艇編隊(duì)多補(bǔ)給艦海上補(bǔ)給路徑規(guī)劃問題，通過模型分析和實(shí)例驗(yàn)證，所提模型能夠較好地為艦艇編隊(duì)中補(bǔ)給艦實(shí)施補(bǔ)給任務(wù)規(guī)劃路線，實(shí)現(xiàn)最短補(bǔ)給時(shí)間和最少補(bǔ)給艦參與補(bǔ)給的雙重目標(biāo)。本文研究結(jié)論可為艦艇編隊(duì)海上補(bǔ)給行為提供決策基礎(chǔ)依據(jù)，具有較強(qiáng)的實(shí)用性和針對(duì)性。

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

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