救災(zāi)物資高維多目標(biāo)自適應(yīng)分配問題建模與求解

嚴(yán)華健 ，張國富 ，蘇兆品 ，劉 揚

（1. 合肥工業(yè)大學(xué)計算機(jī)與信息學(xué)院，合肥230601；2. 工業(yè)安全與應(yīng)急技術(shù)安徽省重點實驗室（合肥工業(yè)大學(xué)），合肥230601；3. 安全關(guān)鍵工業(yè)測控技術(shù)教育部工程研究中心（合肥工業(yè)大學(xué)），合肥230601；4. 安徽省經(jīng)濟(jì)信息中心網(wǎng)絡(luò)管理處，合肥230001）

0 引言

近年來，我國各類自然災(zāi)害多發(fā)頻發(fā)，給國民經(jīng)濟(jì)與社會發(fā)展造成巨大的損失。當(dāng)災(zāi)害發(fā)生后，如何及時、有效、合理地把各個儲備點有限的救災(zāi)物資分配到災(zāi)區(qū)的各個物資發(fā)放點，成為應(yīng)急管理部門非常關(guān)心的一個重要問題，也是國內(nèi)外學(xué)者研究的一個熱點［1］。時至今日，現(xiàn)有針對救災(zāi)物資分配問題的研究大致可以粗略地分為單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化兩大類。

在單目標(biāo)優(yōu)化方面，Arora 等［2］針對單種醫(yī)療救援物資的分配，建立了費用約束下的救助率最大化模型。Altay［3］根據(jù)各儲備點和發(fā)放點之間的供需關(guān)系，構(gòu)建了基于應(yīng)急能力的救災(zāi)物資分配整數(shù)規(guī)劃模型，以最大化物資分配效用。Wex等［4］構(gòu)建了一種以最小化所有事故救援總完成時間為目標(biāo)的各種救援力量分配模型。李永義等［5］基于災(zāi)區(qū)區(qū)域大小、受災(zāi)程度、人口密度和災(zāi)區(qū)群眾需求構(gòu)建了基于區(qū)間數(shù)的地震應(yīng)急物資分配多屬性決策模型。王旭坪等［6］在考慮受災(zāi)地區(qū)災(zāi)民非理性攀比心理的基礎(chǔ)上，依據(jù)應(yīng)急物資分配數(shù)量和配送時間最小化應(yīng)急物資分配的攀比函數(shù)值。劉長石等［7］考慮應(yīng)急物資分配的公平性，以所有需求點的損失攀比效應(yīng)總和最小為目標(biāo)構(gòu)建應(yīng)急物資分配模型。于冬梅等［8］從需求區(qū)域和應(yīng)急設(shè)施應(yīng)急服務(wù)質(zhì)量的視角構(gòu)建了一個基于障礙約束、容量及安全庫存約束的應(yīng)急設(shè)施選址與資源分配優(yōu)化模型，追求障礙約束下的應(yīng)急設(shè)施最大時間滿意度。胡忠君等［9］對受災(zāi)區(qū)域進(jìn)行無監(jiān)督聚類劃分來明確各受災(zāi)點的緊急度，然后基于粒子群算法最小化救災(zāi)物資分配方案帶來的相關(guān)運輸費用。

在多目標(biāo)優(yōu)化方面，王旭坪等［10］利用前景理論建立了一個最大化感知救援時間滿意度、災(zāi)區(qū)需求滿意度和物資分配效用滿意度的三目標(biāo)非線性整數(shù)規(guī)劃模型，并利用分散搜索算法對模型進(jìn)行求解。Chang 等［11］構(gòu)建了一個最小化物資需求不滿足度、總消耗時間和總運輸成本的三目標(biāo)優(yōu)化模型，并提出了一種基于貪心策略的多目標(biāo)遺傳算法來搜索最佳分配方案和配送路徑。陳瑩珍等［12］考慮發(fā)放點之間物資分配的公平性，建立了一個最大化發(fā)放點的物資滿足量、最小化最大運送時間的兩目標(biāo)優(yōu)化模型，并引入差異演化算法進(jìn)行求解。蘇兆品等［13］針對多儲備點、多發(fā)放點和多種救援物資，同時考慮應(yīng)急響應(yīng)總時間和應(yīng)急資源總成本這兩個優(yōu)化目標(biāo)，并設(shè)計了一種基于非支配排序差異演化和編碼修正機(jī)制的求解算法。張國富等［14］構(gòu)建了一個最小化救援物資的未滿足量、最小化最大通行時間和最大化最小通行可靠度的三目標(biāo)救災(zāi)物資分配和調(diào)度集成優(yōu)化模型，并設(shè)計了一種基于二維第二代非支配排序遺傳算法（Non-dominated Sorted Genetic Algorithm 2，NSGA2）與蟻群優(yōu)化的混合智能搜索算法進(jìn)行求解。陳剛等［15］同時考慮物資分配的效率和公平，構(gòu)建了一個最小化受災(zāi)點的總加權(quán)嫉妒值和最小化總物流成本的兩目標(biāo)優(yōu)化模型，并引入NSGA2算法進(jìn)行求解。

總的來說，基于單目標(biāo)優(yōu)化的救災(zāi)物資分配，雖然模型和算法簡單易行，但只能輸出一個最終解，很難在各個優(yōu)化指標(biāo)上達(dá)到一個理想的平衡［16］；而對于救災(zāi)物資多目標(biāo)分配，最終可以輸出一個Pareto 解集，可以讓決策者根據(jù)實際的需求挑選合適的偏好解，但是，現(xiàn)有研究均局限于三個優(yōu)化目標(biāo)之內(nèi)，且大都考慮時間、成本等因素。此外，在現(xiàn)有研究中，往往只考慮某種特定情況下的救災(zāi)物資分配，例如所有種類的應(yīng)急物資供應(yīng)量都很充足，導(dǎo)致應(yīng)急救援場景較為單一。眾所周知，災(zāi)害應(yīng)急響應(yīng)是一個十分復(fù)雜的系統(tǒng)工程，需要考慮的因素牽涉到方方面面，甚至需要考慮社會心理學(xué)等，簡單的多目標(biāo)優(yōu)化思路和單一的應(yīng)急場景很難契合復(fù)雜的應(yīng)急環(huán)境，難以滿足實際應(yīng)急決策的需求。

基于上述背景，本文在總結(jié)已有工作的基礎(chǔ)上，引入社會心理學(xué)中的相關(guān)因素，從應(yīng)急響應(yīng)工程的系統(tǒng)性、社會性上進(jìn)行設(shè)計，綜合考慮了應(yīng)急響應(yīng)總時間、災(zāi)民恐慌度、救災(zāi)物資未滿足度、物資分配公平性、災(zāi)民損失、應(yīng)急響應(yīng)總成本等決策指標(biāo)，構(gòu)建了一個多儲備點、多發(fā)放點、多種救災(zāi)物資的高維多目標(biāo)（大于等于四個優(yōu)化目標(biāo)）分配模型，從而為決策者提供更加全面、科學(xué)的思考。此外，本文引入了在高維多目標(biāo)優(yōu)化方面性能優(yōu)越的移位密度估計（Shift-based Density Estimation，SDE）［17］和第二代強(qiáng)度帕累托進(jìn)化算法（Strength Pareto Evolutionary Algorithm 2，SPEA2）［18］混合算法 SPEA2+SDE 來求解所提的模型，并針對SPEA2+SDE 無法處理約束的弊端，基于自適應(yīng)個體修正（Adaptive Individual Repair，AIR）改進(jìn)SPEA2+SDE，以提升它在解決本文的復(fù)雜高維多目標(biāo)約束優(yōu)化問題上的性能。最后，通過和已有方法的對比實驗分析驗證了所提模型和算法的有效性。

1 問題描述

設(shè)某地區(qū)突發(fā)災(zāi)害后，周邊有n 個救災(zāi)物資儲備點A={a1，a2，…，an}，需要響應(yīng)災(zāi)區(qū)里 m 個物資發(fā)放點的應(yīng)急需求G ={g1，g2，…，gm}。

定義1 ?gj∈ G(j ∈ {1，2，…，m})有一個相對的受災(zāi)程度 λj∈ [0，1]，滿足越大，表示 gj受災(zāi)情況越嚴(yán)重。

定義2 ?gj∈G 有一定的救災(zāi)物資需求量Dj=其 中 ：r 表 示 救 災(zāi) 物 資 的 種 類 ；表示發(fā)放點gj對第k 種救災(zāi)物資的需求量，可由應(yīng)急專家結(jié)合災(zāi)情評估系統(tǒng)根據(jù)發(fā)放點gj的服務(wù)區(qū)域大小、受災(zāi)程度、人口密度和災(zāi)區(qū)群眾需求進(jìn)行預(yù)估。注意，如果= 0，則gj不需要第k種救援物資。

定義3 ?ai∈ A(i ∈{1 ，2，…，n} )擁有一個救災(zāi)物資儲備量其中表示儲備點 ai在第 k 種救災(zāi)物資上的儲備量。注意，如果= 0，則ai沒有第k種救援物資。

定義4 考慮到各物資儲備點在經(jīng)濟(jì)和地域上的差異性，?ai∈A 有一個救災(zāi)物資單位成本其中：表示儲備點ai在第k種救援物資上的單位成本。

定義5 ?ai∈A 對?gj∈G 有一個救災(zāi)物資分配量Xij=表示儲備點 ai到發(fā)放點 gj在第 k 種救災(zāi)物資上的分配量，滿足，即每個儲備點ai向所有發(fā)放點提供的第k 種救災(zāi)物資的總量不可能超過第k種救災(zāi)物資上的儲備量，且有，即所有儲備點向發(fā)放點gj提供的第k 種救災(zāi)物資總量不會超過gj在第k 種救災(zāi)物資上的需求量。

定義6 考慮到各儲備點之間物資種類和運輸工具的同 ，?ai∈ A 對 ?gj∈ G 有 一 個 單 位 廣 義 時 間 距 離 Tij=表示從儲備點ai到發(fā)放點gj在第k種救災(zāi)物資上的單位運輸時間。

定義7 ?ai∈A 對?gj∈G 有一個單位運輸成本Cij=表示從儲備點 ai到發(fā)放點 gj在第 k 種救災(zāi)物資上的單位運輸成本。

依據(jù)上述定義，對于n 個儲備點和m 個發(fā)放點，總共有n × m 個 Xij，構(gòu)成一個可能的救災(zāi)物資分配方案 Xn×m。在災(zāi)害發(fā)生后，受災(zāi)群眾心理相對比較脆弱，從災(zāi)民心理風(fēng)險感知的角度考慮，如果Xn×m分配不公平或配送不均衡，則容易消解災(zāi)民對安置措施的安全感受，從而導(dǎo)致群體性恐慌事件等嚴(yán)重后果。因此，在災(zāi)害應(yīng)急響應(yīng)過程中，尤其在資源短缺的時期，救災(zāi)物資的分配應(yīng)充分考慮災(zāi)民對救災(zāi)物資的到達(dá)時間和數(shù)量的敏感度。

首先，從救災(zāi)物資的到達(dá)時間上來看，災(zāi)民對救災(zāi)物資分配的時效性最為敏感［19］，因此，決策者總是期望 Xn×m對應(yīng)的應(yīng)急響應(yīng)總時間要盡可能地短，即

除此之外，各個發(fā)放點之間對救災(zāi)物資的獲取時間存在著普遍的攀比心理，如果各發(fā)放點獲得救災(zāi)物資的時間與其心理預(yù)期時間相差過大，則會給災(zāi)民帶來額外的心理恐慌，從而極易誘導(dǎo)群體性事件的爆發(fā)。因此，根據(jù)前景理論的價值函數(shù)模型，可用

來表示發(fā)放點gj獲得救援物資的時間，用

來表示各個發(fā)放點獲得救援物資的平均時間，用δ*（一個較大的常數(shù)）來表示τ*對應(yīng)的災(zāi)民的心理恐慌度，則發(fā)放點gj區(qū)域中災(zāi)民的心理恐慌度［19］為：

其中：α，β ∈ (0，1)為敏感性遞減系數(shù)，γ ∈ [1.5，2.5]為損失厭惡系數(shù)。據(jù)此，決策者總是期望分配方案Xn×m對應(yīng)的災(zāi)民心理恐慌度應(yīng)該越小越好，即

在另一方面，從救災(zāi)物資的數(shù)量上來看，決策者總是期望各發(fā)放點的救災(zāi)物資未滿足度要盡可能地小，即

從社會心理學(xué)角度進(jìn)一步考慮，當(dāng)發(fā)放點gj的救災(zāi)物資未滿足量

大于某個發(fā)放點gj*的未滿足量

時，gj區(qū)域的災(zāi)民就會產(chǎn)生嫉妒心理，相反則沒有嫉妒反應(yīng)。可用

來表示gj區(qū)域的災(zāi)民對gj*產(chǎn)生的嫉妒值。另外，出于對群體效應(yīng)的考慮，受災(zāi)情況越嚴(yán)重的地方越容易引發(fā)群體事件，其嫉妒值的權(quán)重應(yīng)該越大。根據(jù)最小妒忌公平原則［15］，所有發(fā)放點的加權(quán)嫉妒值越小，災(zāi)民的心理效用就會越均等，物資分配的公平性就越高，即

不僅如此，災(zāi)民的損失也與救災(zāi)物資未滿足量和受災(zāi)程度具有典型的凸函數(shù)關(guān)系［20］，受災(zāi)情況越嚴(yán)重，災(zāi)民的損失會隨著救災(zāi)物資未滿足量的增加而急劇增加。因此，可用

來最小化各發(fā)放點所負(fù)責(zé)災(zāi)區(qū)內(nèi)災(zāi)民的損失。

需要注意的是，救災(zāi)物資分配還應(yīng)該考慮經(jīng)濟(jì)因素，尤其在應(yīng)急響應(yīng)的中、后期，決策者需要謹(jǐn)慎考慮投入的成本（包括物資成本和運輸成本），總是期望應(yīng)急響應(yīng)總成本要盡可能地小，即

基于上述考慮，面向多個發(fā)放點的應(yīng)急需求，對多個儲備點的多種救災(zāi)物資同時進(jìn)行分配，構(gòu)建如式（7）所示的高維多目標(biāo)優(yōu)化模型。該模型總共包含了6 個目標(biāo)函數(shù)，基本囊括了應(yīng)急響應(yīng)工程的系統(tǒng)性、社會性等諸方面因素。需要指出的是，這樣設(shè)計的目的是為了盡可能地為決策者提供更加科學(xué)、全面的決策參考。在實際的應(yīng)急決策中，決策者可以在決策支持系統(tǒng)中根據(jù)災(zāi)情信息靈活選擇需要考慮的目標(biāo)函數(shù)，從而提高系統(tǒng)的人機(jī)交互性。此外，第一個約束條件是為了保證任意一個儲備點在任意一種救災(zāi)物資上的供給不存在資源沖突；第二個約束條件是為了確保任意一個發(fā)放點在任意一種救災(zāi)物資上的需求不存在過度供應(yīng)，從而避免資源浪費；第三個等式約束條件是為了讓每個儲備點竭盡全力地貢獻(xiàn)資源，從而盡可能地利用現(xiàn)有資源實現(xiàn)最佳的救援效果。

2 救災(zāi)物資高維多目標(biāo)分配算法

近年來，多目標(biāo)進(jìn)化算法在解決目標(biāo)個數(shù)不多于三個的多目標(biāo)優(yōu)化問題上展現(xiàn)了卓越的性能，例如主流的NSGA2［14］、SPEA2［19］等。然而，上述方法在求解高維多目標(biāo)優(yōu)化問題時卻遇到極大的困難，這是因為隨著目標(biāo)函數(shù)個數(shù)的增加，傳統(tǒng)的Pareto 占優(yōu)關(guān)系很難有效區(qū)分進(jìn)化個體，而且使得逼近問題真實Pareto 前沿所需的候選解個數(shù)猛增，嚴(yán)重影響了算法的探索能力［21-22］。Li 等［17］從維護(hù)種群多樣性的角度出發(fā)，同時兼顧個體的分布和收斂信息，提出了一種移位密度估計策略。SDE通過遷移稀疏個體（即收斂性差的個體）在目標(biāo)空間的位置，使其具有較大的密度值，從而讓其更容易被淘汰。Li 等［17］將 SDE 與 SPEA2 相結(jié)合應(yīng)用于多個基準(zhǔn)高維多目標(biāo)優(yōu)化問題，取得了很好的效果。因此，本文引入簡單易行且效果突出的SPEA2+SDE 算法來求解如式（7）所示的救災(zāi)物資高維多目標(biāo)分配問題。

不過，需要特別指出的是，式（7）是一個典型的約束優(yōu)化問題，特別是還包含一個等式約束條件，而SPEA2+SDE 算法只見長于無約束優(yōu)化問題，因此，需要結(jié)合問題本身，對傳統(tǒng)的SPEA2+SDE 算法進(jìn)行改進(jìn)，以提高算法對這個特殊的高維多目標(biāo)約束優(yōu)化問題的求解能力。

為了更清晰地表達(dá)，本章首先給出基本的SPEA2+SDE 算法，然后給出本文提出的個體編碼方案和個體修正（Individual Repair，IR）策略，最后介紹本文的改進(jìn)型混合優(yōu)化算法。

2.1 基本的SPEA2+SDE算法

SPEA2+SDE 算法［17］包含進(jìn)化種群（包含N 個個體）和外部種群（包含N′個體）兩部分，其大致流程如下：

步驟1 在初始化時，設(shè)置初始迭代次數(shù)t = 0。根據(jù)待求解的問題隨機(jī)生成初始進(jìn)化種群Qt和外部種群Q′t。根據(jù)Q′t中N′個個體的編碼和多目標(biāo)函數(shù)計算每個個體在每個目標(biāo)函數(shù)上的值。

步驟2 如果t 已達(dá)最大迭代次數(shù)，則算法終止迭代，輸出Q′t中的所有非支配個體作為最終的最優(yōu)解集，否則算法繼續(xù)迭代。

步驟3 根據(jù)Qt中N 個個體的編碼和多目標(biāo)函數(shù)計算每個個體在每個目標(biāo)函數(shù)上的值。

步驟 4 將 Qt和 Q′t合并成一個組合種群 Vt= Qt+ Q′t，并對Vt中的每個個體的每個目標(biāo)函數(shù)值進(jìn)行min-max標(biāo)準(zhǔn)化。

步驟5 對Vt進(jìn)行適應(yīng)度分配。對于Vt中的每一個個體x，對應(yīng)一個支配強(qiáng)度值S(x)，為x能夠支配的點的數(shù)目，即

據(jù)此，基于小生境法可得x 的原始適應(yīng)度，即x 的支配者的強(qiáng)度值之和：

此外，每一個個體x還有一個擁擠度值：

步驟6 對Vt進(jìn)行環(huán)境選擇。在Vt中，所有的F(x)＜1的個體（即非支配個體）被全部復(fù)制到新的外部種群Q′t+1。如果|Q′t+1|= N′，則此時環(huán)境選擇結(jié)束。如果|Q′t+1|＜ N′，則外部種群沒有填滿，那么對于在Vt中剩下的所有支配個體（即F(x)≥1），按照適應(yīng)度值F(x)進(jìn)行升序排序，選擇前面適應(yīng)度值最小的 N′-|Q′t+1|個個體進(jìn)入 Q′t+1。如果|Q′t+1|＞ N′，則外部種群過大，進(jìn)行截尾操作，依次從Q′t+1中刪除一個與鄰近個體距離最?。ㄊ諗啃宰畈睿┑膫€體，直到滿足|Q′t+1|=N′。

步驟7 對新的外部種群Q′t+1進(jìn)行min-max 標(biāo)準(zhǔn)化和適應(yīng)度值分配。

步驟8 對Q′t+1進(jìn)行交配選擇。運用錦標(biāo)賽選擇方式依次從Q′t+1中選擇兩個父代個體進(jìn)行模擬二進(jìn)制交叉，生成兩個子代個體放入新的進(jìn)化種群Qt+1中，直到|Qt+1|= N。

步驟9 對新的進(jìn)化種群Qt+1進(jìn)行多項式變異。

步驟10 t = t + 1，轉(zhuǎn)步驟2。

2.2 個體編碼方案

如前所述，對于n 個儲備點和m 個發(fā)放點，對應(yīng)一個救災(zāi)物資分配方案，這恰似一個二維組合優(yōu)化問題。而原始的SPEA2+SDE 算法采用一維實數(shù)編碼，很難描述Xn×m的二維特性。因此，本文設(shè)計了一種二維整數(shù)向量編碼來表示算法中的每個個體，如式（11）所示。這種編碼方式簡單直觀、容易理解，而且從根本上與本文救災(zāi)物資分配問題的二維本質(zhì)相適應(yīng)，且極大方便了后續(xù)AIR 策略的設(shè)計，從而為問題的求解和高效算法的設(shè)計奠定了良好的基礎(chǔ)。

式（11）中，個體編碼的每一行表示一個儲備點（共有n行），每一列表示一個發(fā)放點（共有m 列），編碼中的任意一個元素Xn×m即是儲備點ai向發(fā)放點gj提供的救災(zāi)物資分配量。注意，式（7）是一個約束優(yōu)化問題，因此，任意一個如式（11）所示的編碼可能存在如下情況：

1）對每一行而言，如果 ?i ∈{1，2，…，n}，?k ∈ {1，2，…，則儲備點ai分配出去的第k 種救災(zāi)物資總量超過了其本身所的擁有量，造成應(yīng)急資源沖突。

2）對每一列而言，如果 ?j ∈ {1，2，…，m}，?k ∈ {1，2，…，則發(fā)放點gj分配得到的第k 種救災(zāi)物資總量超過了其本身的需求量，造成應(yīng)急資源浪費。

上述的兩種約束違背情況將會導(dǎo)致在算法進(jìn)化過程中產(chǎn)生大量的不可行個體，從而影響算法的求解效率。而在應(yīng)急響應(yīng)這個特殊的場景中，時效性是一個首要衡量指標(biāo)。因此，在2.3 節(jié)中，本文將在基本的SPEA2+SDE 算法中嵌入AIR 策略，旨在將各種環(huán)境中的不可行個體修正為一個可行個體，讓算法始終在近似可行域中進(jìn)行探索，從而提升算法的整體性能。

2.3 自適應(yīng)個體修正策略

IR 的目的是解決算法進(jìn)化過程中可能出現(xiàn)的應(yīng)急資源沖突和浪費現(xiàn)象。為此，在個體編碼中必須動態(tài)跟蹤每一個儲備點和發(fā)放點的物資供給情況：一旦某儲備點ai當(dāng)前某種救災(zāi)物資的可用量為0，則ai將不再響應(yīng)任何其他發(fā)放點在這種救災(zāi)物資上的需求；此外，一旦某發(fā)放點gj的救災(zāi)物資未滿足度為0，則gj將不再向其他任何儲備點發(fā)送請求。

在實際應(yīng)急救援過程中，對于儲備點而言，少數(shù)幾種救災(zāi)物資量能夠滿足發(fā)放點的救災(zāi)物資需求，而多數(shù)種類的救災(zāi)物資量無法滿足發(fā)放點的救災(zāi)物資需求是比較合理的，但是在現(xiàn)有研究中總是假設(shè)所有種類的救援物資全部充足或者全部不充足，將所有種類的救援物資使用同一種修正策略進(jìn)行統(tǒng)一考慮，這顯然是不符合實際的，因此本文的IR 策略除了要滿足2.2 節(jié)的約束，還應(yīng)該對物資量充足的救援物資以及物資量不充足的救援物資采用不同的修正策略分開考慮。在應(yīng)急這個特殊的應(yīng)用場景，當(dāng)某種救災(zāi)物資的儲備量不充分時，應(yīng)該從儲備點出發(fā)，要求所有的儲備點盡可能貢獻(xiàn)完它們該種資源的全部物資，這樣才能最大化響應(yīng)效率；而對于儲備量充足的某種救災(zāi)物資，應(yīng)該從發(fā)放點的角度出發(fā)，這時本文的IR 策略要求所有發(fā)放點對該種救災(zāi)物資的應(yīng)急需求都得到滿足，這樣才能最大化響應(yīng)效果?；谏鲜鏊枷?，本文提出了AIR策略來應(yīng)對不同情景下的決策需求。

首先，隨機(jī)選擇一種救援物資k ∈ {1，2，…，r}，若則執(zhí)行策略一，否則執(zhí)行策略二。

AIR策略一：

步驟1 從編碼中隨機(jī)選擇一個未檢查的行i（對應(yīng)儲備點 ai）。

步驟2 檢查ai對第k種救災(zāi)物資的供給情況，執(zhí)行：

來更新ai對gj*的供應(yīng)量。重復(fù)此步驟，直到

來更新ai對gj*的供給量。重復(fù)此步驟，直到

步驟2.4 更新每個發(fā)放點在第k種救災(zāi)物資上的剩余需求，對?j ∈ {1，2，…，m}，如果

步驟3 如果所有行檢查完畢（即所有儲備點分配完畢），修正結(jié)束，否則轉(zhuǎn)步驟1。

AIR策略二：

步驟1 從編碼中隨機(jī)選擇一個未檢查的列j（對應(yīng)發(fā)放點 gj）。

步驟2 檢查gj在第k種救災(zāi)物資上的響應(yīng)情況，執(zhí)行：

步驟3 如果所有列檢查完畢（即所有發(fā)放點響應(yīng)完畢）修正結(jié)束，否則轉(zhuǎn)步驟1。

遍歷所有k后，修正結(jié)束，否則返回重新操作。

需要注意的是，在AIR 策略一中，由于該種資源緊缺，本文從儲備點的視角出發(fā)，依次檢查每個儲備點的供給情況，讓每個儲備點盡可能地貢獻(xiàn)該種資源，一旦資源貢獻(xiàn)完則不再響應(yīng)其他發(fā)放點的請求，而且對后續(xù)儲備點的修正均是基于發(fā)放點的剩余需求量進(jìn)行操作，從而有效保證修正后的個體編碼滿足式（7）中的約束條件。同理，在AIR 策略二中，由于該種資源非常充分，本文從發(fā)放點的視角出發(fā)，依次檢查每個發(fā)放點的響應(yīng)情況，讓每個發(fā)放點盡可能地得到滿足，一旦需求得到滿足則不再向其他儲備點發(fā)送請求，而且對后續(xù)發(fā)放點的修正均是基于儲備點的剩余資源量進(jìn)行操作，從而也確保了修正后的個體編碼滿足約束條件。由此，可以清楚地看到，個體編碼在經(jīng)過修正之后，發(fā)放點的需求能夠根據(jù)儲備點的現(xiàn)有資源狀況盡可能地得到滿足（盡可能的向最優(yōu)解靠近），而且可以有效解決可能出現(xiàn)的應(yīng)急資源沖突和浪費現(xiàn)象。

2.4 SPEA2+SDE+AIR算法描述

本文將上述的個體編碼方案和修正策略嵌入到基本的SPEA2+SDE 算法中，提出一種改進(jìn)型混合搜索算法，稱為SPEA2+SDE+AIR，如圖 1 所示。SPEA2+SDE+AIR 算法的基本流程如下：首先根據(jù)二維整數(shù)向量編碼在約束空間內(nèi)隨機(jī)生成初始的進(jìn)化種群和外部種群；然后基于AIR 策略對組合種群進(jìn)行修正，確保每個個體都是可行個體；根據(jù)式（7）計算每個可行個體的目標(biāo)函數(shù)值，并進(jìn)行適應(yīng)度分配；對組合種群進(jìn)行環(huán)境選擇生成新的外部種群；對新外部種群進(jìn)行交配選擇和多項式變異生成新的進(jìn)化種群；如果滿足終止條件，輸出外部種群中的所有非支配個體，否則對新進(jìn)化種群進(jìn)行個體修正使其成為可行種群，并繼續(xù)算法的進(jìn)化。

從圖1 可以看出，與基本的SPEA2+SDE 算法相比，本文提出的SPEA2+SDE+AIR 算法能夠基于構(gòu)造的二維整數(shù)向量編碼，充分考慮數(shù)學(xué)模型中的相關(guān)約束關(guān)系以及實際應(yīng)急救援環(huán)境的復(fù)雜情況，利用AIR 策略將種群始終限制在可行域中進(jìn)化，從而能夠為算法的適應(yīng)度分配、環(huán)境選擇、交配選擇等提供更加準(zhǔn)確可靠的啟發(fā)式信息，增強(qiáng)算法的收斂性能。

圖1 SPEA2+SDE+AIR算法的流程Fig. 1 Flowchart of SPEA2+SDE+AIR algorithm

3 實驗結(jié)果與分析

為了驗證本文SPEA2+SDE+AIR 算法在處理相關(guān)問題時的有效性，本章首先介紹算法的基本參數(shù)設(shè)置以及性能評價指標(biāo)，然后考慮與兩種最新的針對于應(yīng)急救援物資分配問題的算法：帶有編碼修正機(jī)制的非支配排序差異演化（Encoding Repair and Non-dominated Sorting based Differential Evolution，ERNS-DE）算法［13］，以及基于貪心搜索的多目標(biāo)遺傳算法（Greedy-Search-based Multi-Objective Genetic Algorithm，GSMOGA）［11］分別進(jìn)行模型及算法對比。ERNS-DE 采用面向發(fā)放點的編碼修正機(jī)制使種群中的每一個個體都是可行的；GSMOGA 則包含一種貪婪搜索方法，其中最接近發(fā)放點的儲備點在物資分配時優(yōu)先考慮，從而避免了不可行個體的產(chǎn)生。

3.1 參數(shù)設(shè)置與評價指標(biāo)

為了模擬應(yīng)急環(huán)境以充分評估算法性能，本文考慮20 個物資儲備點、10 個物資發(fā)放點以及50 種救援物資，對應(yīng)10 000 個決策變量，并分別在兩種應(yīng)急環(huán)境中進(jìn)行測試。在應(yīng)急環(huán)境1（標(biāo)記為EN1），隨機(jī)設(shè)置5 種物資是充分的，即可以滿足所有需求點的要求，剩余45 種救災(zāi)物資均是短缺的，不能滿足所有需求點的應(yīng)急要求；在應(yīng)急環(huán)境2（標(biāo)記為EN2），隨機(jī)設(shè)置10 種物資可以滿足需求，剩下的40 種救災(zāi)物資極其緊缺。依據(jù)上面的設(shè)定，每個測試實例均根據(jù)輸入的問題規(guī)模和約束條件隨機(jī)生成，且根據(jù)不同的隨機(jī)種子，在Intel Core i7 3.60 GHz CPU、內(nèi)存8.0 GB、操作系統(tǒng)Windows 10 的個人計算機(jī)上獨立運行30 次。為了對比的公平性，ERNS-DE 和GSMOGA 采用各自的推薦參數(shù)設(shè)置。對于本文的SPEA2+SDE+AIR，本文采用實驗法，即結(jié)合已有工作與通過大量測試獲得結(jié)果相對較好的一組參數(shù)組合，這也是目前最常用的確定參數(shù)的方法，其中較小的變異概率和較大的交叉概率有利于維護(hù)種群進(jìn)化過程中的多樣性和收斂性。三種算法的具體參數(shù)如表1所示。

表1 三種算法的基本參數(shù)Tab. 1 Basic parameters of three algorithms

為了比較測試算法的整體性能，本文使用流行的超體積（HyperVolume，HV）［23］指標(biāo)來進(jìn)行衡量。超體積定義為被所求解集支配、但不被參考點支配的空間體積大小。超體積值可以提供有關(guān)于整個解決方案的收斂性和多樣性的一般信息，通常，較大的超體積值意味著解決方案的質(zhì)量更高。需要注意的是，參考點的選擇對于超體積的計算至關(guān)重要。由于在所提的高維多目標(biāo)應(yīng)急救援物資分配問題中不知道Pareto前沿的范圍，因此，對于每一組測試實例，需要將所有獲得的解集放在一起，去除其中的重復(fù)解以及支配解，然后，選擇的參考點略大于合并解集每個目標(biāo)的最大值。這種方法已經(jīng)被證明是有效的，因為它能夠很好地平衡解集的收斂性與多樣性［24］。

在所提的高維多目標(biāo)應(yīng)急救援物資分配問題中，決策者通常更關(guān)心所采用的算法獲得的結(jié)果是否優(yōu)于其他對比算法。因此，本文采用經(jīng)典的覆蓋值（Coverage Value，CV）［25］來評估所得結(jié)果的收斂性。覆蓋值提供了一種直接的方法來比較通過所采用的算法獲得的解集中有多少個解支配了由對比算法所獲得的結(jié)果中的解。假設(shè)E 和F 分別是兩種不同的算法所獲得的解集，假如E 中的一個解的所有目標(biāo)值與F 中的另一個解的所有目標(biāo)值相比，都不比它們差，則認(rèn)為前者覆蓋了后者。Cv（E，F(xiàn)）表示 F 被E 中解集所覆蓋的百分比，若Cv(E，F(xiàn)) ＞ Cv(F，E)，則意味著E 中的解相比 F 更優(yōu)。在本文的實驗中，對于每個測試實例，將在30 次獨立運行中所獲得的所有解放在一起，去除其中的重復(fù)解后再進(jìn)行覆蓋值計算。

3.2 模型對比

首先，對于ERNS-DE 和GSMOGA，本文在進(jìn)行實驗時，僅考慮其原有的目標(biāo)函數(shù)（ERNS-DE 考慮f1和f6，GSMOGA 考慮f1、f3以及f6），剩余的目標(biāo)函數(shù)由分配方案計算得出；而SPEA2+SDE+AIR 考慮所有的目標(biāo)。由于三種算法所要優(yōu)化的目標(biāo)數(shù)不同，所以此處本文不采用超體積和覆蓋值，而是選取了各個目標(biāo)值的范圍，如表2 所示，其中較優(yōu)的目標(biāo)值加粗表示。

由表2可以看出，就所選取的三個目標(biāo)f1、f3以及f6而言，SPEA2+SDE+AIR 在7 個實例上獲得的結(jié)果優(yōu)于ERNS-DE 和GSMOGA所獲得的結(jié)果，而ERNS-DE和GSMOGA在所有實例中都沒有發(fā)現(xiàn)比SPEA2+SDE+AIR 更好的解。此外，SPEA2+SDE+AIR 在所有實例中占優(yōu)的目標(biāo)個數(shù)都遠(yuǎn)要高于ERNSDE 和GSMOGA。以上結(jié)果表明，盡管SPEA2+SDE+AIR 在處理6 個目標(biāo)時具有更大的優(yōu)化負(fù)擔(dān)，但它仍舊可以在考慮的目標(biāo)之間尋找到比ERNS-DE和GSMOGA更好的平衡。

表2 兩種環(huán)境下部分測試實例的目標(biāo)值范圍Tab. 2 Objective value ranges of some test instances in two environments

3.3 算法對比

為了更加全面地比較SPEA2+SDE+AIR、ERNS-DE 和GSMOGA 三種算法之間的性能，在本節(jié)讓三種算法都考慮6個目標(biāo)，在兩種環(huán)境下分別測試30個實例。

表3 顯示了三種算法測試結(jié)果的超體積值，在EN1 中，與ERNS-DE 以及 GSMOGA 相比，SPEA2+SDE+AIR 的超體積分別增大了約55 000 000%和14 000 000%，而在EN2 中，則分別增大了30 000 000% 和29 000 000%，尤其需要注意的是ERNS-DE 和GSMOGA 都出現(xiàn)了超體積值為0 的情形，尤其是GSMOGA 絕大部分的超體積為0。以上結(jié)果表明，SPEA2+SDE+AIR 的整體性能要比ERNS-DE 和GSMOGA 更好，所得解集具有更好的收斂性和多樣性。

表4 給出了在高維多目標(biāo)應(yīng)急救援物資分配問題上三種算法的覆蓋值結(jié)果，其中較優(yōu)的覆蓋值加粗表示。K、L、M 分別表示由SPEA2+SDE+AIR、ERNS-DE 以及GSMOGA 各自獲得的最終解集。在EN1和EN2中，SPEA2+SDE+AIR 與ERNSDE 相比，平均覆蓋值分別提高了34.87%和23.59%，而與GSMOGA相比，在所有測試實例中覆蓋值都提高了100%。以上結(jié)果表明，SPEA2+SDE+AIR 可以獲得比ERNS-DE 和GSMOGA更高質(zhì)量的解。

總體而言，SPEA2+SDE+AIR 在所有60 個測試實例中均表現(xiàn)優(yōu)異，而且可以在各種情況下獲得多樣化的解決方案。

表3 三種算法在兩種環(huán)境下的超體積（均值和標(biāo)準(zhǔn)差）結(jié)果Tab. 3 Hypervolume（mean and standard deviation）results of three algorithms in two environments

表4 三種算法在兩種環(huán)境下的覆蓋值結(jié)果 單位：%Tab. 4 Coverage values of three algorithms in two environments unit：%

續(xù)表

4 結(jié)語

本文針對災(zāi)害應(yīng)急響應(yīng)中的應(yīng)急資源分配這一熱點問題展開研究，首先構(gòu)建了一個多儲備點、多發(fā)放點、多種救援物資的并發(fā)分配模型，然后通過引入相關(guān)心理學(xué)知識來量化受災(zāi)群眾的恐慌心理和公平心理，在此基礎(chǔ)上提出了包括應(yīng)急響應(yīng)總時間、受災(zāi)群眾的恐慌心理、發(fā)放點物資不滿足度、物資分配的公平性、受災(zāi)群眾損失、應(yīng)急響應(yīng)總成本在內(nèi)的優(yōu)化目標(biāo)，并提出了一種基于移位密度估計和自適應(yīng)編碼修正的多目標(biāo)優(yōu)化算法SPEA2+SDE+AIR。對比實驗說明，本文所提出的多目標(biāo)優(yōu)化算法在種群進(jìn)化過程中能夠很好地維持種群的多樣性和收斂性，從而提高算法的整體性能。在未來的工作中，多階段的動態(tài)優(yōu)化，以及救援物資分配與調(diào)度的集成優(yōu)化問題將是研究和改進(jìn)的重要方向。