基于實時路況信息的災后應急配送路徑選擇系統

黃輝，吳翰，楊佳祺，未珂

（西北工業大學 管理學院，西安 710129）

中國是一個自然災害多發的國家，汶川地震、雅安地震等重大災害給國民帶來了嚴重的物質和精神方面的損害。自20世紀，我國發生數次重大災害，包括1979 年唐山大地震，2008 年汶川地震，2010年舟曲泥石流等。高強度的災害往往伴隨著毀滅性的損失，應急救援成為災害發生后立即啟動的最重要也是主要的工作。對應急事件的救援是一個系統工程，由于重大災害往往伴隨著次生災害的問題，持續影響救援工作的開展，如余震可能會使道路損壞，降水量影響道路通行能力等。救援物資在整個災后救援中有著舉足輕重的地位。災后，需要面對隨時會發生的次生情境，合理安排應急物流路線，在救援進行中隨時改進路線以適應不斷變化的道路狀態，提高救援效率，控制救援風險。

對于應急狀況下救援路線規劃的問題，國內外學者做了相關研究。Zhang等[1]提出了一種仿生算法，以求解救援過程中行駛速度變化情況下的應急路線規劃問題。劉春年等[2]提出了基于路阻函數理論與Dijkstra算法的最優路徑數學模型。代穎等[3]構建了應急物資配送中心定位和配送路徑安排的聯合決策問題的定位-路徑問題模型。袁媛等[4]建立了最小化災害疏散時間和最小化疏散路線復雜度的應急疏散路徑選擇雙目標優化模型。Rath等[5]研究了災后應急物資運輸中的定位-路徑問題，模型中考慮了短期和中期的救援經濟性的多目標優化模型，并考慮了人道主義因素。魏航等[6]研究了時變隨機網絡下有應急限制期的應急路徑選擇問題，通過定義應急路徑的風險和成功，給出算法，得出應急限制期下的有效應急路徑。劉楊等[7]提出了城市應急車輛出行前救援路徑選擇的多目標規劃模型。范文璟等[8]針對時變網絡環境下應急路徑問題，提出了考慮跨越多個時段的行駛問題的城市路段行駛時間的計算方法。謝紅薇等[9]提出了結合遺傳算法和模擬退火算法，提出了一種求解應急最優路徑的方法。應急救援有著弱經濟性，但有些研究會還將救援成本作為優化的目標之一。Tzeng 等[10]考慮救援時間成本最小化，以及救援滿意度最大化，構建多目標應急路徑優化方案。很多研究從不同的角度來考慮時變應急路徑選擇的問題，但難以全方位地實現實時根據數據輸入確定救援路線，并根據仿真數據，從宏觀角度隨時規劃救援路線。本文根據自然科學學科專家的評估，得到特定狀況下最優路線改變的概率，讓整個救援路線選擇體系從實時數據的輸入可以即刻得到最優的當前路線，亦可利用仿真數據，配合GIS實現整個救援過程的實時優化與規劃，以指導決策的制定。盡管國內外學者對時變應急物流路徑選擇做過不少研究，但考慮應急狀態下道路綜合屬性實時變化，并運用仿真程序模擬路線選擇過程的研究仍較少。

為此，本文提出適用于災害后次生災害等情況隨時發生狀態下應急救援路徑選擇的方法。通過檢測道路狀態，根據不同的道路受次生事件影響及其程度，隨時調整救援最優路線，結合地質等學科，組成一套應急路徑選擇體系。該體系不僅支持根據實際情況改變救援的行進路線，還可用來進行多次仿真，模擬救援情況，仿真結果可供決策者規劃整體救援資源的分配。最后，通過算例進行說明。

1 問題描述

災害發生后，會出現各種次生事件，如余震、道路阻塞、強降水等。次生事件的發生會導致應急路網狀態的改變，如余震破壞道路使道路無法通行、降水使道路通行能力下降等。次生事件的發生隨時可能會使路網狀態發生變化，進而使應急救援最優路線發生改變。因此，在災后應急配送過程中，為達到最快送達的目的，應急配送路徑的選擇通常不僅需考慮路線長度，還需綜合考慮道路通行能力、路段發生二次災害等因素。根據對道路狀態的實時監測，將道路狀態量化，動態實時調整救援路線，實現應急物資最快送達的目的。

2 建 模

2.1 綜合多種實時路況狀態因素的道路狀態量化

道路的情境狀態，可以由各個路段的多種道路屬性指標來描述。自然災害發生后，根據該災害本身的性質，屬性指標的選取應當呈現多樣化。為實現應急物資最快送達，本文只考慮4種主要道路屬性來描述一個路段的狀態特征：①路段區域二次災害發生風險程度f1。②路段區域降水狀況f2。③路段擁堵程度f3。④路段υiυj長度Lυiυj。

災害發生后，救援人員需要考慮的道路屬性不限于上述4種屬性，本文暫且以這4種屬性來描述路徑選擇過程。

文中符號含義：

υi—— 結點i，i=1，2，…，10

υiυj—— 從i點到j點的路段

P（υi）—— 最短路算法中，υi為P標號點

T（υi）—— 最短路算法中，υi為T標號點

fi—— 路段屬性i

t1——含有路段υ1υj的路網中的最短到達時間

t2—— 不含路段υiυj的路網中的最短到達時間

tυiυj—— 路段υiυj期望通行時間

tυiυjc—— 路段υiυj的臨界值

Lυiυj—— 路段υiυj的路程長度

V0υiυj—— 理 想 狀 況 下 路 段υiυj的 平 均 通 行速度

Vυiυj——路段υiυj在路段屬性影響下的實際平均通行速度

—— 路段υiυj的道路屬性fn的評估值，取值范圍[0，1]

Pυiυj—— 路段υiυj的穩定概率

路段長度直接影響整體運輸時間。其他3種屬性均以一定的程度影響車輛通行的平均速度。

在多種屬性影響程度量化上，各相關學科專家對各路段實時監控數據，給出屬性fn對路段通行平均速度影響程度的評估值，其中為屬性fn對路段υiυj的影響程度，且∈[0，1]。當=0時，路段的fn屬性處于極端情況最差值，即該屬性此時的狀態使道路中斷；當=1時，表示屬性fn處于理想狀態最優值，即該屬性不影響路段的通行速度。

設道路υiυj在各種屬性均處于理想狀態下的平均速度為V0υiυj，假設路段除其路程屬性外共有k種屬性，根據下式可得綜合k種屬性后的路段通行平均速度，即

路段長度除以該路段通行平均速度Vυiυj，進而計算出路段υiυj經過綜合考慮各種道路屬性調整后的該路段期望通行時間為

2.2 基于改進Dijkstra算法的應急配送路徑實時選擇

Dijkstra算法是解決網絡圖中最短路徑問題的經典算法。本文將路段期望通行時間tυiυj作為Dijkstra算法中的路徑長度屬性，將時間作為路網中各弧的弧長。根據改進的Dijkstra最短路算法，可計算得到到達受災點最短時間的網絡路徑，即最優路線，從而達到使救援車輛最快到達受災點的目的。

如圖1所示，災害發生后，由相關學科如地質、氣象、水文等工作者及實時監控人員對路網中各條道路的各種屬性進行評估后得到數據作為輸入，確定路網中各路段的期望通行時間，并得到該路網狀態下的最優路線。救援隊伍可即刻按照該初始最優路線出發。由于路段屬性狀態的實時變化，某路段可能發生某些次生事件，影響了路段的通行能力，進而影響路段的期望通行時間，可能會導致最優路線變化。

圖1 災后實時應急路徑選擇示意圖

在救援隊伍行進過程中，應實時監測路網狀態，若最優路線發生改變，應用如下方法尋找新的最優路徑。改進的Dijkstra算法：

（1）初始j=0；令Sυ1=1，P（υi）=0，u=υ1，對于不為υ1的每個點υi，令T（υi）=tυ1υi，若點υ1與υi可以直接連接，則令P（υi）=1，Sυi=0。

（2）若Sυn=1，可知T（υn）是由υ1到υn的最短路線，則可得出最短路，計算終止；否則，轉（3）。

（3）找出到起始點時間最短的點，令T（υi）=min｛T（υi）｝，此時，Sυ1=1，u=υ1，Su=1。

（4）如果點υi是某條弧的終點，在這個終點上發生了參數的改變，且參數改變是在救援車輛從該點相鄰的上一點向該點出發之后發生的，則設定點υi為新的起始點。根據改變后的道路參數，使用基本最短路算法計算出新的最短路；否則，轉（5）。

（5）更新所有T（υ1），Sυ1=1。令

j自增1，轉（2）。

結合相關學科研究成果，求得路網所需期望通行時間最短的路線。利用計算機仿真獲得仿真數據供決策者分析，以提前規劃路線，指導應急救援運輸任務。盡可能地充分利用時間以及道路資源等應急救援資源，提高救援效率。

2.3 路段臨界值與穩定概率

如圖2所示，若當救援車輛到達路網中某點時，道路狀態發生變化，根據上述方法會立即生成最新的最優路線。結合計算機技術，形成路網狀態信息系統，隨時根據新輸入的道路狀態數據計算出最新的最優路線。該方法可以在路網情況發生改變之后找出當時的最優路線，但若能提前計算出最優路徑發生變更的臨界點，面對不確定的事件發生，更能支持決策者做出恰當的路線選擇決策。

圖2 應急路徑實時選擇流程

該方法不考慮車輛正在行進的路段發生次生事件的情況，若一輛車所正在行駛的路段發生參數變化后，只可能有如下兩種情況發生：①此路不通（如巨石擋路），車輛掉頭回到前一個結點，換路行進。相當于重新選擇路線。②車輛已經走過發生阻擋車輛行進的事件的點，不影響車輛行進，車輛繼續前行，如在車輛后方100 m 處發生巨石墜路事件，而車輛向前行進并不受影響。因此，本研究不考慮此類情況。

若因當前最優路線中的某路段υiυj的期望通行時間tυiυj改變而導致最優路線改變時，計算機可以幫助計算出新的最優路線，而tυiυj改變到何種程度才會令最優路線發生改變，就是臨界值為何值，記作tυiυjc。即假設其他路段狀態不變，υiυj發生了次生事件，導致tυiυj＞tυiυjc，進而導致最優路線的改變；而當該次生事件并未導致tυiυj＞tυiυjc，則不會改變最優路線，tυiυjc即為路段υiυj的臨界值。根據上述對臨界值tυiυjc的定義，在實時變化的路網中，可得：①臨界值tυiυjc是對于已經被選作最優路線中的路段而言的，而不在最優路線上的路段本身并沒有臨界值；②隨 著路網狀態的改變，特定路段tυiυj的臨界值tυiυjc也會發生變化。

臨界值的計算方法：在某一路網狀態下，首先在路網中尋找到最優路線，即總期望通行時間最短的路線，并計算出該總期望通行時間t1。對于最優路線上的某路段υ1υj，將υiυj路段從原路網中剔除，再在剔除路段υiυj的新的路網中找出最優路線，并計算該最優路線的總期望通行時間t2。則對于初始狀態的最優路線，在其他條件不變的狀況下，當tυiυj變化到一定程度，使t1＞t2時，會使路網最優路線發生改變，即υiυj的時間臨值為

當路段υiυj在最優路線上時，其總會存在臨界值tυiυjc，tυiυjc也會因道路屬性的改變而改變，故在該路徑選擇系統中，當道路屬性狀態發生任何變化，需立即計算新的tυiυjc。另外，若想要提前仿真模擬車輛到達受災點的過程，則需要結合其他學科，計算各種次生事件發生的概率，提前知曉眾多救援路線各自最終被使用的可能性。

根據相關學科的研究成果，張彭等[12]提出一種擁堵概率估計方法，并給出了概率分布估計。張國平[13]對災區滑坡及雨量進行了分析，亦給出概率模型。根據相關研究，在應急事件發生后，應急路網中各路段所對應的多種救援路徑屬性，如路段區域余震風險程度f1，路段區域降雨狀況f2，路段擁堵程度f3各自概率分布情況。綜合特定路段的所有屬性的概率分布情況，可得路段綜合屬性的概率分布。本研究中，路段的綜合屬性以期望通行時間tυiυj來描述。對于最優路線上每個路段υiυj，均有各自的臨界值tυiυjc，在 其 期 望 通 行 時 間tυiυj的 分 布 中，可 得tυiυj＜tυiυjc的概率，本文稱為穩定概率Pυiυj。

綜上所述，應急救援路徑確定方法如下：救援任務下達后，根據氣象、地質等相關監測，輸入從出發點到受災點之間的路網的各個路段屬性狀態值，以及各個路段的穩定概率Pυiυj。通過屬性值求得初始狀態下各個路段的期望通行時間tυiυj，并在以各條路段的tυiυj為弧長的路網中運用算法求得最短路，即初始最優路線。重復仿真試驗，得到各路線最終的行駛概率。救援隊伍沿著該初始最優路線出發。出發后，面臨著不確定的次生事件，當次生事件發生，應立即根據實時監測輸入最新的道路屬性值，計算出實時tυiυj、tυiυjc、Pυiυj。形成新的路網參數，用最短路算法重新計算最優路線。每當次生事件發生，均應立即重復仿真試驗（最短路算法時間復雜度O（nlbn），以目前計算機計算能力，規模在30個結點的路網，萬次仿真時間在3 min以內，滿足實時性要求），得出路網的每條可能路線為最終行駛路線的可能性，供決策者參考，根據每條線路的風險程度與所需時間和每種救災物資的重要程度及需求緊急程度，分配給載有不同物資的車輛。根據新的最優路線規劃繼續行進，以此循環，直到車輛到達受災點。并運用高性能計算機，實現實時多次仿真，獲得數據以支持決策。

3 算 例

重慶υ1為應急物資供應點，雅安υ10為受災點，即物資需求點，υ1～υ10之間的路網如圖3所示。

圖3 抽象路網

為便于算例說明及仿真分析，做出如下假設：

（1）所有線路均可雙向行駛。

（2）路線一旦改變，可立即通知所有車輛的救援人員。

（3）路網中每個路段理想平均速度均為V0υiυj=80 km/h。

（4）為模擬應急狀態下路網，假設路段的穩定概率隨機變化。

表2所示為道路屬性輸入值。

表2 道路屬性輸入值

根據式（2），計算各路段的初始的期望通行時間，如表3所示。

表3 路段初始期望通行時間

根據上述數據，應用Dijkstra算法得出初始最優解為υ1-υ3-υ6-υ9-υ8-υ10。

因臨界值tυiυjc在救援過程中是隨著路況而不斷變化的，在此僅給出救援隊伍出發后第1個路段υ1υ3時的臨界值tυiυjc，即對應該初始最優解，計算臨界值。根據式（3），計算數據如表4所示。

實際救援過程中相關氣象、地質等監測人員，根據上述臨界值，通過綜合相關學科對次生事件發生的可能性的預測，得出各路段的穩定概率。本算例中，假設在初始狀態下，每路段υiυj平均通行時間不突破臨界值tυiυjc的概率（穩定概率）如（隨機取得）表5所示。

表4 初始臨界值（對于初始最優路線為v1-v3-v6-v9-v8-v10）

表5 路段初始穩定概率

實際救援中，隨著救援的推進，路段穩定概率會發生變化。利用地質、水文、交通等相關學科，通過監測每次屬性值的變化，隨時計算出當前狀態下穩定概率。由于導致概率變化的因素較多，且需相關學科的支持，本文仿真假設路段的穩定概率隨機變化，反映到仿真程序中，車輛每從一個結點出發走向下一個結點，取一次隨機數，作為各路段的穩定概率，由此模擬救援過程中穩定概率的變化情況。

根據初始最優解，救援車輛從點1出發，沿初始最優解為υ1-υ3-υ6-υ9-υ8-υ10，行進在路段υ1υ3上時，會面臨υ3υ6、υ6υ9、υ8υ9、υ9υ10這4個路段發生次生事件而改變其tυiυj的可能性，即tυ1υ6可能超過tυ3υ6c、tυ6υ9可能超過tυ6υ9c、tυ8υ9可能超過tυ8υ9c。根據表5，υ3υ6的穩定概率Pυ3υ6=0.41。生成控制概率的隨機數，以模擬在一定的概率條件下υ3υ6路段次生事件發生的情形，可能產生如下結果：①若tυ3υ6超過臨界值tυ3υ6c，則最優解變為不選擇υ3υ6的路段的最優路線：υ3-υ5-υ8-υ10，救援隊伍沿該路線行進，并在到達υ5之前監測υ5υ8的屬性值，觀察其是否突破臨界值tυ5υ8c，如此循環直至終點。對于原最優路線上其他路段υ6υ9、υ8υ9、υ8υ10，進行相同的監測，并根據次生事件對道路屬性的影響情況，隨時調整最優路線。②路段υ3υ6、υ6υ9、υ8υ9、υ8υ10各自的tυiυj均未超過各自的tυiυjc，則到達υ3后，繼續沿著原最優路線υ1-υ3-υ6-υ9-υ8-υ10行進，在到達υ6之前繼續監測路段υ6υ9、υ8υ9、υ8υ10的屬性值變化，判斷其是否突破其臨界值tυ5υ8c，并判斷是否改變路線。在整個救援運輸過程中，依次循環、計算當前最優路線，直到救援隊伍到達受災點。

本例運用多次仿真計算各個路線被選擇的次數。當一次仿真結束后，保存記錄本次仿真的路線結果，在多次仿真中，記錄所有結果路線出現的次數，收集并統計，對于路網中每個點，運用配置Intel i3，主頻2.26 GHz CPU，2 GB 內存的計算機，在Windows 7操作系統下運用MATLAB R2 012 A編寫程序，進行10 000次仿真，因靠近終點的結點到終點的路徑較為單一，且無特別的研究意義，僅給出距離終點較遠的結點（υ1，υ2，υ3，υ4）的仿真結果：

（1）以重慶（υ1）為起點的仿真結果（程序運行時間40 s）如表6、圖4所示。

通過上述數據，可以看出，當車輛沿初始最優路線υ1-υ3-υ6-υ9-υ8-υ10出發后，在最終到達目的地時，可能會出現4種路線狀態。路線最終被選擇的可能性不盡相同，決策者可以利用該方針數據，規劃運輸資源的分配。

表6 仿真結果統計（重慶（v1）為起點）

圖4 仿真結果統計（重慶（υ1）為起點）

（2）以遂寧（υ2）為起點的仿真結果（程序運行51 s）如表7、圖5所示。

表7 仿真結果統計（遂寧（v2）為起點）

圖5 仿真結果統計（遂寧（υ2）為起點）

（3）以內江（υ3）為起點的仿真結果（程序運行35 s）如表8、圖6所示。

表8 仿真結果統計（內江（v3）為起點）

（4）以瀘州（υ3）為起點的仿真結果（程序運行38 s）如表9、圖7所示。

圖6 仿真結果統計（內江（υ3）為起點）

表9 仿真結果統計（瀘州（v4）為起點）

圖7 仿真結果統計（瀘州（υ4）為起點）

仿真結果顯示，初始的最優路線只在一定的概率上會成為最終的車輛運行路線，需要結合路段屬性變化的風險，綜合選取、規劃路線。

4 結語

救援任務進程中的不確定性，始終影響救援的進行。本研究中的臨界值和穩定概率，為綜合量化道路屬性，梳理動態救援過程提供了依據及指導。綜合相關學科的應用，本方法針對應急事件下次生事件不確定、路況復雜多變的特點，基于動態路徑選擇方法，指導救援過程中實時選擇最優路線，將救災過程的非常有限的物流資源盡可能充分利用，并規避風險，整體上提高救援效率，為動態救援決策提供有益思考。最后，通過算例分析進行驗證。該方法下，需要多種學科技術的配合，各個學科之間如何更緊密協調，各種門類的數據如何更緊密銜接，以及如何更合理利用仿真數據，分析每個路線的特點，以合理規劃物資運輸，仍需未來的進一步研究。