震后初期救援資源綜合調度模型研究

王　永，劉　蕾，農蘭晶

（重慶郵電大學　經濟管理學院，重慶　400065）

?

震后初期救援資源綜合調度模型研究

王永，劉蕾，農蘭晶

（重慶郵電大學經濟管理學院，重慶400065）

震后初期應急救援的重點主要表現為傷員救援和急需物資的配送，且傷員救援和急需物資配送具有較高的時效性。為最大限度地減少震后損失，提出了集傷員救助和救災物資分配一體的震后救援資源綜合調度模型。針對該模型設計了基于遺傳算法的優化方法。算例檢驗的結果表明，提出的模型能很好地反映震后初期的實際特點，且求解算法快速有效，對震后救援資源的高效調度和減少震后損失有很好的指導作用。

地震災害；傷員救援；物資配送；優化；遺傳算法

1　引言

近年來，地震災害頻繁發生，如2008年四川汶川地震、2015年尼泊爾地震等。破壞性地震造成的損失可綜合概括為人員傷亡和經濟損失兩大方面。面對地震災害，急需建立一套全方位的、高效而科學的應急物流系統，盡可能減少人員傷亡并滿足災區人民的物資需求。因此，綜合調度各種救援資源，包括合理地分配救援運輸工具以及選擇物資配送的最優路徑成為了應急物流系統研究中的關鍵問題。

目前，對應急物流系統優化問題已有一定研究。早在1996年Haghani就首次提出了應急物流系統救援物資配送模型應該包含多種救援物資、多個供應節點、多種運輸模式，采取聯運方式對受災點進行應急救援［1］。Jae Young Choi研究了在道路損壞不確定條件下如何分配應急救援工具，使待救傷員存活數最大的問題［2］。Arun Jotshi等人綜合考慮傷員的傷勢程度和配送中心與災區的距離，給出了救援車輛的最短路徑［3］。我國學者何磊通過對災區的區域劃分以及傷亡人數預測，構建了震后對傷員的應急救援車輛調度模型，優化目標為傷員存活數最大［4］。馬祖軍等通過對救援物資的輕重緩急進行分類，建立了直升機與車輛聯合運輸的災區救援模型［5］。鄭斌等結合震后初期應急物資配送的特征，提出了一個上層以有限的應急物資配送時間最短，下層以物資分配公平性最大為目標的雙層規劃模型［6］。李雙琳等在部分路段受損的情況下，對各個受災點的需求進行了預測與評估，然后通過劃分受災等級，建立了應急物資聯合配送的模型［7］。在優化模型的求解方面，IlKyeong Moon等人指出帶時間窗的車輛路徑問題可延伸為超時、超成本的問題，并利用遺傳算法和模擬退火的混合算法對問題進行了求解［8］。臺灣學者Fu-Sheng Chang等人在2014年提出了以貪婪搜索和遺傳算法為基礎的多目標的應急物流調度問題，模型同時考慮需求點未滿足的損失最小、運輸所耗費成本最小以及運輸時間最短［9］。張曉鴿等人針對物流調度模型提出了一種基于Amoeboid Organism的求解算法［10］。

對已有文獻的分析可知，在研究震后應急救援的問題時，大多數學者主要是對應急物資的運輸路徑優化做了深入研究，且在應急模型的建立過程中，未充分考慮運輸工具的多樣性。震后初期應急救援的重點主要表現為傷員救援和急需物資的配送，且傷員救援和急需物資配送具有較高的時效性。即在第一時間需要將地震中受傷的人員運輸到救治中心，同時將急需的救援物資送到災區。為此，本文考慮震后初期應急救援的特點，針對待救傷員和應急物資的聯運問題，建立了震后初期救援資源綜合調度模型。模型綜合考慮了運輸待救傷員、配送救援物資、多種救援運輸工具的調度以及運輸成本等問題，對提高災后應急救援的科學性和時效性有積極的指導作用。

2　模型

2.1問題描述

地震發生時，救援需求可粗略劃分為五種情況：對重傷員的運輸及救治、對輕傷員的運輸及救治、災區急需物資的配送、災區普通物資的配送和傷員的本地救治。本文專注于解決救援運輸資源的綜合調度問題，故考慮前面四種救援需求。運輸工具對救災物資的運入和對傷員的運出，在設計周密的情況下存在聯運的可行性，從而構成一個應急物流配送系統。另一方面，由于震后道路遭到不同程度的損害，為保證救援的及時性，通常多種運輸工具（直升機、車輛）會投入到救災工作中。因此，需要考慮多種運輸工具的協調調度問題，即根據配送中心和受災點的位置，在滿足配送中心以及運輸設備的容量限制的條件下，選擇合適的運輸方式和運輸路徑將應急物資配送到受災點，同時在有限時間內運送更多的傷員，從而在保證受災點總損失最小的情況下兼顧配送總成本最小。

2.2基本假設

根據地震初期災區的實際情況和問題的復雜性，做出以下假設：

（1）假設有一個物流配送中心、若干個受災點以及不同類型的運輸工具。物流配送中心和受災點的位置以及受災點待救傷員數和物資需求量已知。

（2）假設所有應急物資均嚴格包裝成規則形狀，按規定運輸，無時間限制，不考慮庫存費用。

（3）假設應急物流配送中心有多種運輸設備，每種類型的設備數量固定且容量已知。每臺運輸設備在閉環運輸過程中對受災點服務一次。

（4）假設各災區的道路損壞情況已知，應急物流中心到各災區的實際距離已知。

（5）假設重傷員在與救災物資聯運時，必須為重傷員預留必需的空間。輕傷員可與救援物資在一定條件下混裝運輸。

（6）考慮時效和成本的因素，假設直升機只運輸重傷員和急需物資［5］。

2.3符號定義

決策變量如下：

2.4模型構建

目標函數為：

目標函數（1）表示災區未滿足的總損失最小，第一部分表示災區傷員未救援的損失，第二部分表示災區物資未滿足的損失；目標函數（2）表示直升機和車輛的運輸總成本最小；約束條件（3）、（4）分別表示在某個閉環運輸路線中對某個具體的受災點僅有一輛車輛和一架直升機對其進行服務，且都至多只服務一次；約束條件（5）、（6）分別表示運輸傷員和物資的數量不能超過配送中心的服務能力；約束條件（7）、（8）分別表示車輛和直升機服務該節點后必須從該節點離開；約束條件（9）、（10）表示消去支路約束，即不構成完整環路的路徑，R表示所有受災點所構成的集合；約束條件（11）、（12）分別表示車輛和直升機到達災區的時間；約束條件（13）、（14）分別表示受災點要求車輛和直升機最晚到達時間約束；約束條件（15）、（16）分別表示車輛和直升機從配送中心出發后必須返回到原配送中心；約束條件（17）、（18）分別表示分配給車輛和直升機的所有受災點的需求量之和不能超過車輛和直升機的最大空間數；約束條件（19）表示0-1決策變量。

3　算法設計

上述模型中包括了物資運輸和傷員運輸，而且對物資和傷員進行了類別劃分。同時，采用了汽車和飛機多種運輸工具。模型變量和約束條件眾多，求解的復雜性會隨著參數規模的增大而快速增加，以解析方式難以得出其最優解。遺傳算法是在人工智能領域里應用比較廣泛的一種隨機全局搜索的求最優解的方法，具有多點并行搜索機制，不依賴于函數的可導性以及魯棒性等特點。因此，本文基于遺傳算法求解模型，獲得其滿足約束條件的可行解。

3.1編碼規則

假設應急配送中心和受災點的位置已知，采用十進制編碼方式。以1個配送中心、3輛汽車、3架直升機和10個受災點為例說明編碼規則的設計，如圖1所示。個體的編碼由兩個字串組成，字串1表示汽車的行駛路線，其中汽車1配送路徑為：受災點2—受災點6—受災點8；汽車2的配送路徑為：受災點1—受災點3—受災點4—受災點9；汽車3的配送路徑為：受災點7—受災點5—受災點10。字串2表示直升機的行駛路線，直升機1的路徑1：受災點4—受災點6—受災點1；直升機2的路徑為：受災點3—受災點10—受災點5；直升機3的路徑為：受災點9—受災點2—受災點7—受災點8。

圖1　編碼規則

3.2適應度函數

通過對目標函數進行規范化和一致化處理，采用加權系數法構建適應度函數［11］。表達式為：

式中maxf1、maxf2分別表示 f1、f2所能取得的最大值，minf1、minf2分別表示 f1、f2所能取得的最小值。

加權系數后適應度函數為：

F值即為適應度函數值，值越小表示染色體的適應度越大。

3.3遺傳操作

為防止群體產生誤碼，分別對染色體的兩個字串進行選擇、交叉和變異操作。

（1）選擇算子。為了實現最優保存策略，本文采用最佳個體保留法，即將當前種群中最優的染色體直接復制到下一代，再通過輪盤賭選擇方法按照每條染色體的適應度大小比例確定其選擇的概率。

（2）交叉算子。在基本遺傳算法中，采用單點交叉的方法，針對每個字串分別隨機選擇交叉點。交叉示例如圖2所示，假設第一部分的交叉點為4，交換此點前后對應的兩個染色體A、B的基因，此時A中第三個基因8與交換后第四個基因8重復，因此將A中第三個基因8替換為交叉前的第四個基因1，其余同理。

圖2　染色體交叉操作

（3）變異算子。以變異概率Pm確定初始解x，用適應度函數確定領域搜索方向，產生新的染色體領域搜索過程實際上是染色體的普通變異，根據編碼規則采用交換變異，即隨機選取兩個變異位置點分別交換對應的基因值，如圖3所示。

圖3　染色體變異操作

（4）終止條件。迭代終止的條件是連續迭代到20次都未獲得改進時則停止迭代，輸出最終結果。

4　算例分析

隨機選取1個應急配送中心、8輛卡車、4架直升機、20個受災點。表1為卡車和直升機的參數，表2給出了受災點的坐標以及物資需求量，表3給出了受災點的待救傷員數以及要求運輸設備到達的最晚時間。重傷員由于傷勢較重考慮用擔架抬送，且重傷員不能與物資混裝，因此直升機從配送中心出發時須預留3個重傷員的位置（即非滿載）。

表1　運輸設備信息

設種群規模popsize=80，迭代數maxgen=200，交叉概率Pc= 0.9，變異概率Pm=0.1，為了分析目標函數之間的權重變化對運輸路徑的影響，給出了α1和α2的4種不同的組合，可根據實際情況進行選擇。根據上述設計的算法，通過MATLAB2012編程語言計算，Intel（R）Core（TM）i3-2310MCPU2.1GHz，4GB內存的電腦上運行。其計算結果見表4。

表2　受災點坐標及物資需求量（件）

表3　受災點待救傷員數（人）及要求到達最晚時間（min）

表4　路線安排結果

由表4可以看出，隨著α1的增大（更加強調災區傷員和物資需求），目標函數 f1災區未滿足的總損失隨之減小，目標函數 f2運輸成本卻隨之增大。在實際救援過程中，需要在第一時間滿足災區的需求，使災區未滿足的損失最小，說明模型和算法是真實有效的。

5　結論

針對震后受災點對物資和傷員有不同需求的應急物流系統優化問題，提出了一個以災區總損失最小且兼顧運輸成本的救援資源綜合調度模型。該模型考慮了災區傷員送出和救災物資送入的聯合運輸問題，能根據配送需求的緩急，分配不同種類的運輸設備，對震后救援資源的高效調度有很好的指導意義。根據模型特點，設計了基于遺傳算法的求解方法，并通過算例驗證了算法的可行性。同時，算例的結果也表明該模型能很好地解決災后傷員救送與物資配送的綜合問題，具有實用性，為災后的應急救援提供了更多的參考。

［1］Haghani A，Oh SC.Formulation and solution of a multi-commodity，multimodal network flow model for disaster relief operations［J］.Transportation Research Part A：Policy and Practice，1996，30（3）：231-250.

［2］Jae Young choi.Stochastic Scheduling Problems for Minimizing Tardy Jobs with Application to Emergency Vehicle Dispatching on Unreliable Road Networks［D］.University of New York，2003.

［3］Arun Jotshi，Qiang Gong，Rajan Batta.Dispatching and routing of emergency vehicles in disaster mitigation using data fusion［J］.Socio-Economic Planning Sciences，2009，43（1）：1-24.

［4］何磊，王健.地震條件下的傷員救援車輛調度研究［D］.哈爾濱：哈爾濱工業大學，2009.

［5］王紹仁，馬祖軍.震后隨機動態LRP多目標優化模型及算法［J］.計算機應用研究，2010，27（9）：3 283-3 286.

［6］鄭斌，馬祖軍，李雙琳.基于雙層規劃的震后初期應急物流系統優化［J］.系統工程學報，2014，29（1）：113-124.

［7］李雙琳，馬祖軍，鄭斌，代穎.震后初期應急物資配送的模糊多目標選址—多式聯運問題［J］.中國管理科學，2013，21（2）：144-150.

［8］IlKyeong Moon，Jeong-Hun Lee，June Seong.Vehicle routing problem with time windows considering overtime and outsourcing vehicles［J］. Expert Systems with Applications，2012，（39）：13 202-13 213.

［9］Fu-Sheng Chang，Jain-Shing Wu，Chung-Nan Lee，Hung-Che Shen. Greedy-search-based multi-objective genetic algorithm for emergency logistics scheduling［J］.Expert Systems with Applications，2014，（14）：2 947-2 956.

［10］XiaogeZhang，ZiliZhang，YajuanZhang，DaijunWei，YongDeng. Route selection for emergency logistics management：A bio-inspired algorithm［J］.Safety Science，2013，（54）：87-91.

［11］周騫，劉菊，韋鳳連.基于禁忌遺傳算法的單車場多目標區域調度優化［J］.長沙理工大學學報，2014，11（4）：33-38.

Study on Comprehensive Scheduling Model of Post-disaster Initial Relief Resources

Wang Yong， Liu Lei， Nong Lanjing
（School of Economics Management， Chongqing University of Posts Telecommunications， Chongqing 400065， China）

In this paper， in order to maximally reduce disaster damage， we proposed a post- disaster relief resource comprehensive scheduling model intended both for rescuing the injured and distributing the disaster-relieving materials， then designed the genetic algorithmfor the optimization of the model， and at the end， through a numerical test， proved the validity of the model in reflecting the practical characteristics of the post-disaster period.

earthquake disaster； injury rescue； material distribution； optimization； genetic algorithm

F252；F224

A

1005-152X（2016）01-0042-05

10.3969/j.issn.1005-152X.2016.01.012

2015-12-17

國家自然科學基金資助項目（61003256）；重慶市教委科技項目（KJ120506）；重慶市人文社會科學重點研究基地項目（K2009-117）

王永（1977-），男，四川人，教授，博士，研究方向：系統優化與物流管理、管理信息系統。