鄭斌，馬祖軍

（1.西南交通大學峨眉校區(qū),四川峨眉山614202； 2.西南交通大學經濟管理學院物流與應急管理研究所,成都610031）

震后恢復期物資配送中的多周期選址—聯(lián)運問題

鄭斌*1，馬祖軍2

（1.西南交通大學峨眉校區(qū),四川峨眉山614202； 2.西南交通大學經濟管理學院物流與應急管理研究所,成都610031）

震后恢復期的物資配送是一項復雜的系統(tǒng)工程，針對震后恢復期兩級救援物資配送系統(tǒng)中的多品種物資、多運輸方式、多周期決策等特征，提出了一個以系統(tǒng)總費用最小為目標的混合整數線性規(guī)劃模型，用以解決震后恢復期救援物流系統(tǒng)中的選址—聯(lián)運問題.針對該模型的特點，設計了一種結合啟發(fā)式規(guī)則的分周期、分階段解碼的混合遺傳算法.以“5.12”汶川大地震恢復期救援物資保障過程構建算例，對該模型和算法進行了實例驗證.結果表明，該算法具有較好的性能，可以有效解決震后恢復期物資配送中的多周期選址—聯(lián)運問題.

系統(tǒng)工程；震后恢復；救援物資；選址—聯(lián)運問題；混合遺傳算法

1 引言

近年來，全球地震災害頻發(fā)，給人類造成了巨大危害和損失.而應急物資保障作為震后救援工作的關鍵，需要在有限時間、空間和資源約束下快速滿足應急物資需求，以實現災害損失最小化.其核心是如何科學合理地布局應急物資配送中心、安排多種運輸方式進行應急物資聯(lián)運.

近年來，國內外學者對震后應急物流系統(tǒng)優(yōu)化問題進行了不少研究，主要包括震后應急選址問題[1，2]和震后應急物資運輸問題[3-5].實際上，震后應急設施選址與物資運輸是相互聯(lián)系、相互制約的，有必要進行集成優(yōu)化管理，但目前對應急集成選址—運輸問題研究相對較少.文獻[6]針對自然災害下的應急物資配送及傷員運送建立了協(xié)調優(yōu)化模型，綜合了選址、物資分配及車輛路徑安排等問題.文獻[7]針對美國聯(lián)邦應急管理局的應急供應鏈結構，綜合考慮應對自然災害過程中的臨時物流設施選址、應急物資配送安排、車輛調度和路徑決策，基于混合整數規(guī)劃建立了一種多周期集成供應鏈優(yōu)化模型.文獻[8]建立了以總成本最小為目標的應急物流系統(tǒng)LRP模型.文獻[9]和文獻[10]分別針對震后應急物資配送過程中的模糊動態(tài)定位路徑問題及兩級設施定位路線安排問題進行建模，并設計算法進行求解.文獻[11]考慮災后兩級應急物資配送系統(tǒng)優(yōu)化問題，建立了一個應急物資中轉設施LRP多目標優(yōu)化模型.

震后應急救援活動是個動態(tài)演化的過程，一些學者從不同角度對其進行了階段劃分.例如，文獻[12]將人類應對地震災害的過程概括為五個階段：災害發(fā)生期、災民安置期、重建恢復期、災后建設期、現代發(fā)展期.文獻[13]以汶川大地震為例將應急管理分為應急準備、應急響應、應急恢復三個階段.為此，依據震后應急物資需求的緊迫程度，將震后救援物資配送大致分為應急救援階段和震后恢復階段，且各自具有顯著的特征.

目前有關震后應急物流系統(tǒng)優(yōu)化問題的研究基本上都針對應急救援階段，然而震后恢復期的救援物資配送也非常重要.震后恢復期通信設備已完全恢復，路網基本恢復暢通，災情完全得到掌握和控制.此時災區(qū)對救援物資的需求主要為災民日常生活類物資，以及災后重建所需的工程類物資.經過一段時間有計劃的采購或生產，所需物資基本能夠滿足.震后應急階段所開啟的物資配送中心將在震后恢復期逐漸關閉.由于震后恢復期規(guī)劃期長，每隔一段時間救災管理中心通過采購、生產、捐贈等獲得的物資都會有所變化，災區(qū)根據已經接收的物資量，已消耗的物資量等對各自的需求進行定期更新，因此震后恢復期決策宜采取多周期決策.為此，結合震后恢復期救援物資配送的特點，建立了一個以系統(tǒng)總費用最小為目標的多周期選址—聯(lián)運模型，并設計一個基于分周期、分階段解碼的混合遺傳算法.最后以汶川大地震救援物資配送為背景構造算例進行驗證.

2 模型建立

2.1 問題描述

震后恢復期會根據救災實際逐步關閉應急救援階段所開啟的物資配送中心，并選擇合適的運輸方式有計劃地將多品種物資從災區(qū)外圍物資集散點運至災區(qū)附近的物資配送中心，再配至各個受災點，使得運輸費用及物資配送中心運營費用之和最小，如圖1所示.其中集散點到配送中心的物資配送為上級物資配送，存在多種運輸方式（鐵路，公路，航空，水運等），配送中心到受災點的物資配送為下級物資配送，一般采取靈活性較強的公路運輸，從而構成了“集散點—物資配送中心—受災點”的兩級物資配送網絡系統(tǒng).從實際救援工作效率，以及可操作性角度出發(fā)，震后救援通常將災區(qū)按照一定的規(guī)則（如行政隸屬關系）進行區(qū)域劃分，便于救援工作高效、有序地開展.

震后恢復期救援物資配送系統(tǒng)具有一些明顯的特征，具體如下：震后恢復期規(guī)劃時程長，物資供應、需求情況定期更新，需要多周期動態(tài)決策；考慮經濟成本因素，逐漸關閉震后應急階段已經開啟的物資配送中心；物資供應點、需求點多，物資需求逐漸減少；物資需求種類多，日常生活用品之外，還有用于災后恢復的工程設備類物資；從物資集散點到物資配送中心可以選擇多種運輸方式運輸，從物資配送中心到受災點一般選擇較靈活的公路運輸.

圖1 物資配送中的選址－聯(lián)運問題Fig.1 Framework of Joint Location-Transportation Problem in Relief Distribution

2.2 符號說明

T——物資配送周期集合，t=1,2,…,||T；

SN——物資集散點集合，i∈SN；

R——受災區(qū)域集合，r∈R；

ENr——受災區(qū)域r內已開啟的物資配送中心集合，令EN=∪r∈RENr；

DNr——受災區(qū)域r內的受災點集合，令DN=∪r∈R

DNr；C——物資種類集合，c∈C；

wc——單位物資c的重量，c∈C；

M——物資集散點到物資配送中心的所有運輸方式集；

Am——物資集散點到物資配送中心之間存在運輸方式m的弧集，m∈M；

A'——受災區(qū)域r內物資配送中心與受災點

r間存在公路運輸的弧集，r∈R；

FCjt——周期t物資配送中心j的運營費用，j∈EN，t∈T；

Thjt：——周期t物資配送中心j的吞吐量限制，j∈EN，t∈T；

sict——周期t物資集散點i對物資c的供應量，i∈SN，c∈C，t∈T；

dkct——周期t受災點k對物資c的需求量，t∈T，k∈DN，c∈C；

disijm——從物資集散點i到物資配送中心j使用運輸方式m運輸時的距離，當(i,j)∈Am時，disijm≥0，當(i,j)?Am時，disijm=+∞，i∈N，j∈N，m∈M；

TCijm——從物資集散點i到物資配送中心j單位距離單位重量物資使用運輸方式m運輸的平均費用，當(i,j)∈Am時，TCijm≥0，當(i,j)?Am時，TCijm=+∞，m∈M；

dis′jk——受災區(qū)域r內從物資配送中心j到受災點k采用公路運輸的運輸距離，當(j,k)∈A′r時，dis′jk≥0，當(j,k)?A′r時，dis′jk=+∞，j∈ENr，k∈DNr，r∈R；

TC′jk——受災區(qū)域r內從物資配送中心j到受災點k單位距離單位重量物資使用公路運輸的運輸費用，當(j,k)∈A′r時，TC′jk≥0，當(j,k)?A′r時，TC′jk=+∞，j∈ENr，k∈DNr，r∈R；

B——一個大數；

pijmct——周期t物資c經運輸方式m從物資集散點i運至物資配送中心j的量，i∈SN，j∈EN，m∈M，c∈C，t∈T；

i∈SN，j∈EN，m∈M，c∈C，t∈T；

qjkct——周期t物資c從物資配送中心j運至受災點k的量，j∈ENr，k∈DNr，r∈R，c∈C，t∈T；

2.3 數學模型

目標函數式(1)使系統(tǒng)總費用最小，式中第一項為上級運輸成本，第二項為下級運輸成本，第三項為物資配送中心運營成本.約束式(2)表示從物資集散點發(fā)出的物資不能超過該點的供應量.約束式(3)表示物資配送中心的吞吐量限制.約束式(4)表示物資配送中心接收的物資量等于其發(fā)出量.約束式(5)表示受災點的接收量等于其需求量.約束式(6)表示某種運輸方式只有從某物資集散點出發(fā)為某物資配送中心提供某物資時，才能有該物資由該物資集散點發(fā)出通過該運輸方式運往該物資配送中心.約束式(7)表示下級公路運輸只有從某物資配送中心出發(fā)為某受災點提供物資時，才能有該物資從該物資配送中心發(fā)出通過公路運輸運往該受災點.約束式(8)表示物資配送中心將逐漸被關閉，已關閉的物資配送中心將不會被重新開啟.約束式(9)表示只有當物資配送中心開啟時，才能有物資運往該物資配送中心.約束式(10)表示只有當物資配送中心開啟時才能有物資從該物資配送中心運往受災點.約束式(11)-式(13)為0-1變量約束.約束式(14)、式(15)為非負約束.

3 模型求解

上述模型是一個混合整數線性規(guī)劃模型，包含大量的變量，不僅包括多物資集散點、多受災點、多物資配送中心、多品種物資、多運輸方式，而且涉及多周期決策，計算復雜度隨每個變量數量的增加成倍增長，為此設計一個基于分周期、分階段解碼的混合遺傳算法來求解該模型.

3.1 參數初始化

設遺傳算法的種群規(guī)模為popsize，最大迭代次數為maxgen，交叉率Pc，變異率Pm.

3.2 染色體編碼和種群初始化

每條染色體由3|T|個子串構成，其中子串3(t-1)+1、3(t-1)+2、3(t-1)+3表示周期t（t=1,2,…,|T|）的選址運輸編碼.子串3(t-1)+1為自然數編碼，為1到|DN|·|C|間的自然數的一組隨機排列，長度為|DN|·|C|（|DN|為需求點的數目，|C|為物資種類數目）；子串3(t-1)+2為0-1編碼，長度為|EN|（|EN|為物資配送中心數目），基因位取0或1；子串3(t-1)+3為自然數編碼，取值為1到|EN|·|C|的自然數的一組隨機排列，因此染色體總長度為(|EN|+|DN|)·|C|·|T|+|EN|·|T|.

例如，現有3個物資集散點，2種物資，2個受災區(qū)域受到地震災害的影響，其中受災區(qū)域1有4個物資配送中心，5個物資需求點，受災區(qū)域2有3個物資配送中心，4個物資需求點，則周期t（t=1,2,…,|T|）的染色體編碼的三個子串如圖2所示.

圖2 混合遺傳算法編碼示意圖Fig.2 Chromosome encoding scheme

根據染色體編碼規(guī)則隨機生成種群規(guī)模為popsize的初始種群.

3.3 染色體解碼和適應度函數

染色體解碼分周期分子串進行解碼，由于子串3(t-1)+2為隨機0-1編碼，可能會出現周期t開啟的物資配送中心處理能力不足的情況，即違反了約束式(3)，此時令目標函數值Z=B；否則，按如下步驟進行解碼：

Step1對周期t進行解碼，令t=1.

Step2令sub1=substring 3(t-1)+1，sbu3= substring3(t-1)+3,如果t=1,sub2=substring3(t-1)+ 2,否則,sub2(l)=τΠ≤tsubstring{3(t-1)+2}(l),l=1,2,…,|EN|.初始化qjkct=0,xjt=0,令THjt=Thjt,?j∈EN,?k∈DN，?c∈C，?t∈T.

Step3令λ?=argmax{sub1(l)|l=1,2,…,|DN|· |C|}選擇配送的物資種類接收物資的受災點受災點所屬的受災區(qū)域為受災點提供物資的物資配送中心運送的物資量

Step4更新物資配送中心的容量受災點需求量

Step5若dk?c?t=0，則更新編碼sub1(λ?)=0，計算若是則轉到Step6，否則返回Step3.

Step6用d′jct記錄物資配送中心j的物資流量

Step7若d′jct=0，則令sub3((c-1)|EN|+j)=0,?j∈EN，?c∈C.初始化pijmct=0，?i∈SN，?j∈EN，?m∈M，?c∈C，?t∈T.

Step8令μ?=argmax{sub3(l)|l=1,2,…,|EN|·選擇配送的物資種類接收物資的物資配送中心為物資配送中心提供物資的物資集散點和運輸方式的組合配送的物資量

Step9更新物資集散點供應量更新物資配送中心物資流量

Step10若則計算是否為0，若是執(zhí)行Step11，否則返回Step8.

Step11如果t＜|T|，則令t=t+1，返回Step2，否則執(zhí)行Step12.

Step12如果pijmct＞0，則yijmct=1，否則yijmct=0；如果qjkct＞0，則zjkct=1，否則zjkct=0，?i∈SN，?j∈EN，?k∈DN，?c∈C，?m∈M，?t∈T.計算如果則否則計算目標函數值Z.

由于模型目標函數是求總成本最小，可采取基于線性排序的適應度計算方法求解適應度函數.設Pos為個體的目標函數值在種群中按從大到小排列的序位，即Pos=1,2,…,num；SP為選擇壓力，且則適應度函數為

3.4 遺傳操作

采用輪盤賭和精英保留相結合的選擇策略.對染色體的每個周期的三個子串分別進行交叉變異.其中，子串3(t-1)+1、3(t-1)+3為自然數編碼，采取部分匹配交叉和逆轉變異.子串3(t-1)+2為0-1編碼，可直接采取兩點交叉和離散變異.

3.5 終止條件

設最大迭代次數為maxgen，遺傳算法迭代maxgen次后結束.

4 算例分析

4.1 算例

結合“5.12”汶川大地震的震后恢復期救援物資保障過程，選取3個物資集散點——省紅十字會、雙流機場、火車北站，2種救援物資——水泥（單位：袋）和電力設備（單位：臺）.3個受災區(qū)域：

災區(qū)一內的物資配送中心為都江堰、茂縣、理縣、彭州市、汶川、九寨溝、崇州、大邑；受災點為都江堰、灌口鎮(zhèn)、青城山、紫平鋪、虹口鄉(xiāng)、茂縣、富順、飛虹、黑虎、太平、理縣、樸頭鄉(xiāng)、木卡鄉(xiāng)、通化鄉(xiāng)、汶川、映秀鎮(zhèn)、水磨鎮(zhèn)、臥龍鎮(zhèn)、雁門、紅巖、小金、黑水、松潘、彭州、小魚洞、通濟、三江.

災區(qū)二內的物資配送中心為安縣、什邡、綿竹、北川、平武、江油、德陽、綿陽、廣漢；受災點為安縣、秀水、寶林、高川、什邡、洛水鎮(zhèn)、雙盛鎮(zhèn)、鎣華鎮(zhèn).

災區(qū)三內的物資配送中心為廣元、青川、旺蒼、劍閣；受災點為廣元、青川、瓦礫鄉(xiāng)、板橋鄉(xiāng)、騎馬鄉(xiāng)、營盤鄉(xiāng)、利州區(qū)、朝天區(qū)、蒼溪、劍閣、元壩區(qū).

實際路網中，上級物資集散點到物資配送中心有三種運輸方式——飛機、鐵路、公路.上級各種運輸方式下物資集散點到物資配送中心的距離為實際運輸距離，下級物資配送中心到受災點的距離為實際運輸距離.每個周期時長為1個月，供應點的供應量和需求點的需求量如表1、表2所示.

表1 物資集散點的物資供應量Table 1 Supply distribution

表2 受災點的物資需求量Table 2 Demand distribution

4.2 計算結果

算法參數設置如下：popsize=100,maxgen= 400,pc=0.95,pm=0.01.采用MATLAB R2010a編程，在Inter(R)Core(TM)2 Duo 2.4GHz CPU和1.96G內存的計算機上運行實現，運行時間為829.3 s，目標函數值為Z=10 075 888.7.表3為各周期物資配送中心的選址情況；圖3—圖5為三個周期的物資配送結果示意圖；圖6為震后恢復期算法收斂圖計算結果表明，算法收斂效果良好.

表3 物資配送中心選址情況Table 3 The strategies of location

圖3 t=1時物資配送結果示意圖Fig.3 The result of distribution in the 1stperiod

圖4 t=2時物資配送結果示意圖Fig.4 The result of distribution in the 2ndperiod

圖5 t=3時物資配送結果示意圖Fig.5 The result of distribution in the 3rdperiod

圖6 算法收斂圖Fig.6 The convergence of the proposed algorithm

從表3可以看出，隨著配送任務的減少，逐漸關閉物資配送中心.受篇幅限制，每種運輸方式的各種物資的運輸量未一一列出.鐵路運輸平均費用相對較低，與物資集散點——火車站存在鐵路運輸的物資配送中心有關，如江油、德陽、綿陽、廣元都在不同周期選擇開啟，且在不同周期都能使用鐵路運輸.

表4給出了種群規(guī)模為100，迭代次數為400時，各參數變化時的算法運行時間.計算結果顯示，當問題規(guī)模小時，用CPLEX求解時間較短，當問題規(guī)模較大時，CPLEX計算時間增大明顯，混合遺傳算法在確保相對差異在5%以內的同時，對大規(guī)模問題的求解效率明顯高于CPLEX.

表4 不同參數條件下的算法運行時間及結果對比Table 4 CPU time and result of different size problems

5 研究結論

針對震后恢復期救援物資配送中的選址—聯(lián)運問題，結合震后恢復期救援物資需求多樣化、多運輸方式，以及震后恢復期規(guī)劃時程長，需要進行多周期動態(tài)決策等特點，建立了一個以總費用最小為目標的混合整數線性規(guī)劃模型.并設計了一個基于啟發(fā)式規(guī)則的分周期、分階段解碼的混合遺傳算法.最后，以汶川大地震恢復期為背景構造算例，對模型和算法進行驗證.結果表明，該混合遺傳算法具有較高的計算效率和性能.

[1]Dessouky M,Ordó?ez F,Jia H，et al.Rapid distribution of medical supplies[J].Patient Flow:Reducing Delay in Healthcare Delivery,2006:309-338.

[2]Jia H,Ordó?ez F,Dessouky M.A modeling framework for facility location of medical services for large-scale emergencies[J].IIE Transactions,2007,39(1):41-55.

[3]Tzeng G H,Cheng H J.Multi-objective optimal plan?ning for designing relief delivery systems[J].Transporta?tion Research Part E,2007,43(6):673-686.

[4]Widener M J,Horner M W.A hierarchical approach to modeling hurricane disaster relief goods distribution[J]. Journal of Transport Geography,2011,19(4):821-828.

[5]Shen Z,Dessouky M,Ordó?ez F.A two-stage vehicle routing model for large-scale bioterrorism emergencies [J].Networks 2009,54:255-269.

[6]Yi W,?zdamar L.A dynamic logistics coordination mod?el for evacuation and support in disaster response activi?ties[J].European Journal of Operational Research, 2007,179(3):1177-1193.

[7]Afshar A M,Haghani A.Modeling integrated supply chain logistics in real-time large-scale disaster relief operations[J].Socio-EconomicPlanningSciences, 2012,46(4):327-338.

[8]曾敏剛,崔增收,余高輝.基于應急物流的減災系統(tǒng)LRP研究[J].中國管理科學.2010,18(2):75-80. [ZENG M G,CUI Z S,YU G H.Research on locationrouting problem of relief system based on emergency lo?gistics[J].Chinese Journal of Management Science. 2010,18(2):75-80.]

[9]代穎,馬祖軍,朱道立,等.震后應急物資配送的模糊動態(tài)定位一路徑問題[J].管理科學學報,2012,15(7): 60-70.[DAI Y,MA Z J,ZHU D L et al.Fuzzy dynamic location-routing problem in post-earthquake delivery of relief materials[J].Journal of Management Sciences in China,2012,15(7):60-70.]

[10]王紹仁,馬祖軍.震后緊急響應階段應急物流系統(tǒng)中的LRP[J].系統(tǒng)工程理論與實踐.2011,31(8):1497-1507.[WANG S R,MA Z J.Location-routing problem in emergency logistics system for post-earthquake emer?gency relief response[J].Systems Engineering-Theory &Practice,2011,31(8):1497-1507.]

[11]Rath S,Gutjahr W J.A math-heuristic for the warehouse location-routing problem in disaster relief[J].Comput?ers&Operations Research,2014,42(1):25-39.

[12]胡鞍鋼.特大地震災害的應對周期[J].清華大學學報, 2009,23(4):5-14.[HU A G.The period to combat ex?traordinarily earthquake calamities[J].Journal of Tsing?hua University,2009,23(4):5-14.]

[13]葛洪磊.基于災情信息特征的應急物資分配決策模型研究[D].杭州:浙江大學,2012.[GE H L.Study on re?lief supplies allocation models based on characteristics of disaster situation information[D].Hangzhou:Zhejiang University,2012.]

Multi-period Joint Location-Transportation during Postearthquake Restoration

ZHENG Bin1,MAZu-jun2
(1.Emei Campus,Southwest Jiaotong University,Emeishan 614202,Sichuan,China;2.Institute for Logistics and Emergency Management,School of Economics and Management,Southwest Jiaotong University,Chengdu 610031,China)

ract:The relief distribution during post-earthquake restoration period is a complex system engineering problem.A mixed integer linear programming model which minimizes the total cost is proposed to describe the joint transfer facility location and transportation problem in a two-echelon relief distribution system.It considers the features of relief distribution during post-earthquake restoration stage,such as various relief materials,various modes of transportation,multi-period decision.etc.Then,a hybrid genetic algorithm with multi-period and multi-phase decoded operation is proposed to solve the model.Finally,the validity of the model and algorithm is demonstrated by a numerical example based on Wenchuan earthquake relief distribution during post-earthquake restoration period.The results show that the proposed genetic algorithm has good performance and is suitable for the joint location-transportation problem in relief distribution.

rds:system engineering;post-earthquake restoration;relief materials;joint location-transportation problem;hybrid genetic algorithm

1009-6744（2014）04-0230-09

F252;U116

A

2013-10-10

2014-02-15錄用日期：2014-03-10

國家自然科學基金項目(70771094,90924012)；教育部新世紀優(yōu)秀人才支持計劃資助項目(NCET-10-0706)；四川省哲學社會科學研究規(guī)劃項目(SC11B049)；中央高?；究蒲袠I(yè)務費專項資金資助項目(2682014CX009EM，SWJTU11CX 152,2682013CX073).

鄭斌(1983-),女,河北深州市人,講師.*通訊作者:binzheng@swjtu.cn