應急定位-路徑的模糊機會約束規(guī)劃模型

孫華麗，王循慶，薛耀鋒

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

0 引言

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

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

1.1 問題描述

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

為了方便描述，定義以下變量和符號：

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

yj=1，表示選擇第j處應急設施點進行物資供應；否則，yj=0。

fij=1，表示應急設施點j為災區(qū)需求點i提供物資服務；否則，fij=0。

sjk=1，表示應急設施點j在救援運輸路徑k上；否則，sjk=0。

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

1.2 模型建立

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

在Liu和Iwamura工作基礎上，將模型中帶有模糊參數(shù)的目標函數(shù)(1)和約束條件(4)、(5)轉化為如下等價模糊機會約束規(guī)劃模型：

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

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

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

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

2 模型求解

2.1 染色體編碼

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

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

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

2.3 計算適應度

染色體適應值是個體生存機會選擇的唯一確定性指標。對于違反約束條件的染色體，需加入相應的懲罰確保滿足條件的個體具有較高生存機會。為此需要增加懲罰項以確?？尚薪饩哂休^高的適應值。設δk表示當前種群第k個染色體，則第k個染色體的總成本計算如下：

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

2.4 遺傳操作

2.4.1 選擇

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

2.4.2 交叉和變異

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

2.4.3 終止條件

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

3 實例分析

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

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

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

表1 受災需求點相關數(shù)據(jù)

表2 應急救援設施點相關數(shù)據(jù)

表3 應急設施點到受災點模糊單位運輸費用

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

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

圖2 算例計算結果

4 結論

表4 實驗求解結果對比

本文以系統(tǒng)總成本和災害損失成本之和最小為目標，考慮到應急需求量以及運輸費用的模糊性，構建了應急系統(tǒng)定位-路徑的模糊機會約束規(guī)劃模型，在此基礎上，提出一種遺傳算法，并通過算例分析驗證了模型的正確性。結果表明，該模型和算法可以有效地解決需求和運輸費用不確定的應急物流系統(tǒng)中定位-路徑問題，實現(xiàn)應急設施的科學選擇和應急救援資源的合理調度。突發(fā)公共事件應急系統(tǒng)具有緊急性和動態(tài)性，因而考慮應急資源的多種運輸方式和動態(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ā)公共事件應急物流中的定位－路徑問題研究[J].華中科技大學學報,2008,22(6).

[8] 曾敏剛,崔增收,余高輝.基于應急物流的減災系統(tǒng)LRP研究[J].中國管理科學,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] 趙曉煜,汪定偉.供應鏈中二級分銷網(wǎng)絡優(yōu)化設計的模糊機會約束規(guī)劃模型[J].控制理論與應用,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] 鄭斌,馬祖軍,方濤.應急物流系統(tǒng)中的模糊多目標定位-路徑問題[J].系統(tǒng)工程,2009,27(8).