趙文飛,孫璽菁,司守奎,劉孝磊

(海軍航空大學(xué)航空基礎(chǔ)學(xué)院,山東 煙臺 264001)

0 引 言

近年來,隨著信息化程度的提高、武器裝備的不斷發(fā)展,現(xiàn)代高技術(shù)局部戰(zhàn)爭呈現(xiàn)海、陸、空、天、電等多維態(tài)勢,戰(zhàn)爭具有突發(fā)性強(qiáng)、節(jié)奏快、作戰(zhàn)半徑大、作戰(zhàn)物資消耗大等特點。因此,現(xiàn)代戰(zhàn)爭要求軍事物流系統(tǒng)必須做到快速反應(yīng)、保障充分,并且隨著戰(zhàn)場形勢的變化需要適時地調(diào)整軍事物資的保障方案。而軍事物資運(yùn)輸調(diào)度作為實現(xiàn)戰(zhàn)時后勤保障精確化的關(guān)鍵環(huán)節(jié),已成為現(xiàn)代信息化戰(zhàn)爭取勝的必要條件,所以構(gòu)建合理的軍事物資配送網(wǎng)絡(luò)模型及運(yùn)輸路徑的優(yōu)化問題一直以來是各國軍事物流研究的熱點[1-4]。

軍事物資運(yùn)輸問題往往是非線性多目標(biāo)規(guī)劃問題,屬于non-deterministic polynomial (NP)問題,目前用于求解該問題的主要方法有遺傳算法、蟻群算法、模擬退火等智能算法。例如文獻(xiàn)[5]等針對現(xiàn)代軍事物流中的車輛路徑問題(fuzzy vehicle routing problem,VRP),建立了戰(zhàn)時軍事物流多目標(biāo)VRP數(shù)學(xué)模型,該模型采用非支配排序遺傳(non-dminated srting gnetic agorithm-Ⅱ,NSGA-Ⅱ)算法求解;文獻(xiàn)[6]研究了車輛裝備保障運(yùn)輸網(wǎng)絡(luò),提出了基于蒙特卡羅仿真和遺傳算法的車輛裝備運(yùn)輸網(wǎng)絡(luò)化模型;文獻(xiàn)[7]針對物流配送車輛優(yōu)化調(diào)度問題,建立了多目標(biāo)的優(yōu)化模型,并設(shè)計了基于多目標(biāo)的蟻群算法進(jìn)行求解。而戰(zhàn)時軍事物資運(yùn)輸?shù)母黜梾?shù)往往具有模糊不確定性,從而許多學(xué)者研究了帶模糊參數(shù)的VRP[8-13]。文獻(xiàn)[8]研究了帶模糊時間窗的多目標(biāo)動態(tài)路徑優(yōu)化問題,并利用遺傳算法進(jìn)行求解;文獻(xiàn)[9]考慮了一類帶回路的模糊多目標(biāo)車輛路徑優(yōu)化問題,并提出了一種啟發(fā)式算法;文獻(xiàn)[10]針對車輛旅行時間、卸貨時間為模糊變量的車輛路徑問題,建立了基于可信性測度的模糊機(jī)會約束規(guī)劃模型;文獻(xiàn)[11]針對戰(zhàn)場軍事物資配送中帶硬時間窗VRP的模糊性,基于模糊可信性理論建立了多目標(biāo)模糊期望值模型,并提出了一種改進(jìn)的約束多目標(biāo)粒子群優(yōu)化算法;文獻(xiàn)[12] 分析了模糊模型和模糊方法,有效地解決了車輛容量約束條件下的運(yùn)輸和VRP問題。但在戰(zhàn)時軍事物資運(yùn)輸中,隨著戰(zhàn)場態(tài)勢的變換,運(yùn)輸路徑上具有模糊性的參數(shù)較多,例如運(yùn)輸時間、運(yùn)輸費(fèi)用和安全系數(shù)等參數(shù)實際上都是不確定的,具有一定的模糊性。針對這種具有特殊的多模糊約束優(yōu)化問題,本文建立了模糊約束的多目標(biāo)軍事物資運(yùn)輸模型,并利用改進(jìn)的多目標(biāo)量子遺傳算法對該模型進(jìn)行求解。

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

1.1 多目標(biāo)優(yōu)化問題

多目標(biāo)優(yōu)化問題[14](multiple objective problem,MOP)可以描述為這樣一個極小化優(yōu)化模型。

定義1MOP

Minf(x)={f1(x),f2(x),…,fm(x)}

s.t.hi(x)=0; ?i=1,2,…,p

gj(x)≤0; ?j=1,2,…,q

x=[x1,x2,…,xn]T∈X

式中,fi:Rn→R,?i=1,2,…,m為目標(biāo)函數(shù);約束條件hi,gj為定義在X上的函數(shù):Rn→R。

MOP在優(yōu)化過程中,一個可行解很難使所有的目標(biāo)函數(shù)達(dá)到全局最優(yōu),因此怎樣定義解集是求解MOP的關(guān)鍵。本文采用的解集是Pareto解,其定義如下。

定義2Pareto支配

對于任意的可行解x,y,如果fi(x)≤fi(y),?i=1,2,…,m,且?j∈{1,2,…,m},使得fj(x)

定義3Pareto解

對于給定的MOP,可行解x為MOP的Pareto解,當(dāng)且僅當(dāng)不存在其他可行解y,使得ypx。

所有Pareto最優(yōu)解的集合稱為Pareto最優(yōu)解集,Pareto最優(yōu)解集的像(目標(biāo)函數(shù)值)稱為Pareto最優(yōu)前沿。

1.2 帶模糊約束的多目標(biāo)軍事物資配送問題

帶模糊約束的多目標(biāo)軍事物資配送路徑優(yōu)化問題可以描述為由某一軍事物資配送中心v0向多個戰(zhàn)場配送物資的VRP,在滿足戰(zhàn)場需求、運(yùn)輸路徑的容量限制等約束情況下,求運(yùn)輸距離最短、費(fèi)用最小、安全性能高等多個目標(biāo)的優(yōu)化問題。一般可以用運(yùn)輸網(wǎng)絡(luò)G=(V,A,C)來表示,V表示網(wǎng)絡(luò)節(jié)點集，表示為

V={v0,v1,v2,…,vn,s1,s2,…,sm}

式中,v0表示網(wǎng)絡(luò)中的源點;S={s1,s2,…,sm}表示網(wǎng)絡(luò)中的匯點;{v1,v2,…,vn}為運(yùn)輸路徑上的節(jié)點。A={eij|eij=(vi,vj),其中vi,vj∈V}∈V×V,表示網(wǎng)路的弧集。C={cij|(vi,vj)∈A},cij表示弧eij上所能承受的最大容量。網(wǎng)絡(luò)G=(V,A,C)實際上表示的是一個一對多的運(yùn)輸保障網(wǎng)絡(luò)。

1.2.1 帶模糊時間窗的運(yùn)輸時間最短的模型

由于戰(zhàn)場上軍事物資配送問題的特殊性,每個戰(zhàn)場(匯點)sk(k=1,2,…,m)往往要求在某一個特定的時間窗[ek,lk]被服務(wù),否則將延誤戰(zhàn)機(jī)。這里我們將每一個戰(zhàn)場被服務(wù)時間窗口視為一個模糊數(shù),模糊數(shù)是定義在實數(shù)域上的正規(guī)凸模糊集,最常用的模糊數(shù)為三角模糊數(shù)和梯形模糊數(shù),這兩種形式都是根據(jù)其隸屬函數(shù)的幾何形狀命名的,如圖1所示。

圖1 三角模糊數(shù)和梯形模糊數(shù)隸屬函數(shù)圖Fig.1 Triangular fuzzy number and trapezoid fuzzy number membership function diagram

式中,目標(biāo)函數(shù)越大,說明整個戰(zhàn)場軍事物資保障越及時,約束條件反映了每個戰(zhàn)場必須在固定的時間窗口內(nèi)接收到物資。

事實上,還可以根據(jù)戰(zhàn)時每一個戰(zhàn)場的戰(zhàn)略地位不同,對每一個戰(zhàn)場分配一個權(quán)值λk,這樣優(yōu)化模型更改為

1.2.2 帶模糊約束的運(yùn)輸費(fèi)用最小模型

在經(jīng)典的運(yùn)輸問題中費(fèi)用最小的優(yōu)化模型為

但這只適用于靜態(tài)的運(yùn)輸網(wǎng)絡(luò),戰(zhàn)時由于網(wǎng)絡(luò)路徑隨時都有可能遭到敵方不同程度的破壞,在運(yùn)輸過程中受多種不確定因素的影響,而僅用一個確定的數(shù)額來刻畫每一條弧上的單位運(yùn)輸費(fèi)用不符合實際。為此,這里將單位運(yùn)輸費(fèi)用wij視為一個三角模糊數(shù)。基于該假設(shè)可得運(yùn)輸物資費(fèi)用最小模型為

1.2.3 帶模糊約束的風(fēng)險最小模型

在運(yùn)輸網(wǎng)絡(luò)中,弧eij受攻擊的概率(不安全系數(shù))為qij(0≤qij≤1),則路徑P的風(fēng)險值為

因此風(fēng)險最小的目標(biāo)函數(shù)為

1.2.4 模型建立

基于以上假設(shè)和分析,建立帶模糊約束的多目標(biāo)軍事物資運(yùn)輸路徑優(yōu)化模型為

(1)

(2)

(3)

(5)

(6)

(7)

0≤fij≤cij,?(vi,vj)∈A

(8)

(9)

(10)

(11)

其中,式(1)～式(3)是目標(biāo)函數(shù)；式(4)為運(yùn)輸過程中可行路徑的約束條件;式(5)為可行流的約束條件;式(6)為時間約束,要求可行路徑總的運(yùn)輸時間必須在指定的時間區(qū)間[ek,lk]; 式(7)和式(8)表示流量需滿足戰(zhàn)場的物資需求和運(yùn)輸?shù)缆返娜萘肯拗? 式(9)～式(11)為模糊數(shù)和參數(shù)的設(shè)置要求。

1.3 模型求解

求解第1.2.3節(jié)建立的帶模糊約束的多目標(biāo)軍事物資運(yùn)輸路徑優(yōu)化模型,重點是怎么將帶模糊約束的模型轉(zhuǎn)化為確定性模型。文獻(xiàn)[15-16]分別利用模糊運(yùn)算和效用函數(shù)將模糊約束轉(zhuǎn)化為清晰的等價類來進(jìn)行處理;文獻(xiàn)[17]利用隸屬函數(shù),給出了三角模糊數(shù)取值區(qū)間的期望值和取值的期望值。本文受Jiménez的啟發(fā),將帶模糊約束的模型轉(zhuǎn)化為確定性模型來求解。

從而運(yùn)輸費(fèi)用最小模型可調(diào)整為

同理,風(fēng)險最小模型可修改為

綜上所述,帶模糊約束的多目標(biāo)軍事物資配送問題可轉(zhuǎn)化為

(12)

(13)

(14)

其中約束條件依然為式(4)～式(11)。

2 算法設(shè)計

通過第1節(jié)的處理,本文將帶模糊約束的多目標(biāo)物資運(yùn)輸問題轉(zhuǎn)化為一個帶不等式的確定性約束的多目標(biāo)規(guī)劃問題。針對這個優(yōu)化問題,將對傳統(tǒng)的量子遺傳算法(quantum genetic algorithm,QGA)進(jìn)行改進(jìn)來求解。事實上,目前很多學(xué)者利用QGA 來求解物資運(yùn)輸路徑優(yōu)化問題[18-19]。QGA利用量子計算中的量子比特和量子態(tài)疊加等概念和理論[20],將染色體的編碼用量子比特的概率幅來表示,使得一個量子比特染色體可以同時表示多個狀態(tài),能以較小的種群表示較多的可行解。然后依據(jù)當(dāng)前最優(yōu)染色體的個體信息,利用量子旋轉(zhuǎn)門對染色體進(jìn)行有效的更新,而不是采用傳統(tǒng)的交叉和變異的操作。本文對傳統(tǒng)的QGA算法進(jìn)行改進(jìn),在算法中引入非支配排序和小生境密度,對種群中的個體進(jìn)行前沿非劣分級,并采用精英保留策略,使得較優(yōu)的個體能夠保存下來,這樣能夠有效地提高算法的尋優(yōu)效率。

2.1 量子位

在經(jīng)典計算中,采用0和1二進(jìn)制表示信息,通常稱其為比特。在量子計算中,采用|0〉和|1〉表示微觀粒子的兩種基本狀態(tài),稱其為量子比特。經(jīng)典比特與量子比特之間的區(qū)別在于,量子比特的狀態(tài)除了|0〉和|1〉,還可以是其線性組合,通常稱為疊加態(tài),即

|φ〉=α|0〉+β|1〉

式中,α和β是一對復(fù)常數(shù),稱為量子態(tài)的概率幅,滿足|α|2+|β|2=1。

一個量子比特可同時包含0和1的信息,則m個量子比特可以表示2m個不同的狀態(tài)。含m個量子比特的個體j可表示為

式中,|αi|2+|βi|2=1;?i=1,2,…,m。

2.2 量子比特編碼與解碼

式中,L為染色體的基因位數(shù);n為每個基因的量子比特數(shù)。

實際上在解碼中是將量子的不確定性轉(zhuǎn)化為一個確定個體的過程,其表示方式為二進(jìn)制編碼,需進(jìn)一步將其轉(zhuǎn)化成十進(jìn)制數(shù),這樣染色體的每個基因就對應(yīng)成一個自然數(shù),而每個自然數(shù)就對應(yīng)于網(wǎng)絡(luò)中的一個節(jié)點。例如|011〉轉(zhuǎn)化為十進(jìn)制數(shù)就是3,它代表網(wǎng)絡(luò)中節(jié)點3。染色體的每個基因都這樣處理后,整個染色體就表示成自然數(shù)編碼,其中自然數(shù)的順序就是運(yùn)輸網(wǎng)絡(luò)路徑中節(jié)點的順序。

在解碼的過程中,有可能會出現(xiàn)非法解的情況,主要有兩種:編碼的重復(fù)和越界。因此,在解碼的過程中需要適當(dāng)?shù)男拚?對于重復(fù)的編碼,直接去掉,例如染色體對應(yīng)的路徑P=[012325],重復(fù)路徑為232,直接去掉修正后為P=[0125];對于越界的編碼,則在依概率選取量子態(tài)時去掉越界的量子態(tài)即可。如果經(jīng)過修正后得到的解不滿足約束條件則直接去掉。

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

通過第2.2節(jié)得到的每一個可行解都有3個評價指標(biāo):戰(zhàn)場的滿意度、運(yùn)輸費(fèi)用和安全性,為此本文采用非支配排序和小生境密度來評判解的優(yōu)劣程度。

對于每一個可行解X都設(shè)有兩個參數(shù)Xrank和Xid,其中Xrank為非支配排序,將解分為0,1,…,n個等級,同一個等級非支配序相等,取值越低的解越優(yōu)秀,例如Xrank

式中,V(X)表示個體X中的所有節(jié)點的集合;A(X)為個體X中的所有弧的集合;||表示集合的勢。不難看出,Xid越高的解,反映在運(yùn)輸路徑上表示該路徑與同等解集F中其他路徑相似程度較高,即該運(yùn)輸路徑上比較擁擠,反之則比較稀疏。

2.4 旋轉(zhuǎn)門的更新

旋轉(zhuǎn)門的更新是量子進(jìn)化算法的關(guān)鍵。本文設(shè)計的量子旋轉(zhuǎn)門為

從而旋轉(zhuǎn)角度為

(15)

2.5 精英保留策略

種群中的個體可以根據(jù)適應(yīng)度函數(shù)值的優(yōu)劣來進(jìn)行排序,為了使每一代優(yōu)秀的個體能夠繼續(xù)保留下來,在迭代時將父代中較為優(yōu)秀的個體保留下來直接進(jìn)入子代。具體操作為:

在第t代父代種群Q(t)中,計算每個個體的適應(yīng)度函數(shù)并進(jìn)行優(yōu)劣排序,然后根據(jù)種群規(guī)模確定一定數(shù)量的優(yōu)秀個體用集合Γ(t)表示,再在Q(t)中隨機(jī)選取個體進(jìn)行量子變異產(chǎn)生子代種群P(t),其中量子變異以量子旋轉(zhuǎn)門更新的方式進(jìn)行。最后通過計算集合Z(t)=P(t)∪Γ(t)中個體的適應(yīng)度函數(shù)進(jìn)行排序,選取滿足種群個數(shù)的最優(yōu)個體作為第t+1代父代種群Q(t+1)。

2.6 算法流程

通過前面的討論和分析,設(shè)計本文算法的主要流程如下:

步驟2按照第2.3節(jié)的方法,計算種群Q(t)中每個個體的適應(yīng)度函數(shù)并進(jìn)行排序,選取適應(yīng)度函數(shù)較優(yōu)的個體記為Γ(t)。

步驟3對種群Q(t)中的每個個體按照第2.4節(jié)的方式進(jìn)行量子變異得到種群P(t)。

步驟4令Z(t)=Γ(t)∪P(t);計算Z(t)中每個個體的適應(yīng)度函數(shù)并排序,選取前N個個體作為新一代種群Q(t+1)。

步驟5若t

3 實例分析

因本文所研究問題背景的特殊性,目前沒有統(tǒng)一的測試案例,為此選取文獻(xiàn)[22]中案例的運(yùn)輸網(wǎng)絡(luò)來進(jìn)行仿真實驗分析。將案例中運(yùn)輸網(wǎng)絡(luò)的節(jié)點1設(shè)為源點,即配送中心,網(wǎng)絡(luò)中節(jié)點13,14,15設(shè)為匯點,即模擬為戰(zhàn)時的3個戰(zhàn)場。由于本文研究的是帶模糊約束的多目標(biāo)路徑優(yōu)化問題,因此在仿真時,需對運(yùn)輸網(wǎng)絡(luò)中給定的參數(shù)進(jìn)行修正,將運(yùn)輸時間參數(shù)ti調(diào)整為三角模糊數(shù)(tij-0.1 rand,tij,tij+0.1 rand);運(yùn)輸費(fèi)用參數(shù)wij改為三角模糊數(shù)(wij-10 rand,wij,wij+10 rand);風(fēng)險系數(shù)qij改為(qij-0.01 rand,qij,qij+0.01 rand)。然后采用第1.3節(jié)的處理方法,處理之后的數(shù)據(jù)如表1所示。3個匯點的模糊時間窗口參數(shù)如表2所示。

表1 軍事物資配送網(wǎng)絡(luò)G中各項權(quán)值參數(shù)Table 1 Weight parameters G of military material distribution network

表2 模糊時間窗口參數(shù)明細(xì)Table 2 Parameters of fuzzy time window

根據(jù)前面建立的數(shù)學(xué)模型和設(shè)計的算法,將運(yùn)輸時間、運(yùn)輸費(fèi)用和安全性作為單目標(biāo)進(jìn)行優(yōu)化,分別尋找5條較優(yōu)的路徑作為初始種群,利用改進(jìn)的QGA算法,用Matlab軟件編程仿真,迭代100次,得到節(jié)點1到節(jié)點13,14,15運(yùn)輸最優(yōu)的路徑如圖2所示。

圖2 最優(yōu)運(yùn)輸路徑Fig.2 Optimal transportation route

從圖2中可以看出節(jié)點1到節(jié)點13,14,15的最優(yōu)運(yùn)輸路徑分別為1→3→9→13,1→4→7→14和1→2→5→10→15,其中各運(yùn)輸路徑的相關(guān)參數(shù)如表3所示。事實上因為每一個匯點都帶有模糊時間窗口的限制,所以運(yùn)輸路徑的各項參數(shù)不一定是最優(yōu)的。若不考慮模糊時間窗口的約束條件,只考慮運(yùn)輸時間少、費(fèi)用低和風(fēng)險系數(shù)低的優(yōu)化問題,則最優(yōu)的運(yùn)輸路徑方案及相關(guān)參數(shù)如表4所示。

表3 帶模糊時間窗口的最優(yōu)運(yùn)輸路徑及相關(guān)參數(shù)Table 3 Optimal transportation path and related parameters with fuzzy time windows

表4 不帶模糊時間窗口的最優(yōu)運(yùn)輸路徑及相關(guān)參數(shù)Table 4 Optimal transportation path and related parameters without fuzzy time windows

對比表3和表4不難發(fā)現(xiàn),若不考慮匯點帶模糊時間窗口的約束條件,節(jié)點13的最優(yōu)運(yùn)輸路徑方案不受影響,而表4中節(jié)點14和節(jié)點15的最優(yōu)運(yùn)輸路徑為1→4→6→14和1→2→8→11→15,其實驗參數(shù)明顯比表3中節(jié)點14和節(jié)點15的最優(yōu)運(yùn)輸路徑1→4→7→14和1→2→5→10→15要好,但是正因為運(yùn)輸時間少導(dǎo)致不滿足節(jié)點14和15的時間窗口約束,從而在算法中把這樣的路徑排除。

此外,將本文提出的改進(jìn)的QGA與傳統(tǒng)的GA進(jìn)行對比,雖然都能夠得到最優(yōu)的運(yùn)輸路徑,但本文提出算法的收斂性效果較好,如圖3所示。

圖3 適應(yīng)度值比較Fig.3 Fitness comparison

4 結(jié)束語

本文針對戰(zhàn)場上帶模糊時間窗口、模糊運(yùn)輸費(fèi)用以及模糊運(yùn)輸風(fēng)險問題,建立了帶模糊約束問題的多目標(biāo)運(yùn)輸路徑優(yōu)化模型,并利用改進(jìn)的QGA對其進(jìn)行求解。雖然多目標(biāo)運(yùn)輸路徑優(yōu)化問題很難找到絕對最優(yōu)的運(yùn)輸方案,但仿真結(jié)果表明,將改進(jìn)QGA算法用于求解該問題,決策者能夠有效地獲得最優(yōu)的運(yùn)輸方案以及最優(yōu)的備用運(yùn)輸路徑,根據(jù)仿真結(jié)果中的各項參數(shù)值自行擇優(yōu)選擇運(yùn)輸方案。本文提出的建模方法和算法能夠有效的解決帶模糊約束的運(yùn)輸路徑優(yōu)化問題。