汪文文，方 璽，何 朗，劉 揚，張 亮

WANG Wenwen,FANG Xi,HE Lang,LIU Yang,ZHANG Liang

武漢理工大學(xué) 理學(xué)院，武漢 430070

School of Science,Wuhan University of Technology,Wuhan 430070,China

1 引言

近年來，國內(nèi)各種突發(fā)事件頻發(fā)，造成了極大的人員傷亡和經(jīng)濟損失，如2008年“5·12”汶川特大地震，2015年天津大爆炸，2016年湖北、安徽、河北多地區(qū)暴雨等。在突發(fā)事件[1]頻出不窮的情況下，應(yīng)急問題已經(jīng)成為十分緊迫的重大問題。在應(yīng)急管理中，應(yīng)急設(shè)施是救援過程中必不可少的組成部分，研究應(yīng)急管理中的設(shè)施選址對于提高應(yīng)急管理能力有重要的應(yīng)用價值，吸引了國內(nèi)外眾多研究學(xué)者的目光。

應(yīng)急選址優(yōu)化問題是城市應(yīng)急系統(tǒng)中不可或缺的一部分，近年來無數(shù)學(xué)者對其進行研究，提出不同的模型。Salman等[2]基于突發(fā)事件下的應(yīng)急選址，通過最大化需求覆蓋，提出0-1整數(shù)規(guī)劃求解；Wohlgemuth等[3]考慮最小化配送中心到需求點的距離、區(qū)域內(nèi)的需求點非覆蓋需求建立多目標(biāo)模型；由于傳統(tǒng)靜態(tài)、確定型選址模型在應(yīng)用上僅考慮單一時間，Ballou[4]首先提出了動態(tài)設(shè)施選址問題，研究了如何選擇一個倉庫使其在規(guī)劃期內(nèi)實現(xiàn)利潤最大；Gao等[5]將動態(tài)選址問題分為LAP與VRP兩部分，并在動態(tài)環(huán)境下考慮隨機與循環(huán)流量等因素，對模型進行求解；Marufuzzaman等[6]構(gòu)建一個基于容量的動態(tài)選址模型，以期在滿足需求點的需求條件下以最小的代價在決策時間內(nèi)給出選址方案；動態(tài)模型被運用到多個領(lǐng)域，如戰(zhàn)斗物流[7]、電商物流[8]、應(yīng)急物流等。由于靜態(tài)模型考慮其選址因素均獨立于時間，而動態(tài)選址考慮了在實際應(yīng)用中需求量、能源價格、市場增長等可變因素，其模型在實際應(yīng)用中具有更強的適應(yīng)性，且更加科學(xué)。

應(yīng)急選址所需要考慮的因素極為復(fù)雜，通常需要考慮多個因素，其所研究的問題為多目標(biāo)優(yōu)化問題，該優(yōu)化問題一般采用進化算法進行求解，例如SPEA、PSO、NSGA、MOEA/D。Dong等[9]提出一種基于MOEA/D的改進算法，通過多樣性檢測和混合種群操作增強解的全局搜索能力；MOEA/D算法效率較高，但其最優(yōu)解的分布隨機性較大；NSGA-II采用非支配排序機制降低算法的復(fù)雜度，且Pareto最優(yōu)解集具有良好的分布性，是一種綜合性能較好的算法。Badri等[10]構(gòu)建了一個有約束的多目標(biāo)優(yōu)化問題，并通過NSGA-II、SPEA2以及PESA-II進行求解，實驗結(jié)果顯示NSGA-II可產(chǎn)生相對較優(yōu)的Pareto前沿。由于NSGA-II在收斂過程中易產(chǎn)生重復(fù)個體而陷入早熟，對于NSGA-II算法的改進逐步被提出，Zade等[11]提出一種基于交叉和變異算子改進的NSGA-II，增強了解集的多樣性以及精確性，但增加了算法的計算量；常輝等[12]提出基于遞歸的快速排序法，增強了算法的魯棒性，降低了算法的復(fù)雜性，但其僅適用于雙目標(biāo)問題，而對于多目標(biāo)問題其效率則具有一定的局限性。在實際應(yīng)用中，單一的算法對于求解多目標(biāo)優(yōu)化問題往往已不能滿足需求，混合優(yōu)化算法逐步被提出，Li等[13]提出了一種基于改進的NSGA-II的二階段變量值選擇去解決包含多個解的質(zhì)量特性，但在降低算法復(fù)雜度的同時造成優(yōu)秀解在迭代過程中逐步損失。因此對于NSGA-II算法的改進仍需持續(xù)深入研究。本文擬通過將禁忌搜索算法融入到NSGA-II的精英策略中，加強算法的局部搜索能力，同時保留其多樣性以及分布性，并通過數(shù)值算例驗證算法的收斂性及分布性。

2 多目標(biāo)動態(tài)選址模型

2.1 應(yīng)急物資點選址決策目標(biāo)評價體系

本文考慮以救援時間為評價的主要指標(biāo)，用物資效用反映時效性，以災(zāi)區(qū)滿意度反映公平性，以臨時物資配送中心的個數(shù)反映均衡性，建立多目標(biāo)動態(tài)選址模型；在模型求解時，充分對3個目標(biāo)進行分析，通過改進的NSGA-II算法進行求解，得到更為合適的選址方案，對于應(yīng)急管理系統(tǒng)進行科學(xué)決策具有一定的指導(dǎo)意義。

2.2 基本參數(shù)與決策變量

假定平面上存在3個集合，即需求點集合、臨時物資候選點集合和固定物資點，已知任意兩個點之間的可行距離以及汽車運行速度，選取合適的臨時物資點，并得到最優(yōu)調(diào)度方案。本文考慮物資效用、臨時物資點個數(shù)以及災(zāi)區(qū)滿意度作為目標(biāo)函數(shù)，基本參數(shù)如下：在地震災(zāi)害中人的存活率與時間的關(guān)系，I為固定物資點集合，J為需求點集合，S為臨時物資候選點集合，V為各種汽車運行速度的集合。候選點s被選擇，則hs=1，否則hs=0。

2.3 多目標(biāo)動態(tài)選址模型

基于應(yīng)急物資中心選址決策目標(biāo)評價體系的分析，本文將物資儲備應(yīng)急效用、災(zāi)區(qū)滿意度、臨時物資點的數(shù)目作為目標(biāo)決策函數(shù)。

由文獻[14]知某次地震災(zāi)害后，受災(zāi)人員的存活率與時間的關(guān)系為：

定義物資儲備應(yīng)急效用為各個物資點的有效利用量：

定義受災(zāi)區(qū)域的滿意度為各個物資點（包括固定物資點和臨時物資點）的儲備效用與各個災(zāi)區(qū)所需要應(yīng)急物資之比，且災(zāi)區(qū)的滿意度值盡可能大，即：

式（5）保證了在固定物資點資源都用盡之后，才開始用臨時物資點；式（6）表明由臨時物資點運到各個災(zāi)區(qū)的資源量應(yīng)該小于其儲備量；式（7）表示運往災(zāi)區(qū)的物資量應(yīng)該小于其需求量，以減少不必要的經(jīng)濟損失；式（8）保證運輸量有意義。

本文所構(gòu)建的為多目標(biāo)動態(tài)選址模型，與傳統(tǒng)靜態(tài)選址模型的主要區(qū)別在于隨著災(zāi)害的持續(xù)發(fā)展，往往會導(dǎo)致災(zāi)區(qū)對于應(yīng)急物資的需求量逐步遞增，原有的物資點并不能向災(zāi)區(qū)提供充足的物資，此時會造成供不應(yīng)求的狀況。而本文所構(gòu)建的模型則將這一因素考慮進來，增加了模型的魯棒性。

針對自變量個數(shù)較多且最優(yōu)解較為復(fù)雜的多目標(biāo)優(yōu)化問題，傳統(tǒng)的目標(biāo)優(yōu)化算法MOEA/D、NSGA-II的收斂性以及所得解的精度均較差。同時MOEA/D進行加權(quán)存在一定的主觀因素，而本文所研究的背景為應(yīng)急物資選址，對于目標(biāo)函數(shù)的權(quán)重?zé)o法給出比較客觀的分析，而NSGA-II在迭代搜索過程中難以找到孤立點，且子代容易產(chǎn)生重復(fù)個體，因此本文擬在NSGA-II的基礎(chǔ)上加入禁忌搜索[15-16]算法設(shè)計一種混合優(yōu)化算法，以期算法能夠達到較強的收斂效果。

3NSGA-II及改進

本文研究的內(nèi)容為一個多目標(biāo)優(yōu)化問題，對于多目標(biāo)優(yōu)化問題，一般采用多目標(biāo)進化算法（MOEAs）[17]和多目標(biāo)轉(zhuǎn)換為單目標(biāo)兩種方式來進行求解，然而多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題則可能造成所求的解為非可行解，因此本文采用MOEAs進行求解。NSGA-II是一種較為常用的MOEAs算法，其優(yōu)點在于運行效率高，所得解集具有良好的分布性，其主要不足在于難以找到孤立點，且容易產(chǎn)生大量重復(fù)個體。為克服上述缺點，本文提出一種改進的NSGA-II算法，主要在以下兩方面進行改進：

（1）改進遺傳算子的變異操作，變異個體從當(dāng)前個體的領(lǐng)域產(chǎn)生，而非隨機生成，從而減少了重復(fù)個體產(chǎn)生的概率，同時提高了搜索效率。

（2）提出一種混合的精英策略，在進行合并的時候，將父代個體、遺傳算子所得的子代個體，以及禁忌搜索[18]所得子代進行合并，增強了子代群體的多樣性。

具體操作如下：

（1）變異算子的設(shè)計

變異算子影響著遺傳操作的效果，其可跳出局部最優(yōu)解，從而達到全局最優(yōu)解，而變異概率則影響著變異算子的效果。傳統(tǒng)的變異具有一定的隨機性，在搜索過程中易產(chǎn)生重復(fù)個體且具有一定的隨機性。本文采用變異個體從當(dāng)前解的鄰域中產(chǎn)生而非隨機產(chǎn)生，加強解的局部搜索效率，且變異概率Pm隨著所產(chǎn)生的鄰域解的效果而動態(tài)變化，當(dāng)鄰域最優(yōu)解滿足藐視準(zhǔn)則，則Pm=1，否則Pm=0。當(dāng)Pm=1時，則將當(dāng)前個體作為變異個體加入到子代種群中。通過這種改進，減少了重復(fù)個體產(chǎn)生的概率，同時提高了搜索效率?？梢酝ㄟ^增加搜索到孤立點的概率，從而增加個體的多樣性。

（2）混合精英策略

本文通過將禁忌搜索算法引入到精英策略中，以期增加解集的多樣性以及均勻性。令合并之后的解集為Rt=Pt?Gt?Tt，其中Pt為父代個體，Gt為遺傳算子所得個體，Tt為禁忌搜索算子所得個體。其次由非支配排序及擁擠度距離從Rt中選取前N個個體作為下一代父代個體Rt+1，通過這種操作可以保留NSGA-II避免父代優(yōu)良個體流失的優(yōu)點，同時增強局部搜索能力，進而減少子代中重復(fù)個體的個數(shù)，增強解集的多樣性。

禁忌搜索的策略如下：

（1）初始解

禁忌搜索算法對初始解的依賴性較高，因此初始解從父代個體非支配排序為1的個體中隨機選取。

（2）鄰域解

初始迭代，為增加搜索到最優(yōu)解的概率，擴大搜索范圍，隨著迭代的逐步進行，所得解趨近于最優(yōu)解，因此應(yīng)該縮小搜索的范圍，避免重復(fù)搜索。鄰域生成以及搜索范圍分別按以下公式更新：

邊界處理：

若Xj＞UX,Xj=Xj+LX-UX，否則Xj=Xj-(LXUX)。

（3）候選解

對于給定個體X，計算其所有鄰域解的計算量較大，因此需要一定的策略選取候選解。本文采用非支配排序和擁擠度算子從所給候選解里面選取一定數(shù)量的解作為候選解N(x)。

（4）藐視準(zhǔn)則

X∈opt{N(x)}，若存在X?Xbest，則X被選為下一個當(dāng)前解。

（5）禁忌表

當(dāng)前解X已被禁忌，當(dāng)且僅當(dāng)?Xj∈Tabulist，滿足

算法主要步驟如下：

步驟1產(chǎn)生初始種群Pop。

步驟2快速非支配排序，在進行選擇運算之間，根據(jù)個體非劣解的水平先對種群進行分層得到父代個體Pt。

步驟3遺傳算子操作（選擇、交叉和變異），變異算子采取本文所提方式進行，產(chǎn)生新的個體Gt。

步驟4禁忌搜索策略：按照本文所提的禁忌搜索算法的流程執(zhí)行，產(chǎn)生新的個體Tt。

步驟5精英策略，首先將父代Pt、遺傳算子Gt和禁忌搜索算子Tt合并成一個種群Rt=Pt?Gt?Tt，種群Rt的個體數(shù)目變?yōu)?N；其次，對種群Rt進行非支配排序，并計算相應(yīng)的擁擠度距離；最后，根據(jù)等級的高低逐一選取個體，直至個體總數(shù)達到N，令其為新一輪進化過程的父代種群Pt+1。

步驟6重復(fù)步驟3～步驟5直至滿足迭代終止條件。

根據(jù)步驟1～步驟6可得NSGA-II-TS算法設(shè)計流程圖如圖1所示。

圖1 NSGA-II-TS流程圖

禁忌搜索算法在搜索過程中所產(chǎn)生的候選解在其當(dāng)前解的鄰域產(chǎn)生，而非隨機生成，且其可以接受次優(yōu)解，具有較強的爬山能力，因此其搜索到最優(yōu)解的概率增大，同時保留了NSGA-II的遺傳算子操作，從而保留了NSGA-II所產(chǎn)生個體多樣且均勻的優(yōu)點。基于應(yīng)急選址對于實時性和優(yōu)化性同等重要，本文通過在NSGA-II精英策略中加入禁忌搜索算法，設(shè)計一種混合的進化優(yōu)化算法，一方面加強解的局部尋優(yōu)能力，另一方面保留NSGA-II較優(yōu)的全局搜索能力，從而使得收斂到局部最優(yōu)解的速度加快且所得解的精度提高。

4 數(shù)值算例及結(jié)果分析

仿真實驗分為兩部分：首先對有界閉域上連續(xù)函數(shù)全局優(yōu)化進行算法的有效性分析；其次將其應(yīng)用到離散應(yīng)急選址問題上進行算法分析。本文所有的仿真實驗平臺為Intel?CoreTMi5-4200H，4.0 GB RAM，實驗環(huán)境為MATLAB R2012b（8.0.0.783）。

4.1 連續(xù)函數(shù)的應(yīng)用

本文選擇經(jīng)典二維測試函數(shù)ZDT1、ZDT2、ZDT3[19]對算法進行實證分析，函數(shù)表達式如表1所示，選取經(jīng)典NSGA-II、MOEA/D與NSGA-II-TS進行對比分析，通過Pareto前沿對算法的收斂性以及分布性進行分析。

ZDT1、ZDT2、ZDT3分別在變量個數(shù)為30、100時進行測試，設(shè)置算法的種群大小為500，迭代次數(shù)為100，分別獨立運行20次，3種算法得到的Pareto前沿對比圖如圖2所示。從圖2的Pareto前沿對比圖中可以看出，通過NSGA-II-TS得到的Pareto收斂性以及多樣性明顯優(yōu)于NSGA-II和MOEA/D、NSGA-II-TS所得的Pareto光滑、均勻，且基本上和真實的Pareto重合，而MOEA/D所得Pareto存在較多間斷點，NSGA-II算法雖然得到的曲線形狀與真實的Pareto基本一致，但其收斂性遠(yuǎn)遠(yuǎn)不如NSGA-II-TS；同時隨著決策變量增加至100時，MOEA/D算法的效率明顯下降，逼近效果尤為差，且需要至少300次迭代才可較好地逼近，NSGA-II算法可在100次迭代中逼近真實Pareto，但其效果遠(yuǎn)遠(yuǎn)不如NSGA-II-TS。由此說明，無論是較少的決策變量還是較多的決策變量，NSGA-II-TS均可以較好地逼近最優(yōu)Pareto。

表1 測試函數(shù)

圖2 ZDT系列函數(shù)Pareto對比圖

表2 世代距離

表3 spacing指標(biāo)值

本文為進一步說明3種算法的收斂性以及解集的均勻性，分別采用Deb[20]提出的世代距離和Schott[21]提出的spacing，對算法進行定量分析。表2和表3分別為對ZDT系列函數(shù)在不同變量下測試20次所獲得的spacing以及世代距離的均值、標(biāo)準(zhǔn)差和中值。由表1和表2可以看出，在20次實驗中，NSGA-II-TS獲得的spacing值和世代距離值均小于NSGA-II、MOEA/D，且NSGA-II-TS的波動性比較小，這種優(yōu)勢在決策變量增加至100時更為明顯，說明本文算法在解決連續(xù)多目標(biāo)優(yōu)化問題上具有更好的收斂性。

4.2 應(yīng)用分析

設(shè)置候選臨時應(yīng)急物資點為100個，固定點為3個，需求點為10個，設(shè)定種群為100，迭代次數(shù)100，實驗20次，得到最優(yōu)Pareto解集。由于在實際應(yīng)急救援中需給出最優(yōu)行動方案，本文采用理想點法[11]對組合解的優(yōu)劣程度進行評判，得出在該標(biāo)準(zhǔn)下的最優(yōu)應(yīng)急方案。

首先，利用公式進行標(biāo)準(zhǔn)化：

其次，選擇理想點：

最后，使用歐式距離評測解的好壞，d(h)越小越好：

表4為各個算法通過理想點法所確定的最優(yōu)解。由表4可知，NSGA-II-TS效果比NSGA-II和MOEA/D算法好。首先，對于應(yīng)急物資點個數(shù)NSGA-II比NSGAII-TS少兩個，但其物資效用度卻比NSGA-II-TS小了833 m3，并且災(zāi)區(qū)的滿意度也比NSGA-II-TS小了4.6%，保證災(zāi)區(qū)人民的滿意度較大，且物資效用達到最大，同比增加兩個物資點是值得考慮的；其次，對于MOEA/D算法，其物資效用度平均值基本在47000以上，達到比較好的效果，與NSGA-II-TS差別較小，然而其物資點則增加了NSGA-II-TS的一倍，代價較大，因此NSGA-II-TS在災(zāi)區(qū)滿意度相當(dāng)?shù)那闆r下，表現(xiàn)效果更優(yōu)。

表4 各算法所得的平均值

圖3為NSGA-II、MOEA/D以及NSGA-II-TS基于理想點法所得最優(yōu)解的對比分析圖。由圖3可知，在物資效用和滿意度下NSGA-II-TS所得的最優(yōu)方案均高于NSGA-II和MOEA/D所得的最優(yōu)方案，且NSGA-II-TS的波動性非常小，說明每次實驗基本上可得到最優(yōu)方案。結(jié)合表3，可以得出NSGA-II-TS優(yōu)于傳統(tǒng)的多目標(biāo)求解算法MOEA/D及NSGA-II。

表5為NSGA-II、MOEA/D以及NSGA-II-TS基于秩和檢驗的差異度分析，結(jié)果顯示3種算法在物資效用、臨時物資點個數(shù)、滿意度上的顯著水平分別為0.01、0、0.02。拒絕原假設(shè)：物資效用、臨時物資點個數(shù)、滿意度在NSGA-II、MOEA/D以及NSGA-II-TS算法上是相關(guān)的，即3種算法所得的結(jié)果在統(tǒng)計學(xué)上具有顯著性差異，從而說明基于表3的分析是可靠的，再次驗證了NSGA-II-TS較傳統(tǒng)的NSGA-II、MOEA/D算法更優(yōu)。

由上述對比分析，可以明顯地發(fā)現(xiàn)NSGA-II-TS在處理大規(guī)模應(yīng)急選址問題上效果更優(yōu)，可見本文算法的改進是有效的，隨著應(yīng)急選址規(guī)模的增大，算法的優(yōu)越性更是明顯。

5 結(jié)論

泥石流等突發(fā)自然災(zāi)害造成的人員傷亡和經(jīng)濟損失十分巨大，因此應(yīng)急中心選址問題是應(yīng)急救援方案中的核心環(huán)節(jié)。根據(jù)突發(fā)性事件具有動態(tài)性和時效性，考慮將救濟物資效用、受災(zāi)區(qū)域滿意度以及臨時物資點個數(shù)作為目標(biāo)函數(shù)，建立多目標(biāo)動態(tài)選址模型，提出了一種改進的NSGA-II算法。該算法在精英策略上引入禁忌搜索的思想，從而實現(xiàn)了局部和全局搜索能力同時達到較優(yōu)的結(jié)果，同時保留解集的多樣性和均勻性，其理論與數(shù)值分析結(jié)果優(yōu)良。

圖3 對比分析圖

表5 假設(shè)檢驗匯總

（1）通過經(jīng)典函數(shù)ZDT1、ZDT2和ZDT3分別進行測試，從Pareto前沿、世代距離以及spacing指標(biāo)值驗證了算法的收斂性和分布性。實驗結(jié)果顯示NSGA-II-TS的收斂性以及Pareto解集的分布性相比NSGA-II、MOEA/D均有顯著的提升。

（2）實證分析中NSGA-II-TS比NSGA-II所得的物資效用高出818 m3，滿意度同比增長4.6%，而臨時物資點個數(shù)僅僅增加兩個；與MOEA/D算法相比較，在物資效用及滿意度略優(yōu)的情況下，其臨時物資點的個數(shù)少了一倍，體現(xiàn)了NSGA-II-TS算法在解決應(yīng)急物資處理中更為高效。

（3）通過秩和檢驗驗證NSGA-II、MOEA/D及NSGAII-TS所得最優(yōu)解之間的差異性，結(jié)果顯示3種算法在物資效用、臨時物資點個數(shù)、滿意度在統(tǒng)計學(xué)上具有顯著性差異，再次驗證了NSGA-II-TS較傳統(tǒng)的NSGA-II、MOEA/D算法在處理大規(guī)模應(yīng)急選址優(yōu)化問題上表現(xiàn)更優(yōu)。

本文提出的算法在突發(fā)性災(zāi)害危機的應(yīng)急管理以及其他保障體系建設(shè)問題中具有較高的應(yīng)用價值。