基于層次分析法的應急救援最優路徑選擇分析

張 慧

（重慶交通大學交通運輸學院，重慶400074）

0 引言

應急救援系統中最重要的問題之一就是如何使救援車輛在最短時間內到達事故現場，這就涉及到應急救援系統中最短路徑選擇問題。相關資料表明，高效的應急救援系統可以將事故損失降低到無應急系統的6%[1]。而最短路徑不僅僅指一般意義上的距離最短，還可以引申到其他的度量，如時間、費用、線路容量、路況等。傳統的最短路徑算法主要有Dijkstra算法和Floyd算法。前者用于計算一個節點到其他所有節點的最短路徑，后者是用于計算所有節點之間的最短路徑。但這兩種算法的時間花費很大。Dijstra 算法對于有k個節點的圖，計算一個節點到其余節點最短路徑的算法時間復雜度是O（k2）。

由于最短路徑算法的復雜性，國內外許多學者對此進行了大量的研究。文獻[2]根據起始點和終止點的方向，在最短路徑計算中限制了一定的方向，減少了計算時間。文獻[3]以要計算的最短路徑的起始點和終止點為焦點，畫出一個橢圓，最短路徑的計算限制在這個橢圓中。在這些算法中增加了一些約束條件，使得最短路徑解并不一定是精確解。本文在傳統的Dijkstra 算法基礎上結合實際的交通情況提出了一種新的算法稱為最優路徑算法，主要思想就是應用Dijkstra 算法探索了應急救援新的路徑權重計算方法，提出一套最優路徑決策方法。

1 最短路徑算法的實現

最短路徑問題的求解方法主要有Dijkstra 標號法、灰色理論、蟻群算法、Floyd 算法、遺傳算法等。本文根據解決應急救援最優路徑問題的需求，應用MATLAB 仿真，以Dijkstra 標號法為基礎，求解應急救援最優路徑選擇問題。

1.1 Dijkstra算法原理

Dijkstra 算法是圖論中求解最短路徑的一個著名的算法，用于求圖中一個節點到其他各個節點的最短路徑。將道路抽象為網絡中的邊，以邊的權值來表示與道路相關的參數，權是廣泛的，可以表示速度、天氣情況、交通情況、距離等。最短路徑的衡量是通過計算路徑的邊權來決定的，所以邊的權值都是非負數。網絡中所有節點初始化為未記節點，在搜索過程中和最短路徑中的節點相連通的節點設置為臨時標記節點，每次循環都是從臨時標記節點中搜索距源點最短的路徑長度的節點標記為永久標記節點，直到所有節點或目標節點都成為永久標記節點，算法結束。

1.2 Dijkstra算法的實現步驟

假設每個點都有一堆標號（dj，pj），其中dj是從起源點s到點j的最短路徑的長度（從頂點到其本身的最短路徑是零路（沒有弧的路），其長度等于零）；pj則是從點s到點j的最短路徑中點j的前一點。求解從起源點s到點j的最短路徑算法的基本過程如下。

（1）初始化，起源點設置為：

①ds=0，ps為空；

②所有其他點：di=$，pi=？；

③標記起源點s，記k=s，其他所有點設為未標記的。

（2）檢驗從所有已標記的點k到其直接連接的未標記的點j的距離，并設置：

式中，lkj為從點k到j的直接連接距離。

（3）選取下一個點，從所有未標記的結點中，選取dj中最小的一個i：di=min[di，所有未標記的點j]，點i就被選為最短路徑中的一點，并設為已標記的。

（4）找到點i的前一點，從已標記的點中找到直接連接點i的點j*，作為前一點。

（5）設置：i=j*，如果所有點已標記，則算法完全退出；否則，記k=i，轉到第（2）步再繼續。

2 建立層次模型

每個因素對尋求最優路徑的影響不一樣，也就是各自所占權重不一樣。各層指標權重的確定是最優路徑選擇的關鍵的一個步驟，直接影響救援效率。確定指標權重的方法有很多種，包括層次分析法（AHP法）、德爾菲法、熵權法和模糊聚類分析法等。相對于其他方法，AHP 法不需要具備樣本數據[4]，專家僅憑對評價指標內涵與外延的理解即可作出判斷，且結合了定量分析和定性分析，可以把定性分析的結果量化。另外，AHP 法的使用范圍比較廣泛，且簡單易行。因此，本文采用層次分析法來確定各指標的權重是比較適合的。

2.1 建立層次結構模型

AHP 法首先把問題層次化，按照問題性質和總目標將此問題分解成不同層次，構成一個多層次的分析結構模型。本文將層次結構分為三層（見圖1）。目標層A計算路徑權重，準則層B是影響權重的因子，方案層C是關于道路的使用功能。任務和交通量等分為5個等級，由高到低分別為道路1、道路2、道路3、道路4、道路5。

圖1 路徑權重層次結構模型

2.2 權重值的解算過程

先利用層次分析法對準則層各指標對于目標層的權重進行計算，再用層次分析法對方案層各指標對于準則層的權重進行計算。步驟如下：

（1）構造判斷矩陣。構造下層各因素對于上一層準則的兩兩比較判斷矩陣，依據表1 進行取值。

表1 1-9標度的含義

（2）完成所有的兩兩比較，計算權重，權重的計算方法有根法、合法、對數最小二乘法、特征根法。本文選用特征根法：

式中，Kmax是A 的最大特征根；W是特征向量，且歸一化后就可作為權重向量。

（3）計算一致性比例CR，它表明判斷矩陣偏離可靠性的程度，計算方法如下：

式中，CI為一致性指標，CI=（Kmax-n）/(n-1)；RI為平均一致性指標，取值如表2所示。

表2 平均一致性指標RI

當CR＜0.1 時，判斷矩陣一致性是可靠的；當CR≥0.1時，必須對判斷矩陣作修正。

（4）各層都完成第（1）、（2）、（3）步的計算。

（5）層次合層計算。

（6）整個層次進行整體一致性檢驗。不通過就對部分判斷作適當的改善，使其滿足一致性檢驗標準[5]。

建立各層對目標層的判斷矩陣，如表3所示。

表3 準則層對目標層的判斷矩陣

運用MATLAB 軟件求得判斷矩陣A 的最大特征值Kmax=3.0940，對應的歸一化特征向量為W（2）,其值見表3。

CI（2）=0.047＜0.1；CR（2）=0.09＜0.1 滿足一致性檢驗標準。表明A通過一致性檢驗，各個指標的權重系數為歸一化的特征向量。

建立方案層對準則層B1的判斷矩陣，如表4所示。

表4 方案層對準則層B1的判斷矩陣

運用MATLAB 軟件求得判斷矩陣B1的最大特征值Kmax=5.0681，對應的歸一化特征向量為其值見表4。性檢驗標準。

方案層對準則層B2的判斷矩陣，如表5所示。

表5 方案層對準則層B2的判斷矩陣

運用MATLAB 軟件求得判斷矩陣B2的最大特征值Kmax=5.3136，對應的歸一化特征向量為其值見表5。性檢驗標準。

方案層對準則層B3的判斷矩陣，如表6所示。

表6 方案層對準則層B3的判斷矩陣

運用MATLAB 軟件求得判斷矩陣B3的最大特征值Kmax=5.0681，對應的歸一化特征向量為其值見表6。致性檢驗標準。

C層對A層的總排序如表7所示。

表7 C層對A層的總排序

C層對目標層的一致性檢驗：故滿足一致性檢驗要求。表明C通過一致性檢驗，各個指標權重系數為歸一化后的特征向量。

3 最優路徑仿真實驗

圖2為某地區發生一起交通事故后，醫院到救援事故點的路徑情況。其中V1表示醫院，V5表示事故發生點。通過上述計算，可以獲得各影響因子的權重值，然后利用式（4）計算路徑權值。其中整個網絡圖中各路徑的s/v取相同單位，最終對路徑權重W進行等值的無量綱處理。

表8 該地區的各參數取值

將表8中的各數據代入式（4），可得到每個路徑的取值（見圖2）。

運用Dijkstra 算法在MATLAB 軟件中實現，可求得醫院到事故的最短路徑為：V1—V2—V5，最短路徑長為2.5。

4 結語

在研究各種最短路徑算法的基礎上，選用經典的Dijkstra 算法作為最優路徑選擇的基礎，運用層次分析法計算應急救援道路的權值影響因子系數，提出一種路徑權值的計算方法，并運用MATLAB計算仿真，驗證整套方案的可行性。這個方案在一定程度上能提高應急救援決策的效率，但是該方法對各路徑權重的確定的合理性仍需實踐的進一步檢驗。

[1] 李志憲.事故應急救援預案范例精選[M].北京：煤炭工業出版社，2007.

[2] 嚴寒冰，劉迎春.基于GIS的城市道路網最短路徑算法探討[J].計算機學報，2000，（2）：210-215.

[3] 陸峰，施曉東，朱大奎.GIS中使用改進的Dijkstra算法實現最短路徑的計算[J]. 中國圖形圖象學報：A 輯，1999，（10）：1019-1023.

[4] 王靖，張金鎖.綜合評價中確定權重向量的幾種方法比較[J].河北工業大學學報，2001，30（2）：52-57.

[5] 同濟大學出版社. 線性代數[M]. 成都：四川大學出版社，2003：25-29.