基于遺傳算法的應(yīng)急物流設(shè)施選址與調(diào)度

馮瑛杰， 謝慶紅

(南京工業(yè)大學(xué) 經(jīng)濟(jì)與管理學(xué)院， 南京 211816)

對(duì)資源的不斷索取以及人口密集化等因素使得各種災(zāi)害風(fēng)險(xiǎn)不斷交織，不斷疊加，各種自然災(zāi)害、社會(huì)事故屢見(jiàn)不鮮，對(duì)人們正常生活造成嚴(yán)重影響，威脅著其生命安全，人們所面臨的形勢(shì)和困難前所未有。各類突發(fā)性事件考驗(yàn)國(guó)家災(zāi)害處置能力。提前建立好應(yīng)急物流設(shè)施，合理地選址以及布局不僅能及時(shí)應(yīng)對(duì)突發(fā)事件，保障救援工作快速運(yùn)行，更能進(jìn)一步豐富完善中國(guó)應(yīng)急體系建設(shè)。

目前，國(guó)內(nèi)外許多學(xué)者對(duì)應(yīng)急物流設(shè)施選址問(wèn)題中的不確定性因素進(jìn)行了研究。馮春等[1]計(jì)算比較了魯棒優(yōu)化模型RO和隨機(jī)優(yōu)化模型SO兩類選址模型，證明魯棒優(yōu)化法相對(duì)于隨機(jī)優(yōu)化法的優(yōu)異性。杜博等[2]以各項(xiàng)成本為目標(biāo)建立了兩階段魯棒優(yōu)化模型，協(xié)同優(yōu)化預(yù)選址、重選址之間關(guān)系并與傳統(tǒng)p中心模型比較。高雷阜等[3]在構(gòu)建確定型模型的基礎(chǔ)上將不確定因素描述為橢圓形集合，建立目標(biāo)函數(shù)為最小加權(quán)距離魯棒優(yōu)化模型。Karamyar等[4]研究了不確定情景下醫(yī)院的選址和服務(wù)分配魯棒模型，并用包含模擬退火法以及Benders分解的混合算法對(duì)模型進(jìn)行驗(yàn)證。De Mattos[5]以成本為主要因素建立魯棒模型，并用分層優(yōu)化的方法減輕每個(gè)約束所設(shè)置特定魯棒性的負(fù)擔(dān)。張聆曄等[6]考慮海上應(yīng)急效率，通過(guò)離散情景對(duì)魯棒優(yōu)化模型求解。郭子雪[7]等學(xué)者利用梯形模糊數(shù)為參數(shù)，以加權(quán)距離最小為目標(biāo)函數(shù)構(gòu)建選址模型并進(jìn)行了驗(yàn)證計(jì)算。朱曉霞等[8]分析選址影響因素建立了混合多屬性指標(biāo)體系，并將這些指標(biāo)轉(zhuǎn)化為三角模糊數(shù)對(duì)模型進(jìn)行計(jì)算。Yadav等[9]將模糊邏輯與分析網(wǎng)絡(luò)過(guò)程相結(jié)合，呈現(xiàn)旋風(fēng)災(zāi)害防備活動(dòng)的識(shí)別與評(píng)估過(guò)程。Sarma等[10]用梯形模糊數(shù)和中智數(shù)表示模型中的不確定參數(shù)，以應(yīng)對(duì)災(zāi)后應(yīng)急設(shè)施選址成本最小化問(wèn)題。趙遠(yuǎn)飛等[11]通過(guò)分析應(yīng)急設(shè)施選址各種因素，利用層次分析法對(duì)TOPSIS法改進(jìn)，科學(xué)有效地處理選址優(yōu)化問(wèn)題，提高了模型的適應(yīng)性。

上述文獻(xiàn)大多以魯棒優(yōu)化以及模糊數(shù)等方法解決模型中的不確定性參數(shù)，本文以前者理論研究為基礎(chǔ)，針對(duì)突發(fā)情景下數(shù)據(jù)短缺、需求不確定等問(wèn)題，采用基于灰色預(yù)測(cè)模型對(duì)需求進(jìn)行預(yù)測(cè)并通過(guò)非支配排序遺傳算法對(duì)模型進(jìn)行求解，并通過(guò)實(shí)例對(duì)模型有效性進(jìn)行相關(guān)驗(yàn)證。

1 應(yīng)急物流設(shè)施選址模型構(gòu)建與求解

1.1 問(wèn)題描述

為預(yù)防突發(fā)事件需要在若干個(gè)地點(diǎn)選擇建立應(yīng)急物流設(shè)施，在有限時(shí)間內(nèi)預(yù)測(cè)應(yīng)急物資數(shù)量并運(yùn)送至已知需求點(diǎn)，實(shí)現(xiàn)快速對(duì)受災(zāi)地區(qū)進(jìn)行救援。假設(shè)已知受災(zāi)區(qū)域物資需求點(diǎn)，應(yīng)急物流設(shè)施只能從若干備選點(diǎn)選擇，且各應(yīng)急物流設(shè)施均能滿足需求點(diǎn)供需要求；各受災(zāi)區(qū)域需求點(diǎn)對(duì)救援物資的需求量是不確定的，可由多個(gè)應(yīng)急設(shè)施提供物資輸送并且應(yīng)急設(shè)施可向多個(gè)需求點(diǎn)提供服務(wù)。

選址模型需要解決的問(wèn)題是: 對(duì)各個(gè)需求點(diǎn)所需要的物資進(jìn)行預(yù)測(cè)；在滿足目標(biāo)函數(shù)下求得最優(yōu)Pareto解集并得到選址以及調(diào)度方案。

1.2 基于聯(lián)系數(shù)的區(qū)間灰數(shù)

1.3 參數(shù)定義

I為已知需求點(diǎn)集合，i∈I；J為潛在應(yīng)急物流設(shè)施備選點(diǎn)集合，j∈J；Qj為應(yīng)急物流設(shè)施最大儲(chǔ)備容量；qj為應(yīng)急物流設(shè)施現(xiàn)儲(chǔ)備物資量；cj為建立應(yīng)急物流設(shè)施所需相關(guān)成本；?i為需求點(diǎn)i預(yù)測(cè)物資需求量；lj為應(yīng)急物流設(shè)施物資儲(chǔ)存成本；pij表示由備選點(diǎn)j運(yùn)送物資到需求點(diǎn)i的單位價(jià)格；tij表示由備選點(diǎn)j運(yùn)送應(yīng)急物資到需求點(diǎn)i所需要的時(shí)間；μi為未能滿足需求點(diǎn)i物資所產(chǎn)生的懲罰成本；wi為各個(gè)需求點(diǎn)的權(quán)重；θi為未能在響應(yīng)時(shí)間內(nèi)完成需求點(diǎn)i服務(wù)的延時(shí)成本；Ti為各個(gè)需求點(diǎn)物資服務(wù)需要的響應(yīng)時(shí)間。

決策變量：qij表示由備選點(diǎn)j運(yùn)送物資到需求點(diǎn)i的數(shù)量；Xj為0～1變量，當(dāng)Xj取1時(shí)，表示在該點(diǎn)建立應(yīng)急物流設(shè)施，取0則表示不建立；γij為0～1變量，當(dāng)γij取1時(shí)，表示備選點(diǎn)j向需求點(diǎn)i運(yùn)送應(yīng)急物資，否則不運(yùn)送。

1.4 模型建立

建立的多目標(biāo)優(yōu)化模型是選取若干個(gè)應(yīng)急物流設(shè)施，使得受災(zāi)區(qū)域所建立設(shè)施到需求點(diǎn)滿足時(shí)效性、滿意度、成本3個(gè)目標(biāo)。依據(jù)上述建立如下優(yōu)化模型：

1)目標(biāo)函數(shù)。為滿足時(shí)效性目標(biāo)，建立子目標(biāo)F1為

(1)

式(1)表示最小化備選點(diǎn)j運(yùn)送物資到需求點(diǎn)i的總時(shí)間。

為滿足服務(wù)滿意度目標(biāo)，建立子目標(biāo)F2為

(2)

式(2)是為了所覆蓋區(qū)域需求點(diǎn)滿意度最大化，為了簡(jiǎn)便計(jì)算，引入文獻(xiàn)[14]中線性時(shí)間滿意度函數(shù)，同時(shí)設(shè)立參數(shù)Li和Ui，前者表示為需求點(diǎn)i非常滿意時(shí)所能接受的最長(zhǎng)等待時(shí)間，后者表示為需求點(diǎn)i非常不滿意時(shí)的最短等待時(shí)間，當(dāng)tijUi時(shí)，f(tij)=0；當(dāng)tij∈[Li,Ui]時(shí)，f(tij)=(Ui-tij)/(Ui-Li)。

為滿足成本目標(biāo)，建立子目標(biāo)F3為

(3)

式(3)表示整個(gè)應(yīng)急物流系統(tǒng)所產(chǎn)生的費(fèi)用最低，第1項(xiàng)表示設(shè)施建設(shè)成本和運(yùn)營(yíng)成本，第2項(xiàng)表示應(yīng)急物資運(yùn)輸成本以及未達(dá)到響應(yīng)時(shí)間產(chǎn)生的延時(shí)成本，第3項(xiàng)表示未滿足需求點(diǎn)服務(wù)產(chǎn)生的懲罰成本。

2)約束條件。各應(yīng)急物流設(shè)施點(diǎn)容量存在限制，即

0≤qj≤QjXj

(4)

建立的應(yīng)急設(shè)施數(shù)量應(yīng)該滿足

(5)

只有備選點(diǎn)已建立應(yīng)急物流設(shè)施才能向需求點(diǎn)運(yùn)送物資,即

?i∈I,γij-Xj≤0

(6)

任一需求點(diǎn)至少有一個(gè)應(yīng)急物流設(shè)施進(jìn)行物資運(yùn)送，即

(7)

需求點(diǎn)物資最低需求必須得到滿足

(8)

運(yùn)送物資的數(shù)量不超過(guò)備選點(diǎn)現(xiàn)有容量，即

(9)

γij∈{0,1},Xj∈{0,1}

(10)

1.5 模型求解

建立的選址模型可歸納為多目標(biāo)優(yōu)化問(wèn)題(MOP)，它包含3個(gè)目標(biāo)函數(shù)：時(shí)間、成本、滿意度，3個(gè)目標(biāo)函數(shù)之間存在一定制約關(guān)系，無(wú)法同時(shí)得到三者的最優(yōu)解。因此采用帶精英制的非支配遺傳算法(NSGA-Ⅱ)[15]對(duì)模型進(jìn)行求解。該算法基本流程如下：

1)種群初始化。采用實(shí)數(shù)編碼的形式隨機(jī)產(chǎn)生Pt個(gè)個(gè)體組成種群，假設(shè)突發(fā)事件種類為1，需求點(diǎn)為i，待選應(yīng)急物流設(shè)施點(diǎn)為j，則該模型決策變量為(2i+1)j個(gè)。

2)快速非支配排序。選取兩個(gè)個(gè)體分別記為xi與xj(j≠i)，比較它們的支配關(guān)系，相比之下xi最優(yōu)則將它進(jìn)行標(biāo)記。令i=i+1，所找到的每個(gè)最優(yōu)的個(gè)體被稱為非支配個(gè)體。這些最優(yōu)個(gè)體組成第一級(jí)非支配層，然后，去除已被標(biāo)記的非支配個(gè)體，再重復(fù)上述步驟，得到第n級(jí)非支配層。

3)擁擠度計(jì)算。在每一個(gè)非支配層對(duì)個(gè)體依據(jù)目標(biāo)函數(shù)值進(jìn)行排序，計(jì)算個(gè)體的擁擠度。

4)遺傳操作。和傳統(tǒng)遺傳算法一樣包含選擇、交叉、變異3部分。首先通過(guò)錦標(biāo)賽的形式從父代種群選取兩個(gè)個(gè)體，對(duì)選擇的個(gè)體進(jìn)行交叉，交叉點(diǎn)隨機(jī)生成直至產(chǎn)生規(guī)模大小和父代種群一樣的子代種群，選擇部分個(gè)體變異。

5)精英策略。將子代種群放入父代種群形成2倍大小的新種群，以非支配排序后以及擁擠度計(jì)算選取優(yōu)良個(gè)體構(gòu)成下次迭代的父代種群，重復(fù)前面步驟直到程序結(jié)束。

NSGA-Ⅱ算法流程如圖1所示。

圖1 NSGA-Ⅱ算法流程

2 實(shí)例分析

某地區(qū)應(yīng)急物資需求點(diǎn)的數(shù)量為8個(gè)，需要在10個(gè)應(yīng)急物流設(shè)施備選點(diǎn)選取若干個(gè)對(duì)需求點(diǎn)進(jìn)行物資輸送。已知應(yīng)急物資單位儲(chǔ)存成本為1萬(wàn)元/萬(wàn)件，應(yīng)急物資的運(yùn)輸成本為0.2萬(wàn)元/萬(wàn)件，未能在響應(yīng)時(shí)間內(nèi)送達(dá)的延時(shí)成本為1.2萬(wàn)元，運(yùn)送應(yīng)急物資未能滿足需求點(diǎn)需要的懲罰成本為5萬(wàn)元。表1為應(yīng)急物流設(shè)施備選點(diǎn)相關(guān)參數(shù)設(shè)置，表2為各備選點(diǎn)到達(dá)需求點(diǎn)的時(shí)間。

表1 擬建應(yīng)急物流設(shè)施建設(shè)成本和儲(chǔ)備容量

表2 擬建應(yīng)急物流設(shè)施備選點(diǎn)到需求點(diǎn)的時(shí)間 單位：h

2.1 需求預(yù)測(cè)

對(duì)8個(gè)需求點(diǎn)應(yīng)急物資需求量進(jìn)行灰色預(yù)測(cè)，預(yù)測(cè)結(jié)果見(jiàn)表3。預(yù)測(cè)模型檢驗(yàn)結(jié)果見(jiàn)表4。通過(guò)計(jì)算級(jí)比表示該數(shù)據(jù)可以用灰數(shù)模型進(jìn)行預(yù)測(cè)，從平均級(jí)比偏差值和殘差可以看出兩者均小于0.1，相對(duì)誤差較小，表示達(dá)到較高要求。其中同部序列方差比為0.126，異部序列方差比為0.468 1，建模精度分別為1級(jí)、2級(jí)，表明對(duì)應(yīng)急物資的需求預(yù)測(cè)具有較高的精度，預(yù)測(cè)結(jié)果較為準(zhǔn)確。

表3 各需求點(diǎn)的預(yù)測(cè)需求量、響應(yīng)時(shí)間以及需求點(diǎn)的權(quán)重wi

表4 預(yù)測(cè)模型檢驗(yàn)結(jié)果

2.2 模型求解

實(shí)驗(yàn)過(guò)程通過(guò)Python編程，初始種群規(guī)模大小設(shè)置為500個(gè)，交叉概率設(shè)為0.9，變異概率為0.1，進(jìn)行1 000次迭代，算法不斷迭代直至收斂總用時(shí)19.9 s，共找到非支配個(gè)體數(shù)500個(gè)，單位時(shí)間找到帕累托前沿點(diǎn)個(gè)數(shù)為25個(gè)，帕累托最優(yōu)解集分布如圖2所示。模型所得選址結(jié)果為(0,1,0,1,1,1,0,0,1,1)，即在備選點(diǎn)2、4、5、6、9、10建立應(yīng)急物流設(shè)施，表5為模型運(yùn)行結(jié)果中的4個(gè)物資調(diào)度方案目標(biāo)函數(shù)值，表6為方案1的具體調(diào)度措施。

圖2 帕累托最優(yōu)解集分布

通過(guò)對(duì)表5進(jìn)行分析可以看出，運(yùn)送時(shí)間、服務(wù)滿意度、總成本3個(gè)目標(biāo)函數(shù)之間緊密聯(lián)系又彼此限制，當(dāng)運(yùn)送時(shí)間一定時(shí)，服務(wù)滿意度的增加會(huì)導(dǎo)致總成本的增加；當(dāng)服務(wù)滿意度一定時(shí)，增加總成本可以減少救援時(shí)間；當(dāng)總成本恒定，運(yùn)送時(shí)間的減少導(dǎo)致救援物資數(shù)量較少，降低了服務(wù)滿意度。對(duì)于決策者而言，如果要盡可能地提高需求點(diǎn)服務(wù)滿意度，那么可以通過(guò)增加應(yīng)急物資的數(shù)量、提高救援速度等方式；如果要在最低滿意度的情況下，盡可能地減少救援時(shí)間，則需要對(duì)成本進(jìn)行投入。

表5 調(diào)度方案目標(biāo)函數(shù)值

由表6可知，當(dāng)指標(biāo)為1時(shí)，選建應(yīng)急物流設(shè)施才能對(duì)需求點(diǎn)進(jìn)行服務(wù)，如需求點(diǎn)7和8由2號(hào)備選點(diǎn)服務(wù)。觀察表格可以發(fā)現(xiàn)應(yīng)急物資運(yùn)送數(shù)量均能滿足需求點(diǎn)的最低需求，且調(diào)運(yùn)的數(shù)量小于設(shè)施持有量，4、5備選點(diǎn)所建設(shè)施倉(cāng)庫(kù)容量遠(yuǎn)大于物資調(diào)運(yùn)量，決策者可適當(dāng)減小物流設(shè)施規(guī)模以免造成資金浪費(fèi)。由于突發(fā)事件下所處情景不同，決策者決策偏好側(cè)重點(diǎn)也不一樣，本文所得選址以及調(diào)度方案具備一定參考價(jià)值。

表6 方案1具體調(diào)度措施

3 結(jié)論

建立了以總成本、運(yùn)送時(shí)間、服務(wù)滿意度為目標(biāo)的應(yīng)急物流設(shè)施選址模型，通過(guò)灰色預(yù)測(cè)模型對(duì)需求點(diǎn)進(jìn)行應(yīng)急物資預(yù)測(cè)將突發(fā)事件下的需求不確定性進(jìn)行轉(zhuǎn)化，同時(shí)利用NSGA-Ⅱ?qū)x址多目標(biāo)優(yōu)化問(wèn)題進(jìn)行求解，所得Pareto前沿分布均勻，算法穩(wěn)定性好，對(duì)實(shí)際選址問(wèn)題具有一定參考性。

研究?jī)H對(duì)需求的不確定性進(jìn)行了重點(diǎn)分析，忽視了突發(fā)事件以及需求物資的多樣性等不確定因素，今后研究可將多種不確定性因素納入模型中。