震后初期救援資源綜合調(diào)度模型研究

王　永，劉　蕾，農(nóng)蘭晶

（重慶郵電大學(xué)　經(jīng)濟(jì)管理學(xué)院，重慶　400065）

?

震后初期救援資源綜合調(diào)度模型研究

王永，劉蕾，農(nóng)蘭晶

（重慶郵電大學(xué)經(jīng)濟(jì)管理學(xué)院，重慶400065）

震后初期應(yīng)急救援的重點(diǎn)主要表現(xiàn)為傷員救援和急需物資的配送，且傷員救援和急需物資配送具有較高的時(shí)效性。為最大限度地減少震后損失，提出了集傷員救助和救災(zāi)物資分配一體的震后救援資源綜合調(diào)度模型。針對(duì)該模型設(shè)計(jì)了基于遺傳算法的優(yōu)化方法。算例檢驗(yàn)的結(jié)果表明，提出的模型能很好地反映震后初期的實(shí)際特點(diǎn)，且求解算法快速有效，對(duì)震后救援資源的高效調(diào)度和減少震后損失有很好的指導(dǎo)作用。

地震災(zāi)害；傷員救援；物資配送；優(yōu)化；遺傳算法

1　引言

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

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

對(duì)已有文獻(xiàn)的分析可知，在研究震后應(yīng)急救援的問題時(shí)，大多數(shù)學(xué)者主要是對(duì)應(yīng)急物資的運(yùn)輸路徑優(yōu)化做了深入研究，且在應(yīng)急模型的建立過程中，未充分考慮運(yùn)輸工具的多樣性。震后初期應(yīng)急救援的重點(diǎn)主要表現(xiàn)為傷員救援和急需物資的配送，且傷員救援和急需物資配送具有較高的時(shí)效性。即在第一時(shí)間需要將地震中受傷的人員運(yùn)輸?shù)骄戎沃行?，同時(shí)將急需的救援物資送到災(zāi)區(qū)。為此，本文考慮震后初期應(yīng)急救援的特點(diǎn)，針對(duì)待救傷員和應(yīng)急物資的聯(lián)運(yùn)問題，建立了震后初期救援資源綜合調(diào)度模型。模型綜合考慮了運(yùn)輸待救傷員、配送救援物資、多種救援運(yùn)輸工具的調(diào)度以及運(yùn)輸成本等問題，對(duì)提高災(zāi)后應(yīng)急救援的科學(xué)性和時(shí)效性有積極的指導(dǎo)作用。

2　模型

2.1問題描述

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

2.2基本假設(shè)

根據(jù)地震初期災(zāi)區(qū)的實(shí)際情況和問題的復(fù)雜性，做出以下假設(shè)：

（1）假設(shè)有一個(gè)物流配送中心、若干個(gè)受災(zāi)點(diǎn)以及不同類型的運(yùn)輸工具。物流配送中心和受災(zāi)點(diǎn)的位置以及受災(zāi)點(diǎn)待救傷員數(shù)和物資需求量已知。

（2）假設(shè)所有應(yīng)急物資均嚴(yán)格包裝成規(guī)則形狀，按規(guī)定運(yùn)輸，無時(shí)間限制，不考慮庫存費(fèi)用。

（3）假設(shè)應(yīng)急物流配送中心有多種運(yùn)輸設(shè)備，每種類型的設(shè)備數(shù)量固定且容量已知。每臺(tái)運(yùn)輸設(shè)備在閉環(huán)運(yùn)輸過程中對(duì)受災(zāi)點(diǎn)服務(wù)一次。

（4）假設(shè)各災(zāi)區(qū)的道路損壞情況已知，應(yīng)急物流中心到各災(zāi)區(qū)的實(shí)際距離已知。

（5）假設(shè)重傷員在與救災(zāi)物資聯(lián)運(yùn)時(shí)，必須為重傷員預(yù)留必需的空間。輕傷員可與救援物資在一定條件下混裝運(yùn)輸。

（6）考慮時(shí)效和成本的因素，假設(shè)直升機(jī)只運(yùn)輸重傷員和急需物資［5］。

2.3符號(hào)定義

決策變量如下：

2.4模型構(gòu)建

目標(biāo)函數(shù)為：

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

3　算法設(shè)計(jì)

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

3.1編碼規(guī)則

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

圖1　編碼規(guī)則

3.2適應(yīng)度函數(shù)

通過對(duì)目標(biāo)函數(shù)進(jìn)行規(guī)范化和一致化處理，采用加權(quán)系數(shù)法構(gòu)建適應(yīng)度函數(shù)［11］。表達(dá)式為：

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

加權(quán)系數(shù)后適應(yīng)度函數(shù)為：

F值即為適應(yīng)度函數(shù)值，值越小表示染色體的適應(yīng)度越大。

3.3遺傳操作

為防止群體產(chǎn)生誤碼，分別對(duì)染色體的兩個(gè)字串進(jìn)行選擇、交叉和變異操作。

（1）選擇算子。為了實(shí)現(xiàn)最優(yōu)保存策略，本文采用最佳個(gè)體保留法，即將當(dāng)前種群中最優(yōu)的染色體直接復(fù)制到下一代，再通過輪盤賭選擇方法按照每條染色體的適應(yīng)度大小比例確定其選擇的概率。

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

圖2　染色體交叉操作

（3）變異算子。以變異概率Pm確定初始解x，用適應(yīng)度函數(shù)確定領(lǐng)域搜索方向，產(chǎn)生新的染色體領(lǐng)域搜索過程實(shí)際上是染色體的普通變異，根據(jù)編碼規(guī)則采用交換變異，即隨機(jī)選取兩個(gè)變異位置點(diǎn)分別交換對(duì)應(yīng)的基因值，如圖3所示。

圖3　染色體變異操作

（4）終止條件。迭代終止的條件是連續(xù)迭代到20次都未獲得改進(jìn)時(shí)則停止迭代，輸出最終結(jié)果。

4　算例分析

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

表1　運(yùn)輸設(shè)備信息

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

表2　受災(zāi)點(diǎn)坐標(biāo)及物資需求量（件）

表3　受災(zāi)點(diǎn)待救傷員數(shù)（人）及要求到達(dá)最晚時(shí)間（min）

表4　路線安排結(jié)果

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

5　結(jié)論

針對(duì)震后受災(zāi)點(diǎn)對(duì)物資和傷員有不同需求的應(yīng)急物流系統(tǒng)優(yōu)化問題，提出了一個(gè)以災(zāi)區(qū)總損失最小且兼顧運(yùn)輸成本的救援資源綜合調(diào)度模型。該模型考慮了災(zāi)區(qū)傷員送出和救災(zāi)物資送入的聯(lián)合運(yùn)輸問題，能根據(jù)配送需求的緩急，分配不同種類的運(yùn)輸設(shè)備，對(duì)震后救援資源的高效調(diào)度有很好的指導(dǎo)意義。根據(jù)模型特點(diǎn)，設(shè)計(jì)了基于遺傳算法的求解方法，并通過算例驗(yàn)證了算法的可行性。同時(shí)，算例的結(jié)果也表明該模型能很好地解決災(zāi)后傷員救送與物資配送的綜合問題，具有實(shí)用性，為災(zāi)后的應(yīng)急救援提供了更多的參考。

［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］何磊，王健.地震條件下的傷員救援車輛調(diào)度研究［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，2009.

［5］王紹仁，馬祖軍.震后隨機(jī)動(dòng)態(tài)LRP多目標(biāo)優(yōu)化模型及算法［J］.計(jì)算機(jī)應(yīng)用研究，2010，27（9）：3 283-3 286.

［6］鄭斌，馬祖軍，李雙琳.基于雙層規(guī)劃的震后初期應(yīng)急物流系統(tǒng)優(yōu)化［J］.系統(tǒng)工程學(xué)報(bào)，2014，29（1）：113-124.

［7］李雙琳，馬祖軍，鄭斌，代穎.震后初期應(yīng)急物資配送的模糊多目標(biāo)選址—多式聯(lián)運(yùn)問題［J］.中國管理科學(xué)，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］周騫，劉菊，韋鳳連.基于禁忌遺傳算法的單車場(chǎng)多目標(biāo)區(qū)域調(diào)度優(yōu)化［J］.長沙理工大學(xué)學(xué)報(bào)，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

國家自然科學(xué)基金資助項(xiàng)目（61003256）；重慶市教委科技項(xiàng)目（KJ120506）；重慶市人文社會(huì)科學(xué)重點(diǎn)研究基地項(xiàng)目（K2009-117）

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