周愉峰, 陳 娜, 李 志, 龔 英
(1.重慶工商大學(xué) 重慶市發(fā)展信息管理工程技術(shù)研究中心,重慶 400067; 2.南京航空航天大學(xué) 管理科學(xué)與工程博士后流動(dòng)站,江蘇 南京 211106; 3.重慶工商大學(xué) 商務(wù)策劃學(xué)院,重慶 400067)
大規(guī)模地震的爆發(fā)可能造成眾多人員傷亡,短時(shí)間內(nèi)產(chǎn)生大量救災(zāi)物資需求。震后救援初期,特別是地震發(fā)生后的前72小時(shí),是應(yīng)急救援的黃金時(shí)間。該時(shí)期對(duì)藥品、血液、救助工具等應(yīng)急物資的需求非常緊迫。因此,大地震發(fā)生后,需立刻建立有效的應(yīng)急物流網(wǎng)絡(luò),實(shí)現(xiàn)應(yīng)急物資從供應(yīng)點(diǎn)到受災(zāi)點(diǎn)的快速調(diào)配。
大量研究者將震后應(yīng)急物流網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)問(wèn)題描述為設(shè)施選址-分配問(wèn)題(Facility location-allocationproblem,F(xiàn)LAP)。例如,Salman等[1]研究了隨機(jī)路網(wǎng)損壞下的應(yīng)急FLAP。Boonmee等[2]綜述了人道主義救援物流中的FLP。Tzeng等[3]考慮震后應(yīng)急物資分配的特點(diǎn),研究了應(yīng)急中轉(zhuǎn)設(shè)施的多目標(biāo)LAP模型。鄭斌等[4]以運(yùn)輸時(shí)間滿意度和物資分配公平性最大為目標(biāo),基于雙層規(guī)劃方法研究了震后應(yīng)急物流系統(tǒng)中的選址-聯(lián)運(yùn)問(wèn)題,并設(shè)計(jì)相應(yīng)的混合遺傳算法。劉亞杰等[5]考慮需求不確定性,研究了震后初期應(yīng)急FLAP,并將其描述成隨機(jī)混合整數(shù)規(guī)劃模型。Yahyaei和Bozorgi-Amiri[6]研究了震后應(yīng)急物資供應(yīng)設(shè)施與避難設(shè)施的集成選址問(wèn)題。
以上研究均含有一個(gè)隱藏的假設(shè):設(shè)施是完全可靠而不中斷的。這一假設(shè)并不符合現(xiàn)實(shí)[7]。由于自然災(zāi)害或人為因素影響,已經(jīng)建立的設(shè)施有可能發(fā)生中斷。一旦設(shè)施發(fā)生中斷,其服務(wù)的需求點(diǎn)將有可能得不到物資供應(yīng),或者需重新指派其他設(shè)施為其服務(wù)。臨時(shí)指派的其他設(shè)施距離更遠(yuǎn)且?guī)齑嫒萘靠赡懿蛔恪R虼?,設(shè)施中斷現(xiàn)象會(huì)影響整個(gè)物流系統(tǒng)的運(yùn)行效率。You等[8]采用兩階段隨機(jī)規(guī)劃方法,研究了考慮中斷風(fēng)險(xiǎn),多產(chǎn)品不確定需求和不確定運(yùn)價(jià)的供應(yīng)鏈優(yōu)化設(shè)計(jì)問(wèn)題,結(jié)果證明考慮風(fēng)險(xiǎn)因素的模型可節(jié)約超過(guò)5%的成本。因此,考慮設(shè)施中斷風(fēng)險(xiǎn)十分必要,有助于構(gòu)建具有可靠性的物流網(wǎng)絡(luò),降低應(yīng)急成本。Snyder等[9]最早引入中斷風(fēng)險(xiǎn),研究了可靠性設(shè)施選址問(wèn)題(Reliable facility location problem,RFLP)。他們?cè)谖墨I(xiàn)[9]中構(gòu)建了兩類RFLP模型,分別稱之為無(wú)容量約束的RFLP(Reliability uncapacitated fixed-charge location problem,RUFLP)和可靠性P-中位問(wèn)題(Reliability p-median problem,RPMP)。他們的模型既考慮了設(shè)施日常運(yùn)行成本,也考慮了設(shè)施的期望中斷成本。其研究結(jié)論證明了少量增加成本可以大大提高系統(tǒng)的可靠性。此后十多年來(lái),RFLP受到了研究者們的高度關(guān)注,成為選址研究的一類前沿性問(wèn)題,取得了豐碩的研究成果。An等[10],Albareda-Sambola等[11]也分別研究了RPMP與RUFLP。此外,Sadegh等[12]研究了有容量限制的可靠性固定費(fèi)用選址問(wèn)題;Aydin等[13]研究了有容量限制的可靠性p-hub覆蓋選址問(wèn)題。
傳統(tǒng)的RFLP研究一般針對(duì)常規(guī)環(huán)境,考慮中斷風(fēng)險(xiǎn)的應(yīng)急設(shè)施選址研究尚不多見(jiàn)。周愉峰等[14]以血站為研究對(duì)象,同時(shí)考慮血液產(chǎn)品供應(yīng)的及時(shí)性和可靠性目標(biāo),研究了設(shè)施具有不同失靈概率的RPMP模型。Fu等[15]建立了一個(gè)區(qū)域應(yīng)急儲(chǔ)備設(shè)施的RFLP模型。上述文獻(xiàn)的研究對(duì)象是防災(zāi)備災(zāi)過(guò)程中的應(yīng)急儲(chǔ)備設(shè)施,通常需要考慮系統(tǒng)成本。震后初期的應(yīng)急物資供應(yīng)具有弱經(jīng)濟(jì)性及其他典型特征,因而這些防災(zāi)備災(zāi)應(yīng)急RFLP的研究成果難以應(yīng)用于災(zāi)后救援期內(nèi)的選址-分配決策。
震后救援初期的應(yīng)急物資調(diào)配具有眾多突出特征,主要體現(xiàn)在:①需求不確定。由于震后初期信息傳遞渠道不暢,災(zāi)情信息不明,只能根據(jù)地震烈度、建筑物抗震等級(jí)、地震發(fā)生時(shí)間以及災(zāi)區(qū)人口密度等因素大致推斷災(zāi)區(qū)需求信息。②救災(zāi)物資品種多且緊迫性高。此時(shí)期需要緊急調(diào)運(yùn)食品、飲用水、帳篷、藥品等多種應(yīng)急物資。由于初期災(zāi)情嚴(yán)重,物資需求具有很高的緊迫性。③道路通行能力嚴(yán)重受限。大規(guī)模地震后路網(wǎng)受損且短期內(nèi)難以完全修復(fù),降低了車輛通行速度。④供不應(yīng)求現(xiàn)象突出。震后初期應(yīng)急物資需求爆炸性增長(zhǎng),短期內(nèi)物資儲(chǔ)備及籌措受限,加上路網(wǎng)受損物資調(diào)運(yùn)速度下降,導(dǎo)致該時(shí)期物資短缺。⑤設(shè)施中斷概率參數(shù)難以準(zhǔn)確獲取。此時(shí),基于中斷情景描述問(wèn)題更具實(shí)用性。
鑒于此,本文在傳統(tǒng)RFLP與應(yīng)急FLAP的基礎(chǔ)上,引入設(shè)施中斷情景,考慮應(yīng)急物資調(diào)配特性,研究震后救援初期應(yīng)急物流網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)中的選址-分配問(wèn)題,并設(shè)計(jì)相應(yīng)的遺傳算法對(duì)問(wèn)題進(jìn)行求解。
為快速響應(yīng)震后救援初期(震后1~7天)的緊急需求,需迅速構(gòu)建好應(yīng)急物流網(wǎng)絡(luò)。其核心是合理確定應(yīng)急物資配送中心的位置。候選應(yīng)急物資配送中心有容量限制,其作為中轉(zhuǎn)設(shè)施,負(fù)責(zé)接收從上級(jí)集散點(diǎn)運(yùn)來(lái)的救援物資,并快速將各類應(yīng)急物資配送到各個(gè)受災(zāi)點(diǎn)。震后初期應(yīng)急救援的首要目標(biāo)是快速響應(yīng)災(zāi)區(qū)需求,因此應(yīng)以應(yīng)急物資供應(yīng)的時(shí)效性最好為優(yōu)化目標(biāo)。由于該時(shí)期內(nèi)多類物資緊缺,供不應(yīng)求現(xiàn)象突出,應(yīng)急物資分配的公平性問(wèn)題也成為災(zāi)民的重大關(guān)切點(diǎn)。為保證應(yīng)急物資在受災(zāi)點(diǎn)之間分配的公平性,要求任意兩個(gè)受災(zāi)點(diǎn)的需求未滿足率之差不超過(guò)給定的閾值。
救災(zāi)物資需求具有不確定性,根據(jù)震后物資需求特點(diǎn),將不確定需求處理成三角模糊數(shù)。同時(shí),決策期內(nèi)受地震影響道路嚴(yán)重受損,車輛通行速度受限,文章引入路況系數(shù)來(lái)反應(yīng)車輛的實(shí)際通行速度。由于余震、山體滑坡等因素威脅,建立的應(yīng)急物資配送中心可能會(huì)失效。鑒于設(shè)施中斷的具體概率難以準(zhǔn)確獲取,選擇設(shè)置若干典型中斷情景進(jìn)行建模。
綜上,問(wèn)題可以描述為:考慮設(shè)施中斷情景、模糊需求、多品種物資以及有能力約束的FLAP模型。要解決的關(guān)鍵問(wèn)題是:需要建立多少個(gè)應(yīng)急物資配送中心?建在哪里?如何確定受災(zāi)點(diǎn)與應(yīng)急物資配送中心的指派關(guān)系?每個(gè)受災(zāi)點(diǎn)應(yīng)該分配多少物資量?
假設(shè)如下:①受災(zāi)點(diǎn)的位置已知;②各候選應(yīng)急物資配送中心的位置已知,且有處理能力限制;③每個(gè)應(yīng)急物資配送中心可同時(shí)服務(wù)多個(gè)受災(zāi)點(diǎn);每個(gè)受災(zāi)點(diǎn)僅指派給一個(gè)開(kāi)放且未中斷的應(yīng)急物資配送中心。
符號(hào)定義如下:
(1)參數(shù)
I:受災(zāi)點(diǎn)集合,i∈I;
J:候選應(yīng)急物資配送中心集合,j∈J;
C:應(yīng)急物資種類集合,c∈C;
W:情景結(jié)合,w∈W;
dij:應(yīng)急物資配送中心j到受災(zāi)點(diǎn)i的距離;
vij:正常條件下應(yīng)急物資配送中心j到受災(zāi)點(diǎn)i的運(yùn)輸速度;
γij:應(yīng)急物資配送中心j到受災(zāi)點(diǎn)i的路況系數(shù),0≤γij≤1;
Tij:路網(wǎng)受損條件下應(yīng)急物資配送中心j到受災(zāi)點(diǎn)i的運(yùn)輸時(shí)間;
Wj:決策期內(nèi)應(yīng)急物資配送中心j的最大處理能力;
KQc:c類應(yīng)急物資的最大可用量;
qij:應(yīng)急物資配送中心j到受災(zāi)點(diǎn)i的最大單次運(yùn)力;
uiw:情景w下受災(zāi)點(diǎn)i的需求未滿足率;
ξ:一個(gè)很小的正數(shù)。
2)決策變量
Qicw:情景w下,受災(zāi)點(diǎn)i的c類物資分配量;
Qjc:應(yīng)急物資配送中心j對(duì)c類應(yīng)急物資的供應(yīng)量;
至此,建立如下的數(shù)學(xué)模型:
(1)
Yij≤Xj,?i∈I,j∈J
(2)
(3)
(4)
(5)
(6)
?i∈I,c∈C,w∈W,且Yijajw=1
(7)
(8)
|uew-ufw|≤ξ,?e∈I,f∈I且e≠f,w∈W
(9)
(10)
(11)
Qjc,Qicw為正整數(shù),?i∈I,j∈J,c∈C,w∈W
(12)
Xj,Yij∈{0,1},?i∈I,j∈J
(13)
目標(biāo)式(1)表示任意情景下的最大配送時(shí)間最小,從而保證了應(yīng)急物流網(wǎng)絡(luò)的時(shí)效性。式(1)的第1項(xiàng)表示初始指派設(shè)施未中斷的受災(zāi)點(diǎn)接受物資的配送時(shí)間,第2項(xiàng)表示初始指派設(shè)施發(fā)生中斷的受災(zāi)點(diǎn)接受物資的配送時(shí)間。式(2)表示應(yīng)急物資配送中心提供服務(wù)的前提是設(shè)施已開(kāi)放且未中斷;式(3)表示每個(gè)受災(zāi)點(diǎn)僅被指派給一個(gè)應(yīng)急物資配送中心;式(4)表示路網(wǎng)受損條件下從應(yīng)急物資配送中心到受災(zāi)點(diǎn)的運(yùn)輸時(shí)間;式(5)表示若受災(zāi)點(diǎn)初始指派的應(yīng)急物資配送中心發(fā)生中斷,則將其重新指派給最近的開(kāi)放且未中斷的設(shè)施;式(6)為應(yīng)急物資配送中的物資供應(yīng)量約束;式(7)表示受災(zāi)點(diǎn)的物資分配量按需求比例分配,以保證局部公平性最好;式(8)為各種情景下受災(zāi)點(diǎn)需求未滿足率的表達(dá)式;式(9)表示所有情景下任意兩個(gè)受災(zāi)點(diǎn)的需求未滿足率之差在給定的閾值范圍內(nèi),以實(shí)現(xiàn)物資分配的公平性;式(10)為應(yīng)急物資可用量限制;式(11)為應(yīng)急物資配送中心的容量約束;式(12)為非負(fù)整數(shù)約束;式(13)為0-1變量約束。
受災(zāi)點(diǎn)需求量為三角模糊數(shù),采用文獻(xiàn)[16]提出的模糊參數(shù)期望公式進(jìn)行期望值轉(zhuǎn)換。震后救援初期受災(zāi)點(diǎn)i對(duì)c類物資的期望需求量可用式(14)進(jìn)行處理。
(14)
由于目標(biāo)函數(shù)以及約束(4),(7),(8)均為非線性表達(dá)式,建立的模型屬于非線性0-1混合整數(shù)規(guī)劃模型。該模型的求解屬于NP-hard問(wèn)題,無(wú)法應(yīng)用分支定界算法或者Gurobi、Cplex等優(yōu)化工具對(duì)問(wèn)題進(jìn)行精確求解。為此,針對(duì)模型的特點(diǎn),設(shè)計(jì)一種整數(shù)編碼的混合遺傳算法。算法流程見(jiàn)圖。
圖1 算法流程圖
(1)參數(shù)初始化
初始化種群規(guī)模popsize,最大迭代次數(shù)maxgen,交叉概率pc,變異概率pm等參數(shù)。
(2)染色體編碼
染色體長(zhǎng)度為|I|。以圖2為例,假設(shè)網(wǎng)絡(luò)中有7個(gè)候選設(shè)施點(diǎn),20個(gè)受災(zāi)點(diǎn),則圖2的編碼表示:選擇開(kāi)放的應(yīng)急物資配送中心有1,4,5;設(shè)施1服務(wù)受災(zāi)點(diǎn)分別對(duì)應(yīng)受災(zāi)點(diǎn)2,5,6,8,11,14,16,17,20;設(shè)施4服務(wù)受災(zāi)點(diǎn)3,7,10,12,18,19;設(shè)施5服務(wù)受災(zāi)點(diǎn)1,4,9,13,15。因此,選址解Xj與分配解Yij可直接通過(guò)編碼解碼獲得。供應(yīng)量Qjc,Qicw根據(jù)變量Yij進(jìn)行解碼,由指派配送中心的物資總量按受災(zāi)點(diǎn)的需求比例進(jìn)行分配。
圖2 染色體編碼示意
(3)初始化種群
基于matlab內(nèi)嵌的randi函數(shù)隨機(jī)均勻生成初始化種群。
(4)適應(yīng)度值計(jì)算
建立的模型為最小化問(wèn)題,在此,將適應(yīng)度值改寫為目標(biāo)函數(shù)值的倒數(shù)。設(shè)Fitness(chromosome1(gen))為第i條染色體在第gen代的適應(yīng)度值,Zi(ge)為第代的目標(biāo)函數(shù)值,則:
(15)
采用罰函數(shù)處理約束(9),避免出現(xiàn)非可行解。
(5)遺傳操作
①選擇。采用輪盤賭進(jìn)行選擇操作。同時(shí)加入精英保留策略,將已有的最優(yōu)個(gè)體復(fù)制到下一代,以加速收斂并增強(qiáng)算法有效性[17]。
②交叉。采用均勻交叉策略:均勻隨機(jī)生成長(zhǎng)度為|I|規(guī)模為popsize的0-1矩陣,根據(jù)基因位對(duì)應(yīng)位置隨機(jī)選擇兩條染色體進(jìn)行交叉。如圖3所示,若基因位對(duì)應(yīng)位置為0,選擇染色體1的基因;否則,選擇染色體2的基因;從而得到兩條新的染色體。
圖3 染色體交叉示意
③變異。如圖4所示,隨機(jī)選取染色體的兩個(gè)基因進(jìn)行實(shí)值變異。為避免變異后的基因值超過(guò)臨界值,選擇加入?yún)^(qū)域掃描器。采用可變變異率pm,即算法迭代初期pm取一個(gè)較大的值,促進(jìn)解的多樣性;在一定迭代次數(shù)以后,pm取一個(gè)較小的值以加速收斂[17]。
圖4 染色體變異示意
(6)算法終止條件
若迭代代數(shù)達(dá)到maxgen,算法終止并計(jì)算最優(yōu)解。
以5·12汶川地震為背景構(gòu)建模擬算例。假設(shè)受災(zāi)點(diǎn)為30個(gè)重災(zāi)區(qū),受災(zāi)點(diǎn)之間的距離通過(guò)坐標(biāo)位置進(jìn)行計(jì)算。30個(gè)重災(zāi)區(qū)的坐標(biāo)信息與物資需求信息見(jiàn)文獻(xiàn)[18]。主要應(yīng)急物資有3類,3類應(yīng)急物資的當(dāng)前可用量分別為26000單位、22500單位和6400單位。15個(gè)候選應(yīng)急物資配送中心的坐標(biāo)和處理能力信息見(jiàn)表1。各候選應(yīng)急物資配送中心到受災(zāi)點(diǎn)的運(yùn)輸距離、正常行駛時(shí)間、路況系數(shù)、單次運(yùn)力限制等參數(shù)值見(jiàn)文獻(xiàn)[18]。假設(shè)有4種中斷情景,如表2所示,在情景2~4中分別有一個(gè)設(shè)施發(fā)生中斷。其它參數(shù)設(shè)置如下:vij=80km/h,ξ=0.05。
表1 候選應(yīng)急物資配送中心信息
表2 候選應(yīng)急物資配送中心的中斷情景集合
遺傳算法參數(shù)設(shè)置如下[17,19]:popsize=100,maxgen=400,pc=0.9。前100次迭代,pm取0.2;100代以后pm取0.1。采用Matlabr 2010b作為編程語(yǔ)言和實(shí)現(xiàn)平臺(tái),在Intel Core i5 CPU和8G內(nèi)存的個(gè)人筆記本電腦上運(yùn)行程序,取10次運(yùn)算結(jié)果的最優(yōu)解作為最終解。得到算法收斂時(shí)間為213.77s,算法收斂曲線見(jiàn)圖5,計(jì)算結(jié)果見(jiàn)表3。
表3 考慮設(shè)施中斷情景的選址-分配解
為了測(cè)試所建模型的可靠性,將當(dāng)前優(yōu)化方案(記為方案1)與不考慮設(shè)施中斷情景的優(yōu)化方案(記為方案2,結(jié)果見(jiàn)表4)進(jìn)行比較。在方案2中,重新將設(shè)施中斷情景考慮進(jìn)來(lái),計(jì)算每種情景下的目標(biāo)值,并將其與方案1的結(jié)果進(jìn)行比較(見(jiàn)表5)。結(jié)果表明:情景1下,方案2略優(yōu)于方案1(差距-8.3%);而在其它情景下,方案1明顯優(yōu)于方案2(差距大于21.6%)。這意味著,中斷一旦發(fā)生將產(chǎn)生大量的應(yīng)急成本。因此,在應(yīng)急物流網(wǎng)絡(luò)設(shè)計(jì)階段就考慮中斷情景可以提升系統(tǒng)的可靠性和穩(wěn)健性。
表4 不考慮設(shè)施中斷情景的選址-分配解
表5 兩種優(yōu)化方案的比較
圖5 算法收斂圖
震后初期是應(yīng)急救援的黃金時(shí)期。該時(shí)期對(duì)應(yīng)急物資的需求量大、緊迫性高。此時(shí)建立迅速有效的應(yīng)急物流網(wǎng)絡(luò)對(duì)搶險(xiǎn)救災(zāi)具有非常重大的價(jià)值??紤]到震后應(yīng)急救援物流系統(tǒng)中,應(yīng)急設(shè)施曝露于余震等次生衍生災(zāi)害下,并非完全可靠。因此,應(yīng)急物流網(wǎng)絡(luò)的設(shè)計(jì)需考慮設(shè)施中斷現(xiàn)象。由于設(shè)施中斷的具體概率難以準(zhǔn)確獲取,故采用設(shè)置典型中斷情景的方法具有更好的實(shí)用性。在此基礎(chǔ)上,文章基于震后救援初期的階段性特點(diǎn),建立了一個(gè)考慮設(shè)施中斷情景、多品種模糊需求、有設(shè)施處理能力限制、物資公平分配、交通路網(wǎng)部分損傷的應(yīng)急FLAP模型,并設(shè)計(jì)了一種的基于整數(shù)編碼的混合遺傳算法。最后,以5·12汶川地震為背景構(gòu)建算例對(duì)模型和算法進(jìn)行了驗(yàn)證。
數(shù)值仿真結(jié)果表明,若震后設(shè)施出現(xiàn)中斷現(xiàn)象,本文的研究結(jié)果可將系統(tǒng)目標(biāo)優(yōu)化21.6%以上;即使震后沒(méi)有發(fā)生應(yīng)急設(shè)施中斷現(xiàn)象,優(yōu)化結(jié)果與最優(yōu)目標(biāo)值的差距也僅有8.3%。從而得到主要的研究結(jié)論:考慮設(shè)施中斷情景后,即使部分設(shè)施失效,整個(gè)應(yīng)急物流網(wǎng)絡(luò)仍能較好運(yùn)行。優(yōu)化結(jié)果具有一定的可靠性和穩(wěn)健性。因此,有必要在系統(tǒng)設(shè)計(jì)階段就考慮設(shè)施的中斷風(fēng)險(xiǎn),建立更加可靠與穩(wěn)健的應(yīng)急物流網(wǎng)絡(luò)。
進(jìn)一步研究可以將應(yīng)急物資集散點(diǎn)考慮進(jìn)來(lái),構(gòu)建考慮設(shè)施中斷情景的多級(jí)應(yīng)急物流網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)問(wèn)題。也可以綜合考慮救援后期的階段性特點(diǎn),研究中斷情景下多類應(yīng)急設(shè)施的動(dòng)態(tài)選址-分配問(wèn)題。