突發事件下應急救援物資車輛路徑選擇方法

陳紅，文若蘭，周和平

（1.長沙理工大學 交通運輸工程學院，湖南 長沙 410114；2.衡陽技師學院，湖南 衡陽 421101；3.湖南高速鐵路職業技術學院，湖南 衡陽 421002）

近年來，應急救援系統在許多突發事件中發揮了不可替代的作用。在突發事件中，面對緊迫的受災點物資需求和不確定的路網行程時間，如何科學地調度應急救援物資、選擇車輛運輸路線是應急救援的關鍵。許多學者深入研究了應急救援物資車輛調度問題。ALINAGHIAN等［1］考慮動態變化的受災點需求、位置等要素，構建了應急救援物資車輛的路徑選擇模型。MARINAKIS等［2］結合了3種自適應策略改進粒子群優化算法，得到優選的配送路徑。盛虎宜等［3］綜合考慮災后路網的損毀程度、隨機行駛時間等因素，設計了兩階段啟發式算法來求解以物資需求點損失最大化和配送時間最小化為目標的應急物資分配-路徑選擇問題。趙星等［4］考慮受災點緊急級別、受災后行程時間變化等因素，以交通量可靠性和路阻函數的行程時間為目標函數來建模，并采用禁忌搜索和非支配排序算法對模型進行了求解。宋英華等［5］結合受災點人群的年齡分布、傷情嚴重狀況等信息來劃分受災點的受災嚴重級別，考慮同一級別的受災點物資滿意度，建立了物資調度模型，并采用經典遺傳算法對其進行求解。韓孟宜等［6］設計了結合節約算法、大規模鄰域搜索的遺傳算法，該算法的速度和結果均優于傳統遺傳算法的。盧建鋒等［7］以運輸時間與總環境風險、缺貨損失費用最小化為目標函數，構建了多目標的多種類物資調度模型，并設計了NSGAⅡ算法對其進行求解。在求解過程中，先采用錦標賽法進行個體選擇，再結合多點交叉算子，加快算法搜索速度，最后采用逼近理想解排序法得到最優解。張文暉［8］考慮多種類應急物資需求，采用拉格朗日松弛算法分解問題，提高了解的收斂速度。石崇玉［9］考慮了不確定的受災點物資需求，構建多目標車輛調度魯棒優化模型，確保車輛及時地將應急食品物資配送到各受災點。許德剛等［10］以行駛時間最小化、需求點的滿意度最大化為目標，建立應急調度模型，并提出優化煙花算法對其進行求解，通過改變變異策略、引入禁忌表，提升了算法尋找局部最優解的能力。

這些研究主要集中在應急救援車輛路徑問題的模型構建以及求解算法優化兩方面。對于應急救援車輛的路徑問題，很多學者考慮了受災點物資需求的不確定性或優先級，對其進行研究［11］，還有部分學者考慮到了路段行程時間的不確定性，對其進行研究［12-13］。目前，同時考慮以上兩個條件的研究鮮見。因此，本研究基于交通路網區間阻抗，在受災點需求優先級約束、車輛行駛時間約束等約束條件下，以魯棒成本最小化為目標，構建應急救援車輛物資配送路徑優化模型，并設計Benders分解算法來求解該模型，以便快速、合理地進行多應急物資集散中心的救援與協同調度，以期為應急管理部門的決策制定提供借鑒。

1 問題描述與符號說明

車輛在行駛中會受到交通擁堵、惡劣天氣、交通管制等不確定性因素的影響，車輛的行程時間也不會是一個固定值。因此，本研究采用區間來度量交通路網行程時間，該區間內最短與最長行程時間分別對應在道路交通的最好與最差狀態下，車輛在該路段上所花費的時間。車輛在該路段上的行程時間可以是處于最長、最短行程時間之間的任意值。本研究以這種方式來表征在實際交通場景中車輛行駛時間的不確定性。

假設在突發事件發生時，交通網絡圖為G=(N，D)，其中，D為路段集，(i，j)∈D，路段(i，j)的行駛時間處于區間阻抗分別是車輛在路段(i，j)最好情況與最差情況下的行程時間，且為節點集，任意節點i∈N；S為應急物資集散中心點集，?s∈S；M為受災點集，?m∈M；K為應急救援車輛集，?k∈K；E為配送路徑方案集，?e∈E；pi為受災點i的物資需求量；Tmax為車輛的最長行駛時間。

本研究討論多個應急物資集散中心車輛的協同調度優化問題，依據災區實際情境，科學地評估各受災點的物資需求量，并優先考慮配送需求量大的受災點。應急救援車輛k從應急物資集散中心s出發，依次給受災點配送物資，車輛的配送路徑為e。在突發事件發生時，需要快速地制定可靠的應急資源調度方案來滿足所有受災點i的物資需求。

2 模型建立

考慮交通路網行程時間的不確定性，建立區間阻抗下應急物資配送路徑優化模型，以輔助應急管理部門進行決策，得到最優車輛調度方案。求解此模型的思路為：先尋找出所有符合約束條件的車輛調度方案；再基于該調度方案的情景找到最優調度方案；最后，獲得最優調度方案的最大后悔值（魯棒成本）。該模型旨在找到所有車輛調度方案的最小最大后悔值（最小魯棒成本），從而最小化決策者的后悔值。

2.1 目標函數與決策變量

以車輛調度方案魯棒成本最小為目標函數：

式中：為最差情況下車輛在路段的行程時間，即車輛k在路段(i，j)的行程時間取路段(i，j)區間阻抗上界值表示特定情景下路段(i，j)的阻抗，當xkij=1時，式（2）將取到路段(i，j)阻抗的區間上界值tuij；當xkij=0時，式（2）將取到路段(i，j)阻抗的區間下界值tlij。wkij為特定情景下的車輛路徑方案。

該模型決策變量為：

其中，wkij為變量xkij基于特定情景下的最佳車輛調度方案；連續變量yikj為路段(i，j)上車輛k的物資載重量；Tik為車輛k行駛到節點i的時刻。

2.2 約束條件

2.2.1 站點約束

每個應急物資集散中心i都能發出與接收多輛車，式（5）表示每個集散中心i最少發出一輛車到受災點；式（6）表示每個集散中心i最少有一輛車從受災點返回來；式（7）表示任意受災點j只由一輛車從一個集散中心出發，為其配送物資；式（8）表示任意車輛k在任意節點j進出流量守恒。

2.2.2 車輛約束

式（9）表示車輛k的行程只能以同一個應急物資集散中心i作為起終點；式（10）表示任意車輛k在任意受災點j至多服務一次。

2.2.3 邊約束

式（11）表示從受災點i駛向受災點j的車輛最多有一輛，保證所有受災點只被一輛車服務。

2.2.4 車輛容量限制約束

式（12）表示從受災點i駛向受災點j的車輛k上的物資量ykij要小于車輛額定載量Q；式（13）表示應急救援車輛k在受災點j卸下了其物資需求量pj，即車輛k在受災點j前的車內物資量與經過受災點j后的車內物資量的差值。

2.2.5 時間約束與優先級約束

式（14）表示車輛行駛時間順序，即若車輛k從受災點i駛向受災點j，則該車到達j點的時刻與其到達i點的時刻的差值要小于等于路段(i，j)最大行程時間；式（15）表示受災點的優先配送權與車輛到達受災點時刻的關系，即若某受災點需求越急迫，則其優先配送權就越高，車輛會越早配送物資到該受災點；式（16）表示車輛k的總行駛時間不能超過最長行駛時間Tmax。

2.2.6 特定情景Xr中的車輛路徑wkij方案約束

在特點情景中，路網時間阻抗是確定的，在此確定的阻抗下求解的車輛路徑wkij方案，同樣要滿足車輛路徑變量xkij的站點、車輛、優先級等方面的約束。

3 算法設計

應急救援車輛物資配送路徑優化模型是容量限制的車輛路徑問題。Benders分解算法常用來求解同時包含了0-1整數變量和連續變量的極值問題。其將問題分解為許多小問題來做。其具體思想是采用割平面法，固定復雜變量（0-1整數變量），得到子問題，不斷迭代，產生Benders割約束，并將其加入主問題，直至得到最優解。該算法不斷迭代，生成新約束條件，故又被稱為行生成算法。

在基于阻抗區間的應急救援車輛調度模型中，第一步是確定一個車輛調度方案，第二步是得到基于該方案的特定路網阻抗情景下的最佳車輛調度方案，第三步是通過計算兩個方案的總行程時間差值，得到最小魯棒成本。

3.1 應急救援車輛路徑優化模型分解

3.1.1 子模型

隨著迭代次數增加，應急車輛調度方案的魯棒成本逐漸向下界靠攏。

3.1.2 主模型

主模型每被迭代一次， Benders可行性分割約束將被添加一次，使魯棒成本逐漸向其上界靠攏。當上界值等于下界值時，迭代停止。

3.2 計算步驟

1） 設置模型初始上界值bl為-∞， 初始下界值bu為+∞，路網行程時間取區間阻抗下界值，求解松弛主問題，即得可行方案

3）把wkij代進主模型，新加約束（31），對其進行求解，得到新調度方案xkij、yikj，若Z>bl，則更新bl；

4） 若bl=bu，則輸出最優解，停止計算，否則進入5）；

5） 令xkij=，返回2），進行迭代，直至bl=bu。

4 算例分析

本研究采用仿真交通路網來測試模型與算法。在該仿真交通路網中，共存在53個節點、125條路段，區間阻抗為圖中路段上括號內的數據。其中，設節點1～3為應急物資集散中心，容量限制為3 500 kg； 設節點17～46為受災點；受災點物資需求數據見表1，該數據由數值軟件MATLAB隨機生成，也可根據受災點特性對受災點進行需求評估，并且以此為物資配送需求量，配送時將優先配送物資需求量大的受災點。假定應急物資配送中心有6輛車，每輛車出發時刻均為9∶00，車輛額定載重均為1 500 kg，每輛車的最大行駛時間均限制為45 min，既每輛車總救援時間不超過45 min。

表1 受災點物資需求數據Table 1 Material demand data

采用AMPL軟件，編寫應急救援車輛路徑優化模型的Benders算法，調用CPLEX對算例進行求解。應急救援車輛路徑優化模型迭代了5次，求解時間為0.15 s，總魯棒成本為93.8，魯棒車輛調度方案見表2，應急救援車輛物資配送路徑圖如圖1所示，表2中最短路徑的括號的點表示該點僅經過但不停留。

圖1 物資配送路徑圖Fig.1 Material distribution route

表2 魯棒車輛調度方案Table 2 Robust vehicle scheduling scheme

從圖1可以看出，加粗的車輛路線為車輛調度方案中各應急救援車輛物資配送路徑，路段上的區間值表示為車輛在路段上不確定的行程時間。各車輛以應急物資集散中心節點1、2、3為起終點，在不確定的路況下，沿途經過各受災點進行物資配送，滿足每個受災點的物資需求。

由表2可知，每個應急集散中心均派出了2輛車，所有受災點物資需求均得到了滿足，每輛車的最大行駛時間（總救援時間）均沒超過時間限制，如1號集散中心的車輛最大行程時間分別為34、37 min；且滿足了受災點的物資需求量大而優先救援的策略，如45號受災點的需求量為220 kg，該需求量大于46號的需求量200 kg，故45號受災點得到了優先配送。本研究得到的配送方案的魯棒成本更小，行程時間更穩定可靠，可供應急物流決策參考。

5 結論

突發事件發生后的救援具有緊迫性，需要及時地把應急物資從應急物資集散中心配送到受災點。因此，應急救援車輛調度方案的確定是應急救援的關鍵。本研究以車輛調度方案最大后悔值最小化為目標，考慮受災點需求優先級、車輛最大行駛時間、車輛載重量限制等約束條件，基于路段區間阻抗來構建應急救援車輛調度模型，在交通路網阻抗不確定的情況下，保證得到最優的車輛調度方案。通過AMPL軟件，采用Benders分解算法對模型進行編程，求解算例。研究結果表明，本模型在滿足所有受災點物資需求的情況下，應急救援車輛路徑方案具有較強的穩定性與魯棒性，可為突發事件下考慮不確定性因素的應急救援調度方案的決策提供借鑒。