基于免疫優(yōu)化算法的應(yīng)急物資儲(chǔ)備庫(kù)選址

張愛琳，劉曉佳，何利軍

(集美大學(xué)航海學(xué)院，福建 廈門 361021)

0 引言

災(zāi)后應(yīng)急物資不同于一般物資，它具有時(shí)效性、不確定性、弱經(jīng)濟(jì)性和非常規(guī)性等特征，而應(yīng)急物資儲(chǔ)備庫(kù)選址直接影響著物資運(yùn)輸?shù)臅r(shí)效性。為了達(dá)到時(shí)間效益最大化或?yàn)?zāi)害損失最小化的目的，國(guó)內(nèi)外許多學(xué)者從不同角度運(yùn)用不同的方法對(duì)應(yīng)急物資儲(chǔ)備庫(kù)選址進(jìn)行了深入研究。Sheu[1]針對(duì)緊急救援期間的應(yīng)急需求，提出了一種混合模糊聚類優(yōu)化方法，以需求滿足率最大為目標(biāo)函數(shù)并設(shè)計(jì)了動(dòng)態(tài)規(guī)劃算法求解。Pereira等[2]以最小化距離和成本為優(yōu)化目標(biāo)建立最大覆蓋概率的應(yīng)急設(shè)施選址優(yōu)化模型，提出一種混合算法求解模型。Yang等[3]提出一種模糊多目標(biāo)規(guī)劃和遺傳算法相結(jié)合的方法，以成本和最遠(yuǎn)距離最小為目標(biāo)建立雙目標(biāo)選址模型。Ai等[4]針對(duì)海上應(yīng)急系統(tǒng)中應(yīng)急物資儲(chǔ)備庫(kù)選址問題，提出一種離散的多目標(biāo)非線性整數(shù)規(guī)劃模型，并用遺傳算法求解了該模型。王芳等[5]采用R因子分析法計(jì)算出應(yīng)急物資儲(chǔ)備設(shè)施備選點(diǎn)，再以設(shè)施點(diǎn)與應(yīng)急需求點(diǎn)距離之和最小為目標(biāo)函數(shù)構(gòu)建應(yīng)急物資儲(chǔ)備庫(kù)選址模型。吳坷等[6]運(yùn)用弗洛伊德最短路徑算法以時(shí)間成本為目標(biāo)函數(shù)值，計(jì)算出最短路徑長(zhǎng)度，以便確定應(yīng)急資源儲(chǔ)備點(diǎn)的個(gè)數(shù)以及位置分布。趙玲等[7]針對(duì)應(yīng)急環(huán)境的復(fù)雜性和不確定性，構(gòu)建了基于三角模糊數(shù)的最大覆蓋模型。俞武揚(yáng)等[8]構(gòu)建了基于最小風(fēng)險(xiǎn)的應(yīng)急服務(wù)設(shè)施選址模型，設(shè)計(jì)改進(jìn)后的模擬退火算法對(duì)模型進(jìn)行求解，提出應(yīng)急服務(wù)設(shè)施選址優(yōu)化策略。

可以看出，多數(shù)應(yīng)急物資儲(chǔ)備庫(kù)選址的研究都是以時(shí)間效益最大化為目標(biāo)函數(shù)建立選址模型。在應(yīng)急物資儲(chǔ)備庫(kù)選址的研究中不但要關(guān)注時(shí)間效益，同時(shí)也需要考慮到應(yīng)急系統(tǒng)一旦建立后所帶來的社會(huì)效益，譬如公眾的“易接近性”。Church等[9]曾表示，確定公眾到設(shè)施的平均距離是測(cè)量某個(gè)應(yīng)急系統(tǒng)位置有效性的重要方式，平均距離上升，設(shè)施的易接近性下降。以往的選址模型忽略了各個(gè)應(yīng)急需求點(diǎn)的風(fēng)險(xiǎn)權(quán)重，不同應(yīng)急需求點(diǎn)的風(fēng)險(xiǎn)權(quán)重是不同的。因此，本文針對(duì)應(yīng)急物資運(yùn)輸調(diào)度的時(shí)效性特點(diǎn)，從應(yīng)急物資儲(chǔ)備庫(kù)的“易接近性”出發(fā)，利用三角模糊數(shù)對(duì)應(yīng)急需求點(diǎn)歷史災(zāi)害事件數(shù)據(jù)進(jìn)行模糊化處理，引入風(fēng)險(xiǎn)權(quán)重系數(shù)，建立應(yīng)急物資儲(chǔ)備庫(kù)選址模型。構(gòu)建的選址模型目標(biāo)函數(shù)在滿足設(shè)置的約束條件下取最小值，即實(shí)現(xiàn)了應(yīng)急物資運(yùn)輸距離最短或用時(shí)最少。鑒于模型非凸和非光滑的非線性結(jié)構(gòu)特點(diǎn)，利用具有良好自適應(yīng)性的免疫優(yōu)化算法進(jìn)行求解。最后結(jié)合實(shí)例進(jìn)行分析，獲得最優(yōu)可行解，為決策者提供方案選擇。

1 應(yīng)急物資選址優(yōu)化模型

1.1 問題描述

災(zāi)害事件發(fā)生時(shí)，制定應(yīng)急物資調(diào)度方案需要對(duì)多個(gè)應(yīng)急需求點(diǎn)進(jìn)行處理，通常情況下一般物資的運(yùn)輸調(diào)度只考慮經(jīng)濟(jì)效益，但在災(zāi)害情況下的應(yīng)急物資運(yùn)輸調(diào)度更大程度上考慮的是時(shí)效性。為了實(shí)現(xiàn)對(duì)某一區(qū)域應(yīng)急需求點(diǎn)和重要高危需求點(diǎn)的全面覆蓋，需要解決如下問題：1)應(yīng)急物資儲(chǔ)備庫(kù)到需求點(diǎn)的時(shí)間最少或距離最短，以便在災(zāi)害事件發(fā)生時(shí)能夠快速到達(dá)應(yīng)急需求點(diǎn)；2)在模型中引入應(yīng)急需求點(diǎn)的風(fēng)險(xiǎn)權(quán)重系數(shù)，保證應(yīng)急物資儲(chǔ)備庫(kù)設(shè)置在風(fēng)險(xiǎn)權(quán)重較高的需求點(diǎn)附近；3)每個(gè)應(yīng)急物資儲(chǔ)備庫(kù)的應(yīng)急救援能力有限，超過其能力范圍外，則儲(chǔ)備庫(kù)無法對(duì)應(yīng)急需求點(diǎn)提供應(yīng)急物資，因此保證任何一個(gè)需求點(diǎn)至少有一個(gè)應(yīng)急物資儲(chǔ)備庫(kù)提供應(yīng)急救援。

模型假設(shè)如下：

1)假設(shè)接到預(yù)警通知后，應(yīng)急物資儲(chǔ)備庫(kù)馬上展開應(yīng)急行動(dòng)；

2)各運(yùn)輸工具均滿載應(yīng)急物資正常運(yùn)行，物資流為單向流，考慮到裝卸時(shí)間差別不大，因此在模型中不做考慮，只求解最小運(yùn)輸距離；

3)不考慮應(yīng)急物資儲(chǔ)備庫(kù)到應(yīng)急需求點(diǎn)的運(yùn)輸費(fèi)用。

1.2 模型構(gòu)建

根據(jù)以上分析，可建立如下選址模型。

約束條件：

應(yīng)急物資儲(chǔ)備庫(kù)到應(yīng)急需求點(diǎn)的距離要滿足其應(yīng)急救援半徑的要求，sj為應(yīng)急物資儲(chǔ)備庫(kù)的應(yīng)急救援半徑，則dij≤sj。

1.3 三角模糊數(shù)學(xué)理論

由于每個(gè)地區(qū)的地理位置不同，氣候和地殼運(yùn)動(dòng)等信息難以預(yù)測(cè)，使得災(zāi)害事件的發(fā)生具有較大的不確定性，只能類比該地區(qū)已發(fā)生的災(zāi)害事件來估計(jì)該地區(qū)的災(zāi)害事件區(qū)間值，從而得到上述模型中各地區(qū)的風(fēng)險(xiǎn)權(quán)重系數(shù)。三角模糊數(shù)就是為了解決不確定環(huán)境下的問題，因此先剔除一些非常規(guī)異常數(shù)據(jù)，再利用三角模糊數(shù)對(duì)各地區(qū)往年災(zāi)害事件數(shù)進(jìn)行模糊處理。對(duì)于三角模糊數(shù)A=(a,b,c)，其中：a≤b≤c，a,b,c∈R，則其隸屬度為：

(1)

對(duì)于三角模糊數(shù)的比較，可利用該模糊數(shù)的整體期望值進(jìn)行去模糊化處理[11]。若A是一模糊數(shù)，其隸屬函數(shù)定義如式(1)所示，可知該模糊數(shù)的整體期望值為：IT(A)=[IL(A)+IR(A)]/2。式中：IT(A)表示該模糊數(shù)的整體期望值；IL(A)代表模糊數(shù)的左期望值；IR(A)代表模糊數(shù)的右期望值。對(duì)于A=(a,b,c)，有IT(A)=(a+c+2b)/4。

2 模型求解

本文建立的應(yīng)急物資儲(chǔ)備庫(kù)選址模型屬于NP-hard問題，精確求解的計(jì)算量會(huì)隨問題規(guī)模的增加呈指數(shù)形式增長(zhǎng)，為避免陷入局部最優(yōu)解，采用免疫優(yōu)化算法求解該模型。

免疫優(yōu)化算法的核心思想是：選擇一組任意解，輸入目標(biāo)約束條件，然后隨機(jī)進(jìn)行交叉、選擇以及變異操作來提高種群進(jìn)化的自我解決問題的能力，更大程度提高其適應(yīng)度，避免群體的退化，最終求得全局最優(yōu)解[12]。它利用免疫系統(tǒng)的整體多樣性和個(gè)體特異性來保持群體的多樣性，避免了在該問題尋優(yōu)過程中難以處理的“早熟”問題。因此，本文利用免疫優(yōu)化算法跳出局部最優(yōu)解和增強(qiáng)算法遍歷尋優(yōu)能力，可以有效而快速地求得應(yīng)急物資儲(chǔ)備庫(kù)選址模型的最優(yōu)解或近似最優(yōu)解。

免疫優(yōu)化算法流程如圖1所示。

2.1 產(chǎn)生初始抗體群

將要解決的問題看作抗原，抗原識(shí)別即問題識(shí)別，對(duì)問題進(jìn)行分析后，設(shè)計(jì)出解的合適表達(dá)形式?？梢圆捎眠z傳算法中的簡(jiǎn)單編碼方式，每個(gè)選址方案形成一個(gè)長(zhǎng)度為q的抗體(q表示應(yīng)急物資儲(chǔ)備庫(kù)數(shù)量)，每個(gè)抗體表示被選為應(yīng)急物資儲(chǔ)備庫(kù)的序列。例如，考慮包含32個(gè)需求點(diǎn)的問題,1，2，…，32代表需求點(diǎn)的序號(hào)，從中選出7個(gè)作為儲(chǔ)備庫(kù)?？贵w[3,9,14,17,25,28,35]代表一個(gè)可行解向量，它表示3、9、14、17、25、28、35被選為儲(chǔ)備庫(kù)。

2.2 解的多樣性評(píng)價(jià)

1)抗體與抗原之間的親和力。

抗體與抗原之間的親和力用于表明抗體對(duì)抗原的識(shí)別程度，針對(duì)應(yīng)急物資儲(chǔ)備庫(kù)選址模型設(shè)計(jì)了親和力函數(shù)Av，

2)兩抗體之間的親和力。

抗體與抗體之間的親和力用于表明兩抗體之間的相似程度，即Sv,s=kv,s/L。其中：kv,s為抗體v與抗體s中相同的位數(shù)；L為抗體的長(zhǎng)度。

3)評(píng)價(jià)解的濃度。

4)期望繁殖概率。

每個(gè)個(gè)體的期望繁殖概率由Av和Cv兩部分共同決定，即P=α(Av/∑Av)+(1-α)(Cv/∑Cv)。其中：α為常數(shù)。個(gè)體的適應(yīng)度越高，則期望繁殖概率就越大；個(gè)體濃度越大，則期望繁殖概率就越小。

3 算例分析

安徽省作為南北地理交匯的過渡地帶，因其特殊的地理位置，天然匯聚低溫冷凍災(zāi)害、干旱、雨雪冰凍災(zāi)害、洪澇、臺(tái)風(fēng)以及次生災(zāi)害等時(shí)有發(fā)生[13]。利用本文設(shè)計(jì)模型和算法對(duì)安徽省應(yīng)急物資儲(chǔ)備庫(kù)選址進(jìn)行研究分析。該省有16個(gè)地級(jí)市，要在這些地級(jí)市中選擇7個(gè)地區(qū)作為應(yīng)急物資儲(chǔ)備庫(kù)，為其余9個(gè)應(yīng)急需求點(diǎn)提供應(yīng)急物資救援(如果在該地區(qū)建有應(yīng)急物資儲(chǔ)備庫(kù)，則該地物資由本地應(yīng)急物資儲(chǔ)備庫(kù)供應(yīng))。

根據(jù)建立的模型，需要知道各地區(qū)的風(fēng)險(xiǎn)權(quán)重系數(shù)，利用該地區(qū)發(fā)生自然災(zāi)害等突發(fā)事件的歷史頻率乘以地區(qū)人口數(shù)并歸一化來表示該地區(qū)的風(fēng)險(xiǎn)權(quán)重系數(shù)。由于災(zāi)害事件的發(fā)生具有很大的不確定性，因此先剔除一些非常規(guī)異常數(shù)據(jù)，再利用三角模糊數(shù)對(duì)16個(gè)地區(qū)2010—2017年災(zāi)害事件起數(shù)進(jìn)行模糊處理，處理后的歷史災(zāi)害起數(shù)統(tǒng)計(jì)見表1。表1中列出各地區(qū)人口數(shù)量以及各地區(qū)的幾何中心坐標(biāo)，在實(shí)際運(yùn)算中將其視為平面坐標(biāo)，以便計(jì)算各地區(qū)間的距離。

表1 各地區(qū)坐標(biāo)、風(fēng)險(xiǎn)權(quán)重系數(shù)及人口數(shù)量

根據(jù)應(yīng)急物資儲(chǔ)備庫(kù)選址優(yōu)化模型，在Window 10系統(tǒng)下，運(yùn)行內(nèi)存為8GB的運(yùn)行環(huán)境下，利用Matlab編程，按照免疫優(yōu)化算法步驟對(duì)模型進(jìn)行求解。求解過程收斂曲線如圖2所示。從表2可以看出，隨著初始種群規(guī)模的增大，迭代次數(shù)增加，目標(biāo)函數(shù)值逐漸變小，但同時(shí)運(yùn)行時(shí)間也越來越長(zhǎng)。當(dāng)初始種群規(guī)模為50，迭代次數(shù)增加到300以后，適應(yīng)度函數(shù)值基本穩(wěn)定。

表2 不同種群規(guī)模與迭代次數(shù)的運(yùn)行結(jié)果對(duì)比

采用免疫優(yōu)化算法對(duì)模型進(jìn)行求解，選擇初始種群規(guī)模為50，迭代次數(shù)為500次，可以求得較好的結(jié)果，此時(shí)運(yùn)行結(jié)果為[2,13,6,9,15,3,10]。選出的應(yīng)急物資儲(chǔ)備庫(kù)與各應(yīng)急需求點(diǎn)詳見圖3，圖3中方框表示應(yīng)急物資儲(chǔ)備庫(kù)，圓點(diǎn)表示城市點(diǎn)，若點(diǎn)間有連線表示該點(diǎn)的應(yīng)急物資由連接的應(yīng)急物資儲(chǔ)備庫(kù)供應(yīng)。

從圖3可以看出，求解得到的應(yīng)急物資儲(chǔ)備庫(kù)選址地點(diǎn)分別為阜陽(yáng)、六安、淮北、蚌埠、池州、蕪湖和黃山。經(jīng)查閱資料可知安徽省現(xiàn)有應(yīng)急物資儲(chǔ)備庫(kù)分別位于阜陽(yáng)、六安、淮北、蚌埠、池州及蕪湖。求解結(jié)果與安徽省現(xiàn)有應(yīng)急物資儲(chǔ)備庫(kù)選址基本一致，而黃山市地處皖南山區(qū),區(qū)域地質(zhì)環(huán)境脆弱,災(zāi)害頻發(fā)，在黃山市建設(shè)應(yīng)急物資儲(chǔ)備庫(kù)，可以有效地彌補(bǔ)救助力量的薄弱區(qū)。

4 結(jié)論

本文以應(yīng)急物資儲(chǔ)備庫(kù)到各應(yīng)急需求點(diǎn)風(fēng)險(xiǎn)加權(quán)距離最小為目標(biāo)函數(shù)，建立了考慮時(shí)間和安全風(fēng)險(xiǎn)的選址模型，利用免疫優(yōu)化算法對(duì)模型進(jìn)行求解，并通過實(shí)例加以驗(yàn)證。驗(yàn)證結(jié)果表明，求解得到的應(yīng)急物資儲(chǔ)備庫(kù)選址地點(diǎn)與現(xiàn)有應(yīng)急物資儲(chǔ)備庫(kù)選址基本一致。此外，本文未考慮多種物資的情況以及不同應(yīng)急物資的優(yōu)先級(jí)問題，并且簡(jiǎn)略了裝卸時(shí)間，這些問題都有待于進(jìn)一步研究。