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

齊玉東 宋 冰 郭 聚

（海軍航空大學岸防兵學院 煙臺 264001）

1 引言

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

2 輸送規劃問題描述

近年來，物資的就近調配和同裝互保模式成為主要發展趨勢［2］。本文將彈藥物資輸送規劃問題描述如下：為完成軍事斗爭準備，需要向某預定地域運輸一批彈藥物資，已知目的地域周邊有多個彈藥物資倉庫，如何在各倉庫間合理調配，并選擇合適的運輸路線，使得運輸時間、成本以及可能造成的損耗最小。

根據這一問題的實際需求，可以將彈藥物資的運輸問題抽象為從多個起始點到一個終點的運輸網絡模型。在這個模型中，把每個彈藥物資倉庫供應點作為模型中的起始點，到達的任務地域作為模型中的終點，除了起始點、終點以外，網絡中的其它各個節點實際上是指道路上的分岔口，網絡中的弧表示節點間的路徑，各個節點和弧上的權值表示節點間的長度、流量等意義。通常情況下，還需考慮運輸的時間、成本和運輸中的損耗情況等。

N Ramkumar［3］針對軍事物資調配多對多的情況，建立了時間消耗最小的網絡模型，解決了單向運輸路徑沖突問題。Minciardi［4］等以成本和風險為主要目標，建立了彈藥運輸路徑優化模型，并設計了求解算法。祁松［5］利用GIS的最優路線算法，得出最短路徑。杜潔等［6］針對應急物流條件下，時間最快和成本最低兩個方面進行了模型建立。關云飛［7］基于最近插入法，引入風險權重指標，給出彈藥補給運輸優化路徑多回路計算模型。除此之外，與該問題有關的還有很多研究成果［8～13］。本文在借鑒前述的成果基礎上，研究針對本文針對彈藥物資轉運的特點，結合網絡模型，構造了一個綜合時間、成本、損耗度最小的多目標網絡模型。

3 數學模型

3.1 變量定義

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

網絡G上定義非負函數集 D={dij|(vi，vj)∈E}，W={wij|(vi， vj)∈ E}Q={qij|(vi， vj)∈ E} ，C={cij|(vi， vj)∈E}，其中 dij、wij、qij和 cij分別表示從節點 vi出發經過弧(vi， vj)到達節點vj的單位運送時間、費用消耗、損失程度和弧eij最大容量限制。

設vs和ve分別為網絡G的始點和終點，f是弧 集 E 的 一 個 實 函 數 ，? e=(vi，vj)∈E ，記f(e)=fij，如果函數 f滿足流量守恒條件：

為方便描述，本文將網絡 G=(V， E， D，W，Q， C) 中 的 集 合 V={v1， v2， … ， vm，vm+1，…，vn，vn+1}改為V={ }s1，s2， …，sm，v1， v2， … ， vn，vb，其中節點V的子集S={s1，s2，…，sm}表示彈藥物資運輸網絡中的彈藥倉庫供應點，ve表示終點，弧和弧上的權值函數描述與上相同。

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

S表示所有彈藥倉庫供應點的集合；

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

M 表示目標終點的彈藥總量，M={m1，m2，…，ml}，其中mk表示彈藥物資Rk的需求數量；

3.2 目標函數及約束

對 ?Rk(?Rk∈?)，建立由網絡中出發點集 S到終點ve的彈藥物資運輸時間最短、費用最低和損失度最小的多目標優化問題模型。

4 算法設計

上述建立的彈藥物資運輸模型屬于多目標優化問題。多目標優化問題的最優解集常被稱為帕累托最優解的解集，即Pareto最優解集［14］。為了求得上述運輸網絡模型的Pareto最優集，本文采用NSGA-II多目標優化算法對該彈藥物資運輸問題進行求解。

4.1 NSGA-II算法執行流程

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

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

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

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

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

4.2 算法執行過程

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

step1 初始化參數，令k=1，k∈{1，2，…，l}，表示從第一種彈藥開始；構造彈藥物資倉庫供應點集合S={s1，s2，…，sn}。

step2 令j=0，sj∈S。

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

step4進入循環迭代i=1。

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

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

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

5 仿真實驗

為驗證所提出的問題模型及其求解算法，使用Matlab軟件編制相應程序進行仿真實驗并分析。

假設某軍事行動中，上級要求某部向某地集結，作戰任務所需彈藥物資從目的地附近的4個倉庫進行調運。所需彈藥物資的基本信息見表1，倉庫具備彈藥物資的數量見表2，各倉庫載具信息見表3，運輸網絡模型見圖6，運輸過程中各點間距離、成本、損失度等權值參數見表4。

表1 彈藥物資信息

表2 各倉庫彈藥物資數量

表3 載具性能參數

表4 物資1和物資2在網絡中的參數

圖1所示的圖形為此次輸送的網絡模型，其中節點1～4為彈藥倉庫供給點，也就是起點，節點18為目標終點，網絡中的其它節點表示路上的岔路口，節點間有弧的表示該段路徑相連通，弧上的數字代表節點間的距離。

圖1 運輸網絡圖

根據已經建立的模型和算法，通過將相關參數輸入后，執行程序得到如下運行結果。

通過仿真實驗，得到物資1的仿真輸送路徑與時間最短的路徑的方案進行的對比。

表5 物資1運輸路徑仿真實驗結果

同樣的，可以得到物資2通過仿真實驗得到的路徑方案與費用最少的路徑方案進行的對比。

表6 物資2運輸路徑仿真實驗結果

通過分析該實驗結果我們可以看出，按照物資輸送的時間最短或費用最低，得到的路徑結果往往是不同的，而且在其中一個或兩個目標為最優時，剩下的目標卻不一定是最好的，這正反映出多目標規劃往往很難取得絕對最優解這一特點。在結果對比上，相較于采用時間最短或費用最低，根據改進算法得出的仿真結果綜合優化了多個目標因素，充分體現了其優越性，能夠滿足實際問題的需要。

6 結語

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