基于蟻群算法的應急物資運輸路徑優(yōu)化*

楊菊花，朱昌鋒，田志強

(蘭州交通大學交通運輸學院，甘肅 蘭州 730070)

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

1 研究的理論基礎

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

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

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

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

定義應急物資路徑k的可達通行能力為

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

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

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

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

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

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

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

第2部分為運輸總時間最省，該部分目標函數(shù)為:

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

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

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

該目標函數(shù)表示運輸單位流量物資花費的時間最短，與原目標函數(shù)一致。

3 算法設計

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

3.1 解構建圖的表示

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

圖1 解構建圖Fig.1 The construction diagram of solution

圖中的實線表示從上一結點選擇第m種可能的運輸方式到達當前結點;虛線表示虛擬的連接，意味著無論選擇何種方式到達該結點，下一步都可以認為實際上仍是從該結點出發(fā)。

3.2 解的構建

在構建解時，若選擇的下一路段arc(i，j)的流量fij小于當前流量fnow，則將當前流量fnow更新為fij，同時，對于除起點及終點外的所有結點，若到達該結點的路段與從該結點出發(fā)的路段的運輸方式不同時，需要計算相應的中轉接續(xù)時間。

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

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

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

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

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

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

3.4 選擇策略

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

其中:θij是1個與當前流量以及各路段流量相關的函數(shù)。其計算公式如下:

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

3.5 評價函數(shù)的建立

當給定解構建圖中1條從源點至匯點(起點至終點)的路徑后，可以很快的計算出該路徑的最大流量以及相應的走行時間，因此，本文直接選取問題的優(yōu)化目標式(12)作為蟻群算法的評價函數(shù)來衡量螞蟻構建出的解的質量。

3.6 算法終止條件

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

4 實例分析

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

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

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

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

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

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

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

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

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

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

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

5 結論

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

［1］劉志學.現(xiàn)代物流［M］.北京:中國物資出版社，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］歐忠文，王會云，姜大立.應急物流［J］.重慶大學學報，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］張曉波，謝紅薇.并行遺傳算法求解應急系統(tǒng)最短路徑的研究［D］.太原:太原理工大學，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］盧 茜，施先亮.地震災害應急物流系統(tǒng)中公路運輸路徑選擇的研究［D］.北京:北京交通大學，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］段滿珍.國際集裝箱運輸與多式聯(lián)運［M］.北京:清華大學出版社，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］段海濱.蟻群算法原理及其應用［M］.北京:科學出版社，2005.DUAN Hai－bing.Theory of ant colony algorithm and implement［M］.Beijing:Science Press，2005.