設施失靈風險下不確定需求應急定位-路徑魯棒優化研究

孫華麗，項美康

(上海大學管理學院，上海 200444)

1 引言

地震、洪澇和雪災等自然災害的頻繁發生不僅威脅著人類的生命，也對國家經濟運轉和社會穩定發展產生重大影響。科學地進行應急救援設施選址和應急救援物資配送體系優化可以最大限度地降低災害帶來的損失。突發災害具有破壞力強，難以準確預測等特點，常致使道路或救援設施等受損，應急物資需求難以準確預測，增加救援物資配送工作的挑戰性。應急物流定位-路徑(location-routing problem，LRP)問題將應急救援設施的選址問題和救援物資配送路徑問題集成研究[1]，可以增強應急救援物流系統的抗風險性。

應急物流定位-路徑優化問題受到國內外很多學者的關注。早期學者對單目標信息確定的應急定位-路徑問題進行研究。曾敏剛等[2]將減災系統定位-路徑問題劃分為應急設施選址和應急資源運輸路線安排兩個子問題，建立了最小化總成本為目標的應急LRP優化模型，采用混合啟發式算法進行求解。王紹仁和馬祖軍[3]以最小化總救援時間為目標，設計了基于兩階段分解思想的“三角”啟發式算法。也有學者對信息確定的多目標應急定位-路徑問題進行了研究， Abounacer等[4]構建了以運輸時間和應急設施點規模最小為目標的應急物流定位-路徑模型，并將Pareto優化算法運用到模型的求解中。Wang Haijun等[5]建立了一個考慮運輸時間、總成本和分配可靠性的非線性整數規劃定位-路徑模型，并以汶川地震為例，對模型與算法的有效性進行驗證。樓振凱[6]以應急物流系統響應時間最小為上層目標，以配送成本和時間懲罰成本之和最小為下層目標，建立了設施定位-運輸路線問題的雙目標規劃模型。還有學者對信息不確定的應急定位-路徑問題進行了研究。針對需求的不確定，Goli和Alinaghian[7]以最長路徑救援時間最小為目標建立定位-路徑模型。Caunhye等[8]建立了最小化設施建設成本和最長路徑救援時間為雙目標的兩階段LRP模型。李雙琳等[9]以最小化應急物資配送總時間和受災點應急物資未滿足的總損失為雙目標，建立了多式聯運問題優化模型，采用非支配排序多目標遺傳算法求解。對于時間不確定的應急定位-路徑問題研究，Toro-Díaz等[10]建立了整數規劃的選址-配送決策模型和解決排隊及擁堵現象的超立方體綜合模型，采用改進的遺傳算法求解。Zarandi等[11]考慮需求點的時間窗約束，基于模糊機會約束規劃建立了最小化總成本模型。也有學者開展多不確定信息的應急定位-路徑問題研究，劉長石等[12]考慮救災點應急物資需求量的不確定及車輛行駛時間的隨機性，以最小化救援物資運達總時間和總成本為目標，建立了模糊機會約束規劃模型。Bozorgi-Amiri和Khorsi[13]等假設應急資源需求、應急救援時間和費用不確定，建立了以需求不滿足率、總救援時間和總救援成本最小為目標的LRP模型。Moreno等[14]考慮應急救援中多階段、多物資、多模態環境下的不確定問題，以救援總成本最小為目標建立兩個隨機混合整數規劃模型。孫華麗等[15]假設需求量和單位運輸費用均為模糊變量，采用模糊機會約束理論，以最小化系統總成本和災害損失成本之和為雙目標建立了應急物流定位-路徑模型。Bai Xuejie[16]考慮到需求和道路連通性的不確定，以物資需求的未滿足率、應急響應時間和總成本最小為目標建立多目標期望值模型。Chang Keliang等[17]假設需求及運輸速度不確定，建立了最大化最長路徑滿意度和最小化總成本及道路運輸能力為目標的非線性定位-路徑問題。

綜上，當前研究的不足如下：(1)實際中很多不確定信息是離散的，或隨機變化的，而現有文獻多是用模糊數來表示需求等不確定信息，或假定其服從某種概率分布。(2)實際救援中，因災害的破壞性或次生災害常造成區域內道路等基礎設施中斷或設施點失靈，而現有文獻很少考慮上述風險對救援系統的影響。為此，針對需求的不確定，本文采用區間數進行表述，基于偏差魯棒優化的思想解決應急設施點的失靈風險，采用直升機進行運輸以規避路徑中斷風險，構建了最小化總救援時間及系統總成本的雙目標LRP魯棒優化模型，基于遺傳算法對其求解。

2 模型描述

2.1 問題描述

突發自然災害后，快速選擇機場，火車站等作為臨時應急設施點，及時安全地將救援物資運送到各個受災點是應急救援的關鍵。由于存在道路受損中斷風險，采用直升機將物資從臨時應急設施點配送至災害需求點，但次生災害可能導致臨時設施點突然失靈，無法及時完成受災點的物資配送任務。問題是如何在物資需求不確定，設施點存在失靈風險下，集成救援設施點選址和物資運輸路徑規劃，以最小化系統總成本及總救援時間。本文假設災害發生區域有l個應急候選救援設施點，n個物資需求點，h架救援直升機。所有直升機都為同質的。每個候選應急設施點都可能失靈，但每次失靈至多一個設施點，失靈的設施點不能提供服務。此時，直升機選擇從離該需求點最近的臨時應急救援設施點運送物資到需求點。救援直升機容量不超過任何一個應急候選救援設施點的容量；每個需求點只能被一架直升機服務，其需求量不超過直升機容量。每架直升機起飛于應急設施點，完成任務后原地待命。

2.2 符號說明

為了方便描述問題，定義如下符號和變量：

臨時應急救援設施點集合J={1,2,3,…,l},j∈J；災區物資需求點集合I={1,2,3,…,n},i∈I,r∈J∪I；救援直升機集合H={1,2,3,…,h},h∈H；dij-兩點之間的距離；qri-災區物資需求點i的物資需求量；dhi-直升機到達需求點i時已經行駛的距離；thi-直升機到達點i的時間；vh-直升機的速度；qli-需求點i的物資缺少量；wji-直升機從應急設施點j運送到災區物資需求點i的物資總量；cj-選擇應急救援設施點j的固定費用；cl-直升機單位載貨量的裝載費用；ct-直升機單位距離單位運量的運費；m1,m2分別為臨時應急救援設施點，救援直升機的最大裝載能力。

Xji=

2.3 模型構建

在前述假設基礎上，可以構建應急救援物資配送的雙目標確定LRP模型如下：

(1)

(2)

*qri,h∈H

(3)

(4)

(5)

(6)

(7)

(8)

m2≤m1

(9)

dhi=(dhr+dri)Zrih,r∈(I∪J),

i∈I,h∈H

(10)

(11)

Uj,Xji,Zrih∈{0,1}

(12)

模型中式(1)為最小化系統總救援時間，式(2)為最小化包括應急救援設施點的固定費用、直升機的裝載費和運輸費等系統總救援成本。式(3)表示直升機h在保證不超過自身裝載能力的前提下，盡可能地滿足其所服務需求點的需求量；式(4)表示直升機裝載能力約束；式(5)表示應急設施點的容量限制；式(6)保證需求點接受直升機和應急設施點服務的唯一性；式(7)表示直升機不會從未選中的應急救援設施點發出；式(8)保證應急救援設施點之間不連通；式(9)表示應急救援設施點與直升機容量關系；式(10)直升機飛行距離dhi的表達式；式(11)給出了直升機到達救援物資需求點i的時間表達式；式(12)為整數變量非0即1約束。

2.4 雙目標的轉化

(13)

2.5 基于魯棒優化的不確定信息處理

魯棒優化基于魯棒控制思想處理不確定數據集合，它不必掌握不確定參數的分布函數或取值的發生概率，通過求解問題的魯棒對應轉換模型以求解不確定優化問題[18]。災害發生時，決策者無法及時準確得到受災點物資需求情況，采用區間型集合描述受災點物資需求情況：

qri={qi|qi∈[q1i-q2i,q1i+q2i]},i∈I

(14)

q1i表示需求點i物資需求量的名義值，q2i表示偏離名義值的最大擾動值。在實際需求中，qri一般可根據災害級別、受災人口密度等信息預測。各種物資到達區間邊界的可能性極小，因為若qri=q1i-q2i，會造成需求的預期估計不足；若qri=q1i+q2i，為絕對魯棒問題，基于最大需求的情況會有失最優性決策的意義，造成物資的浪費。為此，參照相對魯棒模型[19]，在q2i中引入需求控制系數Γh描述需求的變化情況(控制系數越大，需求不確定越大)，代入式(3)中得：

h∈H

(15)

為了求解上述模型，引入引理1對式(15)進行轉化。

(16)

則等價于下面問題的最優目標值：

0≤zij≤1,?j∈Ji

(17)

引入需求擾動系數ηh來控制需求量擾動的范圍，進而調節模型解的保守性和最優性。依據強對偶定理及上述引理將前述模型轉化為下列魯棒優化模型：

ηh≥0,h∈H

ρhi≥0,h∈H,i∈I

(18)

(19)

因此，上述問題可轉換為以(1)-(2)為目標函數，以(4)-(13)和(18)-(19)為約束條件的設施點失靈風險下不確定需求定位-路徑魯棒優化模型。

3 遺傳算法設計

本文的應急物流LRP問題是一個NP-hard問題，精確算法很難有效求解，采用遺傳算法對其進行求解。

3.1 編碼

將每個染色體分為三段，用自然數進行編碼，第一段表示各救援直升機歸屬的應急設施點，有h個基因位，h為救援直升機數目，每個基因位都是在1到l的自然數中隨機產生；第二段表示將物資配送到各個受災需求點的救援直升機編號，隨機產生；第三段表示救援路徑中各受災需求點的服務順序，長度為n，每個基因位從1到n的自然數中隨機產生，與第二段基因位對應，但不能相互重復，則每條染色體長度可表示為(h+2n)。

3.2 初始種群及適應度函數

隨機產生N個初始種群，設第i條染色體為δi；第i條染色體的總目標函數值為Z；M為正大數。適應度函數為：

3.3 遺傳操作及終止條件

染色體的選擇策略采用輪盤賭和精英保留相結合的方法。染色體第一段基因采用單點交叉和對換變異操作；第二段基因使用兩點交叉和對換變異操作，第三段基因使用部分匹配交叉和逆轉變異操作。當遺傳算法的繁衍代數達到最大值時，輸出最優個體，終止算法。

4 算例分析

為驗證相對魯棒優化方法處理需求不確定和偏差魯棒思想解決設施點失靈的有效性和模型的適用性，本部分設計三個算例進行仿真分析。參照已有文獻并經試算，種群規模設置為100，最大迭代次數為500，權重為0.6，交叉概率和變異概率分別為0.7和0.05。采用Matlab7.11.0 (R2016a)編程，并在CPU為Intel 2.60GHz，內存為4G的計算機上進行仿真求解。

算例1選取4個候選應急救援設施點，15個受災需求點，8架同質的直升機運輸物資。部分數據選自文獻[3]的LRP問題。直升機飛行速度為210km/h，每份物資每千米的運輸費用為30元，每份物資裝載費為30元，最大裝載量為400份。設需求擾動系數為5%-20%，控制系數為1-15。表1-表2為候選應急救援設施點和受災需求點的相關數據。

表1 應急設施點數據

表2 受災需求點數據

4.1 不確定需求處理的有效性

對于不考慮設施點失靈和僅存在一個設施點失靈的情景，采用相對魯棒優化方法處理需求不確定對應急救援時間和成本的影響來驗證該方法的有效性。

限于篇幅，僅列出無設施點失靈和僅設施點1失靈情景下不同控制系數和需求擾動系數(5%，10%，15%，20%)對總目標函數值的影響，如圖1和圖2所示。由圖可看出，無論是否考慮設施點失靈，總目標函數值均隨著控制系數的增加而增大，且同一控制系數下需求擾動系數越大，總目標函數值增加越快。無設施點失靈情景下的總目標函數增長速度與僅考慮設施點1失靈情景下的總目標函數增長速度相似。

圖1 無設施點失靈情景下總目標函數增長比

圖2 設施點1失靈情景下總目標函數增長比

表3是不考慮設施點失靈和僅考慮設施點1失靈情景下，需求不確定時的目標函數值。Z1,Z2,Z含義同模型目標函數。由表3可知，無論是否考慮設施點失靈，總目標函數值和系統總成本隨需求變化范圍的增大，均呈現增長趨勢；總救援時間目標函數基本穩定在5.5-6.7小時，且受需求不確定的影響較小，這是因為應急救援直升機均僅需飛行一次即可滿足各需求點的物資需求量。在總目標函數值方面，不確定需求魯棒優化模型與需求確定模型(此時控制系數為0)的偏差呈現遞增趨勢。在需求不確定量(需求控制系數、需求擾動系數)相同時，僅考慮設施點1失靈情景的總目標函數值總略大于不考慮設施點失靈時的取值，這是因為有設施點失靈時，整個應急救援系統增加了直升機的額外運輸成本，但是這種方案是魯棒的。而不考慮設施失靈情景，一旦設施點失靈，方案將變得無效。

表3 不同情景下目標函數值

續表3 不同情景下目標函數值

圖3 控制系數對偏差魯棒后悔值的影響

因此，可以得出結論，需求信息不確定性越大，為了滿足所有需求，其系統總成本將越大。在實際中，可以依據需求不確定情況確定需求控制水平，最終制定科學的方案。

4.2 設施點失靈處理的有效性

為了驗證偏差魯棒優化方法處理設施點失靈風險的有效性，對比不同需求下偏差魯棒后悔值的變化情況。圖3給出了在需求控制系數為0-15，所有可能情景(僅一個設施點失靈)的偏差魯棒后悔值隨著控制系數的變化情況。由圖可知，后悔值最大為6.50；控制系數為9時，后悔值最小為2.34；其次控制系數為5時，后悔值為3.47，其余均在最大后悔值附近，總體上偏差魯棒后悔值不受控制系數的影響，即模型的最優解對大部分情景下的后悔值比較均衡。這說明偏差魯棒優化方法能有效處理設施點失靈風險。

4.3 模型的適用性

算例2 為驗證模型的適用性，在算例1的基礎上增加候選應急救援設施點、受災點和直升機數量，生成另外兩個算例，其中算例2是8個候選應急設施點，20個受災點，10架直升機。新增候選應急設施點的坐標分別為E5(20,50)、E6(100,235)、E7(225,170)、E8(70,15)，其對應的容量和選擇成本分別由集合{1000,800,1000,800}和集合{20841,21961,17570,17497}給出。新增加受災點分別為D16(60,30)、D17(40,120)、D18(80,40)、D19(150,170)、D20(230,100)，其對應的物資需求名義值由集合{60,20,30,40,40}給出，其他信息同算例1。分別求出需求控制系數為4、12、20時，需求擾動量為5%、10%、20%，不考慮設施點失靈和僅考慮設施點1失靈時確定模型與魯棒優化模型的總目標函數值對比情況如表4所示。

算例3再次增加候選應急救援設施點、受災點和直升機數量，使問題變為10個候選應急設施點，25個受災點，16架直升機。限于篇幅，新增候選應急設施點和受災點相關信息不再給出，其他信息同算例2。分別求出需求控制系數為5、15、25時，需求擾動量為5%、10%、20%，存在設施點失靈風險的確定模型與魯棒優化模型的總目標函數值如表4所示。

由表4可以看出，確定模型的總目標函數值隨問題規模的擴大而增大；而魯棒優化模型則在需求不確定范圍增大時，總目標函數值也隨著增大，且無論是否考慮設施點失靈，魯棒優化模型的總目標函數值始終大于確定模型的值。表4中的“可行解個數”一列為不考慮設施點失靈時魯棒優化模型的可行解情況。具體操作如下：在需求名義值區間中隨機取20個隨機數，將這20個數分別代入不考慮設施點失靈下魯棒優化模型，得到選址方案，在此選址方案的基礎上，觀測解的可行性。這時，只有在設施點1剛好未被選擇為服務的設施點時，才能得到可行解，因此，表中可行解個數多為0。由此說明魯棒優化處理需求不確定和設施點失靈應急定位-路徑優化問題的適用性。

表4 魯棒模型與確定模型解的比較

5 結語

本文對應急設施點失靈風險下的需求不確定應急物流定位-路徑問題進行了深入研究，針對災害、后的路徑風險，采用直升機運送模式規避。以最小化系統總成本和救援運輸時間之和為雙目標，分析采用相對魯棒優化的區間型數據描述方法處理應急需求的不確定和偏差魯棒優化思想處理應急設施點的失靈風險。為了說明魯棒優化方法和模型的適用性，對三個算例進行仿真對比分析，結果表明，無論設施點是否失靈，總救援成本和總目標函數值隨著需求不確定的增大，呈現遞增趨勢，而總救援時間幾乎不受需求不確定的影響。偏差魯棒優化處理各設施點失靈時的后悔值基本不受需求不確定的影響。總的來說，采用相對魯棒優化處理應急物流定位-路徑問題的需求不確定和采用偏差魯棒優化處理設施點失靈風險均表現出較好的適用性，從而提高決策者制定救援方案的抗風險性和科學性。

然而，由于直升機的運輸距離受限且費用大，在應急物流系統中，后續研究將考慮車輛運輸為主，直升機運輸為輔的多式聯運三級路網模式，并且同時考慮道路運輸超期風險和設施點失靈風險。