震后初期應急物資短缺情景下的定位-路徑問題研究

盛虎宜, 劉長石, 魯若愚

(1.電子科技大學 經濟與管理學院，四川 成都 611731； 2.湖南商學院 工商管理學院，湖南 長沙 410205； 3.湖南商學院 移動商務智能湖南省重點實驗室，湖南 長沙 410205)

0 引言

地震災害具有突發性與強破壞性，經常造成嚴重傷亡與巨大財產損失。為有效開展抗震救災工作、同時滿足災區群眾的應急物資需求，應急物資應盡快配送到需求點。應急物流的實踐工作證明有效保障災后應急物資供應的關鍵在于合理進行應急設施定位分配(Location Allocation Problem, LAP)與科學規劃應急物資配送路線(Vehicle Routing Problem, VRP)，而且二者相互依賴、相互影響，應將二者整體規劃與優化，即研究震后應急物資配送的定位-路徑問題(Location-Routing Problem, LRP)[1,2]。

學者們已經基于不同視角研究了應急物資不同配送情景下的LRP。部分學者綜合考慮災區路網存在損毀、受損路網動態恢復與應急物資動態需求等情況，分別以總配送成本最小、總配送時間最短為目標構建數學模型，并設計相應優化算法求解應急物資配送的LRP[3～5]。文獻[6]考慮應急物資模糊需求與多式聯運情景下的LRP，以總配送時間最短、應急物資短缺情景下受災點的總損失最小為目標構建多目標的LRP數學模型，設計多目標遺傳算法求解。文獻[7]綜合考慮震后多品種應急物資、多方式配送與公平分配等因素構建動態LRP數學模型。文獻[8]研究了應急物資的中轉運輸問題，設計應急物資需求點的滿意度函數，在此基礎上構建基于時間滿意度LRP數學模型，設計啟發式模擬退火算法求解。文獻[9]考慮了多階段隨機需求情景下應急物資配送的LRP，以總運輸時間最短、系統總成本最小為目標構建LRP模型。文獻[10]綜合考慮災區路網損毀、配送時間限制與配送路線可靠性等因素，構建震后應急物資配送的開放式LRP數學模型。文獻[11]整體優化災后應急中轉點選擇與醫療物資多方式聯合配送路線。文獻[12]綜合考慮應急物資配送的多車型、開放式車輛路徑與模糊需求等因素，以總運達時間最短、總配送成本最小為目標建立LRP模型。文獻[13]在綜合考慮應急物資覆蓋率、倉庫建設費用與配送費用等因素的基礎上構建多目標LRP模型，設計數學啟發式求解算法。文獻[14]針對震后初期應急路網部分受阻、應急物資短缺與多方式配送的兩層配送網絡，以總配送時間最短、受災點的應急物資滿足率最大為目標構建LRP模型。文獻[15]綜合考慮應急物資模糊需求、部分道路損毀與車輛不確定行駛時間等因素，以總運輸時間最短、總運輸成本最小為目標構建LRP模型。文獻[16]綜合考慮應急路網可靠性、總配送成本與開放式路徑等因素構建應急物資配送的LRP模型。文獻[17]研究應急物資供應網絡的動態LRP，以總運輸時間最短、系統總成本最小為目標構建LRP模型。最近，還有文獻[18]研究了震后災區應急物流路網存在故障與救援時間限制條件下的LRP，文獻[19]研究了車輛行駛時間隨機與模糊需求情景下震后應急物資配送的LRP，文獻[20]考慮了震后應急物資多方式供應的動態LRP，文獻[21]研究了應急物資災前預置與災后配送聯合優化的LRP，文獻[22]設計了一種兩階段連續近似方法求解災后應急物資配送的LRP。

已有成果從不同角度對應急物系統中的LRP進行了有益探索，為后續研究奠定良好基礎。分析已有文獻，發現如下研究缺口：①已有成果大多假設應急物資對每個需求點的重要程度相同，鮮少考慮災害級別與應急物資短缺情景下需求點造成損失的難易程度；②震區道路遭受不同程度損毀，導致應急車輛行駛時間隨機，相關研究文獻不多。震后初期，災區預置的應急救災物資儲備總量通常不能滿足災區的應急物資需求[23,24]。與此同時，震區道路遭受不同程度損毀，難以及時修復，災區外部的應急物資在短時間內難以及時運達災區。在地震災害等特殊環境下，受災群眾身心相對脆弱。如果應急物資不公平分配，容易引發人們的公憤，甚至可能演變成為群體性事件，導致嚴重后果[7,26]。因此，本文基于公平與效率兼顧視角研究震后初期應急物資短缺情景下的LRP，為有效保障應急物資供應提供參考。

1 模型構建

1.1 問題描述

震后，需在規定時間內將物流中心的應急物資配送到需求點。為明確本文適用范圍，提出如下假設：①震后初期應急物資短缺，難以滿足災區需求；②災區路網存在不同程度的損毀情況，應急車輛行駛時間具有不確定性；③應急物流中心可以征調到足夠的運輸車輛，車輛具有不同類型與容量；④應急物資運達需求點具有時間期限。決策問題：在公平與效率兼顧的前提下如何合理規劃應急物資配送方案？

1.2 符號說明

參數：B{b|b=1,2,…,m}為應急物流中心集合；gb為物流中心b擁有的應急物資數量；V{r|r=1,2,…,k}為應急車輛集合；qr為車輛r的容量；C{i|i=1,2,…,n}為需求點集合；di為需求點i的應急物資需求量；si為需求點i的應急物資實際分配量；N=B∪C為應急物流網絡內的所有節點集合，i,j∈N；tijr為車輛r從節點i行駛到節點j的隨機時間；l為應急物資配送時間期限。

決策變量：βbi為需求點i(i∈C)被分配給物流中心b(b∈B)則為1，否則為0；xijr為車輛r(r∈V)從節點i(i∈N)行駛到節點j(j∈N)則為1，否則為0。

1.3 應急物資公平分配

已有部分學者從不同視角探討了災后應急物資的公平分配問題，分別以單個需求點最大缺貨量最小[1]、需求點的累計滿足率最大[7,14]、應急物資短缺情景下受災點的總損失最小[10,16,24]為目標構建數學模型進行應急物資公平分配。文獻[23,25]基于公平理論與前景理論構建應急物資公平分配的多目標數學模型，文獻[27]通過在負效用函數中引入災民需求未滿足的比例量化了災后資源嚴重短缺情況下的應急物資公平分配效果。最近，有學者基于公平與效率兼顧的視角探討了應急物資分配問題[28～30]，分別以需求點未滿足的需求量之和最小表示應急物資分配的公平性、以總配送延誤時間最小表示應急物資配送的效率性[34]。本文綜合參考上述文獻方法，綜合考慮應急物資短缺、災害級別、需求點的易損性等因素，設計需求點損失函數，具體如下：

(1)

其中，1/Dγ表示歸一化處理，γ≥1。

以單個需求點的最大損失最小為目標來衡量應急物資分配數量的公平性，即

(2)

1.4 LRP模型

以單個需求點的最大損失最小為應急物資分配的公平性衡量指標、以總配送時間最短為應急物資配送的效率性衡量指標，建立LRP模型如下：

式(3)為公平目標，最小化單個需求點的最大損失；式(4)為效率目標，最小化總配送時間。約束式(5)表示災區應急物資短缺；約束式(6)表示分配給某一物流中心的所有需求點的應急物資實際分配數量總和不能超過該物流中心的擁有數量；約束式(7)表示要把所有物流中心的應急物資全部分配；約束式(8)表示分配給某一車輛的所有需求點的應急物資實際分配數量之和不超過該車輛的容量限制；約束式(9)表示車輛行駛路徑連續性約束；約束式(10)表示子巡回消除約束；約束式(11)表示車輛只能分配給一個物流中心；約束式(12)表示車輛從上一個節點行駛到下一個節點的時間計算方法；約束式(13)表示車輛到達需求點的時間不能超過時間期限；約束式(14)表示變量取值約束。

1.5 車輛隨機行駛時間計算

(15)

關于災后應急車輛隨機行駛時間的研究成果屈指可數。文獻[2]與文獻[20]對行駛在震后災區損毀道路上的車輛隨機行駛時間進行了模擬仿真。文獻[15]認為行駛在災區損毀道路上的車輛隨機行駛時間服從正態分布。文獻[31]研究了汶川地震之后的災區道路損毀程度量化問題，將災區道路損毀程度?ij分為5個級別。即：?ij>0.3表示節點i與j的之間的道路完全損毀、0.2

(16)

其中，M表示山區、P表示平原。決策者可以根據實際經驗合理確定ε、η、σ、φ、ξ、ψ的值。

2 混合啟發式算法

分層序列法能有效求解多目標優化問題，核心思想是將所有目標按照重要性程度排序，首先求出前序目標的最優解，再使用前序目標最優解依次求出后序目標的最優解[23,33]。遺傳算法具有隨機化搜索、多點并行搜索與魯棒性等特性，已經被廣泛應用于各研究領域[7,14]。因此，針對模型特點，本文采用分層序列法的思想設計二階段混合啟發式求解算法，第一階段進行應急物資分配，第二階段采用遺傳算法規劃應急物資配送方案。

2.1 應急物資分配算法

步驟1初始化。輸入di、gb、γ、δi的值，令當前迭代次數iter=1，z1=∞，最優分配方案Sbest=φ。

步驟4算法結束判斷。如果iter等于最大迭代次數，算法結束，求得z1與Sbest；否則，iter=iter+1，轉步驟3。

2.2 遺傳算法設計

步驟1種群初始化。將目標函數z2及約束條件對應于抗原，問題的解對應于抗體。設定群體規模為E，隨機生成一組抗體作為遺傳算法的初始抗體群W。

抗體由3個子串組成。子串1為實數編碼，長度為m×n，表示物流中心b對需求點i的配送量?bi。子串2為自然數編碼，長度為n，表示為需求點服務的車輛序號r。子串3為實數編碼，長度為n，表示車輛到達需求點的時間Tir。

(17)

而且fitness(w)的值越大，抗體w與抗原的親和力Q(w)越大，表明該抗體越優。

步驟4抗體促進與抑制。①根據抗體編碼特征，定義抗體w的濃度為

(18)

②根據種群的親和力類型總數κ，設定抗體濃度閥值為κ/E。③選擇親和力較高而且濃度較低的抗體進行促進。④當抗體的濃度達到閥值時，隨機生成超濃度規模數量的ω條新抗體替換舊抗體進行抑制。

步驟5遺傳操作。采用精英選擇和輪盤賭選擇方法進行遺傳操作。另外，抗體的子串1與子串3采用文獻[7]設計的算術交叉方法，子串2采用順序交叉與逆轉變異方法。

步驟6終止條件。算法迭代maxgen次后結束，得出最優z2。

3 算例分析

采用文獻[16]中汶川地震之后的帳篷配送數據作為基礎構造算例，具體如下：①需求點汶川(V1)、綿竹(V2)、北川(V3)、青川(V4)、茂縣(V5)、都江堰(V6)、安縣(V7)、平武(V8)、彭州(V9)、江油(V10)與德陽(V11)的帳篷需求量、易損性如表1；②物流中心成都(V12)、綿陽(V13)與廣元(V15)的擁有應急物資數量如表2；③各物流中心擁有大型卡車、中型卡車、小型卡車的行駛速度與容量如表3；④應急物流網絡圖中的劍閣(V14)表示轉運點，節點之間的鏈路表示可用道路，可用道路越粗表示該道路允許車輛行駛的速度越大，一共有4種類型的可用道路：快速通行道路(限速80KM/小時)、中速通行道路(限速60KM/小時)、緩慢通行道路(限速40KM/小時)、難以通行道路(限速20KM/小時)，如圖1。⑤采用百度地圖里面的推薦路線距離計算方法求得應急物流網絡中節點之間的距離，如表4。⑥限于篇幅，需求點j的地形yj、節點i至節點j之間的道路損毀程度指標?ij等不再一一詳細描述。

程序采用Matlab 2013a編程，參數設置：maxgen=1000、γ=1.5、l=24小時，ε=4、η=3、σ=2、φ=3.5、ξ=2.5、ψ=1.5、ζ=5。

將本文的公平分配方法(BW)與文獻[23]的優先考慮應急物資歸屬地的分配方法(GS)、文獻[25]的比例分配方法(BL)比較，各需求點的分配數量(FP)、需求點損失(SS)如表5所示。按照文獻[23]的應急物資歸屬地方法(GS)，成都配送中心必須優先考慮都江堰(V6)、彭州(V9)的應急物資需要，綿陽配送中心必須優先考慮北川(V3)、平武(V8)、江油(V10)的應急物資需要，廣元配送中心必須優先考慮青川(V4)的應急物資需要。然后，如果各配送中心還剩余應急物資，再考慮其他屬地需求點的需要。值得注意的是，GS方法容易導致具有優先分配權的需求點應急物資滿足率達到100%，而受災比較嚴重的汶川(V1)、茂縣(V5)竟然沒有優先權，甚至沒有同等對待。這種情況下，容易引起災區群眾的不滿，引起公憤，極端情況下可能發生應急物資哄搶等社會事件，導致嚴重后果(例如2010年海地地震之后發生了災民哄搶應急物資的事件)。震后應急物資分配應“以人為本”，綜合考慮公平、效用與易損性等因素，盡可能避免社會事件。

圖1 應急物流網絡圖

表1 需求點的帳篷需求量與易損性

表2 物流中心擁有的應急物資數量

表3 配送車輛數據

車輛類型大型車中型車小型車容量(個)800600400行駛速度(km/小時)806040

表4 節點之間的距離(KM)

從表5可知，BW方法計算得到的需求點損失(SS)最大值為0.0037，最小值為0.0008，總損失為0.0208；BL方法計算得到SS最大值為0.0057，最小值為0.0004，總損失為0.0243；GS方法計算得到SS最大值為0.0124，最小值為0，總損失為0.0338。從公平性視角來看，BW方法求得的最大SS的值最小，SS的值在需求點之間的跨度最小，優于其余2種方法；BL方法次之，GS方法第三。從總損失最小的角度來看亦如此。說明了本文設計的應急物資分配方法同時兼顧了應急物資分配的公平性與效用性。決策者在進行應急物流規劃時，應綜合考慮災害級別、應急物資效用、需求點優先級別、災區群眾的心理多種因素，制定科學、公平、合理的應急物資分配方法。

表5 需求點的應急物資實際分配數量與損失

最優應急物資配送路線如圖2所示。一共使用了大型卡車11輛、中型卡車18輛、小車卡車1輛，應急物資總配送時間為207.328小時。配送時間較長的需求點主要是汶川、茂縣、平武，原因是通往這些需求點的道路難以通行，致使配送車輛行駛非常緩慢。從而可知：①影響應急物資配送時間的關鍵在于災區是否存在高可靠連通性的應急路網；②為滿足災區群眾需要，對路網損毀特別嚴重、車輛難以通行的需求點應空投應急物資；③應及時開展災區損毀道路的搶通工作，使損毀道路盡快恢復，配送車輛可以正常通行。

圖2 應急物資配送路線

在各種參數不變的前提下，通過擴展上文算例(算例1)的規模參數a、b形成算例2至算例4，采用本文的二階段混合啟發式求解算法(TSHHA)與文獻[12]的混合遺傳算法(HGA)分別求解各個算例，結果如表6所示。其中，a表示配送中心數量，b表示需求點數量。從表6可知，TSHHA的求解時間隨著LRP規模增大有所增長；TSHHA在程序運行時間方面略勝HGA。說明TSHHA能夠在較短時間內有效求得應急物資配送方案。

表6 不同問題規模的LRP求解結果

4 結論

震后初期，由于外界的應急物資難以及時運達各配送中心，災區存在應急物資短缺情況，應急物資應該公平配送。本文基于公平視角研究震后初期應急物資短缺情況下的LRP，綜合考慮災區路網不同程度損毀、車輛行駛時間難以準確計算、災害級別、需求點受災指數與易損性等因素，以單個需求點的最大損失最小作為應急物資分配的公平性衡量指標、總配送時間最短為應急物資配送的效率性衡量指標，在此基礎上建立應急物資公平配送的LRP模型，并設計兩階段混合啟發式求解算法。基于汶川地震之后的帳篷配送算例分析結果表明，該算法運行效率較高，能夠迅速求解出規定期限內的震后應急物資配送方案。

進一步的研究將考慮應急車輛動態調度、應急車輛協作救援等問題。