任其亮，喬 丹

(重慶交通大學(xué)交通運(yùn)輸學(xué)院，重慶400074)

REN Qi-liang，QIAO Dan

(School of Traffic＆ Transportation，Chongqing Jiaotong University，Chongqing 400074，China)

特大自然災(zāi)害以其突發(fā)性和毀滅性而受到高度重視，因?yàn)?zāi)后救援物資的運(yùn)輸情況十分復(fù)雜，在很多方面具有不確定性，使救援物資的運(yùn)輸調(diào)度在災(zāi)后應(yīng)急救援中占有非常重要的位置。目前的應(yīng)急救援運(yùn)輸研究大都是基于確定的路徑，主要依靠經(jīng)驗(yàn)，從時(shí)間、費(fèi)用、危險(xiǎn)性等方面做定性或半定量分析［1－3］。筆者從災(zāi)后救援運(yùn)輸?shù)膶?shí)際出發(fā)，其各種不確定性，建立運(yùn)輸路徑的不確定優(yōu)化模型，并探討模型的求解算法。

1 災(zāi)后救援運(yùn)輸?shù)牟淮_定性因素

災(zāi)后救援物資運(yùn)輸?shù)奶厥庑栽谟跁r(shí)間的緊迫性和多因素不確定性［4］。救援運(yùn)輸網(wǎng)絡(luò)優(yōu)化模型的不確定性包括變量的不確定性、約束條件的不確定性、決策目標(biāo)的不確定性等，具體表現(xiàn)為:

1)網(wǎng)絡(luò)可靠度不確定性。網(wǎng)絡(luò)可靠度是指網(wǎng)絡(luò)在規(guī)定的時(shí)間和條件下完成預(yù)定功能的概率，是衡量交通網(wǎng)絡(luò)在緊急災(zāi)害情況下，系統(tǒng)功效能否正常發(fā)揮、運(yùn)行狀態(tài)是否達(dá)到預(yù)期要求的重要指標(biāo)［2］。由于對(duì)災(zāi)區(qū)的具體環(huán)境不了解，救援運(yùn)輸網(wǎng)絡(luò)的節(jié)點(diǎn)及其各路段受災(zāi)情況的不同，對(duì)整個(gè)救援的網(wǎng)絡(luò)不清楚。運(yùn)輸網(wǎng)絡(luò)的節(jié)點(diǎn)和路段可能在某一時(shí)刻遭到毀壞，毀壞后又可能在某一時(shí)刻得到修復(fù);另一方面發(fā)生災(zāi)害后，救援車(chē)輛異常增加，加之人員的盲目流動(dòng)，會(huì)造成某些路段交通量驟增，運(yùn)輸網(wǎng)絡(luò)可靠度是不確定的。

2)容量可靠度不確定性。路網(wǎng)容量可靠性［5］是指在一定的服務(wù)水平下，路網(wǎng)容量能滿足一定交通需求水平的概率。受災(zāi)后，由于各類(lèi)路段毀壞的程度是不確定的，因此，救援物資運(yùn)輸網(wǎng)絡(luò)的容量可靠性是不確定的。

3)運(yùn)輸時(shí)間不確定性。由于運(yùn)輸網(wǎng)絡(luò)各路段遭受災(zāi)害的破壞程度是不確定的，而運(yùn)輸梯隊(duì)通過(guò)遭受不同程度的破壞路段的時(shí)間是不確定的，救援運(yùn)輸梯隊(duì)通過(guò)不同路徑的時(shí)間常常是不確定的。

4)運(yùn)輸物資需求量不確定性。在救援物資運(yùn)輸?shù)臅r(shí)間段，次生災(zāi)害隨時(shí)可能發(fā)生，造成更多的人員傷亡和財(cái)產(chǎn)損失，并且往往會(huì)破壞通信和電力設(shè)施，給指揮協(xié)調(diào)和信息反饋造成不利，無(wú)法確切得到救援物資需求量。因此，運(yùn)輸物質(zhì)的需求量也具有不確定性。

5)運(yùn)輸損耗不確定性。災(zāi)害對(duì)交通設(shè)施的破壞，使得運(yùn)輸梯隊(duì)通過(guò)路段時(shí)會(huì)產(chǎn)生損耗。由于各路段遭受的破壞程度是不確定的，其造成的運(yùn)輸損耗也是不確定的。因此，運(yùn)輸梯隊(duì)通過(guò)網(wǎng)絡(luò)路段時(shí)的運(yùn)輸損耗也是不確定的。

6)多重目標(biāo)下選擇不確定性。災(zāi)后救援運(yùn)輸路徑選擇中，當(dāng)多個(gè)目標(biāo)發(fā)生沖突時(shí)該如何選擇，如當(dāng)選擇一條運(yùn)輸路徑時(shí)，運(yùn)輸時(shí)間最少，而運(yùn)輸損耗又比較多，而這時(shí)要達(dá)到運(yùn)輸時(shí)間和運(yùn)輸損耗的最優(yōu)化，該如何選擇?由于救援任務(wù)的需要，2個(gè)指標(biāo)往往都是路徑?jīng)Q策的重要因素，不能只考慮某一方面，且在很多時(shí)候這些因素是不確定的，即路徑優(yōu)化問(wèn)題是一個(gè)在不確定性環(huán)境下的多目標(biāo)優(yōu)化問(wèn)題。

2 救援運(yùn)輸路徑優(yōu)化模型

2.1 網(wǎng)絡(luò)圖

根據(jù)災(zāi)后救援運(yùn)輸任務(wù)的特點(diǎn)，將交通網(wǎng)絡(luò)抽象為一個(gè)有向賦權(quán)圖G=(V，E，C)。式中:V={1，2，…，n}是節(jié)點(diǎn)的集合(n為節(jié)點(diǎn)個(gè)數(shù))，若i，j∈V，則xij表示從i到j(luò)的一條弧;E為弧集，可以表示成以下網(wǎng)絡(luò)結(jié)構(gòu):x={xij:1≤i≤n－1，i+1≤j≤n}，其中，xij∈{0，1}，xij=1 表示路段xij在選擇的可行路徑上，否則xij=0;C為弧xij的權(quán)集，可以是弧的運(yùn)輸時(shí)間、運(yùn)輸損耗和可靠度的集合。

假設(shè)節(jié)點(diǎn)完全可靠，而節(jié)點(diǎn)之間的連接失效與否是彼此統(tǒng)計(jì)獨(dú)立的，且失效的概率已知，那么在V的子集K中的所有節(jié)點(diǎn)是否連接成功是一個(gè)隨機(jī)事件，把這個(gè)時(shí)間的概率稱(chēng)為K，即節(jié)點(diǎn)可靠性，記做R(K，x)，其中x為網(wǎng)絡(luò)結(jié)構(gòu)。如果K中的所有節(jié)點(diǎn)在G中都是連通的，那么稱(chēng)這個(gè)網(wǎng)絡(luò)G是K連通的。因此，K節(jié)點(diǎn)可靠性R(K，x)=Pr{G相對(duì)網(wǎng)絡(luò)結(jié)構(gòu)x是K連通}，當(dāng)K=G時(shí)，K節(jié)點(diǎn)可靠性R(K，x)就是網(wǎng)絡(luò)可靠性［6］。

2.2 約束條件

2.2.1 目標(biāo)約束

災(zāi)后救援運(yùn)輸?shù)穆肪€選擇中，一般行駛時(shí)間這個(gè)參數(shù)最為重要，行駛時(shí)間越短的道路越適合作為災(zāi)害后的緊急救援道路［2］。災(zāi)后應(yīng)急救援運(yùn)輸?shù)哪繕?biāo)是在運(yùn)輸時(shí)間、運(yùn)輸路徑可靠度和運(yùn)輸損耗以一定的置信水平不超過(guò)目標(biāo)值，從而使救援運(yùn)輸效率達(dá)到最高，使災(zāi)區(qū)能在第一時(shí)間內(nèi)得到物資供應(yīng)［7］。因此，假設(shè)有如下目標(biāo)優(yōu)先級(jí)結(jié)構(gòu):第1優(yōu)先級(jí):時(shí)間目標(biāo)，在給定的置信水平α1下，運(yùn)輸時(shí)間應(yīng)盡可能的不超過(guò)目標(biāo)值b1;第2優(yōu)先級(jí):可靠性目標(biāo)，網(wǎng)絡(luò)可靠性盡可能以置信水平α2不低于目標(biāo)值b2;第3優(yōu)先級(jí):損耗目標(biāo)，運(yùn)輸損耗盡可能以置信水平α3不超過(guò)目標(biāo)值b3。

2.2.2 路徑約束

災(zāi)后救援運(yùn)輸路徑優(yōu)化問(wèn)題的約束，假設(shè):1)運(yùn)輸路徑起終點(diǎn)均只有一個(gè)且是確定的;2)單梯隊(duì)從起點(diǎn)出發(fā)，只能選擇一條路段作為運(yùn)輸?shù)缆?，最后到達(dá)終點(diǎn);

3)網(wǎng)絡(luò)中任意中間節(jié)點(diǎn)vi，梯隊(duì)進(jìn)入該節(jié)點(diǎn)，必須還要從該節(jié)點(diǎn)出發(fā)，不得停留或消失;

4)梯隊(duì)通過(guò)各路段的時(shí)間和損耗是隨機(jī)的;

5)運(yùn)輸網(wǎng)絡(luò)可靠性是隨機(jī)的。

可得路徑約束方程如下:

2.3 目標(biāo)規(guī)劃模型

令tij表示弧vij的通行時(shí)間，且記t={tij│(i，j) ∈V}，那么路徑x的通行時(shí)間就可以寫(xiě)成f(x，t)=令sij表示弧vij的通行損耗，且記是s={sij│(i，j)∈V}，那么路徑x的通行損耗就可以寫(xiě)成

根據(jù)不確定機(jī)會(huì)約束理論［6］，得機(jī)會(huì)約束目標(biāo)規(guī)劃模型約束為:

式中:lexmin{*}為按字典序極小化目標(biāo)向量;Pr{*}為事件的概率;αi(i=1，2，3)為給定的置信;bi(i=1，2，3)為給定的目標(biāo)值;為目標(biāo)i偏離目標(biāo)值bi(i=1，2，3)的樂(lè)觀正偏差;x為路徑?jīng)Q策變量，且x={xij:1≤i≤n－1，i+1≤j≤n}(n為網(wǎng)絡(luò)節(jié)點(diǎn)的個(gè)數(shù)，xij∈{0，1}，xij=1表示路段xij在選擇的可行路徑上，否則xij=0)。

3 模型求解

3.1 算法

為求解不確定規(guī)劃模型，筆者設(shè)計(jì)了基于遺傳算法的混合智能算法:首先利用隨機(jī)模擬［6］產(chǎn)生不確定函數(shù)的訓(xùn)練樣本;然后利用這些數(shù)據(jù)訓(xùn)練神經(jīng)元網(wǎng)絡(luò)［8］以逼近不確定函數(shù);最后把訓(xùn)練好的神經(jīng)元網(wǎng)絡(luò)嵌入到遺傳算法中。根據(jù)災(zāi)后救援運(yùn)輸?shù)奶厥馇闆r，對(duì)遺傳算法中的因素做以下說(shuō)明:

1)編碼。采用十進(jìn)制編碼構(gòu)造染色體，染色體的基因?qū)?yīng)網(wǎng)絡(luò)節(jié)點(diǎn)序號(hào)，而序號(hào)的排列順序代表救援運(yùn)輸梯隊(duì)從起點(diǎn)到終點(diǎn)的路徑。設(shè)路網(wǎng)的節(jié)點(diǎn)集合V中節(jié)點(diǎn)總數(shù)為n，則染色體的基因總數(shù)也為n。染色體基因的組成方式:第1個(gè)為起點(diǎn)序號(hào)“1”;接下來(lái)是中間節(jié)點(diǎn)，設(shè)中間節(jié)點(diǎn)總數(shù)為n，則有0≤l≤n－2;然后是終點(diǎn)“n”。如果 0≤l＜n－2，則在“n”點(diǎn)后補(bǔ)“0”，使基因總數(shù)保持為n。設(shè)染色體中從“1”到“n”的非0基因個(gè)數(shù)為m，定義其為有效基因數(shù)。以圖1為例，建立路徑1－2－3－6－7的連接矩陣(表1)，則該路徑對(duì)應(yīng)的染色體的編碼為1 2 3 6 7 0 0。

圖1 網(wǎng)絡(luò)圖Fig.1 Network diagram

表1 連接矩陣Tab.1 Connection matrix

基于這樣的編碼方式，可得出染色體中的第1個(gè)基因是“1”，最后一個(gè)不為“0”的基因是終點(diǎn)的序號(hào)“n”，當(dāng)基因中包含“0”基因時(shí)，說(shuō)明有部分節(jié)點(diǎn)沒(méi)有在這個(gè)染色體所代表的路徑上。

2)評(píng)價(jià)函數(shù)。比較常用的評(píng)價(jià)函數(shù)是基于序的評(píng)價(jià)函數(shù)［6］，設(shè)目前該代中的染色體為T(mén)1，T2，…，Tpop_size，對(duì)于目標(biāo)規(guī)劃模型，種群中的染色體有以下序關(guān)系:對(duì)于2個(gè)染色體，如果它們?cè)诟咭患?jí)的目標(biāo)值相同，則在當(dāng)前一級(jí)中染色體所對(duì)應(yīng)的目標(biāo)值越小越好。如在每一級(jí)中2個(gè)染色體都對(duì)應(yīng)相同的目標(biāo)值，就認(rèn)為這2個(gè)染色體無(wú)差別，從而可以對(duì)它們進(jìn)行隨機(jī)的排序。設(shè)參數(shù)α∈(0，1)給定，定義基于序的評(píng)價(jià)函數(shù)為:eval(Ti)=a(1－a)i－1，i=1，2，…，pop_size 。

3)選擇。采用改進(jìn)的輪盤(pán)賭選擇法。在選擇新個(gè)體時(shí)，首先在當(dāng)前代中選擇最佳個(gè)體直接進(jìn)入下一代(若有多個(gè)，則隨機(jī)選取一個(gè))，然后對(duì)其它個(gè)體依累積概率大小采用輪盤(pán)賭方式進(jìn)行選擇。對(duì)每個(gè)染色體Ti，計(jì)算累計(jì)概率1，2，…，pop_size 。從區(qū)間(0，qpop_size)中產(chǎn)生一個(gè)隨機(jī)數(shù)r，若qi－1＜r≤qi，則選擇第i個(gè)染色體Ti，重復(fù)選擇，得到pop_size個(gè)復(fù)制的染色體。

4)交叉。根據(jù)染色體編碼規(guī)則的特點(diǎn)及與路徑節(jié)點(diǎn)序號(hào)的關(guān)聯(lián)性，采用類(lèi)OX法作為染色體交叉的方法，交叉步驟為:①?gòu)纳弦淮x擇染色體T0、T1的基因中隨機(jī)選擇2個(gè)交叉點(diǎn)，交叉點(diǎn)必須同時(shí)位于2個(gè)染色體的“1”之后，“n”之前，以保證“0”基因不被交叉，交叉點(diǎn)之間的部分為匹配區(qū)域段;②將T0的匹配段加到T1的基因“1”之后，將T1的匹配區(qū)域加到T0的基因“1”之后;③消除染色體匹配段后面的重復(fù)節(jié)點(diǎn)。

5)變異。采用的染色體變異方式有3種:①在基因“1”和“n”之間隨機(jī)刪除一個(gè)非必經(jīng)點(diǎn)所代表的基因，同時(shí)在“n”后補(bǔ)“0”基因，以使保持基因數(shù)為n;②當(dāng)有效基因總數(shù)m＜n時(shí)，增加一個(gè)基因中沒(méi)有的節(jié)點(diǎn)序號(hào)作為基因，其位置可以在有效基因的中間部份隨機(jī)選取，同時(shí)在“n”后刪除一個(gè)“0”基因;③互換“1”和“n”之間的2個(gè)基因。為提高遺傳算法的性能，筆者采用類(lèi)似于模擬退火算法中的Metropolis準(zhǔn)則［1］對(duì)變異進(jìn)行改進(jìn)，如果變異后的值優(yōu)于變異前的值，則新染色體進(jìn)入下一代;否則，依概率確定是否進(jìn)入下一代。公式如下代中的適應(yīng)度最大值，P為變異后染色體接受概率。

3.2 算例

以圖1為救援運(yùn)輸網(wǎng)絡(luò)圖，對(duì)建立的目標(biāo)規(guī)劃模型進(jìn)行試驗(yàn)，以驗(yàn)證模型和算法的有效性。

單梯隊(duì)通過(guò)各路段的隨機(jī)時(shí)間和通行損耗分布如表2和表3。路網(wǎng)各路段的可靠性服從正態(tài)分布N(1，4)。

表2 通行時(shí)間隨機(jī)分布Tab.2 Random distribution of time

表3 通行損耗隨機(jī)分布Tab.3 Random distribution of loss

根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，染色體的基因個(gè)數(shù)為7。在置信水平(α1，α2，α3)=(0.8，0.85，0.8)下，通行時(shí)間、路網(wǎng)可靠性和通行損耗的目標(biāo)水平為(b1，b2，b3)=(5，0.85，5)。設(shè)遺傳算法的種群大小為 50，交叉概率 0.85，變異率 0.05。

通過(guò)運(yùn)行混合智能算法(1 000次模擬循環(huán)，500次遺傳迭代)，得到最優(yōu)路徑為1－3－7，它滿足前2個(gè)目標(biāo)，第3個(gè)目標(biāo)偏差為0.975。

4 結(jié)語(yǔ)

從災(zāi)后救援運(yùn)輸?shù)慕嵌瘸霭l(fā)，建立災(zāi)后救援運(yùn)輸路徑動(dòng)態(tài)優(yōu)化模型和算法。該模型能符合發(fā)生各類(lèi)特大自然災(zāi)害時(shí)的實(shí)際情況，解決不確定性救援運(yùn)輸路徑動(dòng)態(tài)優(yōu)化問(wèn)題，滿足各類(lèi)特大自然災(zāi)害時(shí)的救援運(yùn)輸需求，并指導(dǎo)其他緊急狀態(tài)下的運(yùn)輸問(wèn)題，能夠?yàn)闃O大地減少因現(xiàn)有理論方法不足而產(chǎn)生的人員、物資的損耗問(wèn)題提供借鑒，提高救援運(yùn)輸?shù)男?，具有較高的社會(huì)經(jīng)濟(jì)效益。

［1］黃金虎.應(yīng)急物流系統(tǒng)若干關(guān)鍵技術(shù)的研究與實(shí)現(xiàn)［D］.上海:上海交通大學(xué)，2007.

［2］巴桑次仁，鄧桂英，巴桑央金.西藏地震應(yīng)急救援體系建設(shè)的探索［J］.高原地震，2009，21(2):58 －61.

［3］王洪，陸愈實(shí)，王莎莎.基于MATLAB的應(yīng)急救援最優(yōu)路徑選擇［J］.工業(yè)安全與環(huán)保，2009，35(5):48－50.

［4］繆成，許維勝，吳啟迪.大規(guī)模應(yīng)急救援物資運(yùn)輸模型的構(gòu)建與求解［J］.系統(tǒng)工程，2006，24(11):6 －12.

［5］任其亮.灰色馬爾可夫模型在公路運(yùn)量彈性系數(shù)預(yù)測(cè)中的應(yīng)用研究［J］.重慶交通大學(xué)學(xué)報(bào):自然科學(xué)版，2009，28(2):290－293.

［6］石玉峰.戰(zhàn)時(shí)不確定性運(yùn)輸路徑優(yōu)化研究［D］.成都:西南交通大學(xué)，2006.

［7］彭錦，劉寶碇.不確定規(guī)劃的研究現(xiàn)狀及其發(fā)展前景［J］.運(yùn)籌與管理，2002，11(2):1 －10.

［8］陳燕燕，劉小明，梁穎.可靠度在交通系統(tǒng)規(guī)劃與管理中的應(yīng)用［M］.北京:人民交通出版社，2006.