災(zāi)后交通網(wǎng)絡(luò)修復(fù)與救援協(xié)同優(yōu)化方法

秦進(jìn)，楊康，徐玖龍，陳學(xué)偉

(中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙410075)

當(dāng)今世界自然災(zāi)害頻發(fā)，其破壞性威脅人類的生命安全，嚴(yán)重影響社會(huì)經(jīng)濟(jì)的發(fā)展，而緊急開(kāi)展高效有序的應(yīng)急救援行動(dòng)，能夠最大程度上減少人員傷亡和財(cái)產(chǎn)損失。由于應(yīng)急救援行動(dòng)通常具有時(shí)效性、突發(fā)性等特點(diǎn)，需要在短時(shí)間內(nèi)對(duì)運(yùn)送應(yīng)急物資的救援隊(duì)伍科學(xué)規(guī)劃行駛路線。同時(shí)，必須兼顧路網(wǎng)節(jié)點(diǎn)損壞程度，修復(fù)順序及受災(zāi)地區(qū)的物資需求量。如果未能在需求緩沖期間內(nèi)將應(yīng)急物資配送至指定地點(diǎn)，人們則會(huì)因?yàn)槿狈ξ镔Y而產(chǎn)生焦慮、受凍、受餓等痛苦。因此，為了有效減輕救援期間內(nèi)人們的痛苦程度，盡快滿足受災(zāi)地區(qū)的物資需求，就必須對(duì)道路維修和物資運(yùn)輸路線結(jié)合考慮。近些年來(lái)，已經(jīng)有許多國(guó)內(nèi)外學(xué)者對(duì)災(zāi)后交通網(wǎng)絡(luò)修復(fù)和救援協(xié)同優(yōu)化問(wèn)題進(jìn)行了深入的研究和討論。高學(xué)英[1]為應(yīng)急救援資源布局及調(diào)度提供重要可行方法。程碧榮等[2]通過(guò)考慮服務(wù)時(shí)間窗和車(chē)輛裝載能力等，保證救援關(guān)鍵期內(nèi)應(yīng)急物資供應(yīng)不足下車(chē)輛路徑合理規(guī)劃。MAYA等[3]采用DP算法和GRASP元啟發(fā)式算法解決災(zāi)后維修人員的調(diào)度和路徑問(wèn)題。?ELIK[4]對(duì)有關(guān)網(wǎng)絡(luò)重建和修復(fù)的文獻(xiàn)進(jìn)行全面的概述。WANG等[5]構(gòu)建用于公路網(wǎng)恢復(fù)的雙層編程模型，采用模擬退火算法與拉格朗日梯度投影法相結(jié)合進(jìn)行求解。但在上述研究中，維修隊(duì)伍與救援隊(duì)伍的路徑規(guī)劃是分離的，導(dǎo)致維修隊(duì)伍在不必經(jīng)過(guò)或不緊急受損路段用很長(zhǎng)的時(shí)間進(jìn)行修復(fù)，使救援隊(duì)伍在關(guān)鍵受損道路進(jìn)行等候。因此，需要從系統(tǒng)的角度平衡兩者之間的關(guān)系，減少等待時(shí)間。SHIN等[6]以時(shí)間長(zhǎng)度最小化為決策目標(biāo)，構(gòu)建時(shí)空網(wǎng)絡(luò)模型，確保在短時(shí)間內(nèi)對(duì)緊急維修和救援的分配路線和時(shí)間表合理安排。ILOGLU等[7]提出對(duì)P中值問(wèn)題的擴(kuò)展，通過(guò)協(xié)調(diào)網(wǎng)絡(luò)恢復(fù)人員和應(yīng)急救援人員，使得緊急響應(yīng)者在時(shí)間范圍內(nèi)與服務(wù)請(qǐng)求之間的累積加權(quán)距離最小化。SHIN等[6]將災(zāi)后救援隊(duì)伍和維修車(chē)輛進(jìn)行統(tǒng)一研究，建立綜合調(diào)度模型。王晶等[8]以道路中斷和可靠性下降來(lái)闡述災(zāi)后交通網(wǎng)絡(luò)對(duì)物流配送的影響?，F(xiàn)有的災(zāi)后應(yīng)急救援路徑選擇文獻(xiàn)的決策目標(biāo)以最小化救援時(shí)間為主，而實(shí)際上，還需要更多地關(guān)注受難者在等待救濟(jì)過(guò)程中承受的痛苦。HOLGUíNVERAS等[9]將“剝奪成本”定義為人類因無(wú)法獲得物資或者服務(wù)導(dǎo)致其痛苦所引起的經(jīng)濟(jì)價(jià)值，認(rèn)為人道主義物流模型需要將福利經(jīng)濟(jì)原則考慮其中。ZHU等[10]以“相對(duì)剝奪成本”作為決策目標(biāo)，更強(qiáng)調(diào)受難者承受的痛苦和救援公平性。SHAO等[11]對(duì)有關(guān)剝奪成本及其對(duì)關(guān)鍵問(wèn)題討論的最新文獻(xiàn)進(jìn)行回顧，分析當(dāng)前剝奪成本的最新研究進(jìn)展與研究成果。

1 問(wèn)題分析及變量定義

自然災(zāi)害發(fā)生后，必須迅速開(kāi)展應(yīng)急救援預(yù)案，在確定受災(zāi)區(qū)域范圍和交通網(wǎng)絡(luò)受損狀況以及物資需求量后，根據(jù)現(xiàn)有維修隊(duì)伍和救援隊(duì)伍的數(shù)量，以最小化受難群眾累計(jì)產(chǎn)生的剝奪成本為目標(biāo)，選擇合理的路徑優(yōu)先修復(fù)受損節(jié)點(diǎn)，以保證救援隊(duì)伍及時(shí)將應(yīng)急物資輸送至需求節(jié)點(diǎn)。由于途經(jīng)的受損節(jié)點(diǎn)處在中斷或者正在維修的狀態(tài)，救援隊(duì)伍無(wú)法通過(guò)，容易導(dǎo)致物資無(wú)法在短時(shí)間內(nèi)運(yùn)輸至指定的需求節(jié)點(diǎn)，錯(cuò)過(guò)需求緩沖期，甚至有可能因?yàn)榈缆沸迯?fù)計(jì)劃和物資運(yùn)輸路徑的不協(xié)調(diào)，造成救援隊(duì)伍在關(guān)鍵受損節(jié)點(diǎn)長(zhǎng)時(shí)間等待，嚴(yán)重影響救援活動(dòng)的開(kāi)展。同時(shí)，由于受災(zāi)地點(diǎn)和受損節(jié)點(diǎn)較多且相對(duì)分散，救援隊(duì)伍無(wú)法完全滿足所有受災(zāi)地點(diǎn)在各自的需求緩沖期內(nèi)將應(yīng)急物資及時(shí)運(yùn)送。因此，如何對(duì)有限數(shù)量的救援隊(duì)伍和道路維修隊(duì)伍進(jìn)行協(xié)同調(diào)度，確定受損道路修復(fù)次序和應(yīng)急物資運(yùn)輸路線，是災(zāi)后應(yīng)急救援中必須首先解決的重大問(wèn)題。

為了方便建立模型，定義變量如下：

V為節(jié)點(diǎn)集，Vd為需求節(jié)點(diǎn)集，Vr為受損節(jié)點(diǎn)集，E為路段集(i,j)，?i,j∈V，Er為受損節(jié)點(diǎn)對(duì)集合，W為救援隊(duì)伍數(shù)量集合，?w∈W，Z為維修隊(duì)伍數(shù)量集合，?z∈Z，so為初始起點(diǎn)，sd為虛擬終點(diǎn)，tij表示(i,j)的出行時(shí)間，?i,j∈V，dij表示(i,j)的路程，?i,j∈V，v表示隊(duì)伍的行進(jìn)速度，θ表示節(jié)點(diǎn)的損壞程度，θ=1,2,3，xiθ表示損壞程度為θ的情況下，節(jié)點(diǎn)i的修復(fù)時(shí)間，?i∈Vr，x,i表示節(jié)點(diǎn)i的救濟(jì)時(shí)間，?i∈Vd，γi表示節(jié)點(diǎn)i的需求緩沖期，?i∈Vd，qi表示節(jié)點(diǎn)i的需求量，?i∈Vd，tarzi表示維修隊(duì)伍z到達(dá)i的時(shí)間，?i∈Vr，trzi表示維修隊(duì)伍z修復(fù)i的時(shí)間，?i∈Vr，tarwi表示救援隊(duì)伍w到達(dá)i的時(shí)間，?i∈Vd，trwi表示救援隊(duì)伍w完成i的供給時(shí)間，?i∈Vd，f2i表示i可訪問(wèn)的時(shí)間，?i∈Vd，f′w表示救援隊(duì)伍w完成救濟(jì)服務(wù)的時(shí)間，?i∈Vd。Ω+為救援隊(duì)伍w到達(dá)之前產(chǎn)生的剝奪成本，Ω-表示救援隊(duì)伍w到達(dá)之后產(chǎn)生的剝奪成本，Γiw表示救援隊(duì)伍w完成i的供應(yīng)后，在i累計(jì)產(chǎn)生的剝奪成本，?i∈Vd，C表示所有需求節(jié)點(diǎn)的剝奪總成本。

另外，定義決策變量如下：

另外，結(jié)合實(shí)際情況，對(duì)問(wèn)題做如下合理假設(shè)：

1)救援隊(duì)伍在單次出行期間具有足夠的供應(yīng)能力。2)節(jié)點(diǎn)的損壞程度，修復(fù)時(shí)間以及路段間的距離是確定性的。3)節(jié)點(diǎn)之間若無(wú)連通路徑，隊(duì)伍均無(wú)法通過(guò)。4)隊(duì)伍從同一起點(diǎn)出發(fā)，且行進(jìn)速度相同。5)物資的需求量和需求緩沖期是確定性的。

2 模型構(gòu)建

根據(jù)以上變量定義和問(wèn)題描述，可以構(gòu)建優(yōu)化模型如下：

式(1)為目標(biāo)函數(shù)，即總的剝奪成本最小化，其中的剝奪成本具體由式(2)～(4)計(jì)算。式(2)表示若從救援隊(duì)伍w到達(dá)i的時(shí)間tarwj大于需求緩沖期γi時(shí)，Γiw為i累計(jì)產(chǎn)生的剝奪成本，反之Γiw=0。式(3)表示剝奪成本Ω+在等待救援隊(duì)伍w到達(dá)之前呈現(xiàn)指數(shù)形式增長(zhǎng)。式(4)表示剝奪成本Ω-在救濟(jì)期間x'i，群眾負(fù)面心理影響不會(huì)立即消失，而是以線性形式減少，直到完成救濟(jì)后才完全消除。若tarwi-γi≤0，Γiw為0，即不產(chǎn)生剝奪時(shí)間成本。式(5)和式(6)表示確保每個(gè)受損節(jié)點(diǎn)i僅由維修隊(duì)伍z修復(fù)。式(7)表示維修隊(duì)伍z進(jìn)入節(jié)點(diǎn)i完成修復(fù)任務(wù)后應(yīng)離開(kāi)該節(jié)點(diǎn)。式(8)是維修隊(duì)伍z從已修復(fù)的i出發(fā)時(shí)間與從i到j(luò)的旅行時(shí)間之和，即達(dá)到節(jié)點(diǎn)j的時(shí)間tarzj。式(9)是維修隊(duì)伍z∈Z完成節(jié)點(diǎn)j的修復(fù)時(shí)間。式(10)表示確保是在完全修復(fù)與需求節(jié)點(diǎn)相鄰的節(jié)點(diǎn)i之后。式(11)和式(12)表示確保救援隊(duì)伍w從i到j(luò)都僅服務(wù)一次。式(13)表示救援隊(duì)伍w完成i的救援任務(wù)后應(yīng)離開(kāi)該節(jié)點(diǎn)。式(14)表示救援隊(duì)伍w完成i供應(yīng)后，到達(dá)j的時(shí)間tarwj。式(15)表示救援隊(duì)伍w在j完成供應(yīng)的時(shí)間tsjw。式(16)表示保證救援隊(duì)伍w到j(luò)的到達(dá)時(shí)間tarwj不小于j的可訪問(wèn)時(shí)間f2j與相鄰受損節(jié)點(diǎn)b到需求節(jié)點(diǎn)j之間旅行時(shí)間的總和。因此，救援隊(duì)伍必須在最近的受損節(jié)點(diǎn)被修復(fù)之后才能訪問(wèn)需求節(jié)點(diǎn)。式(17)表示滿足約束條件。

3 求解算法

本文提出了適用于該模型的二階段蟻群算法[12]。第1階段是對(duì)帶時(shí)間窗的維修隊(duì)伍進(jìn)行路徑規(guī)劃，獲得受損節(jié)點(diǎn)的修復(fù)順序和修復(fù)時(shí)間。第2階段根據(jù)修復(fù)方案對(duì)帶時(shí)間窗的救援隊(duì)伍進(jìn)行路徑規(guī)劃，獲得需求點(diǎn)的訪問(wèn)順序和救濟(jì)時(shí)間。每一種維修隊(duì)伍的修復(fù)計(jì)劃，救援隊(duì)伍都能找到相對(duì)應(yīng)的路徑選擇方案，根據(jù)救援方案的局部可行解判斷其優(yōu)劣性。重復(fù)上述步驟，更新和改進(jìn)可行的解決方案以獲得全局最優(yōu)解。在該算法中，定義維修螞蟻和救援螞蟻。2種螞蟻分別在各自的子網(wǎng)絡(luò)圖尋找可行的路徑，可以有效地減少計(jì)算時(shí)間。本文采用Dijkstra算法確定螞蟻行進(jìn)路徑的節(jié)點(diǎn)對(duì)是否存在于子網(wǎng)絡(luò)圖中，以便進(jìn)行添加可行性檢查。

4)救援螞蟻y完成對(duì)所有需求節(jié)點(diǎn)的訪問(wèn)后，記錄救援方案Uny，計(jì)算目標(biāo)函數(shù)值Cy。若y=1，則令C0=Cy為初始目標(biāo)函數(shù)值，令為初始救援方案。

5)令y=y+1，若y

Step 4令k=k+1，若k≤mr，重復(fù)步驟Step 2～Step 3；否則，轉(zhuǎn)至Step 5。

Step 5信息素更新。采用帶精英和排序混合策略更新信息素Δτr ij和Δτn ij。2種螞蟻均根據(jù)目標(biāo)函數(shù)值按從小到大依次排序，對(duì)排名λ位次的螞蟻進(jìn)行加權(quán)，并只考慮σ只精英螞蟻數(shù)量。在排列中，前σ-1只螞蟻中所經(jīng)過(guò)的邊獲得信息素的量與該螞蟻的排名位次成正比。此外，還采用精英策略，即到目前為止找出最優(yōu)方案的螞蟻所經(jīng)過(guò)的邊也將獲得額外的信息素。在這樣混合策略的設(shè)置中，信息素τr ij和τn ij根據(jù)下式進(jìn)行更新：

表示σ-1只螞蟻在節(jié)點(diǎn)對(duì)(i,j)之間根據(jù)排序?qū)π畔⑺氐母?；如果第λ只最好維修螞蟻經(jīng)過(guò)(i,j)，則Δτrλ ij=(σ-λ)Q/Cλ0，否則Δτrλ ij=0；同理可得Δτnλ ij=(σ-λ)Q/Cλ0，否則Δτnλ ij=0；如果(i,j)是找出最優(yōu)解的邊，Δτr*ij=σQ/C*0，否則Δτr*ij=0；同理可得Δτn*ij=σQ/C*0，否則Δτn*ij=0。其中：λ為螞蟻排列的順序號(hào)；Δτrλ ij與Δτnλ ij表示第λ只螞蟻在路徑(i,j)上信息素的增加量；Cλ0是第λ只螞蟻的目標(biāo)函數(shù)值；Δτr*ij和Δτn*ij是由精英螞蟻在路徑(i,j)上信息素的增加量；σ為精英螞蟻的數(shù)量；C*0是當(dāng)前最優(yōu)值。

Step 6收斂性判斷。若n

4 算例分析

4.1 算例簡(jiǎn)述

假設(shè)某地區(qū)發(fā)生災(zāi)害，救援中心共有1個(gè)供應(yīng)點(diǎn)，其位置、維修隊(duì)伍數(shù)量、救援隊(duì)伍數(shù)量已知，如表1所示。有25個(gè)節(jié)點(diǎn)，包括15個(gè)需求節(jié)點(diǎn)，10個(gè)受損節(jié)點(diǎn)，其坐標(biāo)及相關(guān)參數(shù)已知，如表2所示。受災(zāi)地區(qū)節(jié)點(diǎn)連接情況如圖1所示。

圖1 受災(zāi)地區(qū)需求節(jié)點(diǎn)與受損節(jié)點(diǎn)分布圖Fig.1 Distribution of demand nodes and

表1 供應(yīng)點(diǎn)位置坐標(biāo)和隊(duì)伍的數(shù)量Table 1 Supply point location coordinates and the number of teams

表2 節(jié)點(diǎn)坐標(biāo)及相關(guān)參數(shù)Table 2 Node coordinates and related parameters

需求點(diǎn)間旅行時(shí)間如表3所示，受損點(diǎn)間旅行時(shí)間如表4所示。

表3 供應(yīng)點(diǎn)與各個(gè)需求節(jié)點(diǎn)之間的旅行時(shí)間Table 3 Travel time/hour between supply point and each demand node h

表4 供應(yīng)點(diǎn)與各個(gè)受損節(jié)點(diǎn)之間的旅行時(shí)間Table 4 Travel time/hour between the supply point and each damaged node h

4.2 算例結(jié)果及分析

本算例中，取救援隊(duì)伍和維修隊(duì)伍的行進(jìn)速度v為30 km/h，常系數(shù)α和β分別為30和-1。在二階段蟻群算法的求解過(guò)程中，目標(biāo)函數(shù)的收斂情況如圖2所示。隨著迭代次數(shù)的增長(zhǎng)，目標(biāo)函數(shù)值和平均值均呈持續(xù)下降的趨勢(shì)，在第5代時(shí)目標(biāo)函數(shù)值收斂，C=287.8。此時(shí)3組救援隊(duì)伍完成應(yīng)急物資配送的時(shí)間分別為25.3，19.1和27.4 h。具體的路徑方案如表5所示。

圖2 目標(biāo)函數(shù)值vs.迭代次數(shù)Fig.2 Objective function value and number of iterations

由表5可知，維修隊(duì)伍的訪問(wèn)節(jié)點(diǎn)數(shù)量分別為4，3和3，完成修復(fù)時(shí)間分別為15，12.3和10.9 h，平均時(shí)間為12.7 h，完成修復(fù)時(shí)間相差較小。節(jié)點(diǎn)R21最后維修是由于N2和N10在救援過(guò)程中安排較后，因此節(jié)點(diǎn)R21同樣被安排在較后的訪問(wèn)順序中，維修隊(duì)伍優(yōu)先訪問(wèn)其他受損節(jié)點(diǎn)，如圖3所示。同時(shí)，共有3組救援隊(duì)伍均從初始點(diǎn)出發(fā)，訪問(wèn)節(jié)點(diǎn)數(shù)量分別為4，4和7，完成救援時(shí)間分別為25.3，19.3和27.4 h。節(jié)點(diǎn)N8分配給1號(hào)隊(duì)伍并且最后一個(gè)訪問(wèn)，是由于該節(jié)點(diǎn)所需物資為2 t，與其他地區(qū)相比，需求量較少，且有較長(zhǎng)的需求緩沖期，因此3號(hào)隊(duì)伍可優(yōu)先考慮對(duì)物資更加緊缺的需求節(jié)點(diǎn)，運(yùn)輸路線如圖4所示。

圖3 維修隊(duì)伍路徑方案Fig.3 Maintenance team path plan

圖4 救援隊(duì)伍路徑方案Fig.4 Path plan of rescue team

表5 路徑方案及時(shí)間窗Table 5 Route plan and time window

如圖5所示，在維修隊(duì)伍規(guī)模為3的情況下，救援隊(duì)伍規(guī)模的擴(kuò)大能夠有效減少剝奪成本，表明救援隊(duì)伍數(shù)量的增多加快物資配送的效率，以減少群眾的負(fù)面心理影響。剝奪成本最終趨于穩(wěn)定，是由于維修隊(duì)伍數(shù)量有限，關(guān)鍵受損路段未能及時(shí)修復(fù)，部分救援隊(duì)伍受阻。平均維修用時(shí)先降后升，最后趨于穩(wěn)定，表明當(dāng)救援隊(duì)伍的數(shù)量少于或等于維修隊(duì)伍的數(shù)量時(shí)，部分維修隊(duì)伍為優(yōu)先救援的需求節(jié)點(diǎn)所途經(jīng)的受損節(jié)點(diǎn)進(jìn)行修復(fù)，以減少救援隊(duì)伍中途等待時(shí)間。由于救援隊(duì)伍數(shù)量有限，規(guī)劃路徑下排序較后的需求節(jié)點(diǎn)需要等待，其余維修隊(duì)伍在為這些需求節(jié)點(diǎn)所途經(jīng)路線中受損節(jié)點(diǎn)維修的時(shí)間緊迫性小，但是隨著救援隊(duì)伍數(shù)量的增加，促使維修規(guī)劃路徑更合理化，維修計(jì)劃用時(shí)縮短；當(dāng)救援隊(duì)伍的數(shù)量超過(guò)維修隊(duì)伍的數(shù)量時(shí)，平均維修用時(shí)增大且維持不變，表明此時(shí)維修隊(duì)伍的修復(fù)計(jì)劃趨于合理化。

圖5 不同救援隊(duì)伍數(shù)量下目標(biāo)函數(shù)及隊(duì)伍平均用時(shí)情況Fig.5 Objective function and average team time under

如圖6所示，在救援隊(duì)伍數(shù)量為3的情況下，維修隊(duì)伍數(shù)量的增加，促使多個(gè)受損節(jié)點(diǎn)同時(shí)進(jìn)行維修，縮短了救援隊(duì)伍等待的時(shí)間，使得剝奪成本和平均維修用時(shí)都在減少。平均救援用時(shí)有所上升，是由于每個(gè)需求節(jié)點(diǎn)存在需求緩沖期階段，且需求量不一樣，救援隊(duì)伍在規(guī)劃可連通路徑時(shí)，更優(yōu)先考慮需求節(jié)點(diǎn)的急需程度，而不是以救援時(shí)長(zhǎng)最小為目的，平均救援用時(shí)趨于穩(wěn)定表明救援路徑方案已達(dá)到最優(yōu)化；而維修隊(duì)伍達(dá)到一定數(shù)量時(shí)，有部分停留在初始節(jié)點(diǎn)，處于待命狀態(tài)，未參與維修工作，表明此時(shí)對(duì)該受災(zāi)地區(qū)中受損節(jié)點(diǎn)的修復(fù)能力已經(jīng)達(dá)到飽和狀態(tài)。

圖6 不同維修隊(duì)伍數(shù)量下目標(biāo)函數(shù)及平均用時(shí)情況Fig.6 Objective function and average time consumption under

5 結(jié)論

1)結(jié)合災(zāi)害發(fā)生后維修隊(duì)伍和救援隊(duì)伍存在協(xié)調(diào)欠缺而導(dǎo)致物資不能快速輸送的特點(diǎn)，在假設(shè)受損節(jié)點(diǎn)的損壞程度及修復(fù)時(shí)間均為已知的前提下，同時(shí)考慮需求節(jié)點(diǎn)的物資需求量、救濟(jì)時(shí)間以及需求緩沖期，以最小化累計(jì)產(chǎn)生的剝奪成本作為決策目標(biāo)，構(gòu)建了混合整數(shù)非線性規(guī)劃模型。

2)設(shè)計(jì)出適用于該模型的二階段蟻群算法，采用帶精英和排序混合策略對(duì)信息素的更新進(jìn)行改進(jìn)，在提高解質(zhì)量的同時(shí)，也加快了計(jì)算效率。最后，通過(guò)算例結(jié)果表明，維修隊(duì)伍能夠根據(jù)救援隊(duì)伍的運(yùn)輸路徑，優(yōu)先對(duì)途經(jīng)的關(guān)鍵受損路段進(jìn)行修復(fù)，合理規(guī)劃受損節(jié)點(diǎn)的修復(fù)次序，保證路網(wǎng)的暢通，減少救援隊(duì)伍中途的等待時(shí)間。該方法具備合理性和可行性，能夠?yàn)榻窈髴?yīng)急物流運(yùn)輸?shù)南嚓P(guān)決策提供有效的科學(xué)依據(jù)。