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

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

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

1 問題分析及變量定義

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

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

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

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

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

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

2 模型構(gòu)建

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

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

3 求解算法

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

4)救援螞蟻y完成對所有需求節(jié)點的訪問后，記錄救援方案Uny，計算目標(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ù)值按從小到大依次排序，對排名λ位次的螞蟻進(jìn)行加權(quán)，并只考慮σ只精英螞蟻數(shù)量。在排列中，前σ-1只螞蟻中所經(jīng)過的邊獲得信息素的量與該螞蟻的排名位次成正比。此外，還采用精英策略，即到目前為止找出最優(yōu)方案的螞蟻所經(jīng)過的邊也將獲得額外的信息素。在這樣混合策略的設(shè)置中，信息素τr ij和τn ij根據(jù)下式進(jìn)行更新：

表示σ-1只螞蟻在節(jié)點對(i,j)之間根據(jù)排序?qū)π畔⑺氐母拢蝗绻讦酥蛔詈镁S修螞蟻經(jīng)過(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。其中：λ為螞蟻排列的順序號；Δτ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 算例簡述

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

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

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

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

需求點間旅行時間如表3所示，受損點間旅行時間如表4所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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