孫華麗，王循慶，薛耀鋒

(1.上海大學(xué)管理學(xué)院，上海 200444；2.華東師范大學(xué) 教育信息化系統(tǒng)工程研究中心，上海 200062;3.上海數(shù)字化教育裝備工程技術(shù)研究中心，上海 200062)

0 引言

近年來(lái)，世界各地自然災(zāi)害、公共衛(wèi)生事件、軍事沖突和恐怖襲擊等突發(fā)事件頻繁發(fā)生。如2005年美國(guó)“卡特里娜”颶風(fēng)、2008年中國(guó)汶川地震，2010年中國(guó)甘肅舟曲特大泥石流，2011年日本9級(jí)特大地震等。這些非常規(guī)突發(fā)事件給人類(lèi)和社會(huì)造成了巨大的人員傷亡和財(cái)產(chǎn)損失，成為阻礙社會(huì)發(fā)展的主要因素。突發(fā)事件發(fā)生后，應(yīng)急救援物資的及時(shí)供應(yīng)是關(guān)乎人民群眾生命安全和維持社會(huì)安定的重大問(wèn)題。為了最大程度的提高應(yīng)急資源保障的能力，迫切需要在有限的時(shí)間、空間和資源約束下實(shí)現(xiàn)應(yīng)急救援機(jī)構(gòu)的合理選擇和應(yīng)急物資配送體系的科學(xué)優(yōu)化。突發(fā)公共事件的突發(fā)性和破壞性經(jīng)常導(dǎo)致需求具有很大的模糊性。此外，自然災(zāi)害等突發(fā)事件可能造成部分道路毀壞，導(dǎo)致單位時(shí)間運(yùn)輸費(fèi)用不確定。為此，本文擬考慮應(yīng)急系統(tǒng)總成本和災(zāi)害損失成本之和最小，采用模糊機(jī)會(huì)約束規(guī)劃理論，建立一個(gè)應(yīng)急資源需求和單位救援運(yùn)輸費(fèi)用均模糊的應(yīng)急物流系統(tǒng)定位-路徑模型，設(shè)計(jì)改進(jìn)的遺傳算法對(duì)模型進(jìn)行求解，并用算例驗(yàn)證該模型的正確性和算法的有效性。

1 應(yīng)急系統(tǒng)LRP模糊機(jī)會(huì)約束規(guī)劃模型

1.1 問(wèn)題描述

突發(fā)公共事件發(fā)生后，有若干災(zāi)區(qū)物資需求點(diǎn)，應(yīng)急設(shè)施點(diǎn)和同類(lèi)型的救援車(chē)輛。需求點(diǎn)的需求量和單位運(yùn)輸費(fèi)用是模糊的，每輛車(chē)必須從應(yīng)急設(shè)施點(diǎn)出發(fā)，完成運(yùn)輸任務(wù)后返回到出發(fā)點(diǎn)，每個(gè)災(zāi)區(qū)需求點(diǎn)只能由應(yīng)急設(shè)施點(diǎn)的一輛車(chē)為其提供服務(wù)，且車(chē)輛的物資容量大于任一個(gè)災(zāi)區(qū)點(diǎn)的救援物資需求量。問(wèn)題是如何選擇若干應(yīng)急設(shè)施點(diǎn)，并在滿足車(chē)容量限制的條件下確定一套從應(yīng)急設(shè)施點(diǎn)到物資需求點(diǎn)的車(chē)輛路徑，使系統(tǒng)總成本和災(zāi)害損失成本最小的方案。

為了方便描述，定義以下變量和符號(hào)：

I∈{1 ,2,...,m} 為災(zāi)區(qū)物資需求點(diǎn)集合；J∈{1 ,2,...,n}為備選的應(yīng)急設(shè)施點(diǎn)集合；K∈{1 ,2,...,k}為應(yīng)急救援運(yùn)輸車(chē)輛集合；i為災(zāi)區(qū)物資需求點(diǎn)(i∈I)；j為應(yīng)急設(shè)施節(jié)點(diǎn)(j∈J)；k表示救援運(yùn)輸車(chē)輛(k∈K)；g,h表示物資需求點(diǎn)或應(yīng)急設(shè)施點(diǎn)，g∈(I?J),h∈(I?J)；pj為應(yīng)急設(shè)施點(diǎn)固定建設(shè)費(fèi)用；rj為應(yīng)急設(shè)施點(diǎn)運(yùn)營(yíng)可變費(fèi)用；qi表示需求點(diǎn)i的救援物資需求量；Q表示救援車(chē)輛的最大裝載容量；Wj表示應(yīng)急設(shè)施點(diǎn)j的總?cè)萘?；dgh表示點(diǎn)g到點(diǎn)h的距離；υk為救援車(chē)輛的平均行駛速度；Ck為車(chē)輛k的單位裝載貨物費(fèi)用；Φi表示應(yīng)急救援開(kāi)始前受災(zāi)點(diǎn)i的災(zāi)害損失成本；Φt表示各災(zāi)區(qū)點(diǎn)的單位時(shí)間災(zāi)害損失成本；ξ為災(zāi)害損失最大成本時(shí)間上限；～qi=（qei，qdi,qui）表示災(zāi)區(qū)需求點(diǎn)i的模糊需求量，其中qei，qui分別表示該模糊數(shù)的左右邊界，qdi表示該模糊數(shù)隸屬度為1的點(diǎn)；～Cgh=(Cegh,Cdgh,Cugh)表示救援車(chē)輛從點(diǎn)g到點(diǎn)h的模糊單位運(yùn)輸費(fèi)用。

yj=1，表示選擇第j處應(yīng)急設(shè)施點(diǎn)進(jìn)行物資供應(yīng)；否則，yj=0。

fij=1，表示應(yīng)急設(shè)施點(diǎn)j為災(zāi)區(qū)需求點(diǎn)i提供物資服務(wù)；否則，fij=0。

sjk=1，表示應(yīng)急設(shè)施點(diǎn)j在救援運(yùn)輸路徑k上；否則，sjk=0。

μghk=1，表示第k輛車(chē)從節(jié)點(diǎn)g到節(jié)點(diǎn)h；否則，μghk=0。

1.2 模型建立

其中，目標(biāo)函數(shù)(1)是使系統(tǒng)總成本(包括應(yīng)急設(shè)施點(diǎn)建設(shè)和運(yùn)營(yíng)成本、救援貨物裝載成本、救援車(chē)輛運(yùn)輸成本、災(zāi)害損失成本之和)最??；約束式(2)保證只有選中的應(yīng)急設(shè)施點(diǎn)才能為災(zāi)區(qū)需求點(diǎn)提供救援物資服務(wù)；約束式(3)表示在一條救援運(yùn)輸路徑上只能由一個(gè)應(yīng)急設(shè)施提供服務(wù)；約束式(4)保證每條救援路徑上的物資總需求量不超過(guò)運(yùn)輸車(chē)輛物資運(yùn)載能力；約束式(5)保證分配給應(yīng)急設(shè)施點(diǎn)j的所有受災(zāi)點(diǎn)物資總需求量不能超過(guò)該應(yīng)急設(shè)施點(diǎn)總?cè)萘浚患s束(6)保證每個(gè)災(zāi)區(qū)需求點(diǎn)只能在一條巡回運(yùn)輸路線上；約束(7)保證救援運(yùn)輸路線的連續(xù)性；約束式(8)保證每輛車(chē)的運(yùn)輸路線最多起止于一個(gè)應(yīng)急設(shè)施點(diǎn)；約束式(9)表示只有救援路線經(jīng)過(guò)了受災(zāi)需求點(diǎn)，該受災(zāi)點(diǎn)才能指派給應(yīng)急設(shè)施點(diǎn)；約束式(10)表示救援車(chē)輛到達(dá)災(zāi)區(qū)點(diǎn)的時(shí)間；約束式(11)、(12)和(13)是決策變量，取值是0或1。

在Liu和Iwamura工作基礎(chǔ)上，將模型中帶有模糊參數(shù)的目標(biāo)函數(shù)(1)和約束條件(4)、(5)轉(zhuǎn)化為如下等價(jià)模糊機(jī)會(huì)約束規(guī)劃模型：

其他約束與原模型的約束相同。其中，Pos{}表示{}中事件成立的可能性，α，β，γ表示給定的置信水平。模型中目標(biāo)機(jī)會(huì)約束(14)表示所求的目標(biāo)值fˉ應(yīng)該是在保證置信水平至少是α?xí)r所取的最小值；機(jī)會(huì)約束(15)、(16)和(17)表示約束得到滿足的可能性至少應(yīng)該達(dá)到給定的置信度水平α、β、γ。

引理 設(shè)三角模糊數(shù)r～=(r1,r2,r3)，其隸屬函數(shù)以μr～(x)表示，則對(duì)任意給定的置信水平α(0≤α≤1)，當(dāng)且僅當(dāng)z≥(1-α)r1+αr2時(shí)，有Pos{r～ ≤z} ≥α。

根據(jù)以上引理，將機(jī)會(huì)約束轉(zhuǎn)變?yōu)橐韵虑逦葍r(jià)形式：

將以上約束分別替代模糊機(jī)會(huì)約束(15)、(16)和(17)，其他約束與原模型的約束相同，從而將該模型轉(zhuǎn)化為確定性模型求解。

2 模型求解

2.1 染色體編碼

將模型變量采用特定的實(shí)值進(jìn)行染色體編碼，每個(gè)染色體代表該模型的一個(gè)解，每個(gè)染色體有3段。染色體的第一段有k個(gè)基因，k為最大救援車(chē)輛數(shù)目，每個(gè)基因位都由1到n的自然數(shù)中隨機(jī)產(chǎn)生一個(gè)，n為候選應(yīng)急設(shè)施點(diǎn)數(shù)目；第二段的長(zhǎng)度為m，m為受災(zāi)需求點(diǎn)數(shù)目，每個(gè)基因位都由1到k的自然數(shù)隨機(jī)產(chǎn)生；第三段的長(zhǎng)度也為m，每個(gè)基因位由1到m的自然數(shù)產(chǎn)生，并且不能相互重復(fù)。得到染色體的長(zhǎng)度為k+m+m，如(a1,a2,...,ak‖b1,b2,...bm‖c1,c2,...,cm)。

2.2 初始種群創(chuàng)建

隨機(jī)產(chǎn)生N個(gè)初始種群，用chrom(l)表示每一代種群中的第l(l=1,2,...,N)個(gè)染色體。

2.3 計(jì)算適應(yīng)度

染色體適應(yīng)值是個(gè)體生存機(jī)會(huì)選擇的唯一確定性指標(biāo)。對(duì)于違反約束條件的染色體，需加入相應(yīng)的懲罰確保滿足條件的個(gè)體具有較高生存機(jī)會(huì)。為此需要增加懲罰項(xiàng)以確保可行解具有較高的適應(yīng)值。設(shè)δk表示當(dāng)前種群第k個(gè)染色體，則第k個(gè)染色體的總成本計(jì)算如下：

式中，M為正大數(shù)。

2.4 遺傳操作

2.4.1 選擇

采用輪盤(pán)賭選擇和精英保留相結(jié)合的選擇策略。在每次生成下一代種群時(shí)，將父代種群以及交叉、變異操作產(chǎn)生的臨時(shí)種群中的最優(yōu)個(gè)體直接復(fù)制進(jìn)入下一代種群；新種群中的其他個(gè)體采用輪盤(pán)賭方法從父代種群和臨時(shí)種群中選擇。

2.4.2 交叉和變異

為保持群體的多樣化，需要對(duì)染色體中各段分別進(jìn)行交叉變異。對(duì)染色體第一段采用單點(diǎn)交叉，并進(jìn)行對(duì)換變異操作；對(duì)第二段進(jìn)行兩點(diǎn)交叉操作和對(duì)換變異操作；對(duì)第三段采用部分匹配交叉操作，并進(jìn)行逆轉(zhuǎn)變異。

2.4.3 終止條件

若群體代數(shù)達(dá)到設(shè)置的最大迭代次數(shù)Maxgen時(shí)，則輸出當(dāng)前最優(yōu)個(gè)體，算法結(jié)束。

3 實(shí)例分析

本文用下面算例說(shuō)明模型和算法的有效性。采用Matlab 7.0編程，并在CPU為Intel 2.80GHz，內(nèi)存為2G的計(jì)算機(jī)上運(yùn)行。算法參數(shù)設(shè)置如下：種群規(guī)模N=100，最大迭代次數(shù)Maxgen=500，代溝率GGAP=0.96，交叉概率pc=0.7,變異概率pm=0.05。

算例1：隨機(jī)給出4個(gè)可供選擇的應(yīng)急設(shè)施點(diǎn)，12個(gè)受災(zāi)物資需求點(diǎn)，6輛同類(lèi)型的車(chē)輛可提供運(yùn)輸服務(wù)，受災(zāi)點(diǎn)應(yīng)急救援設(shè)施點(diǎn)受災(zāi)和的相關(guān)數(shù)據(jù)如表1、表2所示。設(shè)應(yīng)急救援車(chē)輛的平均單位行駛速度為30km/h，車(chē)輛的最大裝載能力為120件，車(chē)輛的單位載貨量裝卸費(fèi)用為10元/件，受災(zāi)點(diǎn)單位時(shí)間損失成本為5萬(wàn)元/h，災(zāi)害損失成本時(shí)間上限為50h，置信水平均為0.8。

對(duì)算例進(jìn)行了10次求解，平均計(jì)算時(shí)間為13.61s，目標(biāo)函數(shù)值的收斂情況如圖1所示，可以看出經(jīng)過(guò)119次迭代后，目標(biāo)函數(shù)值趨于收斂，收斂效果顯著，驗(yàn)證了上述模型的正確性和遺傳算法的有效性。算法獲得最優(yōu)解的目標(biāo)函數(shù)值為F=2.93×107元，選擇編號(hào)為1、2和4的應(yīng)急設(shè)施點(diǎn)，對(duì)應(yīng)的車(chē)輛路線如圖2所示，圖中“○”表示受災(zāi)點(diǎn)，“□”表示應(yīng)急設(shè)施點(diǎn)，“—”表示運(yùn)輸路線，“…”表示返回路線。

表1 受災(zāi)需求點(diǎn)相關(guān)數(shù)據(jù)

表2 應(yīng)急救援設(shè)施點(diǎn)相關(guān)數(shù)據(jù)

表3 應(yīng)急設(shè)施點(diǎn)到受災(zāi)點(diǎn)模糊單位運(yùn)輸費(fèi)用

算例2：對(duì)文獻(xiàn)[13]的問(wèn)題進(jìn)行計(jì)算，其中文獻(xiàn)[13]的模型中考慮了救援所用總時(shí)間最小和成本最小，為方便比較，將本文模型中的總成本分成與文獻(xiàn)[13]相同的兩部分。對(duì)算例進(jìn)行10次求解，平均計(jì)算時(shí)間是70.38s，計(jì)算所得的救援路線為：車(chē)輛 1：1-15-20-7-1；車(chē)輛2：1-18-11-1;車(chē)輛3：3-12-16-10-3； 車(chē) 輛 7： 3-19-13-4-3； 車(chē) 輛 8：3-23-14-5-22-3；車(chē)輛9：1-17-6-21-1；車(chē)輛10：1-9-8-1，與文獻(xiàn)[13]計(jì)算結(jié)果比較如表4所示。從結(jié)果對(duì)比可以看出，本文實(shí)驗(yàn)得到的主要目標(biāo)函數(shù)值Z1比文獻(xiàn)[13]的結(jié)果縮短了171.5分鐘，次要目標(biāo)函數(shù)值Z2與文獻(xiàn)結(jié)果的相對(duì)誤差為0.27%，計(jì)算時(shí)間節(jié)約了22.8%，能夠更好地迎合應(yīng)急物流時(shí)效性強(qiáng)的特點(diǎn)，對(duì)于應(yīng)急救援物資的高效保障和及時(shí)供應(yīng)具有重要的現(xiàn)實(shí)意義。

圖1 目標(biāo)函數(shù)值收斂情況

圖2 算例計(jì)算結(jié)果

4 結(jié)論

表4 實(shí)驗(yàn)求解結(jié)果對(duì)比

本文以系統(tǒng)總成本和災(zāi)害損失成本之和最小為目標(biāo)，考慮到應(yīng)急需求量以及運(yùn)輸費(fèi)用的模糊性，構(gòu)建了應(yīng)急系統(tǒng)定位-路徑的模糊機(jī)會(huì)約束規(guī)劃模型，在此基礎(chǔ)上，提出一種遺傳算法，并通過(guò)算例分析驗(yàn)證了模型的正確性。結(jié)果表明，該模型和算法可以有效地解決需求和運(yùn)輸費(fèi)用不確定的應(yīng)急物流系統(tǒng)中定位-路徑問(wèn)題，實(shí)現(xiàn)應(yīng)急設(shè)施的科學(xué)選擇和應(yīng)急救援資源的合理調(diào)度。突發(fā)公共事件應(yīng)急系統(tǒng)具有緊急性和動(dòng)態(tài)性，因而考慮應(yīng)急資源的多種運(yùn)輸方式和動(dòng)態(tài)性的LRP需作下一步研究。

[1] Fiedrich F.,Gehbauer F.,Rickers U.Optimized Resource Allocation for Emergency Response after Earthquake Disasters[J].Safety Sci?ence,2000,(35).

[2] BalcikB.,BeamonB.M.FacilityLocationinHumanitarianRelief[J].Inter?national Journal of Logistics:Research and Applications,2008,11(2).

[3] Chang M.S.,Tseng Y.L.,Chen J.W.A Scenario Planning Approach for the Flood Emergency Logistics Preparation Problem under Uncer?tainty[J].Transportation Research,Part E,2007,43(6).

[4] Sheu J.B.An Emergency Logistics Distribution Approach for Quick Response to Urgent Relief Demand in Disasters[J].Transportation Re?search Part,2007,43(6).

[5] Nagy G.,Salhi S.Location-Routing:Issues,Models and Methods[J].European Journal of Operation Research,2007,177(2).

[6] Yi W.,?zdamar L.A Dynamic Logistics Coordination Model for Evac?uation and Support in Disaster Response Activities[J].European Jour?nal of Operational Research,2007,179(3).

[7] 徐琴,馬祖軍,李華俊.城市突發(fā)公共事件應(yīng)急物流中的定位－路徑問(wèn)題研究[J].華中科技大學(xué)學(xué)報(bào),2008,22(6).

[8] 曾敏剛,崔增收,余高輝.基于應(yīng)急物流的減災(zāi)系統(tǒng)LRP研究[J].中國(guó)管理科學(xué),2010,18(2).

[9] Liu B.D.,Iwamura K.Chance Constrained Programming with Fuzzy Parameters[J].Fuzzy Sets and Systems,1998,1994(2).

[10] Liu B.D.,Iwamura K.A Note Chance Constrained Programming with Fuzzy Coefficients[J].Fuzzy Sets and Systems,1998,100(1～3).

[11] 趙曉煜,汪定偉.供應(yīng)鏈中二級(jí)分銷(xiāo)網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)的模糊機(jī)會(huì)約束規(guī)劃模型[J].控制理論與應(yīng)用,2002,19(2).

[12] Molla-Alizadeh-Zavardehi S.,Hajiaghaei-Keshteli M.,Tavakko?li-Moghaddam R.Solving A Capacitated Fixed-charge Transporta?tion Problem by Artificial Immune and Genetic Algorithms with A Prüfer Number Representation[J].Expert Systems with Applications,2011,38(8).

[13] 鄭斌,馬祖軍,方濤.應(yīng)急物流系統(tǒng)中的模糊多目標(biāo)定位-路徑問(wèn)題[J].系統(tǒng)工程,2009,27(8).