突發(fā)事件下應(yīng)急救援物資車輛路徑選擇方法

陳紅，文若蘭，周和平

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

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

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

1 問題描述與符號(hào)說明

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

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

本研究討論多個(gè)應(yīng)急物資集散中心車輛的協(xié)同調(diào)度優(yōu)化問題，依據(jù)災(zāi)區(qū)實(shí)際情境，科學(xué)地評估各受災(zāi)點(diǎn)的物資需求量，并優(yōu)先考慮配送需求量大的受災(zāi)點(diǎn)。應(yīng)急救援車輛k從應(yīng)急物資集散中心s出發(fā)，依次給受災(zāi)點(diǎn)配送物資，車輛的配送路徑為e。在突發(fā)事件發(fā)生時(shí)，需要快速地制定可靠的應(yīng)急資源調(diào)度方案來滿足所有受災(zāi)點(diǎn)i的物資需求。

2 模型建立

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

2.1 目標(biāo)函數(shù)與決策變量

以車輛調(diào)度方案魯棒成本最小為目標(biāo)函數(shù)：

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

該模型決策變量為：

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

2.2 約束條件

2.2.1 站點(diǎn)約束

每個(gè)應(yīng)急物資集散中心i都能發(fā)出與接收多輛車，式（5）表示每個(gè)集散中心i最少發(fā)出一輛車到受災(zāi)點(diǎn)；式（6）表示每個(gè)集散中心i最少有一輛車從受災(zāi)點(diǎn)返回來；式（7）表示任意受災(zāi)點(diǎn)j只由一輛車從一個(gè)集散中心出發(fā)，為其配送物資；式（8）表示任意車輛k在任意節(jié)點(diǎn)j進(jìn)出流量守恒。

2.2.2 車輛約束

式（9）表示車輛k的行程只能以同一個(gè)應(yīng)急物資集散中心i作為起終點(diǎn)；式（10）表示任意車輛k在任意受災(zāi)點(diǎn)j至多服務(wù)一次。

2.2.3 邊約束

式（11）表示從受災(zāi)點(diǎn)i駛向受災(zāi)點(diǎn)j的車輛最多有一輛，保證所有受災(zāi)點(diǎn)只被一輛車服務(wù)。

2.2.4 車輛容量限制約束

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

2.2.5 時(shí)間約束與優(yōu)先級約束

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

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

在特點(diǎn)情景中，路網(wǎng)時(shí)間阻抗是確定的，在此確定的阻抗下求解的車輛路徑wkij方案，同樣要滿足車輛路徑變量xkij的站點(diǎn)、車輛、優(yōu)先級等方面的約束。

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

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

在基于阻抗區(qū)間的應(yīng)急救援車輛調(diào)度模型中，第一步是確定一個(gè)車輛調(diào)度方案，第二步是得到基于該方案的特定路網(wǎng)阻抗情景下的最佳車輛調(diào)度方案，第三步是通過計(jì)算兩個(gè)方案的總行程時(shí)間差值，得到最小魯棒成本。

3.1 應(yīng)急救援車輛路徑優(yōu)化模型分解

3.1.1 子模型

隨著迭代次數(shù)增加，應(yīng)急車輛調(diào)度方案的魯棒成本逐漸向下界靠攏。

3.1.2 主模型

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

3.2 計(jì)算步驟

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

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

4） 若bl=bu，則輸出最優(yōu)解，停止計(jì)算，否則進(jìn)入5）；

5） 令xkij=，返回2），進(jìn)行迭代，直至bl=bu。

4 算例分析

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

表1 受災(zāi)點(diǎn)物資需求數(shù)據(jù)Table 1 Material demand data

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

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

表2 魯棒車輛調(diào)度方案Table 2 Robust vehicle scheduling scheme

從圖1可以看出，加粗的車輛路線為車輛調(diào)度方案中各應(yīng)急救援車輛物資配送路徑，路段上的區(qū)間值表示為車輛在路段上不確定的行程時(shí)間。各車輛以應(yīng)急物資集散中心節(jié)點(diǎn)1、2、3為起終點(diǎn)，在不確定的路況下，沿途經(jīng)過各受災(zāi)點(diǎn)進(jìn)行物資配送，滿足每個(gè)受災(zāi)點(diǎn)的物資需求。

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

5 結(jié)論

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