基于融合免疫優(yōu)化和遺傳算法的多應(yīng)急物資中心選址與調(diào)度

許倫輝，曹宇超，林培群

(華南理工大學(xué) 土木與交通學(xué)院，廣東 廣州 510640)

近年來，全球各類自然和社會(huì)公共突發(fā)性災(zāi)害事件頻發(fā)，給社會(huì)和百姓造成了巨大的損失和困擾。社會(huì)經(jīng)濟(jì)受到影響，人們的生命和安全也受到了巨大的威脅，物資供應(yīng)也面臨著巨大的阻礙。為了降低損失，及時(shí)應(yīng)對(duì)受災(zāi)區(qū)資源短缺，解決物資需求的問題，合理的應(yīng)急物資中心選址及物資調(diào)度就顯得尤為重要，它關(guān)系到能否及時(shí)響應(yīng)災(zāi)區(qū)受災(zāi)點(diǎn)物資需求，保證援助效率。

應(yīng)急物資網(wǎng)絡(luò)的本質(zhì)是從應(yīng)急物資中心出發(fā)配送物資到受災(zāi)點(diǎn)的物流模式，近年來，國內(nèi)外學(xué)者對(duì)于物流方面的選址問題研究成果眾多。如：Yang等[1]建立了以成本和距離最小為雙目標(biāo)的消防站選址模型，并利用遺傳算法求解了模型；王文峰等[2]以最大覆蓋模型為目標(biāo)，建立了多級(jí)覆蓋質(zhì)量要求下的設(shè)施選址模型，并設(shè)計(jì)了啟發(fā)式算法進(jìn)行求解；Rawls等[3]建立了應(yīng)急物資儲(chǔ)備庫選址及救援物資種類決策的兩階段混合整數(shù)規(guī)劃模型；李現(xiàn)美[4]建立了應(yīng)急物資儲(chǔ)備中心多目標(biāo)多級(jí)的最大覆蓋選址模型，并設(shè)計(jì)了遺傳-粒子群混合算法對(duì)模型進(jìn)行求解；徐重岐等[5]提出了一種基于混合整數(shù)規(guī)劃模型的應(yīng)急物流配送中心選址方法；趙仁輝等[6]針對(duì)單一指派約束和容量約束，以總成本費(fèi)用最小為目標(biāo)建立了一種基于改進(jìn)蟻群算法與GIS的配送中心選址方法；Ai等[7]建立了海上救援應(yīng)急物資儲(chǔ)備庫與應(yīng)急救援船舶的資源配置模型，并用遺傳算法求解了該模型；張敏等[8]建立了基于失效情形的應(yīng)急設(shè)施選址評(píng)估指標(biāo)體系并運(yùn)用數(shù)據(jù)包絡(luò)法對(duì)應(yīng)急設(shè)施選址的合理性進(jìn)行了評(píng)價(jià)；馮艦銳等[9]基于運(yùn)籌學(xué)中多目標(biāo)優(yōu)化理論，并引入了多影響因素權(quán)重因子，建立了應(yīng)急物資中心選址問題的優(yōu)化模型；宋英華等[10]構(gòu)建了以最小配送時(shí)間和成本為目標(biāo)函數(shù)，考慮了動(dòng)態(tài)環(huán)境下的應(yīng)急物資中心快速選址模型；Wang等[11]基于局部分支和粒子群優(yōu)化的方法提出了一種隨機(jī)規(guī)劃模型，考慮具體受損場景以及引入抗震能力，確定災(zāi)難現(xiàn)場應(yīng)急倉庫的選址和規(guī)模。文獻(xiàn)[1-11]只研究了應(yīng)急中心的選址，并沒有進(jìn)一步設(shè)計(jì)后續(xù)的物資調(diào)配方案。李進(jìn)等[12]對(duì)于多種類物資分類調(diào)度建立了對(duì)應(yīng)多受災(zāi)點(diǎn)的調(diào)度模型；劉長石等[13]考慮了應(yīng)急物資配送的具體需求量和時(shí)間效率問題，建立了物資由多個(gè)應(yīng)急物流中心到多個(gè)需求點(diǎn)的應(yīng)急物流模式并且建立了總運(yùn)達(dá)時(shí)間最短與總配送成本最小的多目標(biāo)模型；朱洪利等[14]針對(duì)地震等突發(fā)事件發(fā)生時(shí)應(yīng)急物資需求存在動(dòng)態(tài)變化的特點(diǎn)，提出了兩階段應(yīng)急資源調(diào)度模型；Wang等[15]提出了以最短時(shí)間，最少成本多目標(biāo)的二維優(yōu)化模型，應(yīng)用理想點(diǎn)算法來解決應(yīng)急物資的調(diào)運(yùn)問題；趙振亞等[16]建立了基于最小風(fēng)險(xiǎn)路徑的應(yīng)急物資調(diào)度配送方案；孫欣欣等[17]構(gòu)建了基于運(yùn)輸時(shí)間最短、物資儲(chǔ)備庫最少的多目標(biāo)應(yīng)急物資調(diào)度計(jì)算模型，利用遺傳算法進(jìn)行調(diào)度方案求解；李巧茹等[18]提出一種考慮災(zāi)后道路可靠性的多目標(biāo)優(yōu)化應(yīng)急調(diào)度模型，以車輛行駛時(shí)間最小、行駛路徑可靠度最大和系統(tǒng)物資未滿足度最小為目標(biāo)函數(shù)，采用改進(jìn)遺傳算法進(jìn)行求解。雖然文獻(xiàn)[12-18]在物資調(diào)度和路徑規(guī)劃方面給出了解決方案，但沒有給出該情景下如何進(jìn)行應(yīng)急物資配送中心選址的方案。少數(shù)學(xué)者研究了選址-調(diào)度一體化問題。Caunhye等[19]建立了物資需求和設(shè)施狀態(tài)不確定性條件下的兩階段的選址路徑模型；Liu等[20]結(jié)合動(dòng)態(tài)規(guī)劃的車輛運(yùn)輸路徑分配算法和基于蟻群優(yōu)化的災(zāi)區(qū)供應(yīng)序列自學(xué)習(xí)算法，建立了考慮物資需求和車輛數(shù)量不斷變化的應(yīng)急物資調(diào)度模型；曲沖沖等[21]基于在災(zāi)區(qū)實(shí)際狀況，針對(duì)應(yīng)急環(huán)境的動(dòng)態(tài)性，建立了應(yīng)急物資配送中心選址與運(yùn)輸配送路徑優(yōu)化模型，解決了多目標(biāo)動(dòng)態(tài)救援問題；許可等[22]建立了考慮物資供應(yīng)約束以及轉(zhuǎn)運(yùn)平衡約束的多目標(biāo)優(yōu)化選址調(diào)度模型，使用帶慣性權(quán)重的離散二進(jìn)制粒子群算法對(duì)模型進(jìn)行求解；姚紅云等[23]基于模糊層次分析法構(gòu)建了應(yīng)急物資中心選址模型，并建立了災(zāi)害過程中應(yīng)急物資配送路徑優(yōu)化模型。

可以看出，應(yīng)急物資中心的選址與物資調(diào)度配置問題是整個(gè)應(yīng)急物流網(wǎng)絡(luò)的2個(gè)重要問題，多數(shù)學(xué)者是從單一角度將2個(gè)問題分開或看成2個(gè)階段研究；少數(shù)學(xué)者雖然考慮了一體化研究，但解決方案存在改進(jìn)空間。在求解該類最優(yōu)問題時(shí)常采用動(dòng)態(tài)規(guī)劃算法、啟發(fā)式算法或遺傳算法等智能優(yōu)化算法。動(dòng)態(tài)規(guī)劃算法存在著耗時(shí)長、效率低的缺點(diǎn)；啟發(fā)式算法的精確程度往往較差；標(biāo)準(zhǔn)的遺傳算法以及粒子群算法往往存在容易陷于局部最優(yōu)或收斂速度較慢的缺點(diǎn)[24-25]。

由此，本文針對(duì)應(yīng)急物資中心選址與多目標(biāo)點(diǎn)調(diào)度問題，設(shè)計(jì)了基于免疫優(yōu)化算法選址和基于多層編碼遺傳算法調(diào)度的融合算法。免疫優(yōu)化算法可通過自身調(diào)節(jié)機(jī)制[26]，保證個(gè)體多樣性，避免陷入局部解；多層編碼遺傳算法通過改變編碼方式，構(gòu)建雙層染色體分別表示供應(yīng)方和需求方，解決此類多目標(biāo)問題，融合建立了中心選址-調(diào)度一體化解決方案。

1 應(yīng)急物資中心選址和調(diào)度模型

1.1 問題描述

災(zāi)害發(fā)生后，為了響應(yīng)物資需求，不僅需要考慮應(yīng)急物資中心至受災(zāi)區(qū)域的距離成本，而且還需要結(jié)合不同物資種類，物資需求量的運(yùn)輸成本進(jìn)行綜合考慮，選出合理的應(yīng)急物資中心地址，確定最優(yōu)的物資調(diào)度配送方案，以保證好各物資中心的應(yīng)急物資能夠以最低的成本滿足受災(zāi)點(diǎn)的需求，保證救援效率，減少資源浪費(fèi)，獲得系統(tǒng)全局的最優(yōu)方案。問題描述如圖1所示。

圖1 應(yīng)急中心選址-調(diào)度示意Fig. 1 Emergency center site selection and dispatching diagram

1.2 應(yīng)急物資中心選址模型

應(yīng)急物資中心的選址建立在3個(gè)假設(shè)條件上：

1)外界補(bǔ)充物資足夠支持任意配送需求，且應(yīng)急物資中心的容納量默認(rèn)可以滿足配送需求。某一物資中心的調(diào)度目標(biāo)需要在其配送輻射范圍之內(nèi)。

2)每個(gè)應(yīng)急中心物資種類齊全，一個(gè)需求點(diǎn)只由一個(gè)物資中心即可滿足相應(yīng)需求。

3)應(yīng)急物資中心與需求點(diǎn)間的成本評(píng)估考慮綜合代價(jià)，即綜合考慮距離和運(yùn)輸成本[27]。如式(7)所示。

在3個(gè)假設(shè)的基礎(chǔ)上建立選址模型，模型滿足建立M個(gè)物資中心，以供應(yīng)滿足N個(gè)需求點(diǎn)的物資需求。M?N，即物資中心以需求庫中的點(diǎn)進(jìn)行建立，選為物資中心的區(qū)域可滿足供應(yīng)自己區(qū)域的需求，并且可以為其他非物資中心的需求點(diǎn)配送物資。目標(biāo)函數(shù)是使物資中心到其余需求點(diǎn)的綜合代價(jià)值Fs最小，目標(biāo)函數(shù)為

(1)

約束條件為：

(2)

Zi,j≤hj，i∈N，j∈Mi，

(3)

(4)

Zi,j,hj∈0 或 1，i∈N，j∈Mi，

(5)

di,j≤s。

(6)

式中：N表示所有需求點(diǎn)的集合；i表示第i個(gè)目標(biāo)需求點(diǎn)；Mi表示能輻射到i點(diǎn)的應(yīng)急物資中心集合；j表示第j個(gè)物資中心；Zi,j用0和1表示需求點(diǎn)和物資中心是否存在配送關(guān)系，若i點(diǎn)由j中心供應(yīng)，則Zi,j=1，反之為0；hj采用0和1表示j點(diǎn)是否已被選為配送中心，hj=1表示被選為配送中心，反之為0；di,j表示i點(diǎn)與j中心間的距離；s表示輻射范圍。

式(2)表示每個(gè)需求點(diǎn)僅由一個(gè)物資中心提供物資即可；式(3)表示需求點(diǎn)只能被設(shè)為物資中心的點(diǎn)供應(yīng)；式(4)表示建立的物資中心數(shù)目為M；式(6)表示物資配送需在輻射范圍內(nèi)。

下面計(jì)算綜合代價(jià)。綜合代價(jià)分別考慮了物資配送的距離成本和運(yùn)輸成本，計(jì)算公式為

w(d,p,g)=pd+dηg，

(7)

式中：pd表示配送的距離成本；dηg表示運(yùn)輸成本。其中距離成本在配送路徑選擇中，主要需要考慮道路的通暢度，即擁堵程度會(huì)影響距離成本和總體耗時(shí)，因此對(duì)出行距離d添加了交通擁堵系數(shù)p作為距離成本系數(shù)。在運(yùn)輸成本中，η表示運(yùn)輸成本中需求物資單位需求量的成本換算系數(shù)，g表示物資需求量。

表1 速度-交通擁堵系數(shù)對(duì)照

(8)

2)運(yùn)輸成本中需求物資單位需求量的成本換算系數(shù)η的取值結(jié)合具體運(yùn)送的物資，根據(jù)不同種類物資在運(yùn)輸途中的易損程度，通過經(jīng)驗(yàn)函數(shù)及相關(guān)統(tǒng)計(jì)數(shù)據(jù)確定。

1.3 多目標(biāo)物資調(diào)度模型

多目標(biāo)物資中心調(diào)度問題的本質(zhì)就是合理安排配送路線，使得全局總代價(jià)最小，基于物資中心選址模型，受災(zāi)區(qū)中有M個(gè)物資中心，總共要給N個(gè)需求受災(zāi)點(diǎn)配送，設(shè)第m個(gè)物資中心要向Lm(m=1,2,…,M)個(gè)需求點(diǎn)送貨，第m個(gè)物資中心有Km輛配送車，車輛限載量Qm,k(k=1,2,…,Km)，其配送的最大行駛距離為Dm,k。第m個(gè)物資中心服務(wù)的第i個(gè)需求點(diǎn)的貨物需求量為qm，i(i=1,2,…,Lm)，該物資中心到第i個(gè)需求點(diǎn)的綜合代價(jià)為wm，i(m=1,2,…,M;i=1,2,…Lm)，再設(shè)nm，k為第m個(gè)物資中心中第k輛車配送的需求商數(shù)(nm，k=0表示未使用第k輛車)，rm，k，i表示物資中心m使用第k輛車為需求點(diǎn)i運(yùn)送物資。若以全局綜合代價(jià)最小為目標(biāo)函數(shù)Ft，則調(diào)度模型為：

(9)

(10)

s≤Dm，k，

(11)

(12)

(13)

(14)

式(9)～(14)中：wrm，k，i表示物資中心m使用第k輛車為需求點(diǎn)i運(yùn)送物資的綜合代價(jià)值；qm，rm，k，i表示物資中心m使用第k輛車為需求點(diǎn)i運(yùn)送的物資量。式(10)保證配送量能滿足需求量；式(11)保證車輛可送達(dá)距離在物資中心輻射范圍內(nèi)；式(12)表明單一物資中心配送需求點(diǎn)數(shù)不超過總需求點(diǎn)數(shù)；式(13)表明所有需求點(diǎn)均得到供應(yīng)；式(14)表示車輛狀態(tài)，當(dāng)?shù)趉輛車參加了配送任務(wù)則取fsign(nm，k)=1，反之取fsign(nm，k)=0。

2 融合免疫優(yōu)化和多層編碼遺傳算法設(shè)計(jì)

免疫優(yōu)化算法和遺傳算法的本質(zhì)都是從群體中選出優(yōu)質(zhì)個(gè)體。二者的算法步驟相似，由“初始種群產(chǎn)生→評(píng)價(jià)標(biāo)準(zhǔn)計(jì)算→種群間個(gè)體信息交換→新種群產(chǎn)生”這一循環(huán)過程，最終以較大的概率獲得問題的最優(yōu)解。

2.1 基于免疫優(yōu)化算法的物資中心選址

免疫優(yōu)化算法利用免疫系統(tǒng)產(chǎn)生并保持種群的多樣性，對(duì)于存在多峰值的函數(shù)能避免陷入局部循環(huán)，最終可求得全局最優(yōu)解。免疫算法流程如圖2所示。

圖2 免疫優(yōu)化算法流程Fig. 2 Immune optimization algorithm flowchart

2.1.1 生成初始抗體群

根據(jù)候選可建立應(yīng)急物資中心的區(qū)域點(diǎn)信息，生成初始抗體種群。設(shè)需要建立的物資中心數(shù)目為M，則選址方案生成一個(gè)長度為M的抗體[m1,m2,…,mM]。

2.1.2 解的評(píng)價(jià)

①抗體與抗原間的親和度

描述抗體對(duì)抗原的識(shí)別程度，根據(jù)物資中心與需求點(diǎn)之間的關(guān)系定義親和度函數(shù)A。

(15)

式中：Fs為選址模型中的目標(biāo)函數(shù)；Ppun是懲罰函數(shù)；C是一個(gè)趨近于正無窮的數(shù)。

②抗體與抗體間的親和度

描述抗體之間的相似程度。采用R位連續(xù)方法來計(jì)算抗體間的親和度。

(16)

式中：ki,j表示抗體i與j中相同的位數(shù)；M表示抗體長度。如抗體[1 5 8 21 27]與抗體[2 4 8 19 27]中，有2個(gè)位數(shù)相同，則抗體間的親和度為Si,j為0.4。

數(shù)據(jù)傳輸層通過與采集層和數(shù)據(jù)處理層的上下連接，通過通信網(wǎng)絡(luò)進(jìn)行信息傳輸，為系統(tǒng)提供基礎(chǔ)設(shè)施服務(wù)。傳輸層由無線傳感網(wǎng)、有線網(wǎng)、互聯(lián)網(wǎng)及各種私有網(wǎng)絡(luò)組成，在數(shù)據(jù)采集層各傳感器和數(shù)據(jù)處理層之間起到紐帶和橋梁作用，負(fù)責(zé)將獲取的傳感器感知信息，經(jīng)過互聯(lián)網(wǎng)或私有網(wǎng)絡(luò)，安全可靠地傳輸?shù)缴蠈舆M(jìn)行數(shù)據(jù)分析，然后根據(jù)不同的應(yīng)用需求進(jìn)行數(shù)據(jù)的交互與處理。該系統(tǒng)中主要采用藍(lán)牙、3G/4G 移動(dòng)網(wǎng)絡(luò)和局域網(wǎng)絡(luò)等進(jìn)行數(shù)據(jù)的傳輸與通信。

③抗體濃度

表示滿足親和度閾值T的抗體占抗體總數(shù)的比例。

(17)

④期望繁殖概率

在一個(gè)種群中，個(gè)體的期望繁殖概率由抗體間的親和度A和抗體濃度Cv決定。

(18)

式中α是比例系數(shù)。當(dāng)個(gè)體適應(yīng)度越高時(shí)，期望繁殖概率越大；當(dāng)個(gè)體濃度越小時(shí)，期望繁殖概率越大。這種方式有利于選擇適應(yīng)度高的個(gè)體，同時(shí)抑制濃度高的個(gè)體，保證了個(gè)體多樣性。

本文采取精英保留策略進(jìn)行再優(yōu)化，在每次更新記憶庫時(shí)，先將與抗原親和度最高的個(gè)體按比例選取一部分存入記憶庫，再按照期望繁殖概率遞減，從高到低將剩余個(gè)體存入記憶庫，避免由于出現(xiàn)高濃度抑制導(dǎo)致最優(yōu)解的丟失。

2.1.3 免疫操作

①選擇：采用輪盤賭法根據(jù)式(18)的概率進(jìn)行選擇。即抗體被選中的概率與其期望繁殖概率成正比。

②交叉：采用隨機(jī)選擇交叉位置進(jìn)行交叉。即隨機(jī)選取2個(gè)抗體，并取出每個(gè)抗體的前M/4位，然后隨機(jī)選擇交叉位置進(jìn)行同等長度序列的交叉。

③變異：采用隨機(jī)選擇變異位進(jìn)行變異。變異算子首先從種群中隨機(jī)選取某個(gè)抗體作為變異個(gè)體，然后選擇變異位置pos1和pos2，將個(gè)體中pos1和pos2位置序列對(duì)換完成變異。

2.2 基于多層編碼遺傳算法的調(diào)度策略

對(duì)于應(yīng)急物資調(diào)配中多目標(biāo)中心對(duì)多目標(biāo)需求點(diǎn)的問題，一般遺傳算法一個(gè)單層染色體難以準(zhǔn)確表達(dá)問題的解。本文在傳統(tǒng)遺傳算法的基礎(chǔ)上，結(jié)合物資中心-需求點(diǎn)多目標(biāo)調(diào)度的情景，將一般的單個(gè)單層染色體編碼模式改進(jìn)為雙層編碼，通過把個(gè)體分為兩層，定義每層編碼分別表示物資中心和需求點(diǎn)，完整表達(dá)了問題的多項(xiàng)參數(shù)，可獲得最終的最優(yōu)解。

2.2.1 基于雙層編碼的模式

基于每個(gè)物資中心物資種類齊全的背景，采用雙層整數(shù)排列的編碼方法。對(duì)于M個(gè)物資中心，N個(gè)需求點(diǎn)的多目標(biāo)問題，染色體的第1層表示單次運(yùn)送中物資需求點(diǎn)排列；第2層表示對(duì)應(yīng)配送物資的物資中心點(diǎn)排列。例如N為4，M為3的染色體如圖3所示。其表示物資中心1→需求點(diǎn)1和3；物資中心2→需求點(diǎn)2；物資中心3→需求點(diǎn)4。

圖3 N=4且M=3的染色體

2.2.2 種群初始化

基于已知的需求點(diǎn)信息和免疫優(yōu)化算法中生成的物資中心點(diǎn)信息，排列組合生成隨機(jī)的初始種群。

2.2.3 適應(yīng)度計(jì)算

設(shè)染色體的適應(yīng)度值根據(jù)綜合代價(jià)進(jìn)行評(píng)價(jià)，計(jì)算公式為

ffit(i，j)=wi,jCi,j。

(19)

2.2.4 選擇操作

選擇操作采用輪盤賭法選擇適應(yīng)度較好的染色體，個(gè)體選擇概率為：

FFit(i,j)=1/ffit(i,j)。

(20)

2.2.5 交叉操作

采用隨機(jī)選擇交叉位置進(jìn)行交叉。與一般交叉不同的是，2個(gè)雙層染色體之間，對(duì)應(yīng)編碼層之間的基因才可進(jìn)行交叉，并計(jì)算交叉操作后新染色體的適應(yīng)度值。

2.2.6 變異操作

采用隨機(jī)選擇變異位進(jìn)行變異。與一般變異不同的是，雙層染色體中，同層編碼之間的基因才可進(jìn)行變異，即每層獨(dú)立的選擇pos1和pos2位置的基因進(jìn)行對(duì)換變異，并計(jì)算變異操作后新染色體的適應(yīng)度值。

3 算例分析

3.1 問題背景

2020年，我國面臨嚴(yán)峻的新型冠狀病毒疫情的災(zāi)害，世界衛(wèi)生組織(WHO)宣布，將新型冠狀病毒疫情列為國際關(guān)注的突發(fā)公共衛(wèi)生事件。本文以湖北省新型冠狀病毒疫情受災(zāi)需求為背景，結(jié)合國家衛(wèi)健委某日公布的地區(qū)-病人數(shù)據(jù)，根據(jù)當(dāng)?shù)夭∪藬?shù)量正比于應(yīng)急物資需求量的假設(shè)，模擬當(dāng)?shù)貞?yīng)急物資需求案例。如表2所示。

表2 受災(zāi)地區(qū)病人-物資需求量

3.2 應(yīng)急物資中心選址

根據(jù)湖北省的地圖，按比例尺構(gòu)建如圖4所示的坐標(biāo)系，并標(biāo)記受災(zāi)需求點(diǎn)的坐標(biāo)信息。

圖4 湖北省疫情受災(zāi)點(diǎn)信息Fig. 4 Information on the affected areas in Hubei Province

假設(shè)物資調(diào)配均采用陸運(yùn)，且各地交通可達(dá)性一致，物資種類均為應(yīng)急物資且在運(yùn)輸過程中受損度一致，取η=0.3。湖北省各地坐標(biāo)-需求物資的運(yùn)輸成本信息如表3所示。選定17個(gè)城市的坐標(biāo)信息，需要從其中選擇6個(gè)城市設(shè)立為應(yīng)急物資中心，其中選為應(yīng)急物資中心的地址可直接為當(dāng)?shù)靥峁┪镔Y，滿足當(dāng)?shù)匦枨?。設(shè)定種群規(guī)模為50，迭代次數(shù)為50，交叉概率為0.5，變異概率為0.4，多樣性評(píng)價(jià)參數(shù)為0.95，應(yīng)用免疫優(yōu)化算法確定最優(yōu)的應(yīng)急物資中心選址。

表3 受災(zāi)地區(qū)病人-物資需求量

通過免疫優(yōu)化算法，得到隨迭代次數(shù)增加而收斂的曲線如圖5所示，可以看到在迭代次數(shù)10次左右出現(xiàn)收斂；得到物資中心選址方案如圖6所示，其中方框表示應(yīng)急物資中心設(shè)立點(diǎn)，圓圈表示其余的受災(zāi)物資需求點(diǎn)。

圖5 免疫算法收斂曲線Fig. 5 Convergence Curve of Immune Algorithm

圖6 免疫優(yōu)化算法物資中心選址方案Fig. 6 Location plan of material center based on immune optimization algorithm

3.3 應(yīng)急物資調(diào)配方案

根據(jù)應(yīng)急物資中心的選址結(jié)果，武漢、孝感、黃岡、鄂州、荊州、襄陽6地作為物資中心，結(jié)合物資中心與其余各需求點(diǎn)間的距離信息、需求量信息綜合得出每個(gè)物資中心配送給其余各受災(zāi)需求點(diǎn)物資的綜合代價(jià)值，如表4所示。第1列是除了選為物資中心點(diǎn)外其余各需求點(diǎn)位置；第1行是6個(gè)被選為物資中心的點(diǎn)位置；表中數(shù)據(jù)是各物資中心分別到余下各需求點(diǎn)的運(yùn)輸綜合代價(jià)值(選為應(yīng)急中心地址的需求點(diǎn)默認(rèn)由當(dāng)?shù)毓?yīng)物資可滿足需求)。假設(shè)各路段疫情期間為物資車輛保持道路暢通，道路擁堵系數(shù)p=1。運(yùn)往各地物資的單位距離運(yùn)輸成本代價(jià)ηgj的值見表3。

表4 物資中心-受災(zāi)需求點(diǎn)綜合運(yùn)輸代價(jià)值

以武漢—隨州為例，綜合代價(jià)的計(jì)算過程為

w武漢—隨州(d武漢—隨州,g隨州)=d+dηg=2.8d=414.409 5≈414。

(21)

應(yīng)用多層編碼的遺傳算法，分類為每個(gè)物資中心單次配送車輛數(shù)目無上限的情景和每個(gè)物資中心單次運(yùn)輸車輛數(shù)目有限制且最大值Km=2的情景進(jìn)行分析。參數(shù)設(shè)種群數(shù)目為60，迭代次數(shù)為100，交叉概率為0.8，變異概率為0.6，目標(biāo)是獲得全局綜合代價(jià)值最小的物資調(diào)度配送方案。

情景1每個(gè)物資中心單次配送車輛數(shù)目無上限。情景1的收斂曲線如圖7所示，在迭代10次左右出現(xiàn)收斂，最優(yōu)調(diào)度方案如圖8所示。圖中102表示由物資中心2(孝感)為需求點(diǎn)1(隨州)運(yùn)送物資，系統(tǒng)運(yùn)輸綜合代價(jià)為縱坐標(biāo)值283。該調(diào)度方案可以獲得全局最優(yōu)的結(jié)果，且目標(biāo)值物資配送中心的系統(tǒng)運(yùn)輸綜合代價(jià)最優(yōu)，為1 908。情境1下最終形成的選址-調(diào)度方案如圖9所示。

圖7 情景1的調(diào)度方案迭代次數(shù)Fig. 7 Iterations of the scheduling scheme for scenario 1

圖8 情景1的調(diào)度方案甘特示意Fig. 8 Gantt diagram of scheduling scheme for scenario 1

圖9 情景1的最終選址調(diào)度方案Fig. 9 Final location scheduling scheme diagram for scenario 1

情景2每個(gè)物資中心單次運(yùn)輸車輛數(shù)目有限制且最大值Km=2。情景2的收斂曲線如圖10所示，最優(yōu)調(diào)度方案如圖11所示。該調(diào)度方案可以獲得全局最優(yōu)的結(jié)果，目標(biāo)值物資配送中心的系統(tǒng)運(yùn)輸綜合代價(jià)最優(yōu)，為2 314。情境2下最終形成的選址-調(diào)度方案如圖12所示。

圖10 情景2的調(diào)度方案迭代次數(shù)Fig. 10 Scheduling scheme iterations graph for scenario 2

圖11 情景2的調(diào)度方案甘特示意Fig. 11 Gantt diagram of scheduling scheme for scenario 2

圖12 情景2的最終選址調(diào)度方案Fig. 12 Final location scheduling scheme diagram for scenario 2

結(jié)合案例，與其他常用于解決這兩類問題的智能算法做比較，得到的對(duì)比結(jié)果如表5所示。

表5 不同算法實(shí)驗(yàn)性能的結(jié)果

從結(jié)果分析可以看出，本文針對(duì)這兩類問題采用的免疫優(yōu)化遺傳算法和多層編碼的遺傳算法均可以獲得全局最優(yōu)解并且具有更高的求解效率。通過二者融合的算法能夠得到一套合理的選址-調(diào)度方案。

4 結(jié)論

本文對(duì)于災(zāi)害環(huán)境下的援助提出了一套應(yīng)急物資中心選址-調(diào)度配送一體化的解決方案，首先論述了中心選址問題和多目標(biāo)對(duì)多目標(biāo)的調(diào)度配送問題，構(gòu)建了相應(yīng)的數(shù)學(xué)模型，并建立了基于綜合代價(jià)的成本評(píng)估模式。然后選擇了免疫優(yōu)化算法和改進(jìn)的多層編碼遺傳算法分別解決中心選址和調(diào)度配送問題，并論述了算法的優(yōu)勢。免疫優(yōu)化算法利用其多樣性，增強(qiáng)了全局中的搜索能力而不會(huì)陷入局部解；遺傳算法本身基于啟發(fā)式搜索，并且具備快速隨機(jī)搜索能力，針對(duì)物資調(diào)配問題改進(jìn)的多層編碼遺傳算法能更具針對(duì)性地解決多目標(biāo)-多目標(biāo)的問題?；谝陨蟽?yōu)勢，結(jié)合具體問題分別進(jìn)行了改進(jìn)算法步驟的設(shè)計(jì)。最后以湖北省新型冠狀病毒疫情下的受災(zāi)需求援助作為背景，采用融合免疫優(yōu)化算法和改進(jìn)的多層編碼遺傳算法的方式建立了一套合理且高效的應(yīng)急物資中心選址-物資調(diào)度配送的一體化解決方案，并且與其他常用的智能算法相比，論證了本文的方法能獲得全局最優(yōu)解并且保持較高的搜索效率，為災(zāi)害狀況下的應(yīng)急物資處置提供了高效可行的方案。