帶時(shí)間窗軍事物資配送問題的NSGA-Ⅱ算法

趙文飛，周 剛，楊樹杰，董 超

（海軍航空工程學(xué)院基礎(chǔ)部，山東煙臺(tái)264001）

帶時(shí)間窗軍事物資配送問題的NSGA-Ⅱ算法

趙文飛，周 剛，楊樹杰，董 超

（海軍航空工程學(xué)院基礎(chǔ)部，山東煙臺(tái)264001）

針對(duì)戰(zhàn)場軍事物資配送中帶時(shí)間窗的路徑優(yōu)化問題，以運(yùn)輸距離、運(yùn)輸費(fèi)用和風(fēng)險(xiǎn)性為目標(biāo)，建立了帶有時(shí)間窗的多目標(biāo)網(wǎng)絡(luò)運(yùn)輸模型，提出了一種改進(jìn)的多目標(biāo)遺傳算法NSGA-Ⅱ。算法中引入剩余網(wǎng)絡(luò)的概念，采用數(shù)值編碼方式，增加了精英保留策略和小生境密度。仿真實(shí)驗(yàn)結(jié)果表明，本文建立的模型合理，算法在一定程度上克服了求解多目標(biāo)優(yōu)化問題過程中易陷入局部最優(yōu)的現(xiàn)象，提高了戰(zhàn)場上求解軍事物資配送路徑優(yōu)化問題的效率，并能夠使決策者根據(jù)仿真實(shí)驗(yàn)中的各項(xiàng)參數(shù)值自行擇優(yōu)選擇運(yùn)輸方案。

軍事物資；時(shí)間窗；多目標(biāo)；NSGA-Ⅱ

0 引 言

隨著軍事裝備的不斷發(fā)展，軍事物資的配送往往要求運(yùn)輸種類多、批次大、運(yùn)輸量小、運(yùn)輸時(shí)間短等。因此，為了達(dá)到運(yùn)輸目的，軍事物資配送的核心環(huán)節(jié)“車輛路徑優(yōu)化問題”顯得尤為重要。近來，很多學(xué)者在社會(huì)物流配送研究領(lǐng)域中做了大量工作［1］，而在軍事物資配送領(lǐng)域中，尤其是戰(zhàn)時(shí)的軍事物資配送問題研究較少。戰(zhàn)時(shí)軍事物資運(yùn)輸?shù)倪^程中往往會(huì)因?yàn)檫\(yùn)輸路徑或工具遭受破壞而停止，為了避免拖延運(yùn)輸物資的時(shí)間影響戰(zhàn)爭局勢(shì)，必須及時(shí)找到最優(yōu)的備用路徑，擬達(dá)到對(duì)戰(zhàn)爭影響最小的效果。

事實(shí)上，在戰(zhàn)時(shí)的軍事物資調(diào)配中，若將運(yùn)輸路徑的交叉口視為網(wǎng)路中的節(jié)點(diǎn)，運(yùn)輸路徑視為節(jié)點(diǎn)與節(jié)點(diǎn)之間的弧，則戰(zhàn)時(shí)軍事物資調(diào)配網(wǎng)絡(luò)可視為一個(gè)依賴時(shí)間變化的動(dòng)態(tài)網(wǎng)絡(luò)。戰(zhàn)時(shí)運(yùn)輸路徑和工具遭到破壞則可模擬為網(wǎng)絡(luò)中弧和節(jié)點(diǎn)上的權(quán)值發(fā)生改變，也就是模擬為網(wǎng)絡(luò)弧上的權(quán)值依賴時(shí)間動(dòng)態(tài)變化。一般講可分為4種形式：弧的刪除與添加，弧權(quán)重的變大與變小。

對(duì)于一個(gè)實(shí)際的物資配送問題，往往會(huì)考慮多個(gè)運(yùn)輸參數(shù)，如距離、費(fèi)用及風(fēng)險(xiǎn)性等多個(gè)目標(biāo)。而在求解多個(gè)目標(biāo)優(yōu)化問題時(shí)，往往很難找到一個(gè)對(duì)所有目標(biāo)均為最優(yōu)的解，通常處理這類問題的辦法有以下幾種［2-3］：加權(quán)法，效用函數(shù)法，字典序法和距離函數(shù)法。但是當(dāng)決策者如果不能準(zhǔn)確知道目標(biāo)間的任何偏好信息時(shí)，上述方法都是基于一種妥協(xié)的思想。為了能夠有效地解決時(shí)間依賴條件下的物資配送問題，近年來國內(nèi)外學(xué)者做了大量的研究工作［48］，其中文獻(xiàn)［7］提出了1- SA和2- SA方法，并研究了以運(yùn)輸距離、費(fèi)用為目標(biāo)的軟時(shí)間窗車輛路徑問題；文獻(xiàn)［8］研究了帶有時(shí)間窗的多源點(diǎn)、多種裝備物資調(diào)配的多目標(biāo)規(guī)劃問題。目前國內(nèi)對(duì)帶有時(shí)間窗的車輛路徑優(yōu)化問題的研究也取得了一定的結(jié)果［9-12］，其中文獻(xiàn)［12］，提出了一種改進(jìn)的約束多目標(biāo)粒子群優(yōu)化算法，研究帶有硬時(shí)間窗的戰(zhàn)場物資配送的車輛路徑問題。

文獻(xiàn)［13］研究了和平時(shí)期軍事物資配送的多目標(biāo)路徑優(yōu)化問題。本文在此基礎(chǔ)之上，以戰(zhàn)時(shí)軍事物資調(diào)配為背景，以距離、費(fèi)用和風(fēng)險(xiǎn)性為目標(biāo)（風(fēng)險(xiǎn)性取決于各路徑在運(yùn)輸網(wǎng)絡(luò)中的重要程度），構(gòu)造了一個(gè)依賴時(shí)間變化的多目標(biāo)動(dòng)態(tài)網(wǎng)絡(luò)模型，并在傳統(tǒng)的NSGA-Ⅱ算法基礎(chǔ)上進(jìn)行改進(jìn)，用于求解該問題。

1 問題描述及數(shù)學(xué)建模

1.1 問題描述

在戰(zhàn)時(shí)軍事物資調(diào)配網(wǎng)絡(luò)中，運(yùn)輸路徑上的運(yùn)輸距離、費(fèi)用、風(fēng)險(xiǎn)系數(shù)等參數(shù)都隨著時(shí)間的變化發(fā)生改變，網(wǎng)絡(luò)中的節(jié)點(diǎn)位置始終保持不變，如果某條運(yùn)輸路徑遭受損壞，則視該路徑的權(quán)值為無窮大。若在運(yùn)輸過程中某節(jié)點(diǎn)被損壞，則把與該節(jié)點(diǎn)相關(guān)聯(lián)的所有弧的權(quán)值函數(shù)設(shè)為無窮大。因此，戰(zhàn)時(shí)軍事物資調(diào)配可以模擬為帶有時(shí)間窗的動(dòng)態(tài)網(wǎng)絡(luò)問題，模型的動(dòng)態(tài)性體現(xiàn)在網(wǎng)絡(luò)中弧上的權(quán)值函數(shù)隨著時(shí)間改變而改變，且動(dòng)態(tài)網(wǎng)絡(luò)中的弧是不定向的。

為了敘述方便，依據(jù)我軍后勤部門保障體系的實(shí)際情況，將戰(zhàn)時(shí)各地區(qū)物資配送問題模擬為由m個(gè)軍事倉庫向某基地輸送軍事物資，每個(gè)倉庫虛擬為源點(diǎn)，軍事基地為匯點(diǎn)，網(wǎng)絡(luò)中運(yùn)輸路徑上各權(quán)值函數(shù)依賴時(shí)間變化。考慮軍事物資調(diào)配往往會(huì)涉及到運(yùn)輸距離、費(fèi)用、風(fēng)險(xiǎn)系數(shù)等參數(shù)，從而戰(zhàn)時(shí)軍事物資調(diào)配可視為依賴時(shí)間的多目標(biāo)動(dòng)態(tài)的網(wǎng)絡(luò)模型。

1.2 模型建立

戰(zhàn)時(shí)軍事物資配送的動(dòng)態(tài)網(wǎng)絡(luò)為

節(jié)點(diǎn)集為

弧集為

弧上的非負(fù)權(quán)函數(shù)集為

在給出軍事物資調(diào)配動(dòng)態(tài)網(wǎng)絡(luò)模型前，定義變量如下：S表示所有源點(diǎn)的集合，其中S＝｛（a1，t1），（a2，t2），…，（am，tm）｝；vb表示匯點(diǎn)；表示物資種類的集合，＝｛，表示從第a個(gè)源點(diǎn)發(fā)出的物資經(jīng)過弧（vi，vj）的次數(shù)（t）表示在時(shí)刻t從第a個(gè)源點(diǎn)發(fā)出的軍事物資k經(jīng)過弧（vi，vj）的運(yùn)輸路程長度；（t）表示在時(shí)刻t從第a個(gè)源點(diǎn)發(fā)出的軍事物資經(jīng)過弧（vi，vj）的流值；（t）表示在時(shí)刻t從第a個(gè)源點(diǎn)運(yùn)出的軍事物資經(jīng)過弧（vi，vj）的單位流量費(fèi)用（t）表示時(shí)刻t從第a個(gè)源點(diǎn)運(yùn)出的軍事物資在弧（vi，vj）上的容量上限；（t）表示在時(shí)刻t從第a個(gè)源點(diǎn)運(yùn)出的軍事物資k經(jīng)過弧（vi，vj）的單位流量的風(fēng)險(xiǎn)系數(shù)表示第a個(gè)源點(diǎn)運(yùn)出的軍事物資的流值；M表示需求點(diǎn)的物資總量，M＝｛m1，m2，…，mk，…，ml｝，其中mk表示匯點(diǎn)對(duì)軍事物資的需求量。

下面給出軍事物資運(yùn)輸網(wǎng)絡(luò)中源點(diǎn)S到需求點(diǎn)vb軍事物資（?∈）運(yùn)輸路程最短、費(fèi)用最少和風(fēng)險(xiǎn)系數(shù)最低的多目標(biāo)優(yōu)化問題模型。

（1）運(yùn)輸路徑路程最短的目標(biāo)函數(shù)

（2）運(yùn)輸費(fèi)用最少的目標(biāo)函數(shù)

（3）運(yùn)輸風(fēng)險(xiǎn)最低的目標(biāo)函數(shù)

模型的約束條件如下：

（1）運(yùn)輸過程中確保可行解是一條有效運(yùn)輸路徑的約束條件

（2）運(yùn)輸過程中可行流的約束條件

（3）運(yùn)輸過程中需求匯點(diǎn)對(duì)軍事物資點(diǎn)需求量的約束條件

（4）網(wǎng)絡(luò)中弧上的容量限制條件

（5）網(wǎng)絡(luò)中弧上的權(quán)值非負(fù)約束條件

2 算法設(shè)計(jì)及執(zhí)行過程

針對(duì)時(shí)間依賴的動(dòng)態(tài)網(wǎng)路G，通常將時(shí)間以較小的時(shí)間間隔Δ進(jìn)行離散化，在設(shè)定的時(shí)間間隔Δ內(nèi)，近似認(rèn)為網(wǎng)絡(luò)中弧的條件不發(fā)生改變，則所研究的感興趣的時(shí)間區(qū)間［t0，tm］將被離散化為一個(gè)時(shí)刻的集合T＝｛t0，t0＋Δ，…，t0＋（M－1）Δ｝，tM＝t0＋（M－1）Δ。M是正整數(shù)；t0是網(wǎng)絡(luò)中從任意某節(jié)點(diǎn)出發(fā)的最早時(shí)刻。這里假設(shè)t0＝0，則T＝｛0，Δ，…，（M－1）Δ｝，Δ是較小的時(shí)間間隔，在該時(shí)間間隔內(nèi)弧上所有權(quán)值不發(fā)生改變。對(duì)?t∈T，弧上所有權(quán)值函數(shù)均為非負(fù)實(shí)數(shù)，若t＞（M－1）Δ，則定義dij（t）＝∞，wij（t）＝∞，qij（t）＝∞，cij（t）＝0。

通過將時(shí)間區(qū)間［t0，tm］離散化，則網(wǎng)絡(luò)G＝（V，A，D（t），W（t），Q（t），C（t））可調(diào)整為

式中，V*＝｛（vi，t）｜（vi，t）∈V×T｝，即G中的每個(gè)節(jié)點(diǎn)在時(shí)間維展開成一系列節(jié)點(diǎn)時(shí)間組；A*是G*的弧集，弧A*的定義為

弧上所有權(quán)值定義為

其中，Δij（t）指從節(jié)點(diǎn)vi到節(jié)點(diǎn)vj所用的時(shí)間。

容易看出，對(duì)時(shí)間區(qū)間進(jìn)行離散化后，依賴時(shí)間的動(dòng)態(tài)網(wǎng)絡(luò)優(yōu)化問題可近似轉(zhuǎn)化為靜態(tài)網(wǎng)絡(luò)優(yōu)化問題進(jìn)行處理。在離散后的每個(gè)時(shí)間區(qū)間里，弧上的所有權(quán)值近似視為不變。為了符合戰(zhàn)場的實(shí)際規(guī)律，把弧上權(quán)值函數(shù)發(fā)生變化的時(shí)刻抽象為軍事物資運(yùn)輸網(wǎng)絡(luò)受到損壞的時(shí)刻。因此，在感興趣的時(shí)間段里，可根據(jù)網(wǎng)絡(luò)路徑受到破壞的時(shí)刻對(duì)時(shí)間區(qū)間進(jìn)行離散，在離散后的每個(gè)時(shí)間區(qū)間里，弧上的權(quán)值函數(shù)不會(huì)發(fā)生改變。

一般來講，運(yùn)輸網(wǎng)絡(luò)遭到破壞包括以下兩種情況：

（1）運(yùn)輸路徑遭到損壞。這種情況可模擬為網(wǎng)絡(luò)中弧上的權(quán)值發(fā)生改變，包括運(yùn)輸路徑的距離、運(yùn)輸費(fèi)用以及風(fēng)險(xiǎn)系數(shù)等。如果按照原來的運(yùn)輸路線繼續(xù)運(yùn)輸，運(yùn)輸路徑的距離、費(fèi)用以及運(yùn)輸過程中的風(fēng)險(xiǎn)度可能會(huì)大幅度增加，因此必須迅速選擇最優(yōu)的替代路徑。

（2）運(yùn)輸工具遭到損壞。如果運(yùn)輸工具上的物資沒有遭到損壞，原則上則是從相應(yīng)的源點(diǎn)另派運(yùn)輸工具去接應(yīng)，但是實(shí)際情況下，在運(yùn)輸途中沒有運(yùn)輸工具，因此重新裝載會(huì)浪費(fèi)更多時(shí)間。所以如果運(yùn)輸途中運(yùn)輸工具遭到損壞，則需從源點(diǎn)中尋找一條當(dāng)前網(wǎng)絡(luò)中最優(yōu)的替代運(yùn)輸路徑進(jìn)行運(yùn)輸。

為了解決軍事物資運(yùn)輸動(dòng)態(tài)性的問題，本節(jié)引入剩余網(wǎng)絡(luò)的概念。

2.1 剩余網(wǎng)絡(luò)

剩余網(wǎng)絡(luò)的定義：?ti∈T，設(shè)網(wǎng)絡(luò)G在ti時(shí)刻遭到破壞，則網(wǎng)絡(luò)G中的各種參數(shù)需作以下調(diào)整。

（1）需求點(diǎn)需求量的調(diào)整：

式中，Mi為在ti時(shí)刻以內(nèi)需求點(diǎn)已經(jīng)收到物資的總量。（2）容量約束的調(diào)整：

其中，對(duì)?（vi，vj）∈A*，?k∈Q，?a∈S。

（3）時(shí)間約束的調(diào)整：感興趣的時(shí)間段由［t0，tm］改為［ti，tm］。

（5）網(wǎng)絡(luò)節(jié)點(diǎn)的調(diào)整：從源點(diǎn)運(yùn)出的每種物資，在ti時(shí)刻網(wǎng)絡(luò)G中的位置均記為新的源點(diǎn)（需求點(diǎn)除外、被損壞的運(yùn)輸工具除外），與網(wǎng)絡(luò)G中的節(jié)點(diǎn)組成新的網(wǎng)絡(luò)節(jié)點(diǎn)。

經(jīng)過上述（1）～（5）5個(gè)方面的調(diào)整后所得到的網(wǎng)絡(luò)稱之為G的剩余網(wǎng)絡(luò)，記為G′。網(wǎng)絡(luò)G′中新源點(diǎn)的出弧容量上限和源點(diǎn)的供給量均為該節(jié)點(diǎn)的流值。

2.2 算法思想

實(shí)際上，多目標(biāo)的最短路徑問題是單目標(biāo)的最短路徑問題的一種重要的變形問題，以NP－難題著稱于學(xué)界。因此，求解動(dòng)態(tài)的多目標(biāo)最短路徑問題則變得更加復(fù)雜。針對(duì)動(dòng)態(tài)網(wǎng)絡(luò)求解的復(fù)雜性，本文首先將時(shí)間區(qū)間進(jìn)行離散化，利用剩余網(wǎng)絡(luò)重新構(gòu)造運(yùn)輸網(wǎng)絡(luò)，從而把動(dòng)態(tài)運(yùn)輸網(wǎng)絡(luò)轉(zhuǎn)化為靜態(tài)的運(yùn)輸網(wǎng)絡(luò)，然后結(jié)合問題實(shí)際，利用改進(jìn)的NSGA-Ⅱ算法對(duì)靜態(tài)的運(yùn)輸網(wǎng)絡(luò)進(jìn)行求解。

NSGA-Ⅱ算法的核心思想是根據(jù)個(gè)體的非劣排序（非支配序）與其適應(yīng)度函數(shù)進(jìn)行選擇。其中非劣排序（非支配序）是由非劣解［14］產(chǎn)生的。

定義1［14］設(shè)多目標(biāo)優(yōu)化問題的目標(biāo)函數(shù)為

若存在解x和y滿足下面等式：

則稱解x為非劣解，并稱x非劣于y。

種群中的個(gè)體依據(jù)非劣關(guān)系進(jìn)行排序，定義nx為種群中非劣于x的個(gè)體數(shù)量，Rx為個(gè)體x支配的所有個(gè)體存入集合Rx。首先，在種群中利用非劣解的定義計(jì)算出nx＝0的所有個(gè)體，并存入集合F1，并記個(gè)體的非劣序＝1；然后，考慮集合F1中個(gè)體x支配集Rx中的個(gè)體y，若ny－1＝0，則將個(gè)體y存入集合F2，并記集合F2中所有個(gè)體的非劣序＝2；類似地，在集合F2中重復(fù)上述步驟，當(dāng)種群中所有個(gè)體都有非劣序值時(shí)結(jié)束。

為了進(jìn)一步對(duì)非劣序值相同的個(gè)體進(jìn)行排序，這里引入小生境密度的概念。由于本文中考慮的是 “多對(duì)一”的動(dòng)態(tài)網(wǎng)絡(luò)模型，因此將同源點(diǎn)的所有運(yùn)輸路徑分為同一個(gè)區(qū)域。

定義2設(shè)x為集合Fi中的個(gè)體，F(xiàn)j為Fi中與個(gè)體x同區(qū)域的路徑，令個(gè)體x的小生境密度函數(shù)為

式中，A（x）為運(yùn)輸路徑x上所包含的弧集；V（x）為運(yùn)輸路徑x所包含的節(jié)點(diǎn)集；｜B｜為集合B的勢(shì)。從定義2中不難看出，小生境密度高的個(gè)體表示該個(gè)體在同區(qū)域與別的路徑重合度比較高。

種群中所有個(gè)體經(jīng)過非劣序和小生境密度的計(jì)算都得到兩個(gè)屬性：非劣序和小生境密度id。下面針對(duì)這兩個(gè)屬性定義偏序關(guān)系。

2.3 算法步驟

步驟1對(duì)模型G中的時(shí)間區(qū)間［0，Tmax］進(jìn)行離散，得T＝｛0，Δ，…，（M－1）Δ｝，Tmax＝（M－1）Δ；初始化相關(guān)參數(shù)，令t＝0，k＝1；構(gòu)造源點(diǎn)集合S＝｛a1，a2，…，an｝。

步驟2設(shè)時(shí)間為t，令j＝0，aj∈S。

步驟3對(duì)任意一種物資源點(diǎn)aj，設(shè)定算法終止準(zhǔn)則，給定種群規(guī)模為N，雜交概率為pc，變異概率為pm，最大迭代次數(shù)為maxgen，最大時(shí)間迭代步為Tmax；令i＝0（i）＝φ，利用Dijkstra算法確定初始種群Ck（0），對(duì)其進(jìn)行選擇、交叉和變異產(chǎn)生第一代種群Zk（0）。

步驟4進(jìn)入循環(huán)迭代，令i＝1。

步驟5對(duì)種群Ck（i）進(jìn)行交叉操作和變異操作，得到N個(gè)后代Zk（i）。

步驟6記ρ（i）＝Ck（i）∪Zk（i），計(jì)算ρ（i）中每個(gè)個(gè)體的非劣序和小生境密度id，并進(jìn)行非劣前沿分級(jí)，利用精英策略保留方法選擇ρ（i）中較好的N個(gè)個(gè)體組成新的父代種群Ck（i＋1），并記ρ（i）中非支配序＝1的等級(jí)為，令（i＋1）＝（i）∪。

步驟7若i＜maxgen，令i＝i＋1，轉(zhuǎn)步驟4；若i＝maxgen（最大迭代次數(shù)），j＜n，令j＝j(luò)＋1，轉(zhuǎn)步驟3；若i＝maxgen，j＝n，k＜l，令k＝k＋1，轉(zhuǎn)步驟2；若i＝maxgen，j＝n，k＝l，轉(zhuǎn)步驟8；

步驟8若k＜l，令k＝k＋1，轉(zhuǎn)步驟2；若k＝l，t＜Tmax，判別t時(shí)刻匯點(diǎn)已收到的軍事物資Mt，若Mt≥M，則迭代停止；否則，令t＝t＋Δ，構(gòu)造剩余網(wǎng)絡(luò)G′，令G＝G′，轉(zhuǎn)步驟2；若t＝Tmax，則迭代停止，算法結(jié)束。

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

針對(duì)本文提出的戰(zhàn)時(shí)軍事物資配送建模思想及其求解算法，以某海軍岸導(dǎo)團(tuán)軍事物資調(diào)配補(bǔ)給為背景，首先利用本文的建模思想和算法進(jìn)行建模，用Matlab軟件編程進(jìn)行仿真實(shí)驗(yàn)，并采用傳統(tǒng)的加權(quán)遺傳算法與本文提出的建模思想和算法作對(duì)比；其次針對(duì)本文提出的解決動(dòng)態(tài)網(wǎng)絡(luò)的算法思想對(duì)案例做仿真實(shí)驗(yàn)。假設(shè)該岸導(dǎo)團(tuán)需要兩種物資，由3個(gè)聯(lián)勤部后勤倉庫向其提供物資保障。各后勤倉庫與岸導(dǎo)團(tuán)的物資運(yùn)輸網(wǎng)絡(luò)參數(shù)如表1所示。

表1 物資1、物資2在網(wǎng)絡(luò)G中各項(xiàng)權(quán)值參數(shù)_______

3.1 仿真實(shí)驗(yàn)結(jié)果對(duì)比

根據(jù)本文建立的軍事物資調(diào)配的模型和算法思想，利用Matlab編程可求出在時(shí)刻物資1、物資2的最佳運(yùn)輸方案各項(xiàng)參數(shù)值如表2所示。

表2 物資1、物資2在t=0時(shí)刻各運(yùn)輸方案中的相關(guān)參數(shù)（1）

一般來講傳統(tǒng)加權(quán)法是把多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題來進(jìn)行求解，為了消除量綱的不可加性，本文將多目標(biāo)函數(shù)轉(zhuǎn)化如下：

這里假設(shè)3個(gè)目標(biāo)函數(shù)的權(quán)重相等，利用傳統(tǒng)遺傳算法編程仿真，得到結(jié)果如表3所示。

表3 物資1、物資2在t=0時(shí)刻各運(yùn)輸路徑的相關(guān)參數(shù)（2）

從表2和表3不難看出，用傳統(tǒng)的加權(quán)遺傳算法求出的解比較依賴于各目標(biāo)所占的權(quán)重，如物資2運(yùn)輸路徑1→6→11→15的風(fēng)險(xiǎn)系數(shù)比路徑3→6→11→15小，排第1，而路徑3→6→11→15的運(yùn)輸距離及費(fèi)用都比路徑1→6→11→15優(yōu)越。此外，對(duì)比表2，利用傳統(tǒng)的遺傳算法求出的解比較集中，而利用改進(jìn)的NSGA-Ⅱ算法求出的解分布相對(duì)均勻，保證了種群的多樣性，在一定程度上防止算法陷入局部最優(yōu)，并且運(yùn)輸路徑的多樣性有利于戰(zhàn)場上軍事物資的運(yùn)輸。

3.2 動(dòng)態(tài)網(wǎng)絡(luò)仿真實(shí)驗(yàn)分析

從表2不難看出物資1與物資2的最佳運(yùn)輸方案為2→10→12→15與3→6→11→15，現(xiàn)假定物資1、物資2均以速度為60 km／h和58 km／h的速度沿著最優(yōu)路徑進(jìn)行運(yùn)輸，并假設(shè)網(wǎng)絡(luò)在t＝5 h時(shí)該運(yùn)輸網(wǎng)絡(luò)遭到破壞（仿真實(shí)驗(yàn)時(shí)，不是所有的路徑都遭到破壞，而是由計(jì)算機(jī)隨機(jī)選擇路徑，同時(shí)為方便敘述，假設(shè)該運(yùn)輸網(wǎng)絡(luò)只遭到一次破壞，兩次和兩次以上的破壞情況可相同處理）。根據(jù)第2.2節(jié)剩余網(wǎng)絡(luò)的定義，結(jié)合破壞實(shí)際情況，構(gòu)造剩余網(wǎng)絡(luò)圖，如圖1所示。

圖1 剩余網(wǎng)絡(luò)圖

從圖1中可以看出該網(wǎng)絡(luò)在t＝5 h時(shí)刻，路徑（3，5）、（2，9）、（11，15）、（6，11）和網(wǎng)絡(luò)節(jié)點(diǎn)10遭到破壞。從構(gòu)造的剩余網(wǎng)絡(luò)圖1不難發(fā)現(xiàn)，網(wǎng)絡(luò)中新增了節(jié)點(diǎn)16、17，其中節(jié)點(diǎn)16表示當(dāng)物資1運(yùn)輸?shù)皆撐恢脮r(shí)，節(jié)點(diǎn)10遭到了破壞，因此該破壞并不影響物資1的運(yùn)輸，節(jié)點(diǎn)17表示當(dāng)物資2運(yùn)輸?shù)皆撐恢脮r(shí)，按計(jì)劃運(yùn)輸?shù)焦?jié)點(diǎn)11的路徑遭到破壞，但是從節(jié)點(diǎn)6到該位置的路徑并沒有受到影響。

針對(duì)構(gòu)造的剩余網(wǎng)絡(luò)圖1，可知在軍事物資調(diào)配網(wǎng)絡(luò)中新增了兩個(gè)源點(diǎn)節(jié)點(diǎn)16和節(jié)點(diǎn)17，也就是現(xiàn)在仿真的對(duì)象變?yōu)?個(gè)后勤倉庫向1個(gè)岸導(dǎo)團(tuán)配送軍事物資1和物資2。在不考慮軍事物資存在浪費(fèi)情況的前提下，以剩余網(wǎng)絡(luò)圖為仿真對(duì)象，經(jīng)Matlab仿真得到運(yùn)輸路徑及其相關(guān)參數(shù)，如圖2和表3所示。

圖2 運(yùn)輸網(wǎng)絡(luò)破壞后的運(yùn)輸路徑1

表4 運(yùn)輸網(wǎng)絡(luò)破壞后各物資運(yùn)輸路徑的相關(guān)參數(shù)

對(duì)比表2，可以看出物資1最優(yōu)運(yùn)輸路徑并沒有受到影響，但是其備用路徑發(fā)生了變化，由3→6→11→15和1→5→11→15改為3→9→12→15和2→7→13→15（因?yàn)槁窂剑?1，15）遭到破壞）；而物資2的運(yùn)輸路徑均發(fā)生了變化，最優(yōu)路徑變?yōu)?→7→13→15，備用路徑變?yōu)?→6→5→11→14→15和2→7→12→15。經(jīng)對(duì)比表2還可以看出，運(yùn)輸網(wǎng)絡(luò)遭到破壞后，物資1和物資2運(yùn)輸路徑的各項(xiàng)參數(shù)均沒有原來的優(yōu)越。以物資2最優(yōu)路徑為例，破壞之前其運(yùn)輸路徑3→6→11→15的運(yùn)輸距離、費(fèi)用和風(fēng)險(xiǎn)系數(shù)分別為563 km、4793元和0.048，運(yùn)輸網(wǎng)絡(luò)破壞之后，最優(yōu)路徑2→7→13→15的運(yùn)輸距離、費(fèi)用和風(fēng)險(xiǎn)系數(shù)分別為1 075 km、7 212元和0.108，各項(xiàng)參數(shù)均變大，符合客觀規(guī)律。

事實(shí)上，在軍事物資運(yùn)輸中，有時(shí)會(huì)考慮軍事物資的浪費(fèi)情況，因此為避免物資浪費(fèi)，在做仿真實(shí)驗(yàn)時(shí)重新以節(jié)點(diǎn)16和節(jié)點(diǎn)17作為運(yùn)輸源點(diǎn)，尋找其在剩余網(wǎng)絡(luò)中的最優(yōu)路徑。利用本文設(shè)計(jì)的算法編程，計(jì)算出在剩余網(wǎng)絡(luò)中的最優(yōu)運(yùn)輸路徑如圖3所示。

圖3 運(yùn)輸網(wǎng)絡(luò)破壞后的運(yùn)輸路徑2

從圖3中可以看出，物資1的最優(yōu)運(yùn)輸路徑?jīng)]有受到影響，物資2以節(jié)點(diǎn)17為起點(diǎn)，在剩余網(wǎng)絡(luò)中找到的最優(yōu)路徑為17→6→9→12→15。因此在整個(gè)運(yùn)輸過程中，物資1和物資2的最優(yōu)運(yùn)輸路徑分別為2→10→16→12→15和3→6→17→6→9→12→15，其運(yùn)輸路徑中的各項(xiàng)參數(shù)值如表5所示。

表5 運(yùn)輸網(wǎng)絡(luò)破壞后物資1、物資2運(yùn)輸路徑的各項(xiàng)參數(shù)

如果以軍事物資浪費(fèi)程度為重要依據(jù)，則在整個(gè)運(yùn)輸過程中，物資1沒有遭受到網(wǎng)絡(luò)破壞的影響，物資2的運(yùn)輸路徑相對(duì)靜態(tài)情形下的運(yùn)輸路徑發(fā)生了變化。從仿真結(jié)果可以看出，雖然在運(yùn)輸中避免了軍事物資的浪費(fèi)，但其運(yùn)輸路徑各項(xiàng)參數(shù)值相比表2和表3中的最優(yōu)運(yùn)輸路徑參數(shù)的結(jié)果要差，這充分說明多目標(biāo)車輛路徑優(yōu)化問題的絕對(duì)最優(yōu)解是不存在的，決策者根據(jù)不同的決策手段得到的結(jié)果往往不同。

4 結(jié) 論

本文以帶有時(shí)間窗的軍事物資配送問題為研究對(duì)象，基于多目標(biāo)優(yōu)化理論建立了動(dòng)態(tài)的軍事物資配送網(wǎng)絡(luò)模型，提出了一種改進(jìn)的NSGA-Ⅱ算法。在傳統(tǒng)NSGA-Ⅱ算法進(jìn)化中增加精英保留策略和小生境密度，通過仿真實(shí)驗(yàn)得出，算法在一定程度上克服了求解多目標(biāo)優(yōu)化過程易陷入局部最優(yōu)的問題。仿真實(shí)驗(yàn)表明，本文建立的模型合理、算法有效，能夠使決策者根據(jù)仿真實(shí)驗(yàn)中的各項(xiàng)參數(shù)值自行擇優(yōu)選擇運(yùn)輸方案，為指揮員提供有力的決策依據(jù)。

［1］Zhang Q.The scheduling modeling and practice of logistics distribution path optimization［M］.Chinese Material Press，2006.（張潛.物流配送路徑優(yōu)化調(diào)度建模與實(shí)務(wù)［M］.中國物資出版社，2006.）

［2］Miaou S P，Cnin S M.Computing k-shortest paths for nuclear spent fuel highway transportation［J］.European Journal of Operational Research，1991，53（1）：64- 80.

［3］Erkut E.The discrete p-dispersion problem［J］.European Journal of Operational Research，1990，46（1）：48- 60.

［4］Cook K L，Halsey E.The shortest route through a network with time-dependent internode transit times［J］.Journal of mathematical analysis and applications，1996，14（3）：493- 498.

［5］Chabini I.Discrete dynamic shortest path problem in transportation applications［J］.Transportation Research Record，1998，1645：170- 175.

［6］Davies C，Lingras P.Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks［J］.European Journal of Operational Research，2003，144（1）：27- 38.

［7］Narath B，Ali G Q，Eiichi T.The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem transportation［J］.Research Part E，2014，62：1- 22.

［8］Sandeep K，Diwakar P.Fuzzy programming approach to solve multi-objective transportation problem［J］.Advances in intelligent and Soft Computer，2012，130：525- 533.

［9］Tan G Z，Gao W.Shortest path algorithm in time-dependent networks［J］.Chinese Journal of Computers，2002，25（2）：165-172.（譚國真，高文.時(shí)間依賴的網(wǎng)絡(luò)中最小時(shí)間路徑算法［J］.計(jì)算機(jī)學(xué)報(bào)，2002，25（2）：165- 172.）

［10］Li N，Zou T，Sun D B.Particle swarm optimization for vehicle routing problem with time windows［J］.Systems Engineering-Theory&Practice，2004，24（4）：130- 135.（李寧，鄒彤，孫德寶.帶時(shí)間窗車輛路徑問題的粒子群算法［J］.系統(tǒng)工程理論與實(shí)踐，2004，24（4）：130- 135.）

［11］Sheng L J，Zhou X Z.Vehicle routing problem optimization with time windows［J］.Journal of Shanghai Maritime University，2007，28（4）：64- 67.（盛麗俊，周溪召.帶有時(shí)間窗的車輛路徑問題優(yōu)化［J］.上海海事大學(xué)學(xué)報(bào)，2007，28（4）：64- 67.）

［12］Wang L F，Song JS，Wang Z Y，et al.Vehicle routing optimization with time windows in battlefield resources distribution［J］.SystemsEngineering and Electronics，2013，35（4）：771- 776.（王連鋒，宋建社，王正元，等.帶硬時(shí)間窗的戰(zhàn)場物資配送車輛路徑優(yōu)化［J］.系統(tǒng)工程與電子技術(shù)，2013，35（4）：771- 776.）

［13］Zhao W F，Zhao W C，Han Q L，et al.Application of improved NSGA-Ⅱin the transportation problem about the supply of equipment［J］.Ordnance Industry Automation，2013，32（10）：33-36.（趙文飛，趙文昌，韓慶龍，等.改進(jìn)NSGA-Ⅱ算法在裝備保障運(yùn)輸問題中的應(yīng)用［J］.兵工自動(dòng)化，2013，32（10）：33- 36.）

［14］Zitzler E，Thiele L.Multiobjective evolutionary algorithms：a comparative case study and the strength pareto approach［J］.IEEE Trans.on Evolutionary Computer，1999，3（4）：257- 271.

趙文飛（198-6- ），男，講師，主要研究方向?yàn)橹悄芩惴ā⒔M合最優(yōu)化。

E-mail：zhaowenfei1986＠126.com

周 剛（197-5- ），男，副教授，主要研究方向?yàn)閿?shù)據(jù)挖掘、機(jī)器學(xué)習(xí)。

E-mail：Zhg_3019＠163.com

楊樹杰（197-0- ），男，副教授，博士，主要研究方向?yàn)槊}沖泛函微分方程穩(wěn)定性研究。

E-mail：yangshujie＠163.com

董 超（198-8- ），男，講師，主要研究方向?yàn)槟Ｊ阶R(shí)別、圖像處理。

E-mail：117097248＠qq.com

NSGA-Ⅱalgorithm for military resources distribution with time windows

ZHAO Wen-fei，ZHOU Gang，YANG Shu-jie，DONG Chao
（Department of Basic Sciences，Naval Aeronautical and Astronautical University，Yantai 264001，China）

Aiming at the transportation problem of military resources distribution with time windows，a dynamic network model of the vehicle routing problem including travel distance，cost and risk for targets is built，and an improved multi-objective genetic algorithm NSGA-Ⅱis proposed.The algorithm introduces residual network，puts forward numeric code，and adds the elitism strategy and niche density.The simulation results show that the algorithm can avoid the phenomenon of leading to local optimization in some degree and improve the efficiency of solving military resources distribution route，and an effective solution for the transportation problem about the supply of wartime equipment is provided.

military resources；time windows；multi-objective；NSGA-Ⅱ

O 224

A

10.3969／j.issn.1001-506X.2015.11.14

1001-506X（2015）11-2513-07

2014- 10- 27；

2015- 04- 15；網(wǎng)絡(luò)優(yōu)先出版日期：2015- 05- 04。

網(wǎng)絡(luò)優(yōu)先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20150504.1523.006.html

國家自然科學(xué)基金（61205206）；山東省自然科學(xué)基金（ZR2014AM006）資助課題