災后應急資源配送的LRP模型與算法研究*

戴　君，王　晶，易顯強

(1.北京工業大學 應用數理學院，北京 100020; 2.北京工商大學 商學院，北京 100048)

0　引言

近年來自然災害頻發，2008年中國南方地區雪災、汶川地震、2010年海地地震、2011年日本地震、2012年“7.21”北京特大暴雨災害、2014年智利地震和云南魯甸地震、2015年尼泊爾地震等，都給人們的生命和財產帶來了巨大的損失。災害發生后，快速高效的應急資源配送和供應，是災后救援有效開展的前提，對于減少人員傷亡和災害損失具有重要意義。災后救援需要面臨以下2個問題：應急資源配送中心定位問題，災害發生后，為了快速高效地開展應急救援，首先應該確定應急資源配送中心的數量、位置以及配送中心與需求點的歸屬劃分，協調應急資源的調度工作；應急資源配送路徑優化問題，如何在災后的復雜道路網絡中選擇可靠的通行路徑，給出整體優化的應急資源配送方案，是災后應急救援需要解決的關鍵問題。針對以上2個問題，應急救援應該在整體的基礎上給出考慮應急配送中心定位的災后應急資源配送可靠路徑方案。因此，重點研究災后應急資源配送的“定位—路徑問題”(location-routing problem, 簡稱LRP)。

在LRP問題的研究方面，WASTON C等[1]將道路網絡與配送車輛路徑優化結合起來，研究多個需求點巡回的“選址—路線優化問題”。此后，不少學者都在此基礎上對LRP模型進行研究。W. TAI等[2]在LRP模型里加入對車輛型號和最大處理能力的約束；S.ALUMUR等[3]以總成本最小為目標，建立危險廢棄物的LRP模型，研究廢棄物處理站的選址和運輸路線；章海峰等[4]考慮網絡節點的最大承受能力和車輛的容量限制，建立對應的LRP模型；徐琴等[5]以城市突發公共事件為背景，建立以應急救援時間滿意度最大為目標的LRP模型。

近幾年，在LRP問題的基礎上，應急資源配送路徑規劃也成為研究的熱點。BALCIK B等[6]針對應急配送中心到需求點這一階段的應急物資調度與配置，建立基于車輛調度的應急物資配送系統；JOTSHI A等[7]考慮到地震后對應急醫療的需求，提出基于數據融合的應急醫療救援中的車輛調度和路徑選擇模型；?ZDAMAR L等[8]將應急物資分配與車輛調度問題結合起來，以應急物資的未滿足需求之和最小為目標進行建模，并用拉格朗日松弛算法求解；YI WEI等[9]將應急資源配置問題劃分為車輛路徑規劃階段和資源配送階段，并改進蟻群算法對問題進行求解；RAHMAN S U等[10]在救援過程中，考慮運輸方式、運輸路徑以及應急資源分配等問題，同時滿足應急資源調度量最大和成本最小；劉春林等[11]研究帶物資需求約束條件的多個出救點的應急物資配置問題；繆成等[12]研究應急救援中的應急物資和車輛整合問題，把配送問題分解成2個多目標問題，并采用拉格朗日方法取得最優解；應夏暉等[13]建立模糊環境下的應急資源配送機會約束規劃模型，并設計智能算法解決該問題。

目前關于災后應急資源配送問題的研究，大多針對交通路網的情況，忽略應急資源配送中心的定位對應急資源配送的影響，較少考慮定位與配送的集成優化。盡管有些文獻研究應急資源配送的LRP問題，但模型較為簡單，缺少定位對應急資源配送方案改變的刻畫。在實際的應急救援中，配送中心的定位會影響到應急資源配送，進而影響應急救援效率。從整體出發，研究災后應急資源配送LRP問題，將配送中心定位與應急資源配送可靠路徑規劃結合起來進行集成優化，對于提高災后救援效率具有重要的理論意義和實際價值。

1　災后應急資源配送LRP問題優化模型

1.1　問題描述

災害發生后，在開展應急救援時，應根據災區分布情況，建立應急資源配送中心，選擇路徑最短、可靠性最高的路徑方案來協調應急資源的調度。快速建立應急資源配送中心對應急資源的調度具有重要意義，但是可能會導致應急資源配送的總路徑長度增加。選擇離受災點較近的區域建立應急資源配送中心，能夠就近為受災點提供應急資源保障，但需要花費大量時間，容易耽誤搶救的黃金時間。這就是LRP模型所要解決的問題，即在應急資源配送中心的定位和可靠路徑方案中尋求平衡。如何在綜合以上條件下，建立災后應急資源配送LRP模型，給出全局最優條件下的應急資源配送中心定位方案和應急資源配送可靠路徑方案，是需要解決的問題。

1.2　假設

1)網絡中的節點分為3類，應急資源配送中心備選點、應急資源需求點和過渡節點，其中過渡節點可以認為是需求為0的應急資源需求點。

2)災害發生后，需要在備選點里選擇1個或多個點建立應急資源配送中心，然后從這些配送中心向需求點配送應急資源。

3)災害發生后，道路網絡受到影響，表現為每2個節點之間的道路都有通行可靠性，根據實際路況有所不同。

4)每個應急資源配送中心能夠同時滿足多個需求點的需求，但是每個需求點的需求只能由1個應急資源配送中心滿足。

1.3　符號

n：網絡中所有節點集合；

n(s)：網絡中應急資源配送中心備選點集合；

n(d)：網絡中應急資源需求點和過渡節點的集合；

ur：是否在r點建立應急資源配送中心；

Tn(s)r：在r點建立應急資源配送中心需要的時間，包括建立救災中心、應急資源運抵的時間，假設與離災害中心的距離有關；

zijt：t階段是否選擇通過i,j邊，1表示通過，0表示不通過；

lij：不確定網絡中邊i,j的長度(路程)；

pij：不確定網絡中邊i,j的通行可靠性；

TDk：配送車輛在道路正常的情況下的單位距離行駛時間；

si：網絡中應急資源配送中心i的供應量；

dj：網絡中需求點j的最低需求；

VQk：配送車輛k的容量限制；

eij:不確定網絡鄰接矩陣元素，eij=1表示i,j鄰接，否則eij=0為不相鄰；

yit：不確定網絡中點i在階段t的應急資源需求或者供應量，yit>0表示需求已滿足，yit<0表示尚有需求未滿足，yit=0表示是過渡節點；

xijt：t階段通過i,j邊的應急資源的流動量。

1.4　災后應急資源配送LRP問題優化模型

以應急救援時間最短為目標，并對道路通行可靠性進行約束，即：

s.t.

yi1=si,i∈n(s)

(1)

yi1=-di,i∈n(d)

(2)

zijtxijt≤VQk

(3)

r∈n(s)

(4)

(5)

(6)

yiT≥0,i∈V

(7)

zijt≤eijt,i,j∈V,t∈T

(8)

(9)

(10)

xijt≥0

(11)

zijt,ur∈{0,1}

(12)

模型中，目標是總應急救援時間最短，包括2個部分：建立應急資源配送中心所耗費的時間；配送車輛在配送路徑上所耗費的時間。約束(1)，(2)初始化第1個時刻所有節點的應急資源數量；約束(3)表示車輛的最大處理能力約束；約束(4)表示在備選點集合里選擇節點建立應急資源配送中心；約束(5)表示當前時刻的應急資源數量，等于上一階段的所有量加上應急資源到達量，減去應急資源發出量；約束(6)限制從點i運出應急資源時，當且僅當i點已經獲得滿足；約束(7)保證到最后一個階段時所有的需求點的需求都已獲得滿足；約束(8)表示當且僅當ij相鄰時，應急資源方可從i點運輸至j點，否則物資不能直接由i點運輸至j點；約束(9)描述了車輛的不可分性，車輛只能選擇網絡中的1個點作為目的地；約束(10)要求每個需求點的需求只能由1個點來滿足；約束(11)表示路徑上的資源流動量不為負；約束(12)表示“0,1”約束。

2　模型求解的離散粒子群算法

由于該問題包含多階段和變量，屬于“NP-Hard”問題，難以通過精確算法對模型進行求解。同時，災害條件下，需要在短時間內尋找1個相對最優的應急資源配送方案。啟發式算法能滿足該類問題的需求，其中粒子群算法能夠避免復雜的遺傳操作，精度高、收斂快，因此，選擇粒子群算法進行求解。

2.1　粒子群算法簡介

粒子群算法是近年來發展起來的1種新的進化算法，起源于對鳥群捕食的行為研究。通過模擬鳥群中個體間對信息的共享，相互協作，從而獲得最優解。粒子群算法已被證明是1種有效的優化算法，由于容易實現、精度高等優點，一經提出就受到許多學者的關注，并且在解決實際問題中體現出優勢。

粒子群算法中，每個解都是搜索空間中的1個粒子。所有的粒子都有1個適應值，適應值由優化函數決定。還有1個速度決定它們運動的距離和方向，粒子追隨種群中的最優粒子在解空間中搜索。該算法初始化為1群隨機粒子，通過迭代找到最優解。在每1次迭代中，粒子通過2個極值來更新自己，1個是粒子本身所找到的最優解，這個解叫做個體極值pBesti；另1個極值是整個種群目前找到的最優解，這個極值是全局極值gBesti。各粒子根據如下公式來更新自己的速度和位置：

Vid(t+ 1) =wVid(t) +c1r1[Pi d(t)-Xid(t)] +c2r2[Pgd(t)-Xid(t)]

(13)

Xid(t+1)=Xid(t)+Vid(t+1),
1≤i≤N,1≤d≤D

(14)

其中w表示慣性權重，學習因子c1和c2是非負常數，r1和r1是2個獨立的介于[0，1]之間的隨機數，體現了粒子的記憶行為。式(13)中的第1部分表示粒子的慣性速度，第2部分表示粒子的動作來源于自己的經驗，第3部分表示粒子的動作來源于群體中其他粒子的經驗。

2.2　應急資源配送優化模型的離散粒子群算法

粒子群算法在許多連續優化問題中得到了廣泛的應用，但是在離散問題和非數值化問題方面則相對滯后。針對標準粒子群算法在解決離散問題上的缺點，采用文獻[14]提出的1種改進的粒子群算法，引入次優吸引子，使粒子在搜索過程中可以充分利用群體信息，提高算法的搜索能力。在標準粒子群算法中，僅依靠調節w的大小來平衡種群的探索和開發能力是不夠的，因為w值只能左右個體自身的速度。當個體粒子陷入局部收斂時，通過調節w值的大小只能使粒子跳出局部搜索區，而并沒有考慮群體中的相互作用。因此，通過引入次優吸引子來提高種群的搜索能力，并引入收縮因子，使粒子可以根據適應值與平均值的大小動態調節參數。

改進后的粒子群算法的公式為：

Vid(t+ 1) =k(wVid(t) +c1r1[Pi d-Xid(t)] +

(15)

Xid(t)) +c3r3(pc-Xid(t))])

Xid(t+1)=Xid(t)+Vid(t+1),
1≤i≤N,1≤d≤D

(16)

Pc=arg min
{f(Pid|i=1,…,n,且Pij≠Pgd}

(17)

2.3　編碼方式

如何找到1個合適的表達方法，使粒子與解對應，是實現算法的關鍵問題之一。構造M個應急資源配送中心，N個需求點，K輛配送車輛的粒子編碼，其中位置向量X可表示為(x1,x2,…,xM+N+K)，每個元素x1取值為1到M+N+K之間互不相同的整數。改進的多吸引子的離散粒子群優化算法，通過對粒子的合理編碼能夠快速求解模型，同時避免局部最優解。

2.4　算法步驟

1)設定種群中的粒子數和最大迭代次數，各粒子的初始位置和初始速度隨機；

2)計算每個粒子的適應值；

3)對每個粒子，更新Pid和Pgd；

4)對每個粒子，根據式(17)更新Pc；

5)根據式(15)和式(16)更新粒子的速度和位置；

6)如果達到預期，或迭代的次數等于最大迭代次數，轉7)，否則轉2)；

7)輸出最優結果。

3　仿真與分析

以某區域內地震災害條件下的應急資源配送與調度為例，假定有6個應急資源配送中心備選點，16個應急資源需求點，若干個過渡節點。假定只考慮1種物資，由于人員、資源等所限，應急資源配送中心的數量不超過備選點的一半。應急資源配送網絡如圖1所示，每個需求點的需求量、每條路徑的長度和風險值、各應急資源配送中心的建立時間和容量限制如表1、表2和表3所示。

圖1　應急資源配送網絡Fig.1　Emergency resources distribution network

需求點需求量需求點需求量760015950870016100095501711501060018190011400191350123002015001345021145014750221600

表2　每條路徑的長度和通行可靠性數據

表3　建立各應急資源配送中心所需時間和容量限制

網絡圖中共計33個點，65條路徑。在此交通路網基礎上進行優化，進而給出應急資源配送優化方案。在本算例中，我們取車速為70 km/h，VQk為40，在上述路網中通過粒子群算法最終獲得的配送方案如表4所示。

表4　應急資源配送方案

配送方案總時間為134.4 h，具體配送方案如圖2所示。

研究表明，設計的粒子群算法性能優越，具有較高的運算效率，且能得出較優的解，避免陷入局部最優。對于災后應急救援來說，該算法適合求解LRP。

圖 2　應急資源配送優化結果Fig.2　Result og Emergency resources distribution plan

4　結論

研究災后應急資源配送的LRP問題,得出如下結論：

1)引入應急資源配送中心的定位，刻畫定位和路網通行可靠性對應急配送方案的影響，以最小化應急救援時間為目標，構建災后應急資源配送LRP優化模型，給出應急資源配送中心定位與可靠路徑選擇的全局優化方案。

2)根據模型本身的特點和問題的實際性，設計離散粒子群優化模型算法，并結合仿真與分析，驗證模型和算法的有效性，模型與算法的研究對于災后應急資源的配送決策具有一定指導意義。

3)在實際災后應急救援過程中，應急資源包括多個種類，不只是單純的某1類應急資源，此外，災后部分道路路網的中斷也是應急救援需要面臨的問題，這些實際救援中需要考慮的因素，也是后續研究的方向之一。

[1]WASTON C, DOHRN P. Depot location with van Salesman-A practical approach[J]. Omega The International Journal of Management Science, 1973, 1(3): 321-329.

[2]W. TAI, Y.L. CHIN, W.B. JIUN. Heuristic Solutions to Multi-depot Location-Routing Problems[J].Computers and Operations Research， 2002, 29:1393-1415.

[3]S. ALUMUR, B. KARA. A new model for the hazardous waste location-routing problem[J]. Computers and Operations Research， 2007, 34:1406-1423．

[4]章海峰，張敏，楊超．一類運輸工具帶雙重能力約束的LRP問題[J]．武漢理工大學學報(交通科學與工程版)，2006，30(2)：220-223．

ZHANG Haifeng, ZHANG Min,YANG Chao. A locatio and routing problem with double vehicle capacity constraints[J].Journal of Wuhan University of Technology(Transportation Science & Engineering), 2006, 30(2):220-223.

[5]徐琴，馬祖軍，李華俊．城市突發公共事件在應急物流中的定位——路徑問題研究[J]．華中科技大學學報(社會科學版)，2008，22(6)：36-40．

XU Qin, MA Zujun, LI Huajun. Location-routing problem in emergency logistics for public emergencies[J]. Journal of Huazhong University of Science and Technology(Social Science Edition),2008, 22(6):36-40．

[6]BALCIK B, BEAMON B M, KREJCI C C, et al. Coordination in humanitarian relief chains: Practices, challenges and opportunities[J]. International Journal of Production Economics, 2010, 126(1, SI): 22-34．

[7]JOTSHI A, GONG Qiang, BATTA R. Dispatching and routing of emergency vehicles in disaster mitigation using data fusion[J]. Socio-economic Planning Sciences, 2009, 43(1): 1-24．

[8]?ZDAMAR L, EKINCI E, Kü?üKYAZICI B. Emergency logistics planning in natural disasters[J]. Annals of Operations Research, 2004, 129(1/4): 217-245．

[9]YI Wei, KUMAR A. Ant colony optimization for disaster relief operations[J]. Transportation Research Part E-Logistics and Transportation Review, 2007, 43(6): 660-672．

[10]RAHMAN S U, SMITH D K. Use of location-allocation models in health service development planning in developing nations[J]. European Journal of Operational Research, 2000, 123(3): 437-452.

[11]劉春林，施建軍，何建敏．一類應急物資調度的優化模型研究[J]．中國管理科學，2001，9(3)：29-36．

LIU Chunlin, SHI Jianjun， HE Jianmin. The study on optimal model for a kind of emergency material dispatch problem[J]. Chinese Journal of Management Science, 2001, 9(3): 29-36．

[12]繆成，許維勝，吳啟迪．大規模應急救援物資運輸模型的構建與求解[J]．系統工程，2006，24(11)：6-12．

MIAO Cheng, XU Weisheng, WU Qidi. A transportation modal and solution of large-scale emergency relief commodities[J].Systems Engineering,2006, 24(11): 6-12.

[13]應夏暉，孫莉，李錦霞．模糊環境下應急物資配送路徑優化研究[J]．公路交通科技，2014，31(10)：154-158．

YING Xiahui，SUN Li，LI Jinxia. Study on route optimization for emergency supply dispatch in fuzzy environment[J]. Journal of Highway and Transportation Research and Development, 2014,31(10):154-158.

[14]郭崇慧，谷超，江賀．求解旅行商問題的一種改進粒子群算法[J]．運籌與管理，2010，19(5)：20-26．

GUO Chonghui ,GU Chao ,JIANG He.An improved particle swarm optimization for traveling salesman problem [J].Operations Research and Management Science, 2010，19 (5): 20-26.