考慮需求滿意度與救援時間公平的應急物資調度多目標模型及算法

王付宇， 謝昊軒， 湯 濤

(1.安徽工業(yè)大學管理科學與工程學院 安徽 馬鞍山 243032；2.安徽工業(yè)大學復雜系統(tǒng)多學科管理與控制安徽普通高校重點實驗室 安徽 馬鞍山 243002)

0 引言

突發(fā)性災難發(fā)生初期，應急物資的需求往往要大于救援中心的可供應量，決策者在制作救援物資分配方案時，需要同時考慮災區(qū)人民的滿意度最大化與救援時間長短的嫉妒心理[1]。如果不能獲得災區(qū)人民對救援方案的支持，那么對災區(qū)的救援工作將會產生極大的阻礙，容易使災區(qū)人民的情緒不穩(wěn)定，對災區(qū)人民造成心理傷害，嚴重時，造成死傷人數(shù)進一步增加[2]。

關于應急物資調度的研究已有很多成果，早期的研究主要以成本最小化、時間最短等為目標來制定應急物資分配方案。例如，于小兵等[3]針對應急事件的特點，建立了總運輸成本最小、延誤時間最小的多目標模型，利用范數(shù)理想點法將其轉換成單目標問題進行研究；王海軍等[4]針對大規(guī)模突發(fā)事件的應急調度問題，構建了總物流時間和應急成本為目標的多目標非線性整數(shù)規(guī)劃模型，通過對兩個目標的動態(tài)賦權，提高了模型柔性。如今，許多學者開始考慮災民心理[5]，以需求滿意度、時間滿意度、需求滿足率、物資分配的公平性等目標來進行研究。例如，宋曉宇等[6]以調度總成本最小與整體反應時間最早為目標，構建了由受災點、救援中心與儲備中心組成的應急調度模型。陳剛等[7]構建了總加權嫉妒值最小與總物流成本最小的多目標應急物資調度模型，以各災點需求量占總需求量的比例為權重來分配物資，設計改進的非支配排序遺傳算法來求解沖突帕累托解。Jincheng等[8]把時間、路徑可行性加入模型中，提出一種帶有車輛調度的應急物資模型來解決物資調度問題，但未考慮應急物資的分配公平性和成本控制。張力丹等[9]以應急調度救援成本和救援的不及時造成的損失為目標構建多目標數(shù)學模型，利用遺傳算法求解此類大型應急調度問題。王付宇等[10]針對地震后的應急物資配送問題，建立了以總救援時間最短和相對綜合救援權重值最大的多目標數(shù)學規(guī)劃模型。王飛躍等[11]考慮物流成本與系統(tǒng)損失，建立了基于路況的最小化救災行動的成本和最大化有限救災資源分配的多目標應急資源配置模型。王旭坪等[12]量化災區(qū)人民的不理智攀比心理，為了體現(xiàn)分配的公平性，建立了攀比目標函數(shù)。

以上文獻雖然將災民滿意度與時間滿意度以及公平性等目標考慮到模型里面，但是公平分配只針對物資分配量的公平，沒有考慮分配物資時間方面的公平。并且，關于災民的需求滿意度的研究，僅與本受災點物資分配量有關，沒有考慮到災民的滿意度和本受災點物資分配量以及其他受災點物資分配量都有關系，也沒有將道路異質性與災區(qū)異質性等特點考慮到所建立的模型之中。

綜上所述，目前已有部分學者對應急物資需求滿意度與救援時間方面作為目標來進行研究，但是成果較少。本文研究利用人們具有攀比心理來定義災民的滿意度與時間分配公平函數(shù)，本文在現(xiàn)有文獻研究基礎上，以本受災點物資需求滿足程度與其他各個災點的物資滿足程度相比較，從而得出本受災點的需求滿意度，以本受災點物資分配時間和其他受災點物資分配時間的比較來體現(xiàn)時間上的分配公平。本文研究與之前文獻的研究不同在于：(1)本文的災民需求滿意度是通過各個災點物資分配量的比較而計算得出；(2)利用各個災點的救援時間的比較來構造分配時間公平函數(shù)，且將災區(qū)異質性與道路異質性考慮到模型里，構建了多目標應急調度模型；(3)由于標準螢火蟲算法不適用于多目標求解，本文設計了改進的非支配排序螢火蟲算法來對模型進行求解研究。

1 模型構建

災難爆發(fā)后初期，由于應急物資的供不應求，如何對各個受災區(qū)進行合理的救援物資分配，有利于安撫災區(qū)人民[13]，以防傷員的人數(shù)進一步增加。由于人具有攀比的心理，人們在獲得援助時，不可避免地要關注別人所獲得的是否比自己獲得的要多得多，鑒于這種心理，考慮本受災點物資分配量與其他受災點物資分配量，以溫國峰[14]綜合考慮疫區(qū)民眾的時間風險感知、物資滿足率以及公平感知，建立動態(tài)分配模型為例，在此基礎上構建了災民物資滿意度目標函數(shù)和應急物資調度時間公平函數(shù)。

1.1 災民滿意度

Ri=riδi

(1)

(2)

(3)

1.2 差異化時間指標獲得

在應急調度中，每個災區(qū)都希望自己能盡快得到物資的援助，決策者在分配物資時，應該考慮到各個災點接受首批物資的總時間長短。影響救援中心到達災區(qū)的時間因素有很多[15]，主要包括道路的通行可靠性πh(h為道路總數(shù)目)、道路受災程度ρh、道路周邊基礎設施資源αh等。本文借鑒文獻對影響時間的各個指標進行數(shù)據(jù)搜集，衡量道路受災程度，考慮道路所在區(qū)域的傷亡人數(shù)與經濟損失等；衡量道路通行可靠性時，綜合運用一些方法來評估道路的可行性；衡量道路周邊基礎設施資源時，利用道路所屬區(qū)域的基礎設施競爭力指數(shù)來評估。

按照影響因素對時間距離的影響作用分為正向(ρh)與反向(πh、αh)。為了去除量綱，將正向指標與反向指標按照下式進行變換

(4)

(5)

r+=1,2,…,Z+;r-=1,2,…,Z-;h=1,2，…，n×m

(6)

Q′(hr+)、Q′(hr-)分別表示路徑h第r個正、負方向指標上的處理數(shù)據(jù)，Q(hr+)、Q(hr-)分別表示路徑h第r個正、負方向指標上的原始數(shù)據(jù)，Z+、Z-表示正、負方向指標的個數(shù)。將處理后的數(shù)據(jù)進一步平均化，以平均化后的指標作為時間差異化的度量指標。

(7)

1.3 時間公平

當物資調度時間差別太大，會影響部分災民的救助，物資調度的時間公平需要保障。tik表示救援中心k與災點i的時間距離，Tij={Ti-Tj}，Tij表示災點i與災點j比較時的救援時間滿意度，Ti、Tj分別表示災點i和j救援時間偏度。由于種種因素的影響，定義救援中心到達災點i的最小救援時間Tip為參照點，Tip=min{tikLh,h=i×k,?i∈I,?k∈K}，災點i救援時間計算如式(8)，這里假設所有車輛正常情況下行駛速度相同，時間偏度計算如式(9)，時間公平目標函數(shù)如式(10)。

tik=Dik/v,i∈I,k∈K

(8)

(9)

(10)

1.4 成本

在應急救援中，決策者首要考慮災區(qū)的需求滿意度與時間公平，也要考慮整個救援工作成本的大小。本研究將整個救援工作的總成本定義為

(11)

1.5 應急調度模型

1.5.1 模型參數(shù)說明

I表示災點集合，I={1,2，…n}，i,j∈I；K表示救援中心集合，K={1,2,…m}，k∈K；wi表示災點i的權重；ri表示災區(qū)i的幸存人數(shù)；δi為災區(qū)i幸存人數(shù)的人均物資消耗量；Ri表示災點i應急物資需求量，可事先依據(jù)災點情況預測；Gk表示救援中心的物資儲備量；oi表示災點i的物資滿足程度；oij表示災點i與災點j比較時，災點i的滿意度；cik表示救援中心k到災點i的單位物資物流成本；xik表示救援中心k分配給災點i的物資量；tik表示救援中心k到災點i的時間距離；Lh為時間差異化衡量指標；Ti表示災點i接受物資的救援時間偏離度；Tip表示各個救援中心到災點i的平均救援時間；Tij表示災點i與災點j的救援時間差；Dik表示救援中心k與災點i的距離。

1.5.2 模型構建

建立的應急物資分配多目標模型為

(12)

(13)

(14)

s.toij={oi-oj},?i,j∈I

(15)

Tij={Ti-Tj},?i,j∈I

(16)

(17)

(18)

(19)

(20)

其中，式(12)為災民需求滿意度，其值為負數(shù)，為0時，表示各個災點物資滿足程度沒有差別；式(13)為時間公平函數(shù)；式(14)為總成本函數(shù)；式(15)為滿意度計算方式；式(16)為時間公平衡量方式；式(17)為各個災點權重計算方式；式(18)表示災點獲得的應急物資量小于其需求量；式(19)表示救援中心援助各個災點的物資量總量不大于其儲備量；式(20)表示決策變量為非負整數(shù)。

2 算法設計

多目標問題中的各個目標是互相牽制對方的，無法得到使每個目標都是最優(yōu)的最優(yōu)解，得到的是一組帕累托解[16]。隨著智能優(yōu)化算法的發(fā)展，如多目標粒子群算法、NSGA-II算法的出現(xiàn)，為多目標問題的解決提供了有力方法[17]。印度學者Kaipa和Ghose提出了一種新型智能算法，即螢火蟲算法[18]。由于該算法具有實現(xiàn)簡單、參數(shù)少等優(yōu)點，廣泛應用于諸多領域[19-22]，本文研究了標準螢火蟲原理，設計了改進多目標螢火蟲算法來求解該應急物資調度模型。

2.1 標準螢火蟲算法

設xi(t)表示t代i螢火蟲位置，li(t)表示該螢火蟲的熒光素濃度，熒光素的更新由其自身更新與適應度值修正兩部分組成，在每一次迭代時，使熒光素變化與適應度值相關，螢火蟲在移動過程中朝著熒光素濃度最高的螢火蟲前進，即向適應度值最優(yōu)的螢火蟲前進。

li(t+1)=(1-ρ)li(t)+λF(xi(t))

(21)

式中，ρ為熒光素揮發(fā)系數(shù)，λ為目標函數(shù)值修正系數(shù)，F(xiàn)(xi(t))表示t代螢火蟲i的目標函數(shù)值，即適應度值。

螢火蟲移動過程中，依據(jù)選擇概率選擇領域內螢火蟲進行移動，i螢火蟲選擇領域內j螢火蟲的選擇概率計算如式(22)，Ni(t)表示螢火蟲i的領域，其按照式(23)計算，螢火蟲位置更新如式(24)，移動結束后，以式(25)更新決策半徑。

(22)

(23)

(24)

(25)

2.2 改進多目標螢火蟲算法

步長處理：標準螢火蟲算法在搜索最優(yōu)解過程中，始終保持固定步長，導致算法性能低下。正切函數(shù)y=tan(x)的原理是當括號里的自變量x為0.785時，y為1，y的值隨著x的值減小而逐漸減小，在這個過程中y的減小速率也是逐漸變小。為了使螢火蟲算法在搜索過程中步長值可以自適應逐漸變小，因此將正切函數(shù)引入步長更新公式中，改進螢火蟲步長更新機制如式(26)。

(26)

式中：tmax、t分別為最大迭代次數(shù)和當前迭代次數(shù)，s、s0分別為螢火蟲算法步長和步長固定參數(shù)，且步長固定參數(shù)取值為1，改進步長變化趨勢如圖1所示，算法前期，以較大步長搜索，使算法有更好的全局搜索能力，隨著算法迭代，步長逐漸慢慢縮小，增強算法局部搜索能力。

圖1 改進步長變化趨勢圖

多目標處理：標準螢火蟲算法首先利用熒光素在決策半徑內確定領域，然后選擇一個領域最優(yōu)螢火蟲，逐漸向其靠近。為了使螢火蟲算法適用于本文問題模型，需要將非支配排序思想引入螢火蟲算法中，本文以求解兩個最小化目標為例來進行描述，具體如下。

(27)

(28)

位置更新：由于是多目標，原先的熒光素導向更新機制不再適用。本文在Pareto解集里尋找領域，然后，以領域內所有個體位置的平均值來進行位置更新，具體方法為

(29)

(30)

(31)

當螢火蟲領域為空集時，螢火蟲便不會繼續(xù)移動，因此，本文設計了第二種位置更新機制，以避免算法陷入極值，螢火蟲i直接從Pareto解集里隨機選擇一個Pareto解去更新，更新機制具體為

(32)

式中：xpareto(t)表示Pareto解集里隨機選擇的螢火蟲位置。

2.3 改進多目標螢火蟲算法步驟

Step1：設置算法參數(shù)，最大迭代次數(shù)tmax，種群大小，初始決策半徑，步長固定參數(shù)s0等，生成初始解；Step2：計算種群目標函數(shù)值，并且依據(jù)目標函數(shù)值篩選初始帕累托解；Step3：循環(huán)開始，更新算法參數(shù)，在帕累托解集按照式(29)搜索領域；Step4：利用帕累托解，按照式(30)、(31)更新種群個體位置；Step5：判斷領域是否為空集，如果領域為空集，則按式(32)更新種群個體位置；Step6：計算種群目標函數(shù)值，更新帕累托解集；Step7：判斷算法是否達到最大迭代次數(shù)，若是，結束算法，輸出解，否則，轉step3。

3 算例驗證

3.1 參數(shù)設計

由于某種突發(fā)性災難，致使周圍8個地區(qū)成為災區(qū)，附近有5個可供救援物資的救援中心，且物資儲備量分別為G1=1000，G2=800，G3=1500，G4=1200，G5=1400。經過相關專家根據(jù)災區(qū)情況預測出各個災區(qū)的物資需求量，如表1所示，救援中心與災區(qū)之間的單位物資運費如表2所示，距離矩陣如表3。

3.2 計算結果

運用改進多目標螢火蟲算法、標準螢火蟲算法以及多目標粒子群算法來求解該模型。硬件環(huán)境為Intel(R)Core(TM) i7-1065G7@ 2.52 GHz 雙核處理器，運行內存8 GB，軟件環(huán)境為Window8系統(tǒng)64 位，編程軟件為Matlab R2014b軟件。設置種群大小為100，步長固定參數(shù)s0=1，最大迭代次數(shù)tmax為200，為了比較算法性能，3種不同算法相同參數(shù)取值一致，結果如表4，模型初始解分布如圖2。

圖2 初始解分布

由于篇幅限制，表4展示Pareto解集里部分結果，改進多目標螢火蟲算法所求Pareto解集分布如圖3所示，具體物資分配方案如表5所示。除此之外，利用算法對不考慮路徑異質性的應急物資配置方案進行了求解(見表6)。

由表5、表6可以看出，考慮路徑異質性特點時所求得物資分配方案下的災區(qū)需求滿意度值雖然略大于不考慮路徑異質性所得方案的災區(qū)需求滿意度值，但是時間公平函數(shù)值具有明顯差別(1.6<2.016)?？紤]路徑差異所產生的時間差異化影響因素，所求得方案時間公平目標更為優(yōu)化，也更符合實際情況，原因在于，同樣物資滿足的情況下，若時間和往常一樣，可能會產生時間上的浪費。

圖3 改進螢火蟲算法Pareto分布

表1 災區(qū)信息

表2 救援中心與災區(qū)之間的單位物資運費

表3 救援中心與災點距離

表4 算法計算結果

表5 考慮路徑異質性應急物資配置方案

表6 不考慮路徑異質性應急物資配置方案

3.3 算法性能比較

通過比較收斂性指標γ和分布性指標Δ來比較算法性能，由于在計算時需要真實最優(yōu)Pareto，所以，本文將全部運行結果合并為一個集合代替最優(yōu)Pareto解集。

(33)

(34)

表7 算法評價指標

由表7可得，從收斂性指標γ來看，改進螢火蟲算法要優(yōu)于標準螢火蟲算法，從分布性指標Δ來看，改進螢火蟲算法與多目標粒子群算法無顯著差異，且優(yōu)于標準螢火蟲算法。

4 結論

應急物資配置是災后及時開展救援工作的首要任務，合理、科學地制定應急物資調度方案對于防災減災具有重要意義。之前的應急物資配置研究，公平分配只針對物資分配量的公平或者分配物資時間方面的公平，很少有學者將二者結合起來進行研究。并且，沒有考慮到災民的滿意度和本受災點物資分配量以及其他受災點物資分配量都有關系，也沒有將時間差異性特點考慮到所建立的模型之中。

本文利用時間差異化指標、距離來對各個救援中心到災點的時間進行差異化模擬，基于受災點需求程度與其他災區(qū)需求程度構建了以需求滿意度為目標和時間公平目標的應急物資多目標模型?；诜侵渑判蛩枷?，改進設計了多目標螢火蟲算法，通過仿真案例的求解與分析，證明了模型的可行性與算法的有效性。