具有模糊搶修時(shí)間的震后道路搶修排程研究

霍建順，薛 梅，李?lèi)?ài)慶

（西南交通大學(xué) 經(jīng)濟(jì)管理學(xué)院，成都 610031）

0 引言

強(qiáng)震對(duì)于交通網(wǎng)絡(luò)的影響非常巨大，會(huì)造成地面塌陷、龜裂，山體滑坡掩埋道路，橋梁的垮塌等等，這些都使得救援工作受阻。在5.12汶川地震中，多次由于道路受阻使得對(duì)汶川救援工作進(jìn)展緩慢。由于地形復(fù)雜，強(qiáng)余震不斷、惡劣天氣、次生災(zāi)害等，又使得道路搶修工作進(jìn)行地極為艱難。再者震后應(yīng)急期，緊急救援資源(營(yíng)救設(shè)備、營(yíng)救車(chē)輛、救護(hù)車(chē)和相關(guān)營(yíng)救人員、通訊電力搶修人員等)通常都很有限，因而如何最有效地利用這些有限的資源，盡快地將道路搶通變得非常重要。實(shí)際中，應(yīng)急階段對(duì)道路搶修的排程計(jì)劃通常根據(jù)決策者的經(jīng)驗(yàn)進(jìn)行安排，沒(méi)有考慮整個(gè)系統(tǒng)的目標(biāo)，所做方案在理論上只是可行解，在實(shí)際運(yùn)作時(shí)這些方案的實(shí)施效果可能會(huì)非常差。目前對(duì)震后道路災(zāi)點(diǎn)的搶修排程問(wèn)題，國(guó)內(nèi)外學(xué)者有了一定的研究。Cheng-Min Feng[1]將應(yīng)急期界定為災(zāi)后的72小時(shí)，并對(duì)高速公路的道路災(zāi)點(diǎn)搶修排程進(jìn)行了研究。Hitoshi FURUTA et al[2]則考慮了震后不確定性環(huán)境，如：余震，火災(zāi)，天氣等因素，應(yīng)用遺傳算法得到一個(gè)具有魯棒性的道路恢復(fù)排程的決策支持系統(tǒng)。Shangyao Yan et al[3,4]提出一種時(shí)空網(wǎng)絡(luò)模型來(lái)解決震后道路搶修排程的模型，并進(jìn)一步地結(jié)合賑災(zāi)物流情形進(jìn)行討論。

本文考慮到強(qiáng)震后情況的復(fù)雜性，道路搶修不確定性很高，擬將道路災(zāi)點(diǎn)的搶修時(shí)間設(shè)為三角模糊變量，使道路災(zāi)點(diǎn)搶通時(shí)間滿(mǎn)足一定的置信度水平，并用機(jī)會(huì)約束規(guī)劃建構(gòu)數(shù)學(xué)模型，針對(duì)5.12地震后四川省什邡市的道路災(zāi)點(diǎn)數(shù)據(jù)進(jìn)行求解，并進(jìn)行分析。

1 模型及算法

機(jī)會(huì)約束規(guī)劃是由Charnes和cooper提出的第二類(lèi)隨機(jī)規(guī)劃，其顯著特點(diǎn)是約束條件至少以一定的置信水平成立。Baoding Liu et al[5,6]提出了模糊的機(jī)會(huì)約束規(guī)劃，并在文獻(xiàn)[7]中針對(duì)模糊決策系統(tǒng)構(gòu)建了minmax的機(jī)會(huì)約束模型。Yongshuang Zheng et al[8]針對(duì)旅行時(shí)間為模糊變量的車(chē)輛路徑問(wèn)題構(gòu)建了一個(gè)機(jī)會(huì)約束規(guī)劃的模型，在有時(shí)間窗的情形下，最小化行駛距離，并設(shè)計(jì)了一種混合算法來(lái)求解此模糊車(chē)輛路徑問(wèn)題。張建勇等[9]通過(guò)引入決策者主觀偏好值的概念，建立具有模糊特征的車(chē)輛路徑問(wèn)題的模糊機(jī)會(huì)規(guī)劃模型，并設(shè)計(jì)了混合遺傳算法，在最小化總行駛距離的目標(biāo)下進(jìn)行了求解。

在強(qiáng)震應(yīng)急期，政府交通主管部門(mén)根據(jù)收集到的道路受損情況，派出搶修工作隊(duì)進(jìn)行道路搶修，對(duì)道路災(zāi)點(diǎn)搶通的界定為至少有一條車(chē)道可通過(guò)即可。根據(jù)實(shí)際情況，本文對(duì)有關(guān)情形作如下假設(shè)：

（1）每個(gè)道路災(zāi)點(diǎn)僅有一個(gè)工作隊(duì)進(jìn)行搶修；

（2）各個(gè)工作隊(duì)的工作能力相同；

（3）在交通網(wǎng)絡(luò)中，工作隊(duì)的車(chē)輛優(yōu)先或?qū)Ｓ玫缆罚?/p>

（4）工作隊(duì)已掌握所有道路災(zāi)點(diǎn)信息。

因?yàn)樵谡鸷髴?yīng)急期內(nèi)人民的生命依然受到直接威脅，為了盡快的開(kāi)展救援工作，必須使得道路盡快搶通，因此在應(yīng)急階段考慮的目標(biāo)為最小搶修時(shí)間。在整個(gè)交通網(wǎng)路圖中，我們將有關(guān)符號(hào)進(jìn)行如下說(shuō)明：

i=0：工作站；

i=1,2,3,…,n：災(zāi)點(diǎn)；

k=1,2,3,…,m：工作隊(duì)；

Lij：從災(zāi)點(diǎn)i到j(luò)的旅行距離；

Tij：從點(diǎn)i出發(fā)至災(zāi)點(diǎn)j的時(shí)間，由于旅行時(shí)間相對(duì)于維修時(shí)間非常小，故將旅行時(shí)間忽略。將Tij表示為從點(diǎn)i到點(diǎn)j的模糊維修時(shí)間；

[ai,bi]：維修 i點(diǎn)的時(shí)間窗，ai，bi分別為 i開(kāi)始的時(shí)間和結(jié)束的時(shí)間。

我們用x，y和t三個(gè)決策變量刻畫(huà)運(yùn)行計(jì)劃，其中：

x=(x1,x2,…,xn)：整數(shù)決策變量，表示n個(gè)不同的災(zāi)點(diǎn)，對(duì)于所有的 i≠j，有 1≤xi≤n 和 xi≠xj，i,j=1,2,…,n。 實(shí)際上它是序列{x1,x2,…,xn}的一個(gè)重排。

y=(y1,y2,…,ym-1)：整數(shù)決策變量，y0≡0≤y1≤y2≤…≤ym-1。

t=(t1,t2,…,tm)：tk代表車(chē)輛k從工作站出發(fā)的時(shí)間，k=1,2,…,m。因工作隊(duì)投入搶修工作有序，其出發(fā)時(shí)間可能有差別。本文假定工作隊(duì)同時(shí)被指派，僅僅指派時(shí)間不全相同的情況，考慮在滿(mǎn)足道路搶修的時(shí)間窗下，各隊(duì)?wèi)?yīng)在何時(shí)出發(fā)。

注意到運(yùn)行計(jì)劃可以由x，y和t按下面的方式完全確定。對(duì)于每個(gè)k(1≤k≤m)，如果yk=yk-1，表示車(chē)輛k沒(méi)有運(yùn)行；如果yk＞yk-1，則表示車(chē)輛k已運(yùn)行，并且離開(kāi)配送中心的時(shí)間為tk，它的行駛路線(xiàn)為

這種方法比較直觀，且只有n+2m-1個(gè)決策變量。另外，注意到以上定義的決策變量x，y和t保證了：（1）每個(gè)維修隊(duì)最多被派遣一次；（2）所有的路線(xiàn)都以工作站為出發(fā)和結(jié)束點(diǎn)；（3）每個(gè)災(zāi)點(diǎn)有且僅有一個(gè)維修隊(duì)進(jìn)行維修；（4）路線(xiàn)中沒(méi)有子圈。

設(shè)fi(x,y,t)為維修隊(duì)抵達(dá)災(zāi)點(diǎn)i處的時(shí)間函數(shù)，它由決策向量x，y和t決定，i=1,2,…,n。由于當(dāng)維修隊(duì)到達(dá)災(zāi)點(diǎn)時(shí)候，應(yīng)該立即進(jìn)行維修，以爭(zhēng)取最短時(shí)間內(nèi)將道路搶通。如果維修隊(duì) k 被派遣維修（即 yk＞yk-1），1≤k≤m，則對(duì)任何 2≤j≤ykyk-1，有

其中∧表示在兩者中取小（即搶修隊(duì)如果早到，立即投入搶修），由于Tij是模糊的，因此抵達(dá)時(shí)間 fi(x,y,t)，也是模糊變量，并且完全由上面兩式?jīng)Q定。

設(shè)g(x,y)是所有維修隊(duì)的旅行距離，有

其中

決策者根據(jù)實(shí)際情況給出災(zāi)點(diǎn)i以置信水平βi在其指定的時(shí)間窗口[ai，bi]內(nèi)維修完成，于是 Cr{fi(x,y,t)∈[ai,bi]}≥βi,i=1,2,…,n。

可以應(yīng)用痕跡檢驗(yàn)方法檢驗(yàn)油漆附著物，在發(fā)生多車(chē)碰撞交通事故的情況下，可以對(duì)同一部位印壓、刮擦痕上的油漆附著物進(jìn)行檢驗(yàn)，從而明確碰撞順序。具體而言，交通事故往往發(fā)生于瞬間，車(chē)輛相互作用力較大，車(chē)表面在外力的相互作用下容易出現(xiàn)破損、變形等情況。車(chē)輛表面往往會(huì)具有裝飾、保護(hù)功能的漆膜，因外力作用可能發(fā)生脫落、破損等狀況，遺落在其它相關(guān)車(chē)輛表面?；诖?，當(dāng)發(fā)生多車(chē)碰撞的事故時(shí)，以著力點(diǎn)為中心，進(jìn)行痕跡檢驗(yàn)，對(duì)油漆附著情況進(jìn)行分析，即最上層所附著的油漆，為車(chē)輛最后碰撞所留，依次展開(kāi)分析，有助于交通事故處理人員判斷車(chē)輛碰撞順序。

最后給出機(jī)會(huì)約束規(guī)劃模型

本文的利用隨機(jī)模擬和遺傳算法融合而成的混合智能算法進(jìn)行求解，見(jiàn)Yongshuang Zheng[9]，劉保碇等[10]文中的算法描述。

2 案例

本文收集5.12汶川地震后四川省什邡市的有關(guān)數(shù)據(jù)，對(duì)什邡市的震后道路搶修排程問(wèn)題進(jìn)行研究。什邡市民政局提供的5.12汶川地震受災(zāi)人口及其受災(zāi)程度，如表1。

根據(jù)什邡市交通局提供的道路的受損情況，對(duì)道路災(zāi)點(diǎn)進(jìn)行整理如表2，其中連接重災(zāi)區(qū)的道路災(zāi)點(diǎn)以“*”表示。

由于什邡市的重災(zāi)區(qū)很多，連接重災(zāi)區(qū)的道路災(zāi)點(diǎn)很多，假定工作隊(duì)每小時(shí)可搶修的受災(zāi)路段長(zhǎng)度為1km。搶修時(shí)間由前置災(zāi)點(diǎn)的搶修時(shí)間加前置災(zāi)點(diǎn)中最大的搶修時(shí)間表示。因震后道路搶修不確定性因素很多，本文將道路災(zāi)點(diǎn)的搶修時(shí)間用三角模糊數(shù)表示，搶修時(shí)間列表略。

各災(zāi)點(diǎn)由于連接的災(zāi)區(qū)受損程度不同，因此在設(shè)定時(shí)間窗時(shí)，將結(jié)合災(zāi)區(qū)情況予以考慮。本文將連接重災(zāi)區(qū)的道路災(zāi)點(diǎn)搶通須在60小時(shí)內(nèi)，連接一般災(zāi)區(qū)的道路災(zāi)點(diǎn)須在72小時(shí)內(nèi)搶通。將地震發(fā)生時(shí)點(diǎn)定義為0時(shí)，道路災(zāi)點(diǎn)的搶修須在72小時(shí)內(nèi)完成，以便及時(shí)地對(duì)重災(zāi)區(qū)民眾進(jìn)行救助。各災(zāi)點(diǎn)時(shí)間窗如表3。

在應(yīng)急階段，道路搶修的目標(biāo)是在最短時(shí)間內(nèi)搶通道路。因每個(gè)道路災(zāi)點(diǎn)都需要搶修，因此道路災(zāi)點(diǎn)搶修時(shí)間不再考慮，僅考慮旅行時(shí)間，旅行時(shí)間又依賴(lài)于旅行距離，所以將旅行時(shí)間最小化轉(zhuǎn)化為旅行距離最小化，各災(zāi)點(diǎn)之間的距離見(jiàn)表4。

表1 什邡市“5.12”地震災(zāi)害受災(zāi)范圍表

表2 道路災(zāi)點(diǎn)分布情況

續(xù)表

表3 時(shí)間窗

所有的工作隊(duì)從什邡市出發(fā)進(jìn)行搶修，本文設(shè)定有4個(gè)工作隊(duì)，在0.9的置信水平下?lián)屝逓?zāi)點(diǎn)。本文使用混合算法，用vc++6.0編程求解，其結(jié)果如下

工作隊(duì)1：什邡市→14→什邡市

工作隊(duì) 2： 什邡市→12→2→7→6→8→9→10→3→5→17→13→15→4→什邡市

工作隊(duì)3：什邡市→11→什邡市

工作隊(duì)4：什邡市→1→16→什邡市

此時(shí)的置信度為 Cr{fi(x，y，t)∈[ai，bi]，i=1，2， …，17}=0.985，四隊(duì)最遲分別于震后的4.9小時(shí)，3.0小時(shí)，1.2小時(shí)和3.1小時(shí)出發(fā)。從結(jié)果可以看出工作隊(duì)2承擔(dān)的工作量非常重，也說(shuō)明在工作隊(duì)2的工作線(xiàn)路在滿(mǎn)足整個(gè)時(shí)間窗非常重要，這也符合什邡市交通網(wǎng)路“一縱兩橫”的特點(diǎn)，在實(shí)際中則需加強(qiáng)工作隊(duì)2的工作能力，如可以協(xié)調(diào)工作隊(duì)1，3，4協(xié)助工作隊(duì)2完成這條工作線(xiàn)路。

在變換工作隊(duì)數(shù)目時(shí)，在規(guī)定的時(shí)間內(nèi)完成的置信水平0.9的情況下，其置信度水平及總距離改變?nèi)绫?。

表4

表5

從表中可以看出，隨著工作隊(duì)數(shù)目的增加，在時(shí)間窗內(nèi)修通道路災(zāi)點(diǎn)的置信水平是增加的，增加的幅度逐漸降低，但工作隊(duì)行駛的距離也是增加的，其與本文設(shè)置的M有關(guān)，使得工作隊(duì)在通過(guò)某些災(zāi)點(diǎn)時(shí)其行駛距離有很大增加。

3 結(jié)論

地震應(yīng)急期內(nèi)，對(duì)交通路網(wǎng)的搶修工作面臨的不確定性條件很多，在此種情況下，本文將搶修時(shí)間視為模糊變量，在總成本最小化的目標(biāo)下，采用模糊約束規(guī)劃的方法構(gòu)建模型，并使用混合算法對(duì)問(wèn)題進(jìn)行了求解。

本文僅考慮一個(gè)災(zāi)點(diǎn)僅被一個(gè)工作隊(duì)搶修的情況，實(shí)際中往往是會(huì)有多個(gè)工作隊(duì)搶修一個(gè)災(zāi)點(diǎn)，將此假設(shè)條件放松，進(jìn)而求解該問(wèn)題是今后應(yīng)繼續(xù)討論的。

[1]Cheng-Min Feng,Tsai-Chu Wang.Highway Emergency Rehabilitation Scheduling in Post-Earthquake 72 Hours[J].Journal of the Eastern Asia Society for Transportation Studies,2003,.5.

[2]Hitoshi Furuta,Ken Ishibashi,Koichiro Nakatsu,Shun Hotta.Optimal Restoration Scheduling of Damaged Networks Under Uncertain Environment by Using Improved Genetic Algorithm[J].Tsinghua Science And Technology,2008,13.

[3]Yan S.,Shih Y L.A Time-Space Network Model for Work Team Scheduling after a Major Disaster[J].Journal of the Chinese Institute of Engineers,2007,30.

[4]Shangyao Yan,Yu-Lin Shih.Optimal Scheduling of Emergency Roadway Repair and Subsequent Relief Distribution[J].Computers&Operations Research,2008.

[5]Baoding Liu,Kakuzo Iwamura.Chance Constrained Programming with Fuzzy Parameters[J].Fuzzy Sets and Systems,1998,94.

[6]Baoding Liu,Kakuzo Iwamura.A Note on Chance Constrained Programming with Fuzzy Coefficients[J].Fuzzy Sets and Systems,1998,100.

[7]Baoding Liu.Minimax Chance Constrained Programming Models for Fuzzy Decision Systems[J].Information Sciences,1998,112.

[8]Yongshuang Zheng,Baoding Liu.Fuzzy Vehicle Routing Model with Credibility Measure and Its Hybrid Intelligent Algorithm[J].Applied Mathematics and Computation，2006,176.

[9]張建勇,李軍.模糊車(chē)輛路徑問(wèn)題的一種混合遺傳算法[J].管理工程學(xué)報(bào),2005.

[10]劉保碇，趙瑞清，王綱.不確定規(guī)劃及應(yīng)用[M].北京：清華大學(xué)出版社，2003.

[11]李軍，曾鸚，李妍峰.基于汶川地震的震后交通受損評(píng)估研究[J].管理評(píng)論，2008,(12).