不確定條件下后裝協(xié)同保障鏈優(yōu)化調(diào)度

曾 斌, 張泉先, 李厚樸

(1. 海軍工程大學(xué)管理工程與裝備經(jīng)濟(jì)系, 湖北 武漢 430033;2. 海軍工程大學(xué)導(dǎo)航工程系, 湖北 武漢 430033)

0 引 言

后裝保障鏈對于軍隊(duì)后勤和裝備保障具有十分重要的作用,它可以看作是從后方保障基地到前線作戰(zhàn)部隊(duì)的一條需求供應(yīng)鏈或網(wǎng)絡(luò),主要功能是存儲(chǔ)、運(yùn)輸、中轉(zhuǎn)和分配作戰(zhàn)物資,協(xié)調(diào)保障行動(dòng)。它與商業(yè)供應(yīng)鏈存在相似之處,但由于目的要求不同導(dǎo)致二者又有很多不同[1-2],保障鏈相比商業(yè)供應(yīng)鏈的特點(diǎn)體現(xiàn)在:① 敏捷性要求更高;② 供應(yīng)鏈更復(fù)雜;③ 資源類型更加多樣;④ 環(huán)境動(dòng)態(tài)變化;⑤ 對可靠性和維修性要求更高。其中④和⑤與不確定性直接相關(guān)。

近年來后裝保障供應(yīng)鏈已成為軍事理論研究的熱點(diǎn)問題,也取得了不少成果。文獻(xiàn)[3-4]分別利用時(shí)空網(wǎng)絡(luò)和復(fù)雜網(wǎng)絡(luò)技術(shù)描述了保障網(wǎng)絡(luò),但以保障中斷恢復(fù)為研究背景,不確定影響考慮較小。文獻(xiàn)[5]研究了軍事供應(yīng)鏈中武器裝備備件的保障生產(chǎn)問題。文獻(xiàn)[6]研究了軍事供應(yīng)鏈的風(fēng)險(xiǎn)管理問題。文獻(xiàn)[7]通過價(jià)值流圖減小多級軍事供應(yīng)鏈的備件提前期。它們都指出了后裝保障屬于多保障點(diǎn)、多需求點(diǎn)以及多梯隊(duì)的復(fù)雜供應(yīng)鏈,具有較大的失效風(fēng)險(xiǎn)。

文獻(xiàn)[8]利用粒子群算法解決兩層軍事供應(yīng)鏈問題,文獻(xiàn)[9]為一個(gè)3層軍事供應(yīng)鏈提供決策支持,文獻(xiàn)[10-11]分別提出了戰(zhàn)時(shí)陸地和海上的集中式后勤保障規(guī)劃模型并用遺傳算法進(jìn)行求解。它們都指出了軍事供應(yīng)鏈的優(yōu)化計(jì)算復(fù)雜度較高,但都采取了戰(zhàn)時(shí)統(tǒng)一指揮下的集中式規(guī)劃模型。

在研究供應(yīng)鏈的不確定性方面,文獻(xiàn)[12]用區(qū)間數(shù)度量裝備供應(yīng)網(wǎng)的不確定性,采用基于禁忌搜索的兩階段進(jìn)行求解,給本文以較大啟發(fā),但優(yōu)化模型中沒有考慮庫存水平和運(yùn)輸方式,求解算法性能不夠,另外區(qū)間分析在進(jìn)行復(fù)雜運(yùn)算時(shí)易產(chǎn)生區(qū)間擴(kuò)張,產(chǎn)生較大誤差。文獻(xiàn)[13-15]采用魯棒規(guī)劃解決不同類型供應(yīng)鏈的不確定性問題。文獻(xiàn)[16-17]采用模糊控制解決備件多級供應(yīng)的不確定性問題,雖然與本文采用的模糊規(guī)劃在模型建立和應(yīng)用目的上有較大不同,但表明了模糊優(yōu)化在處理保障供應(yīng)不確定性問題方面的優(yōu)勢。文獻(xiàn)[18-19]主要研究了災(zāi)害救援供應(yīng)鏈的設(shè)計(jì),利用歷史統(tǒng)計(jì)數(shù)據(jù)來支持不確定性規(guī)劃問題。

本文主要貢獻(xiàn)如下:① 無論是應(yīng)急保障還是作戰(zhàn)保障,現(xiàn)有研究大多假設(shè)有一個(gè)集中管理部門,由其統(tǒng)一協(xié)調(diào)與控制,這對于持續(xù)時(shí)間較短的小規(guī)模行動(dòng)是有效的,但是對于大規(guī)模且需要長期對抗的軍事活動(dòng),例如爭奪海上資源的分布式海戰(zhàn)場以及海上預(yù)置基地的設(shè)置[20],需要多部門協(xié)調(diào)和征用民用設(shè)施和資源,為此本文提出了一個(gè)基于信息共享的協(xié)同保障算法,解決后方保障基地和前進(jìn)基地之間的資源協(xié)調(diào)問題。② 盡管近年來關(guān)于不確定情況下的供應(yīng)鏈研究越來越受到重視,但是它們主要采用統(tǒng)計(jì)或魯棒規(guī)劃方法來處理不確定性,這需要有大量的客觀歷史數(shù)據(jù)來做支撐,從中預(yù)估出數(shù)據(jù)的離散或連續(xù)概率分布情況,而且只有在系統(tǒng)行為能夠多次重復(fù)時(shí),統(tǒng)計(jì)規(guī)劃的結(jié)果才具有實(shí)踐意義。但是對于作戰(zhàn)保障而言,一方面缺乏足夠多的實(shí)際戰(zhàn)場數(shù)據(jù)來估計(jì)模型中不確定性參數(shù),另一方面由于敵方武器性能和兵力參數(shù)的可信度難以驗(yàn)證,導(dǎo)致兵棋演練或作戰(zhàn)仿真得到的數(shù)據(jù)也缺乏權(quán)威性。因此,本文采用模糊規(guī)劃來處理后裝保障的不確定性參數(shù),綜合保障指揮員的經(jīng)驗(yàn)及小樣本來建立不確定參數(shù)的模糊數(shù)。③ 供應(yīng)鏈優(yōu)化往往包括多個(gè)相互沖突的目標(biāo),現(xiàn)有研究一般以線性加權(quán)法來處理,但是在戰(zhàn)時(shí)后裝保障場景下,優(yōu)化項(xiàng)較多而且缺乏先驗(yàn)知識來估算各個(gè)目標(biāo)權(quán)重值,為此利用加權(quán)增強(qiáng)約束法來估算多目標(biāo)Pareto解,輔助決策后裝指揮人員選擇合適的解決方案。④ 與傳統(tǒng)的應(yīng)急保障和后勤保障研究相比,本文研究對象更為復(fù)雜,屬于多規(guī)劃周期、多物質(zhì)類型、多需求點(diǎn)、多保障梯隊(duì)的供應(yīng)鏈優(yōu)化問題,而且在決策變量中增加了后裝指揮需要的重要指標(biāo)-庫存水平,這些問題在提高模型實(shí)用性的同時(shí)也使得解算過程更為復(fù)雜,為了提高計(jì)算精度和效率,提出了一個(gè)嵌入自適應(yīng)大規(guī)模鄰域搜索的Memetic算法。

1 規(guī)劃模型

本文模型屬于無限時(shí)域規(guī)劃,為了書寫簡便,在參數(shù)和決策變量的定義中省略了系統(tǒng)時(shí)間描述,模型分為以下兩個(gè)部分。

1.1 前進(jìn)基地模型

1.1.1 對象/集合的定義

B:保障基地集合,保障基地b∈B;

Q:候補(bǔ)前進(jìn)基地集合,前進(jìn)基地q∈Q;

R:保障需求點(diǎn)集合,r∈R;

K:保障物質(zhì)類型集合,k∈K;

V:運(yùn)輸方式(工具類型)集合,v∈V。

1.1.2 參數(shù)的定義

hkq:在前進(jìn)基地q每存儲(chǔ)單位數(shù)量的k物質(zhì)所需要花費(fèi)的維護(hù)開銷;

Mv:基地?fù)碛羞\(yùn)輸工具v的最大可用數(shù)量;

Cv:運(yùn)輸工具v的最大運(yùn)輸容量;

av:運(yùn)輸工具v的護(hù)航開銷;

ck:每單位物質(zhì)k占用的存儲(chǔ)空間;

Oq:前進(jìn)基地q的最大庫存容量;

1.1.3 決策變量的定義

xbqkv:以工具v作為運(yùn)輸方式,從保障基地b運(yùn)送到前進(jìn)基地q的物質(zhì)k的數(shù)量(決策者是前進(jìn)基地);

yqrkv:以工具v作為運(yùn)輸方式,從前進(jìn)基地q運(yùn)送到保障需求點(diǎn)r的物質(zhì)k的數(shù)量;

zl:布爾變量,為1表示在l點(diǎn)部署前進(jìn)基地,否則為0;

dkq:前進(jìn)基地q存儲(chǔ)的物質(zhì)k的庫存水平;

ukr:需求點(diǎn)r申請物質(zhì)k,但沒有得到滿足的數(shù)量;

Tbqv:從保障基地b到前進(jìn)基地q之間的運(yùn)輸工具v的數(shù)量;

1.1.4 前進(jìn)基地規(guī)劃模型的設(shè)計(jì)

目標(biāo)函數(shù)如下:

(1)

目標(biāo)函數(shù)包含5項(xiàng),第1項(xiàng)為從保障基地到前進(jìn)基地的運(yùn)輸開銷(與距離有關(guān)),第2項(xiàng)為從前進(jìn)基地到保障需求點(diǎn)的運(yùn)輸開銷,第3項(xiàng)為前進(jìn)基地的庫存維護(hù)開銷,第4項(xiàng)為缺貨開銷,第5項(xiàng)為護(hù)航開銷(與物質(zhì)量或運(yùn)輸工具數(shù)量有關(guān)),這里開銷并非金額,而是懲罰單位。約束條件如下:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

Tbqv≤Mv

(9)

(10)

式(2)表示前進(jìn)基地收到的物質(zhì)不大于保障基地發(fā)送的物質(zhì)量;式(3)表示前進(jìn)基地的庫存約束,即對某一種物質(zhì),本供貨周期中前進(jìn)基地進(jìn)貨數(shù)量加上上一周期的庫存量減去發(fā)貨量,等于現(xiàn)在的庫存量。式(4)表示保障需求點(diǎn)申請的物質(zhì)量減去沒有滿足的物質(zhì)量等于它實(shí)際接收到的物質(zhì)量;式(5)表示前進(jìn)基地庫存總量約束;式(6)表示從保障基地到前進(jìn)基地的運(yùn)輸總量約束;式(7)表示從前進(jìn)基地到保障需求點(diǎn)的運(yùn)輸總量約束;式(8)表示流量約束,M為一個(gè)極大數(shù),表示只有該候選地址部署了前進(jìn)基地才能接收物質(zhì);式(9)和式(10)表示運(yùn)輸工具數(shù)量的限制。

1.2 保障基地模型

模型參數(shù)定義如下:

pkb：保障基地b采辦單位物質(zhì)k的開銷;

ck：每單位物質(zhì)k占用的存儲(chǔ)空間;

Skb：保障基地b被申請發(fā)送的物質(zhì)k數(shù)量(該信息從前進(jìn)基地q獲取)；

決策變量定義如下:

目標(biāo)函數(shù)如下:

(11)

式中，目標(biāo)函數(shù)包括3項(xiàng),第1項(xiàng)為總采辦開銷(戰(zhàn)時(shí)可省略),第2項(xiàng)為庫存開銷,第3項(xiàng)為保障基地的缺貨懲罰。約束條件如下:

(12)

(13)

(14)

(15)

式(12)表示保障基地的庫存約束,即對某一種物質(zhì),本供貨周期中保障基地采辦數(shù)量加上上一周期的庫存量減去發(fā)貨量,等于現(xiàn)在的庫存量。式(13)表示保障基地發(fā)往前進(jìn)基地的物質(zhì)量等于前進(jìn)基地申請量減去保障基地的缺貨量。式(14)表示保障基地的庫存總量限制。

2 分布式協(xié)同算法

如果戰(zhàn)場局勢需要采取處于長期遏制態(tài)勢,前進(jìn)基地作為預(yù)置儲(chǔ)備節(jié)點(diǎn)為分布式殺傷作戰(zhàn)節(jié)點(diǎn)服務(wù)[21],后方保障基地可能會(huì)租用民用物流公司,這時(shí)要更多的從經(jīng)濟(jì)利益和市場活動(dòng)出發(fā),后方保障基地關(guān)心的是采辦開銷,前進(jìn)基地關(guān)心的是庫存和運(yùn)輸開銷,二者之間需要建立一個(gè)基于信息共享的采辦—分發(fā)協(xié)同機(jī)制來提高后裝保障效率。前進(jìn)基地和后方保障基地的協(xié)同算法設(shè)計(jì)如下。

步驟 2前進(jìn)基地計(jì)算前進(jìn)基地規(guī)劃模型,見目標(biāo)函數(shù)式(1)和約束條件式(2)～式(10),得到后裝物質(zhì)的分發(fā)方案,其中xbqkv表示后方保障基地至前進(jìn)基地的物質(zhì)種類及數(shù)量,匯總后作為Skb共享至保障基地模型。

(16)

3 模糊規(guī)劃的轉(zhuǎn)化

根據(jù)作戰(zhàn)區(qū)域激烈程度和任務(wù)的不同,保障需求的類型和數(shù)量具有較大的不確定性,因此前進(jìn)基地模型中的物質(zhì)申請量是一個(gè)不確定參數(shù)。從保障基地到前進(jìn)基地以及從前進(jìn)基地到需求點(diǎn)的運(yùn)輸開銷會(huì)隨著作戰(zhàn)區(qū)域和路線的變化而變化,也屬于不確定參數(shù),由于物質(zhì)短缺導(dǎo)致的懲罰系數(shù)也與作戰(zhàn)任務(wù)和優(yōu)先級相關(guān),屬于不確定參數(shù)。

本文利用了模糊規(guī)劃方法處理優(yōu)化問題中的不確定性。由于本文中參數(shù)不確定性較大,所以采用了梯形分布作為隸屬度函數(shù)。另外模糊規(guī)劃中使用兩種測度來測量置信水平度[22],一種是基于樂觀的可能性測度,還有一種是基于悲觀的必然性測度,在戰(zhàn)場環(huán)境下物質(zhì)供應(yīng)比較緊張,本文采用謹(jǐn)慎態(tài)度來處理物質(zhì)保障問題,所以通過必然性測度來保證機(jī)會(huì)約束的滿意度。下面為本文緊湊形式規(guī)劃模型對應(yīng)的模糊規(guī)劃模型,目標(biāo)函數(shù)如下所示:

(17)

約束條件如下:

(18)

Gx≤Hy

(19)

(20)

x,y為正整數(shù)向量

(21)

圖1 梯形隸屬度函數(shù)

區(qū)間EI和期望值Ev可按下式計(jì)算:

(22)

(23)

(24)

從式(24)可推導(dǎo)得:

(25)

從式(25)可以把緊湊形式模糊規(guī)劃模型轉(zhuǎn)換成對應(yīng)的清晰式,其目標(biāo)函數(shù)描述如下:

(26)

約束條件為

Cx≤(Iβ-β)D(2)+βD(1)

(27)

Gx≤Hy

(28)

(29)

(30)

x,y為正整數(shù)向量

(31)

式中，Iβ為全1矢量，維數(shù)與β相同;Iv為全1矢量，維數(shù)與v相同。因此,基于上述緊湊形式的清晰式規(guī)劃模型,將含有不確定參數(shù)的保障基地模型和前進(jìn)基地模型分別等價(jià)變換為清晰式,下面只描述清晰化改造后的目標(biāo)函數(shù)和原來包括不確定參數(shù)的約束關(guān)系,原來只有確定參數(shù)的約束條件保持不變,帶下標(biāo)(1)～(4)的參數(shù)為對應(yīng)的可調(diào)節(jié)梯形隸屬度函數(shù)參數(shù),前進(jìn)基地清晰等價(jià)模型的目標(biāo)函數(shù)如下:

minZ1=

(32)

原包含不確定參數(shù)的約束條件式(4)改造為以下兩個(gè)不等式,其他約束條件不變。

(33)

(34)

保障基地清晰等價(jià)模型的目標(biāo)函數(shù)如下:

(35)

原包含不確定參數(shù)的約束條件(15)改造為以下不等式,其他約束條件不變。

(36)

4 求解算法

保障基地和前進(jìn)基地的優(yōu)化可以看作是一個(gè)多目標(biāo)規(guī)劃問題。

4.1 多目標(biāo)轉(zhuǎn)換單目標(biāo)

根據(jù)決策者的參與階段,多目標(biāo)轉(zhuǎn)換方法可以歸納為以下3種:① 先驗(yàn)方法，最常用的加權(quán)和[23]就屬于這種方法,它要求決策者在問題求解之前事先確定目標(biāo)的權(quán)重;② 交互法，在求解過程中需要決策者參與問題的搜索過程[24],要求決策者對計(jì)算過程較為了解;③ 后驗(yàn)方法，生成一批有效解,由用戶從中選出最適合的Pareto解[25]。后驗(yàn)方法雖然增加了時(shí)間復(fù)雜度,但能夠在減少用戶事先干預(yù)的情況下提高Pareto解的質(zhì)量,鑒于后裝保障問題的兩個(gè)規(guī)劃問題涉及優(yōu)化項(xiàng)較多,且難以事先給定權(quán)重的具體值,所以本文采用了后驗(yàn)方法中ε-約束法的改進(jìn)版本“加權(quán)增強(qiáng)ε-約束法”[26],目標(biāo)函數(shù)轉(zhuǎn)換為如下形式:

(37)

式中,θ1和θ2為可調(diào)節(jié)優(yōu)先級參數(shù)，θ1+θ2=1;range1和range1分別表示前進(jìn)基地和保障基地目標(biāo)函數(shù)的取值范圍;sl2為保障基地目標(biāo)的松弛度,根據(jù)ε-約束法建議,δ值任取10-3和10-4之間的一個(gè)極小數(shù)。由于前進(jìn)基地的保障效果直接關(guān)系到戰(zhàn)場態(tài)勢,所以取前進(jìn)基地目標(biāo)為主目標(biāo),保障基地目標(biāo)移入約束條件。

原有保障基地目標(biāo)函數(shù)改造為如下所示的懲罰約束,將其加入原有約束條件中:

Z2+sl2=ε2

(38)

式中,ε2不是一個(gè)數(shù),而是一批數(shù),可以看作一個(gè)矢量,所以規(guī)劃模型也根據(jù)ε2的數(shù)量將轉(zhuǎn)換為多個(gè)。本文單目標(biāo)轉(zhuǎn)化算法步驟具體如下。

步驟 2按下式分別計(jì)算前進(jìn)基地和保障基地目標(biāo)函數(shù)的取值范圍:

(39)

步驟 3設(shè)置中間網(wǎng)格點(diǎn)數(shù)量g2,計(jì)算ε2矢量值為

(40)

這樣原模型轉(zhuǎn)換為g2+1個(gè)規(guī)劃模型,每一個(gè)ε2對應(yīng)的模型得到一個(gè)折中解。

4.2 基于Memetic算法的求解過程

盡管經(jīng)過模糊規(guī)劃和加權(quán)增強(qiáng)ε-約束法對原模型進(jìn)行了清晰化和單目標(biāo)轉(zhuǎn)換,但轉(zhuǎn)換后模型還是屬于NP難的混合整數(shù)線性規(guī)劃模型,現(xiàn)有數(shù)學(xué)方法難以計(jì)算其精確解,所以本文借鑒了Memetic算法框架[28],在利用遺傳算法的全局搜索能力的同時(shí),還嵌入了自適應(yīng)大鄰域搜索算法的局部搜索優(yōu)勢,在確保求解精度的前提下提高了計(jì)算速度。圖2為本文算法流程圖。

圖2 Memetic算法流程圖

4.2.1 染色體的編碼和譯碼

對于整數(shù)規(guī)劃,遺傳算法存在Michalewicz矩陣、Prufer數(shù)字以及基于優(yōu)先級等多種染色體編碼方法,本文采用了基于優(yōu)先級的分層分段改進(jìn)編碼方法[29],如圖3所示,編碼矩陣中,縱向分3層,首先按時(shí)間周期分組,在一個(gè)時(shí)間周期內(nèi)又按物質(zhì)種類分組,如果考慮運(yùn)輸工具,則需要再加一層,示例中為了簡潔起見沒有考慮運(yùn)輸工具。最后按優(yōu)先級PR和庫存水平IL分組,橫向分兩段,第一段為保障基地模型涉及的物質(zhì)傳輸節(jié)點(diǎn)(保障基地和前進(jìn)基地),第二段為前進(jìn)基地模型涉及的傳輸節(jié)點(diǎn)(前進(jìn)基地和保障需求點(diǎn))。例子中保障基地?cái)?shù)量|B|=3,前進(jìn)基地?cái)?shù)量|Q|=4,保障需求點(diǎn)數(shù)量|R|=5。在算法初始化階段(見圖2中步驟1),隨機(jī)生成不相同的隨機(jī)數(shù)(1～|B|+|Q|)作為保障基地段染色體,同樣生成|R|+|Q|個(gè)各不相同的隨機(jī)數(shù)(1～|R|+|Q|)作為前進(jìn)基地段染色體。

圖3 染色體編碼示例

設(shè)T為決策周期數(shù),K為保障物質(zhì)類型數(shù),下面為單段(保障基地段或前進(jìn)基地段)染色體譯碼算法(見圖2中步驟3)的偽代碼。

輸入?yún)?shù):

S-發(fā)貨節(jié)點(diǎn)集合(B或Q);

D-收貨節(jié)點(diǎn)集合(Q或R);

Isdk-收發(fā)貨節(jié)點(diǎn)之間的運(yùn)輸開銷;

V(|S|+|D|)-物質(zhì)k的優(yōu)先級PR層染色體編碼。

輸出:

Xsdk-收發(fā)貨節(jié)點(diǎn)之間運(yùn)輸?shù)奈镔|(zhì)數(shù)量;

Zs-布爾量,決策是否在s節(jié)點(diǎn)建立基地。

Fort=1 toT∥遍歷保障決策周期

Fork=1 toK∥遍歷保障物質(zhì)類型

輸入該次循環(huán)所需參數(shù);

While ∑sCks≤0 && ∑dRkd≤0

Xsd=0 ?s∈S,d∈D

n=argmax{V}∥V中找出優(yōu)先級最高的節(jié)點(diǎn)

ifn∈Sthen∥如果n為發(fā)貨節(jié)點(diǎn)

s*=n

d*=argmin{Isdk|V(d)≠0,d∈D}

∥選擇最小運(yùn)輸開銷的節(jié)點(diǎn)為收貨方

else如果n為收貨節(jié)點(diǎn)

d*=n

s*=argmin{Isdk|V(d)≠0,s∈S}

∥選擇最小運(yùn)輸開銷的節(jié)點(diǎn)為發(fā)貨方

Xs*d*=min(Cks*,Rkd*)∥選擇運(yùn)輸物質(zhì)數(shù)量

Cks*=Cks*-Xs*d*∥更新發(fā)貨方庫存

Rkd*=Rkd*-Xs*d*∥更新收貨方需求量

ifCks*=0 thenV(s*)=0

ifRkd*=0 thenV(d*)=0

end loop

fors=1 to |S|

if ∑dXsd≤0 thenZs=1∥s點(diǎn)設(shè)置基地

endfor

endfor

4.2.2 染色體的交叉和變異

交叉算法通過交換父代染色體的部分基因段來擴(kuò)展新的解集空間,整數(shù)互換編碼可以采取的交叉算子較多,包括部分映射交叉、排序交叉以及基于位置的交叉等,但本文采取的是優(yōu)先級分段編碼,常規(guī)的染色體交叉算子容易引起交叉后基因出現(xiàn)互異性和不合理性[21]。

為了避免沖突檢測和修補(bǔ)步驟影響執(zhí)行效率,本文采取了二階段子段互換算子,如圖4所示。首先,生成一個(gè)隨機(jī)二進(jìn)制數(shù)組,把它分配至各個(gè)染色體段。本文只是針對現(xiàn)有2層供應(yīng)鏈的2段編碼進(jìn)行說明,所以圖4只需要2位二進(jìn)制,但本文算法可以擴(kuò)展到3層以上。第2階段,如果被分配的數(shù)字為1,按圖4說明交換算子。這樣可以避免交叉后染色體出現(xiàn)重復(fù)基因,違反優(yōu)先級編碼原則。

圖4 染色體交叉算子示例

與交叉類似,變異算子也用以擴(kuò)展新解集空間并防止過早收斂,只不過它只作用于一個(gè)染色體上,本文采取了“新增”變異算子,即在選中染色體上隨機(jī)選擇一個(gè)位置的基因并把它插入到一個(gè)也是隨機(jī)選擇的新位置處,如圖5所示。

圖5 染色體變異算子示例

4.2.3 鄰域搜索算法

為了彌補(bǔ)遺傳算法局部搜索能力的不足,本文在Memetic算法中增加了自適應(yīng)大鄰域搜索算法[30](見圖2中步驟4),它通過一系列破壞算子和修復(fù)算子對當(dāng)前解進(jìn)行變化,產(chǎn)生相應(yīng)的新鄰居解集合,其中破壞算子會(huì)破壞當(dāng)前解的一部分,而后修復(fù)算子會(huì)對被破壞的解進(jìn)行重建。自適應(yīng)大鄰域搜索算法會(huì)為每個(gè)破壞算子和修復(fù)算子分配權(quán)重,通過該權(quán)重控制對應(yīng)算子在搜索期間使用的頻率,為了得到更好的鄰居解集,算法還會(huì)根據(jù)搜索過程中各個(gè)算子的表現(xiàn)動(dòng)態(tài)調(diào)整其權(quán)重,該算法能在減少計(jì)算時(shí)間的同時(shí)提高解集質(zhì)量。

本文定義了如下兩類破壞算子:

(1) DN1，在當(dāng)前解染色體編碼中隨機(jī)選擇不相鄰位置的基因?qū)嵤┢茐?基因數(shù)量隨機(jī);

(2) DN2,在當(dāng)前解染色體編碼中隨機(jī)選擇相鄰位置的基因?qū)嵤┢茐?基因數(shù)量隨機(jī)。

如果DN1和DN2中的基因數(shù)量不隨機(jī),而是選擇1到多個(gè),可以改變?yōu)槎鄠€(gè)破壞算子。

定義了如下3類修復(fù)算子:

(1) RN1,對選擇破壞的基因集合隨機(jī)重新排序,再放回原位置;

(2) DN2,對選擇破壞的基因集合倒序排列,再放回原位置;

(3) DN3,選擇破壞的基因集合與染色體內(nèi)其他位置的基因交換位置。

鄰域搜索算法偽代碼如下所示。

輸入:

1 遺傳算法傳來的當(dāng)前迭代的最佳解;

2 破壞算子集Ω-和修復(fù)算子集Ω+;

3 破壞算子權(quán)重集ω-和修復(fù)算子權(quán)重集ω+;

4 禁忌表TL。

輸出:改善的解集。

1ω-=(1,…,1);ω+=(1,…,1);∥ω-中每一個(gè)數(shù)字對應(yīng)Ω-對應(yīng)位置算子的權(quán)重,ω+也類似

2s=遺傳算法當(dāng)前迭代的最優(yōu)解

3 repeat

4 根據(jù)ω-和ω+的權(quán)重,選擇r∈Ω-,d∈Ω+

5s’=r(d(s));∥先破壞后修復(fù)s得到新解s’

6 ifs’ ∈TL then continue;∥新解曾經(jīng)出現(xiàn)過

7 按式(37)計(jì)算新解s’的適應(yīng)度F(s’);

8 ifF(s’)>F(s) thens=s’

9 按下式更新ω-和ω+:

(41)

(42)

10 對s’再次應(yīng)用爬山法進(jìn)行搜索

11 更新TL、θd和θr

12t=t+1

13 untilt>maxt

14 返回s’

步驟10中爬山法每次迭代都使用DN1和RN1來更新鄰域。

5 仿真驗(yàn)證

為了評估本文算法的有效性,首先建立了一個(gè)包含3層保障鏈(保障基地、前進(jìn)基地、保障需求點(diǎn))的實(shí)驗(yàn)案例,實(shí)驗(yàn)數(shù)據(jù)包含保障需求點(diǎn)不同時(shí)間段的物質(zhì)申請的種類和數(shù)量以及起始時(shí)保障基地的庫存物質(zhì)等信息,來源于分布式殺傷兵棋演練的存儲(chǔ)數(shù)據(jù),從中選取了5個(gè)不同規(guī)模想定的參數(shù)設(shè)置和仿真演練數(shù)據(jù)驗(yàn)證本文模型,模型中不確定參數(shù)取想定中對應(yīng)參數(shù)的三角分布。

第1個(gè)實(shí)驗(yàn)把協(xié)同算法、集中求解算法與分立求解算法的結(jié)果進(jìn)行了對比。保障基地?cái)?shù)量為5,保障需求點(diǎn)數(shù)量為32,前進(jìn)基地?cái)?shù)量為5,在分立求解算法中,前進(jìn)基地和保障基地模型分別求解,案例中供應(yīng)鏈的每一個(gè)節(jié)點(diǎn)輸出提取計(jì)算求和。集中求解算法中,取消第2節(jié)的分布式優(yōu)化算法,前進(jìn)基地和保障基地模型的約束條件和目標(biāo)函數(shù)合并后優(yōu)化。表1為置信水平分別為0.7、0.8和0.9時(shí)的目標(biāo)函數(shù)值(開銷),從中可以看出協(xié)同算法的總開銷小于分立算法但高于集中算法。例如當(dāng)β=0.7時(shí),分立算法為957 632,但協(xié)同算法的缺貨開銷為0。分立算法轉(zhuǎn)化為協(xié)同算法時(shí),由于存在信息共享機(jī)制,所以前進(jìn)基地開銷沒有增加,與分立算法相同,另外由于協(xié)同算法中沒有缺貨開銷,所以保障基地開銷和總開銷小于分立算法。這里開銷并非金額,代表懲罰單位。從表1可以看出,集中算法的實(shí)施需要后方前方統(tǒng)一指揮,雖然開銷最小,但如第2節(jié)所述,這種方式難以持續(xù)。而當(dāng)前,特別是某些爭議海域局勢緊張的局面可能長期存在,這就需要協(xié)同算法來優(yōu)化處理。

表1 算法開銷比較

第2個(gè)實(shí)驗(yàn)分別對前進(jìn)基地模型(Z1及約束)、保障基地模型(Z2及約束)和協(xié)同保障模型進(jìn)行敏感性分析。

圖6和圖7顯示隨著前進(jìn)基地?cái)?shù)量的變化,3個(gè)模型目標(biāo)函數(shù)值(開銷)的變化情況。如圖6所示,對于所有3個(gè)模型,當(dāng)前進(jìn)基地?cái)?shù)量增加時(shí),Z1的開銷減小,當(dāng)前進(jìn)基地?cái)?shù)量為7時(shí),Z1開銷最小。在圖7中,當(dāng)前進(jìn)基地?cái)?shù)量為6～9之間時(shí),Z2開銷最小。盡管隨著前進(jìn)基地?cái)?shù)量增加,協(xié)同模型和保障基地模型求解得到的Z2開銷相應(yīng)減少,但前進(jìn)基地模型的Z2開銷卻并不總是減少,其運(yùn)輸開銷和護(hù)航開銷會(huì)隨著數(shù)量增加而增加,轉(zhuǎn)折點(diǎn)大概在前進(jìn)基地?cái)?shù)量為7的位置。另外,從圖6和圖7中可以看出協(xié)同算法求解得到的是Z1和Z2之間的較優(yōu)值。

圖6 前進(jìn)基地?cái)?shù)量對Z1開銷的變化

圖7 前進(jìn)基地?cái)?shù)量對Z2開銷的變化

圖8 運(yùn)輸工具可用數(shù)量對Z1開銷的影響

在后裝保障供應(yīng)鏈中的一個(gè)關(guān)鍵問題是如何管理不確定性。如果直接把包含所有不確定參數(shù)的模型與確定性模型進(jìn)行比較,會(huì)導(dǎo)致參數(shù)均值化問題,從而影響比較結(jié)果,為此在第3個(gè)實(shí)驗(yàn)中設(shè)計(jì)了4個(gè)不確定程度不同的比對模型進(jìn)行性能比較。

比對模型4:所有不確定參數(shù)為隨機(jī)數(shù)。

圖9為5類想定下不同比對模型求解得到的總開銷。可以看出由于比對模型1不考慮不確定性,所以在保障供應(yīng)鏈中引起的開銷最大,而且在不同想定下的開銷變化量也比較大。比對模型2考慮了物質(zhì)保障不確定性,盡管模型復(fù)雜度有部分增加,但應(yīng)對不確定環(huán)境的能力也相應(yīng)提高。模型的不確定性程度越高,它轉(zhuǎn)換為概率約束規(guī)劃后包含的參數(shù)種類和數(shù)量也會(huì)相應(yīng)增加,即復(fù)雜度增加,但是與低不確定性模型相比,總開銷會(huì)降低。如圖9所示,不確定性程度越高的模型,總開銷降低的同時(shí)穩(wěn)定性也相應(yīng)增強(qiáng)。比對模型4相較于模型1、2和3,總開銷的平均降低率為8.9%、6.7%和3.7%。

圖9 不確定程度不同模型的總開銷

第4個(gè)實(shí)驗(yàn)檢驗(yàn)協(xié)同算法計(jì)算Pareto解的有效性。根據(jù)保障基地?cái)?shù)量、前進(jìn)基地?cái)?shù)量、保障申請點(diǎn)數(shù)量以及運(yùn)輸工具數(shù)量等參數(shù),從仿真演練想定案例中分別選取小、中、中大、較大和大型5種保障規(guī)模的數(shù)據(jù)進(jìn)行優(yōu)化計(jì)算,并以只實(shí)現(xiàn)第4.2.2節(jié)染色體編碼譯碼的常規(guī)多目標(biāo)遺傳算法NSGA-II作為比對算法,為了公平起見,遺傳算法的最大迭代數(shù)量為本文Memetic算法的3倍。

以下為用于比對的兩種性能指標(biāo):① Pareto優(yōu)化解的平均數(shù)量;② Pareto優(yōu)化解的平均比例APR[31]。設(shè)S1和S2分別為Memetic算法和NSGA 算法計(jì)算得到的Pareto解集,U為S1和S2的并集,S1集合的Pareto解比例定義為U中任何一個(gè)元素非支配的S1解所占比例,表達(dá)式如下:

(43)

如果APR增加,表示U中成員非支配的S1中的Pareto解數(shù)量也增加。

表2為每一個(gè)想定數(shù)據(jù)運(yùn)行15次后計(jì)算結(jié)果的平均值,Met為改進(jìn)Memetic算法,GA為NSGA-II算法。從中可以看出,針對每一個(gè)規(guī)模的案例,改進(jìn)Memetic算法性能都要好于NSGA-II算法。改進(jìn)Memetic算法平均能夠找到7.86個(gè)Pareto優(yōu)化解,而NSGA-II算法只能平均找到4.53個(gè)解。另外改進(jìn)Memetic算法的解質(zhì)量也要明顯高于NSGA-II算法,平均0.99大于0.07。而且改進(jìn)Memetic算法計(jì)算時(shí)間也要優(yōu)于NSGA-II算法,平均花費(fèi)620.81 s,而NSGA-II平均花費(fèi)1 344.55 s。圖10為兩種算法某次運(yùn)行的Pareto前沿示例圖。從性能指標(biāo)比較結(jié)果看,對于后裝保障供應(yīng)鏈優(yōu)化問題,綜合了加權(quán)增強(qiáng)ε-約束法以及鄰域搜索法的改進(jìn)Memetic算法具有良好的求解性能。

表2 兩種算法求解多目標(biāo)規(guī)劃的結(jié)果比較

圖10 兩種算法的Pareto前沿示例

6 結(jié)束語

本文首次提出了不確定條件下基于信息共享的保障基地-前進(jìn)基地的協(xié)同模型,該模型中保障基地作為后裝物質(zhì)的提供者,前進(jìn)基地負(fù)責(zé)物質(zhì)的存儲(chǔ)及配送,二者與作戰(zhàn)部隊(duì)構(gòu)成3層保障鏈模式,并對它們的保障行為進(jìn)行了數(shù)學(xué)描述。然后在仿真案例中從分立、集中和協(xié)同3種決策結(jié)構(gòu)的角度進(jìn)行了模型求解,在分立結(jié)構(gòu)中,由于保障鏈成員各自獨(dú)立決策,造成供貨方經(jīng)常性缺貨,保障鏈總體開銷增大。與之相比,集中結(jié)構(gòu)下的保障鏈總體開銷得到大幅度降低。而協(xié)同結(jié)構(gòu)由于采用了信息共享機(jī)制,開銷同樣得到較大降低,特別是前進(jìn)基地在保持分立結(jié)構(gòu)的同時(shí)還能減少開銷。

本文還采用了模糊規(guī)劃方法來解決保障鏈中的不確定性參數(shù)影響,為了克服轉(zhuǎn)換后規(guī)劃模型的計(jì)算復(fù)雜性過大的問題,提出了改進(jìn)的Memetic算法進(jìn)行模型求解,并通過仿真實(shí)驗(yàn)驗(yàn)證了算法的魯棒性和有效性。下一步工作將繼續(xù)研究存在運(yùn)輸中斷風(fēng)險(xiǎn)的保障鏈規(guī)劃模型。