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

張愛琳，劉曉佳，何利軍

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

0 引言

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

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

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

1.1 問題描述

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

模型假設(shè)如下：

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

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

3)不考慮應(yīng)急物資儲備庫到應(yīng)急需求點的運輸費用。

1.2 模型構(gòu)建

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

約束條件：

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

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

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

(1)

對于三角模糊數(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ù)的右期望值。對于A=(a,b,c)，有IT(A)=(a+c+2b)/4。

2 模型求解

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

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

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

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

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

2.2 解的多樣性評價

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

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

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

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

3)評價解的濃度。

4)期望繁殖概率。

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

3 算例分析

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

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

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

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

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

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

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

4 結(jié)論

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