楊菊花，朱昌鋒，田志強(qiáng)

(蘭州交通大學(xué)交通運(yùn)輸學(xué)院，甘肅 蘭州 730070)

地震、火災(zāi)、流行性傳染病等突發(fā)事件的頻發(fā)，給人民群眾生命財(cái)產(chǎn)和社會(huì)安全造成極大的危害。在突發(fā)性很強(qiáng)的自然災(zāi)害和公共衛(wèi)生事件發(fā)生的地區(qū)，往往平時(shí)沒(méi)有賑災(zāi)物資儲(chǔ)備，或儲(chǔ)備的數(shù)量和種類(lèi)有限，在應(yīng)急物資供應(yīng)方面表現(xiàn)出被動(dòng)局面，需要大量從全國(guó)各地緊急調(diào)運(yùn)。為此，有關(guān)專(zhuān)家學(xué)者就該問(wèn)題開(kāi)展了大量的研究。劉志學(xué)等［1－2］從供給的角度提出了路網(wǎng)的容量可靠性指標(biāo)，以考慮在交通事件影響下路網(wǎng)能夠容納一定水平交通量的概率;Sumalee等［3］建立了不確定需求下的以總行程時(shí)間可靠性最大化為目標(biāo)的網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題的數(shù)學(xué)模型;Chootinan等［4］建立了以容量可靠性最大化為目標(biāo)的網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題的雙層規(guī)劃模型;歐忠文等［5］就應(yīng)急物流保障機(jī)制開(kāi)展了相應(yīng)的研究，張曉波等［6－7］對(duì)應(yīng)急物資公路運(yùn)輸?shù)淖疃搪窂竭M(jìn)行研究和求解。由于應(yīng)急物資的特殊性，單從公路一種運(yùn)輸方式探討其路徑的選擇問(wèn)題難以滿(mǎn)足實(shí)際的需要。此外，從多種運(yùn)輸方式角度探討應(yīng)急物資的調(diào)運(yùn)路徑問(wèn)題，由于存在多目標(biāo)、多種類(lèi)貨物等約束條件，使得應(yīng)急救援物資運(yùn)輸問(wèn)題的構(gòu)建與解決非常復(fù)雜。目前討論此問(wèn)題的文獻(xiàn)較少，不能與其重要性及目前應(yīng)用需要相適應(yīng)。且大多內(nèi)容重點(diǎn)研究了如何將應(yīng)急物資快速有效的從災(zāi)區(qū)救災(zāi)中心運(yùn)往各個(gè)受災(zāi)點(diǎn)，而沒(méi)有涉及應(yīng)急物資的全程調(diào)運(yùn)問(wèn)題。鑒于此，本文擬結(jié)合有關(guān)研究成果，建立應(yīng)急物資全程調(diào)撥時(shí)運(yùn)輸方式和路徑選擇問(wèn)題的綜合優(yōu)化模型，為應(yīng)急決策提供一定的參考。

1 研究的理論基礎(chǔ)

1.1 多式聯(lián)運(yùn)理論

應(yīng)急物流需要綜合考慮運(yùn)輸?shù)臅r(shí)效性和各種運(yùn)輸方式的通行能力，以最短的時(shí)間、最快的速度、最大限度的流量將應(yīng)急物資運(yùn)送至目的地［8］。本文嘗試將多式聯(lián)運(yùn)引入應(yīng)急物資調(diào)運(yùn)徑路的選擇中，建立最短運(yùn)輸時(shí)間最大流的模型，運(yùn)用于自然災(zāi)害等突發(fā)性事件的應(yīng)急物資運(yùn)輸路徑選擇。同時(shí)，考慮突發(fā)性事件引發(fā)的路面變化對(duì)車(chē)輛的延誤，增強(qiáng)了對(duì)時(shí)效性的約束。

1.2 交通網(wǎng)絡(luò)脆弱性

當(dāng)發(fā)生地震、泥石流等自然災(zāi)害事件時(shí)，很可能對(duì)原有路徑造成破壞，必須考慮原有運(yùn)輸路徑被破壞引起的最優(yōu)路徑的變化。因此，本文引入交通網(wǎng)絡(luò)脆弱性理論。1981年，Timmerman［9］提出了脆弱性的概念，即在災(zāi)害事件發(fā)生時(shí)系統(tǒng)受不利因素影響退化的程度。目前國(guó)內(nèi)外關(guān)于交通網(wǎng)絡(luò)脆弱性指標(biāo)的構(gòu)建主要是從網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和居民出行行為2個(gè)方面考慮的，本文擬采用Kalika Suksomboon［11］等提出的期望可達(dá)通行能力脆弱性指標(biāo)(Expected achievable capacity EAC)來(lái)定義運(yùn)輸網(wǎng)絡(luò)的可靠性。

定義應(yīng)急物資路徑k的可達(dá)通行能力為

式中:L(k)表示路徑k所包含的各種運(yùn)輸方式的路段集;ce表示路徑k的通行能力。

假設(shè)qj為第j種災(zāi)害發(fā)生的概率，ce，j為運(yùn)輸網(wǎng)絡(luò)在第j種災(zāi)害發(fā)生情況下路段e的通行能力:

基于以上定義，第j種災(zāi)害發(fā)生的情況下，路徑k的可達(dá)通行能力可表示為:

在多用戶(hù)需求的網(wǎng)絡(luò)中，K為單個(gè)OD對(duì)之間的路徑數(shù)，網(wǎng)絡(luò)在非正常情況 J={1，2，3，…，j}下，網(wǎng)絡(luò)可達(dá)通行能力矩陣可定義為:

假設(shè)用戶(hù)選擇各路徑的概率為HT={H1，H2，H3，…，HK}，各情景發(fā)生的概率為 QT={q1，q2，q3，…，qJ}。在用戶(hù)選擇路徑概率HT和情景概率QT已知的情況下，系統(tǒng)期望可達(dá)通行能力CEA定義為:

2 優(yōu)化模型構(gòu)建

綜上，目標(biāo)函數(shù)包含兩部分，第一部分為運(yùn)輸流量最大，選擇在不同節(jié)點(diǎn)之間運(yùn)輸流量最大的方式為最優(yōu)路徑，并考慮因非正常情況引起路網(wǎng)容量的變化。該部分目標(biāo)函數(shù)為:

第2部分為運(yùn)輸總時(shí)間最省，該部分目標(biāo)函數(shù)為:

運(yùn)輸總時(shí)間包括運(yùn)輸時(shí)間、中轉(zhuǎn)接續(xù)時(shí)間和延遲時(shí)間。目標(biāo)函數(shù)的約束條件為:

其中:式(8)表示在相鄰階段的節(jié)點(diǎn)之間，若存在路徑，則只能選擇1種運(yùn)輸方式.即運(yùn)量不能分割;式(9)表示在每個(gè)節(jié)點(diǎn)只有1次運(yùn)輸方式的改變;式(10)可以確保運(yùn)輸?shù)倪B續(xù)性;式(11)表明貨物必須在規(guī)定的期限內(nèi)運(yùn)到，決策變量取整數(shù)變量0或1。

將上述2個(gè)模型匯總加以變換，則總目標(biāo)函數(shù)為:

該目標(biāo)函數(shù)表示運(yùn)輸單位流量物資花費(fèi)的時(shí)間最短，與原目標(biāo)函數(shù)一致。

3 算法設(shè)計(jì)

蟻群算法是一種典型的基于構(gòu)建式求解過(guò)程的群智能優(yōu)化算法，該算法利用了正反饋原理，在一定程度上可以加快進(jìn)化過(guò)程，是一種本質(zhì)上并行的算法［12］。

3.1 解構(gòu)建圖的表示

根據(jù)本文優(yōu)化的目標(biāo)，對(duì)于結(jié)點(diǎn)i，若存在m種運(yùn)輸方式能夠到達(dá)該結(jié)點(diǎn)，則在解構(gòu)建圖中為結(jié)點(diǎn)i復(fù)制m個(gè)虛擬結(jié)點(diǎn)，分別為Vi1，Vi2，…，Vim。最終的解構(gòu)建圖如圖1所示。需要指出的是，該解構(gòu)建圖是一個(gè)無(wú)環(huán)的網(wǎng)絡(luò)，當(dāng)從結(jié)點(diǎn)i出發(fā)只能以一種運(yùn)輸方式到達(dá)唯一的網(wǎng)絡(luò)結(jié)點(diǎn)j時(shí)，結(jié)點(diǎn)i和j間僅以弧 arc(i，j)相連(如圖1 中 arc(v6，vt2))，當(dāng)從結(jié)點(diǎn)i出發(fā)可以選擇n個(gè)路段及相應(yīng)的m種運(yùn)輸方式時(shí)，分 別 對(duì) 應(yīng) 弧 arc(i，j11)，arc(i，j12)，…，arc(i，jnnm)(如圖 1 中 arc(vs，v11)，arc(vs，v12)，…，arc(vs，v22))。

圖1 解構(gòu)建圖Fig.1 The construction diagram of solution

圖中的實(shí)線表示從上一結(jié)點(diǎn)選擇第m種可能的運(yùn)輸方式到達(dá)當(dāng)前結(jié)點(diǎn);虛線表示虛擬的連接，意味著無(wú)論選擇何種方式到達(dá)該結(jié)點(diǎn)，下一步都可以認(rèn)為實(shí)際上仍是從該結(jié)點(diǎn)出發(fā)。

3.2 解的構(gòu)建

在構(gòu)建解時(shí)，若選擇的下一路段arc(i，j)的流量fij小于當(dāng)前流量fnow，則將當(dāng)前流量fnow更新為fij，同時(shí)，對(duì)于除起點(diǎn)及終點(diǎn)外的所有結(jié)點(diǎn)，若到達(dá)該結(jié)點(diǎn)的路段與從該結(jié)點(diǎn)出發(fā)的路段的運(yùn)輸方式不同時(shí)，需要計(jì)算相應(yīng)的中轉(zhuǎn)接續(xù)時(shí)間。

3.3 信息素的表示、初始化及更新

τij是指當(dāng)螞蟻處于網(wǎng)絡(luò)結(jié)點(diǎn)i時(shí)，選擇從結(jié)點(diǎn)i出發(fā)的第j條路線的期望程度。第j條路線包含兩層含義，分別對(duì)應(yīng)之前描述的2種不同情況。執(zhí)行迭代前，各路徑上的信息素初值均按下式確定:

其中:ni為在結(jié)點(diǎn)i時(shí)可以選擇的路徑(包括到達(dá)不同結(jié)點(diǎn)的路徑以及到達(dá)相同結(jié)點(diǎn)的不同運(yùn)輸方式)的總數(shù)。

每次迭代之后，各路徑上的信息素可按下式更新:

式中:ρ為信息素的揮發(fā)系數(shù)，0＜ρ＜1;n為迭代次數(shù);Δτij為本次迭代的信息素增量。

設(shè)sib為第n次迭代的最優(yōu)解，fib為sib的目標(biāo)函數(shù)值，則Δτij可由下式確定:

3.4 選擇策略

啟發(fā)式信息ηij按下式取值:

其中:θij是1個(gè)與當(dāng)前流量以及各路段流量相關(guān)的函數(shù)。其計(jì)算公式如下:

在初始狀態(tài)，有f0=max{fij}。θij的設(shè)置能夠使螞蟻在構(gòu)建解的過(guò)程中，更傾向于選擇流量較大(大于等于當(dāng)前流量)的路段。

3.5 評(píng)價(jià)函數(shù)的建立

當(dāng)給定解構(gòu)建圖中1條從源點(diǎn)至匯點(diǎn)(起點(diǎn)至終點(diǎn))的路徑后，可以很快的計(jì)算出該路徑的最大流量以及相應(yīng)的走行時(shí)間，因此，本文直接選取問(wèn)題的優(yōu)化目標(biāo)式(12)作為蟻群算法的評(píng)價(jià)函數(shù)來(lái)衡量螞蟻構(gòu)建出的解的質(zhì)量。

3.6 算法終止條件

當(dāng)蟻群算法連續(xù)若干次迭代找到的解不發(fā)生改變時(shí)，算法停止。

4 實(shí)例分析

假設(shè)以蘭州可達(dá)汶川的公路和鐵路兩種運(yùn)輸方式的有效路徑為基本的網(wǎng)絡(luò)圖，蘭州至汶川的可達(dá)路徑、每2個(gè)結(jié)點(diǎn)間的運(yùn)能和運(yùn)輸時(shí)間如圖2所示。該路網(wǎng)圖中的數(shù)據(jù)均為參考?xì)v年統(tǒng)計(jì)年鑒后的平均值。

在圖2所示的路網(wǎng)圖中只選取了運(yùn)量較大且在路網(wǎng)中比較重要的城市作為結(jié)點(diǎn)，在不影響其計(jì)算結(jié)果的情況下對(duì)蘭州至汶川的路網(wǎng)圖進(jìn)行了簡(jiǎn)化。具體求解的流程圖如圖3所示。

圖2 蘭州至汶川路網(wǎng)圖Fig.2 Network diagram from Lanzhou to Wenchuan

圖3 蟻群算法流程圖Fig.3 Flow chart of ant colony algorithm

在自然災(zāi)害或公共衛(wèi)生事件突發(fā)的情況下，很可能會(huì)對(duì)路網(wǎng)的可達(dá)性以及通行能力造成影響。

4.1 對(duì)路網(wǎng)可達(dá)性未造成影響時(shí)的最優(yōu)路徑

通過(guò)多次搜索和疊代，圖2中蘭州至汶川的最優(yōu)路徑為:

目標(biāo)函數(shù)值為0.1418。

4.2 對(duì)路網(wǎng)可達(dá)性造成影響時(shí)的最優(yōu)路徑

假設(shè)上述最優(yōu)路徑中廣元至綿陽(yáng)段的公路運(yùn)輸無(wú)法通行，則圖2中蘭州至汶川的最優(yōu)路徑為:

目標(biāo)函數(shù)值為0.2222。

5 結(jié)論

為了盡快地將盡可能多的應(yīng)急物資運(yùn)往災(zāi)區(qū)，避免將“天災(zāi)”變成“人禍”，需要?jiǎng)訂T全社會(huì)的力量，各種運(yùn)輸方式必須全力以赴，共同完成應(yīng)急物資的運(yùn)送。本文將多式聯(lián)運(yùn)理論引入對(duì)應(yīng)急物資運(yùn)輸路徑的研究，可以清楚地發(fā)現(xiàn)路網(wǎng)中結(jié)點(diǎn)之間的運(yùn)輸時(shí)間、通過(guò)能力以及路網(wǎng)的可靠性，都對(duì)應(yīng)急物資的運(yùn)輸產(chǎn)生重要的影響。由于航空運(yùn)量相較公路和鐵路比較小，在應(yīng)急物資的大批量長(zhǎng)途調(diào)運(yùn)中并不能擔(dān)當(dāng)重要作用，因此，本模型的算例結(jié)果種并沒(méi)有包含蘭州可達(dá)汶川的航空運(yùn)輸。這并不是說(shuō)航空運(yùn)輸不重要，在涉及挽救生命的特殊物資時(shí)，航空運(yùn)輸?shù)目旖菪允瞧渌\(yùn)輸方式無(wú)法比擬的。

［1］劉志學(xué).現(xiàn)代物流［M］.北京:中國(guó)物資出版社，2002.LIU Zhi－xue.The modern logistics［M］.Beijing:China Materials Press，2002.

［2］Chen J，Huang J，Chen S Q.A simple linear time approximation algorithm for multiprocessor job scheduling on four processors［C］//Shenged H T.Algorithms and computation，LNCS 1969.Berlin:SPringer，2000:60 －71.

［3］Sumalee A.Optimal implementation－path of road pricingschemes with time－dependent model［C］//The sixth annual conference of the international emergency management society.Deltf，Netherlands，2008:8 －11.

［4］Chootinant P，Wong S C，Anthony Chen.A reliabilitybased network design problem［J］.Journal of Advanced Transportation，2005，30(30):247 －270.

［5］歐忠文，王會(huì)云，姜大立.應(yīng)急物流［J］.重慶大學(xué)學(xué)報(bào)，2004(3):164－167.OU Zhong－wen，WANG Hui－yun，JIANG Da－li.Emergency logistics［J］.Journal of Chongqing University，2004(3):164－167.

［6］張曉波，謝紅薇.并行遺傳算法求解應(yīng)急系統(tǒng)最短路徑的研究［D］.太原:太原理工大學(xué)，2005.ZHANG Xiao－bo，XIE Hong－wei.Research on shortest path in emergency system using parallel genetic algorithm［D］.Taiyuan:Taiyuan University of Technology，2005.

［7］盧 茜，施先亮.地震災(zāi)害應(yīng)急物流系統(tǒng)中公路運(yùn)輸路徑選擇的研究［D］.北京:北京交通大學(xué)，2009.LU Qian，SHI Xian－liang.Research of route choosing in road transportation of logistics emergency system for earthquake disaster［D］.Beijing:Beijing Jiaotong University，2009.

［8］段滿(mǎn)珍.國(guó)際集裝箱運(yùn)輸與多式聯(lián)運(yùn)［M］.北京:清華大學(xué)出版社，2011.DUAN Man－zhen.The international container transportation and multimodal transportation［M］.Beijing:Tsinghua University Press，2011.

［9］Timmerman P.Vulnerability，resilience and the collapse of society［M］.Institute for Environmental Studies，University of Toronto in Toronto，1981.

［10］Berdica K.Vulnerability in the road transportation system－ basic concepts and theoretical framework［C］//TRITA－ IP AR 99－73，Institutionen f?r infrastruktur och samh?llsplanering，KTH，Stockholm，1999.

［11］Piwat P S，Suksomboon K，Aswakul C.Vulnerability analysis in multicommodity stochastic networks by game theory［C］//Proceedings of ECTI－ CON，357－360.IEEE，2008.

［12］段海濱.蟻群算法原理及其應(yīng)用［M］.北京:科學(xué)出版社，2005.DUAN Hai－bing.Theory of ant colony algorithm and implement［M］.Beijing:Science Press，2005.