震后初期應(yīng)急物資配送的多目標(biāo)混合—聯(lián)運(yùn)問題

沈曉冰　楊保華

摘要：針對震后應(yīng)急物流系統(tǒng)優(yōu)化問題，以所有受災(zāi)點的物資需求未滿足量最小以及送達(dá)時間最短作為目標(biāo)，建立了一個帶中轉(zhuǎn)設(shè)施的雙層混合聯(lián)運(yùn)多目標(biāo)優(yōu)化模型，并根據(jù)所建模型的特點，設(shè)計了一種基于矩陣編碼的混合遺傳算法進(jìn)行求解。最后，以青海玉樹地震為例，驗證了該模型和算法的可行性。

Abstract： In response to the post-earthquake emergency logistics system optimization problems， a multi-objective optimization model of the bi-level mixed transport facilities with transshipment facilities is established. The goal is to minimize the relief delivery time and the total loss. Then a hybrid genetic algorithm based on sub stage decoding method is designed according to the characteristics of the model. Finally， the validity of the model and algorithm are demonstrated by a numerical example derived from Yushu earthquake. The results show that the proposed genetic algorithm has good performance.

關(guān)鍵詞：震后；應(yīng)急物資；雙層混合聯(lián)運(yùn)；混合遺傳算法

Key words： post-earthquake；relief；bi-level programming and mixed transportation；hybrid genetic algorithm

中圖分類號：U291 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2016）30-0022-03

0 引言

地震是一種突發(fā)性自然災(zāi)害，短時間內(nèi)損傷巨大，優(yōu)化震后應(yīng)急資源的配置對以提高救援效率。近幾年來，不少學(xué)者開始關(guān)注震后應(yīng)急物資配送問題。Viswanath[1]設(shè)計了一個救援運(yùn)輸費(fèi)用最小化和關(guān)鍵路徑覆蓋災(zāi)區(qū)最大化的多目標(biāo)規(guī)劃；Haghani et al.[2]基于路徑—分配問題，構(gòu)建了含時間窗的確定型網(wǎng)絡(luò)流模型；？魻zdamar et al[3]考慮到應(yīng)急時間的動態(tài)性，構(gòu)建了車輛路徑和物資網(wǎng)絡(luò)流的集成優(yōu)化模型。然而，目前大部分研究要么只針對定位分配問題[1，4]，要么只考慮調(diào)度問題[2，3]，而在實際救援中，這兩個問題并不是孤立存在的，有必要對這兩個問題進(jìn)行集成優(yōu)化與管理[5-9]。以上文獻(xiàn)大多假設(shè)應(yīng)急物資的供應(yīng)量大于需求量，采用單層配送，忽略了震后初期應(yīng)急物資供不應(yīng)求及物資分配時間有限。本文針對上述已有工作的分析，建立了一個帶雙層混合聯(lián)運(yùn)多目標(biāo)優(yōu)化模型，上層物資運(yùn)輸量較大，采用航空、鐵路、直升機(jī)和公路4種配送方式，而下層僅需公路、直升機(jī)運(yùn)輸，各運(yùn)輸方式均有運(yùn)力限制，可多次往返運(yùn)輸；其中公路和直升機(jī)有一定的數(shù)量限制，航空和鐵路定點間隔運(yùn)輸，并對其進(jìn)行混裝，提高滿載率；對緊迫性要求高的物資進(jìn)行優(yōu)先配送。

1 模型構(gòu)建

1.1 符號說明

式（1）為最小化未滿足物資帶來的相對損失：災(zāi)民的損失與物資未滿足量為凸函數(shù)關(guān)系[11]，其中β為災(zāi)情指數(shù)，β？叟1；式（2）為應(yīng)急救援時間最短。式（3）為供應(yīng)點公路和直升機(jī)的數(shù)量約束；式（4）為中轉(zhuǎn)站公路和直升機(jī)的數(shù)量限制；式（5）為供應(yīng)點自身的物資流守恒；式（6）為供應(yīng)點到受災(zāi)點的物資流守恒；式（7）為應(yīng)急物資供不應(yīng)求；式（8）為上層運(yùn)輸工具重量和體積的單次運(yùn)力限制；式（9）為下層運(yùn)輸工具重量和體積的單次運(yùn)力限制；式（10）為m將物資c從供應(yīng)點i運(yùn)輸至中轉(zhuǎn)站j的時間；式（11）為m將物資c從中轉(zhuǎn)站j運(yùn)輸至受災(zāi)點k的時間；式（12）為只有中轉(zhuǎn)站開啟時，上下層才有物資流；式（13）為0-1變量、非負(fù)和整數(shù)約束。

2 求解算法

本文所建模型比較復(fù)雜，因此選用基于矩陣編碼的遺傳算法進(jìn)行求解，收斂性好、計算時間短。

2.1 染色體編碼

第一階段Part1.k.c.n為受災(zāi)點k接收到n單位的c物資。該基因位的取值為隨機(jī)正整數(shù)，且保證受災(zāi)點各類物資的和為 Sic。第二階段Part2.k.j.c.m.n為由中轉(zhuǎn)站j采用n輛/架m類運(yùn)輸工具運(yùn)c物資至受災(zāi)點k。先隨機(jī)生成中轉(zhuǎn)站選址，再對運(yùn)輸工具數(shù)量生成隨機(jī)矩陣并對其進(jìn)行歸一化處理使其滿足約束（4）。第三階段Part3.j.c.i.m.n為由供應(yīng)中心i運(yùn)輸c物資到中轉(zhuǎn)站j采用m類運(yùn)輸工具的數(shù)量為n。對于運(yùn)輸工具數(shù)量，先生成隨機(jī)矩陣，然后對車輛、直升機(jī)數(shù)量進(jìn)行歸一化處理使其滿足約束（3）。

2.2 初始化種群和適應(yīng)度計算

采用線性加權(quán)評價函數(shù)轉(zhuǎn)化為單目標(biāo)，然后用標(biāo)準(zhǔn)化法對其進(jìn)行無量綱處理，繼而得到適應(yīng)度函數(shù)。

2.3 遺傳操作

染色體第一段利用隨機(jī)基因位交叉，第二、三段采用矩陣交叉法且三段均采用隨機(jī)基因位加減法變異。

2.4 終止條件

算法迭代到終止迭代次數(shù)時結(jié)束。

3 算例分析

以玉樹地震為例，取西寧火車站、曹家堡機(jī)場2個供應(yīng)點，編號為1、2，分別提供帳篷18000、37000單位，食品470000、600000單位，車輛190、120輛；震中地勢險峻，離供應(yīng)點較遠(yuǎn)，不適合鐵路、直升機(jī)運(yùn)輸；取玉樹、治多、稱多3個中轉(zhuǎn)站，編號為1、2、3，分別提供車輛數(shù)65、73、55輛，直升機(jī)14、4、5架；各受災(zāi)點的物資需求情況如表1所示。

設(shè)popsize=1000，maxite=300，λ=0.5，交叉、變異概率分別為0.7、0.01，運(yùn)行的兩目標(biāo)函數(shù)為：minT=1028704，minA=337426，計算結(jié)果如表2、表3所示。

由表2知，上層運(yùn)輸中只有中轉(zhuǎn)站1玉樹采用了航空運(yùn)輸，因為災(zāi)區(qū)僅有巴塘一處機(jī)場，而其他地區(qū)沒有機(jī)場，只能被限制為車輛運(yùn)輸。由收斂圖1可知，該算法收斂較好且運(yùn)行效率較高。

4 結(jié)束語

為提高震后應(yīng)急救援效率，以應(yīng)急物資短缺和時間的緊迫性為基礎(chǔ)，建立了一個雙層混合聯(lián)運(yùn)模型，并設(shè)計了一種基于分階段解碼的混合遺傳算法求解。但是隨著時間的推移，一些基礎(chǔ)設(shè)施逐漸恢復(fù)，可以對應(yīng)急物資配送的動態(tài)優(yōu)化作進(jìn)一步研究。

參考文獻(xiàn)：

[1]Viswanath K， Peeta S. The multicommodity maximal covering network design problem[C]// The IEEE， International Conference on Intelligent Transportation Systems， 2002. Proceedings. 2002：505-510.

[2]Haghani A， Oh S C. Formulation and solution of a multi-commodity， multi-modal network flow model for disaster relief operations[J]. Transportation Research Part A Policy & Practice， 1996， 30（3）：231-250.

[3]？魻zdamar L， Ekinci E， Kü ükyazici B. Emergency Logistics Planning in Natural Disasters[J]. Annals of Operations Research， 2004， 129（1-4）：217-245.

[4]Tavakoli A， Lightner C. Implementing a mathematical model for locating EMS vehicles in fayetteville， NC[J]. Computers & Operations Research， 2004， 31（9）：1549-1563.

[5]文仁強(qiáng)，鐘少波，袁宏永，等.應(yīng)急資源多目標(biāo)優(yōu)化調(diào)度模型與多蟻群優(yōu)化算法研究[J].計算機(jī)研究與發(fā)展，2013，50（7）：1464-1472.

[6]Rath S， Gutjahr W J. A math-heuristic for the warehouse location-routing problem in disaster relief[J]. Computers & Operations Research， 2014， 42（2）：25-39.

[7]馬祖軍，代穎，李雙琳.帶限制期的震后應(yīng)急物資配送模糊多目標(biāo)開放式定位-路徑問題[J].系統(tǒng)管理學(xué)報，2014（5）：658-667.

[8]Yi W， Kumar A. Ant colony optimization for disaster relief operations[J]. Transportation Research Part E Logistics & Transportation Review， 2007， 43（6）：660-672.

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

[10]蘇幼坡.城市生命線系統(tǒng)震后恢復(fù)過程優(yōu)化的研究[D].天津大學(xué)，2001.

[11]葛洪磊，劉南，張國川，等.基于受災(zāi)人員損失的多受災(zāi)點、多商品應(yīng)急物資分配模型[J].系統(tǒng)管理學(xué)報，2010，19（5）：541-545.