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

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

?

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

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

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

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

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

1　引言

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

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

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

2　模型

2.1問題描述

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

2.2基本假設(shè)

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

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

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

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

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

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

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

2.3符號定義

決策變量如下：

2.4模型構(gòu)建

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

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

3　算法設(shè)計

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

3.1編碼規(guī)則

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

圖1　編碼規(guī)則

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

通過對目標(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)生誤碼，分別對染色體的兩個字串進(jìn)行選擇、交叉和變異操作。

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

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

圖2　染色體交叉操作

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

圖3　染色體變異操作

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

4　算例分析

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

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

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

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

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

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

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

5　結(jié)論

針對震后受災(zāi)點對物資和傷員有不同需求的應(yīng)急物流系統(tǒng)優(yōu)化問題，提出了一個以災(zāi)區(qū)總損失最小且兼顧運輸成本的救援資源綜合調(diào)度模型。該模型考慮了災(zāi)區(qū)傷員送出和救災(zāi)物資送入的聯(lián)合運輸問題，能根據(jù)配送需求的緩急，分配不同種類的運輸設(shè)備，對震后救援資源的高效調(diào)度有很好的指導(dǎo)意義。根據(jù)模型特點，設(shè)計了基于遺傳算法的求解方法，并通過算例驗證了算法的可行性。同時，算例的結(jié)果也表明該模型能很好地解決災(zāi)后傷員救送與物資配送的綜合問題，具有實用性，為災(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］王紹仁，馬祖軍.震后隨機動態(tài)LRP多目標(biāo)優(yōu)化模型及算法［J］.計算機應(yīng)用研究，2010，27（9）：3 283-3 286.

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

［7］李雙琳，馬祖軍，鄭斌，代穎.震后初期應(yīng)急物資配送的模糊多目標(biāo)選址—多式聯(liá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］周騫，劉菊，韋鳳連.基于禁忌遺傳算法的單車場多目標(biāo)區(qū)域調(diào)度優(yōu)化［J］.長沙理工大學(xué)學(xué)報，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é)基金資助項目（61003256）；重慶市教委科技項目（KJ120506）；重慶市人文社會科學(xué)重點研究基地項目（K2009-117）

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