基于NSGA-Ⅱ算法的軍用彈藥物資輸送問題研究?

齊玉東 宋 冰 郭 聚

（海軍航空大學(xué)岸防兵學(xué)院 煙臺(tái) 264001）

1 引言

信息化條件下的聯(lián)合作戰(zhàn)，對(duì)軍隊(duì)投送的及時(shí)與高效提出了更高要求［1］。彈藥物資高效安全運(yùn)輸至預(yù)定地域也是影響作戰(zhàn)準(zhǔn)備乃至關(guān)系戰(zhàn)爭(zhēng)勝負(fù)的重要環(huán)節(jié)。目前，我軍的彈藥物資保障已初步形成體系，但也存在運(yùn)載車輛單一、調(diào)配規(guī)劃不夠科學(xué)等問題。因此，如何制定彈藥物資運(yùn)輸保障方案，尋求最優(yōu)的軍事運(yùn)輸路徑，以達(dá)到節(jié)約時(shí)間、里程、成本和損耗具有重要的現(xiàn)實(shí)意義。

2 輸送規(guī)劃問題描述

近年來(lái)，物資的就近調(diào)配和同裝互保模式成為主要發(fā)展趨勢(shì)［2］。本文將彈藥物資輸送規(guī)劃問題描述如下：為完成軍事斗爭(zhēng)準(zhǔn)備，需要向某預(yù)定地域運(yùn)輸一批彈藥物資，已知目的地域周邊有多個(gè)彈藥物資倉(cāng)庫(kù)，如何在各倉(cāng)庫(kù)間合理調(diào)配，并選擇合適的運(yùn)輸路線，使得運(yùn)輸時(shí)間、成本以及可能造成的損耗最小。

根據(jù)這一問題的實(shí)際需求，可以將彈藥物資的運(yùn)輸問題抽象為從多個(gè)起始點(diǎn)到一個(gè)終點(diǎn)的運(yùn)輸網(wǎng)絡(luò)模型。在這個(gè)模型中，把每個(gè)彈藥物資倉(cāng)庫(kù)供應(yīng)點(diǎn)作為模型中的起始點(diǎn)，到達(dá)的任務(wù)地域作為模型中的終點(diǎn)，除了起始點(diǎn)、終點(diǎn)以外，網(wǎng)絡(luò)中的其它各個(gè)節(jié)點(diǎn)實(shí)際上是指道路上的分岔口，網(wǎng)絡(luò)中的弧表示節(jié)點(diǎn)間的路徑，各個(gè)節(jié)點(diǎn)和弧上的權(quán)值表示節(jié)點(diǎn)間的長(zhǎng)度、流量等意義。通常情況下，還需考慮運(yùn)輸?shù)臅r(shí)間、成本和運(yùn)輸中的損耗情況等。

N Ramkumar［3］針對(duì)軍事物資調(diào)配多對(duì)多的情況，建立了時(shí)間消耗最小的網(wǎng)絡(luò)模型，解決了單向運(yùn)輸路徑?jīng)_突問題。Minciardi［4］等以成本和風(fēng)險(xiǎn)為主要目標(biāo)，建立了彈藥運(yùn)輸路徑優(yōu)化模型，并設(shè)計(jì)了求解算法。祁松［5］利用GIS的最優(yōu)路線算法，得出最短路徑。杜潔等［6］針對(duì)應(yīng)急物流條件下，時(shí)間最快和成本最低兩個(gè)方面進(jìn)行了模型建立。關(guān)云飛［7］基于最近插入法，引入風(fēng)險(xiǎn)權(quán)重指標(biāo)，給出彈藥補(bǔ)給運(yùn)輸優(yōu)化路徑多回路計(jì)算模型。除此之外，與該問題有關(guān)的還有很多研究成果［8～13］。本文在借鑒前述的成果基礎(chǔ)上，研究針對(duì)本文針對(duì)彈藥物資轉(zhuǎn)運(yùn)的特點(diǎn)，結(jié)合網(wǎng)絡(luò)模型，構(gòu)造了一個(gè)綜合時(shí)間、成本、損耗度最小的多目標(biāo)網(wǎng)絡(luò)模型。

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

3.1 變量定義

設(shè)G=(V ，E，D，W，Q，C ) 是一個(gè)有向的彈藥物 資 運(yùn) 輸 網(wǎng) 絡(luò) ，其 中 ：定 義 V={v1， v2， … ， vm，vm+1，…，vn，vn+1}為節(jié)點(diǎn)集；E={eij}∈V×V 稱為弧集，其中eij是一個(gè)有序的二元向量(vi，vj)，稱eij為從vi出發(fā)連向vj的弧，其中eij為vi的出弧，vj的入??；vi稱為vj的入鄰點(diǎn)，vj稱為vi的出鄰點(diǎn)，節(jié)點(diǎn)v的所有入鄰點(diǎn)的集合稱為v的入鄰域，記做NG-(v)，節(jié)點(diǎn)v的所有出鄰點(diǎn)的集合稱為v的出鄰域，記做NG+(v)；vj稱為 eij的頭，vi稱為 eij的尾，頭尾相連的弧稱作環(huán)。若有向網(wǎng)絡(luò)中既沒有重弧也沒有環(huán)，則該網(wǎng)絡(luò)稱為簡(jiǎn)單有向網(wǎng)絡(luò)，因此可以看出彈藥物資運(yùn)輸網(wǎng)絡(luò)是一個(gè)簡(jiǎn)單有向網(wǎng)絡(luò)。

網(wǎng)絡(luò)G上定義非負(fù)函數(shù)集 D={dij|(vi，vj)∈E}，W={wij|(vi， vj)∈ E}Q={qij|(vi， vj)∈ E} ，C={cij|(vi， vj)∈E}，其中 dij、wij、qij和 cij分別表示從節(jié)點(diǎn) vi出發(fā)經(jīng)過弧(vi， vj)到達(dá)節(jié)點(diǎn)vj的單位運(yùn)送時(shí)間、費(fèi)用消耗、損失程度和弧eij最大容量限制。

設(shè)vs和ve分別為網(wǎng)絡(luò)G的始點(diǎn)和終點(diǎn)，f是弧 集 E 的 一 個(gè) 實(shí) 函 數(shù) ，? e=(vi，vj)∈E ，記f(e)=fij，如果函數(shù) f滿足流量守恒條件：

為方便描述，本文將網(wǎng)絡(luò) G=(V， E， D，W，Q， C) 中 的 集 合 V={v1， v2， … ， vm，vm+1，…，vn，vn+1}改為V={ }s1，s2， …，sm，v1， v2， … ， vn，vb，其中節(jié)點(diǎn)V的子集S={s1，s2，…，sm}表示彈藥物資運(yùn)輸網(wǎng)絡(luò)中的彈藥倉(cāng)庫(kù)供應(yīng)點(diǎn)，ve表示終點(diǎn)，弧和弧上的權(quán)值函數(shù)描述與上相同。

該模型中所涉及的其他變量定義如下：

S表示所有彈藥倉(cāng)庫(kù)供應(yīng)點(diǎn)的集合；

? 表示裝備種類的集合，?={R1，R2，…，Rl}；

M 表示目標(biāo)終點(diǎn)的彈藥總量，M={m1，m2，…，ml}，其中mk表示彈藥物資Rk的需求數(shù)量；

3.2 目標(biāo)函數(shù)及約束

對(duì) ?Rk(?Rk∈?)，建立由網(wǎng)絡(luò)中出發(fā)點(diǎn)集 S到終點(diǎn)ve的彈藥物資運(yùn)輸時(shí)間最短、費(fèi)用最低和損失度最小的多目標(biāo)優(yōu)化問題模型。

4 算法設(shè)計(jì)

上述建立的彈藥物資運(yùn)輸模型屬于多目標(biāo)優(yōu)化問題。多目標(biāo)優(yōu)化問題的最優(yōu)解集常被稱為帕累托最優(yōu)解的解集，即Pareto最優(yōu)解集［14］。為了求得上述運(yùn)輸網(wǎng)絡(luò)模型的Pareto最優(yōu)集，本文采用NSGA-II多目標(biāo)優(yōu)化算法對(duì)該彈藥物資運(yùn)輸問題進(jìn)行求解。

4.1 NSGA-II算法執(zhí)行流程

NSGA-II算法是一種帶精英保留策略的非支配排序遺傳算法［15］，其基本思想如下。

首先，隨機(jī)產(chǎn)生規(guī)模為N的初始種群，在非劣前沿分級(jí)后通過遺傳算法的選擇、交叉、變異三個(gè)基本操作形成第一代子種群；

其次，從第二代開始，將子代種群與父代種群合并，并進(jìn)行快速非劣前沿分級(jí)操作，并對(duì)每一個(gè)非劣前沿分級(jí)層中的個(gè)體進(jìn)行擁擠度計(jì)算，根據(jù)非劣前沿關(guān)系以及個(gè)體的擁擠度選取合適的個(gè)體組成新的父代種群。

最后，通過遺傳算法的三個(gè)基本操作產(chǎn)生新的子代種群；依次類推，直至滿足程序終止條件。

另外，本文采用精英策略，主要從以下兩個(gè)方面進(jìn)行操作：首先，將父代Q(t)和子代P(t)合成為—個(gè)種群Γ(t)=Q(t)∪P(t)。這樣，種群Γ(t)的個(gè)體數(shù)是2N；其次，分別計(jì)算種群Γ(t)中的每一個(gè)個(gè)體的非支配序和擁擠度，依據(jù)定義偏序的方法逐一選取個(gè)體，直至個(gè)體總數(shù)達(dá)到N；從而形成新一輪的父代種群。而后，進(jìn)行新一輪的三大遺傳操作，形成新的子代種群，由此往復(fù)，直至進(jìn)化結(jié)束。

4.2 算法執(zhí)行過程

該問題的NSGA-II算法的主要步驟可以描述如下。

step1 初始化參數(shù)，令k=1，k∈{1，2，…，l}，表示從第一種彈藥開始；構(gòu)造彈藥物資倉(cāng)庫(kù)供應(yīng)點(diǎn)集合S={s1，s2，…，sn}。

step2 令j=0，sj∈S。

step3對(duì)物資Rk，供應(yīng)點(diǎn)sj，設(shè)定種群規(guī)模N，交叉概率pc=0.8，變異概率pm=0.05，最大迭代次數(shù)maxgen，令i=0，Φjk(i)=φ，利用Dijkstra最短路徑算法分別求出運(yùn)輸網(wǎng)中每一種彈藥物資運(yùn)輸時(shí)間最低、費(fèi)用最少、損失度最小的路徑作為初始種群Ωk(0)，對(duì)其進(jìn)行選擇、交叉和變異產(chǎn)生第一代種群Pk(0)。

step4進(jìn)入循環(huán)迭代i=1。

step5對(duì)種群Ωk(i)進(jìn)行交叉和變異操作，得到N個(gè)后代個(gè)體集Pk(i)。

step6記 Γ(i)=Ωk(i)∪Pk(i)，計(jì)算 Γ(i)中每個(gè)個(gè)體的非支配序irank和擁擠度id，并進(jìn)行非劣前沿分級(jí)排序，利用精英策略選擇Γ(i)中前N個(gè)較好的個(gè)體組成新的父代種群Ωk(i+1)，并記Γ(i)中非支配序irank=1的等級(jí)為Fi1，令

step7若i＜maxgen，令i=i+1，轉(zhuǎn) step4；若i=maxgen（最大迭代次數(shù)），j＜n，令j=j+1，轉(zhuǎn)step3；若i=maxgen，j=n，k＜l，令k=k+1，轉(zhuǎn)step2；若i=maxgen，j=n，k=l，轉(zhuǎn)step8。

5 仿真實(shí)驗(yàn)

為驗(yàn)證所提出的問題模型及其求解算法，使用Matlab軟件編制相應(yīng)程序進(jìn)行仿真實(shí)驗(yàn)并分析。

假設(shè)某軍事行動(dòng)中，上級(jí)要求某部向某地集結(jié)，作戰(zhàn)任務(wù)所需彈藥物資從目的地附近的4個(gè)倉(cāng)庫(kù)進(jìn)行調(diào)運(yùn)。所需彈藥物資的基本信息見表1，倉(cāng)庫(kù)具備彈藥物資的數(shù)量見表2，各倉(cāng)庫(kù)載具信息見表3，運(yùn)輸網(wǎng)絡(luò)模型見圖6，運(yùn)輸過程中各點(diǎn)間距離、成本、損失度等權(quán)值參數(shù)見表4。

表1 彈藥物資信息

表2 各倉(cāng)庫(kù)彈藥物資數(shù)量

表3 載具性能參數(shù)

表4 物資1和物資2在網(wǎng)絡(luò)中的參數(shù)

圖1所示的圖形為此次輸送的網(wǎng)絡(luò)模型，其中節(jié)點(diǎn)1～4為彈藥倉(cāng)庫(kù)供給點(diǎn)，也就是起點(diǎn)，節(jié)點(diǎn)18為目標(biāo)終點(diǎn)，網(wǎng)絡(luò)中的其它節(jié)點(diǎn)表示路上的岔路口，節(jié)點(diǎn)間有弧的表示該段路徑相連通，弧上的數(shù)字代表節(jié)點(diǎn)間的距離。

圖1 運(yùn)輸網(wǎng)絡(luò)圖

根據(jù)已經(jīng)建立的模型和算法，通過將相關(guān)參數(shù)輸入后，執(zhí)行程序得到如下運(yùn)行結(jié)果。

通過仿真實(shí)驗(yàn)，得到物資1的仿真輸送路徑與時(shí)間最短的路徑的方案進(jìn)行的對(duì)比。

表5 物資1運(yùn)輸路徑仿真實(shí)驗(yàn)結(jié)果

同樣的，可以得到物資2通過仿真實(shí)驗(yàn)得到的路徑方案與費(fèi)用最少的路徑方案進(jìn)行的對(duì)比。

表6 物資2運(yùn)輸路徑仿真實(shí)驗(yàn)結(jié)果

通過分析該實(shí)驗(yàn)結(jié)果我們可以看出，按照物資輸送的時(shí)間最短或費(fèi)用最低，得到的路徑結(jié)果往往是不同的，而且在其中一個(gè)或兩個(gè)目標(biāo)為最優(yōu)時(shí)，剩下的目標(biāo)卻不一定是最好的，這正反映出多目標(biāo)規(guī)劃往往很難取得絕對(duì)最優(yōu)解這一特點(diǎn)。在結(jié)果對(duì)比上，相較于采用時(shí)間最短或費(fèi)用最低，根據(jù)改進(jìn)算法得出的仿真結(jié)果綜合優(yōu)化了多個(gè)目標(biāo)因素，充分體現(xiàn)了其優(yōu)越性，能夠滿足實(shí)際問題的需要。

6 結(jié)語(yǔ)

軍事運(yùn)輸保障方案中，科學(xué)合理的軍事輸送路徑，是保障部隊(duì)完成作戰(zhàn)任務(wù)的重要工作。本文根據(jù)彈藥物資輸送實(shí)際，提出了結(jié)合時(shí)間、費(fèi)用、損失度等要素的路徑優(yōu)化模型，并在Matlab中利用NS?GA-II算法進(jìn)行仿真驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，所建立的模型符合彈藥物資運(yùn)輸?shù)那闆r，有利于提高運(yùn)輸效率。但本文研究的問題還未考慮路徑損壞等突發(fā)情況，這是今后主要研究的方向。