摘 要:安全事故發(fā)生后，為了讓救援物質(zhì)#65380;裝備#65380;人員以最快的速度到達事故發(fā)生地，以最大限度減少人員傷亡和物質(zhì)財產(chǎn)損失，開發(fā)一個基于層次分析法的智能GIS救援系統(tǒng)#65377;該系統(tǒng)能夠在收到報警信息后，立即聯(lián)系相關救援單位，并依據(jù)事故發(fā)生地周圍道路交通情況，計算出一條最快到達事故發(fā)生地的路線，為決策者提供第一時間信息#65377;

關鍵詞:GIS; 層次分析法; 最優(yōu)路徑;標準道路

中圖分類號:TP311.11文獻標識碼:A

1 引 言

災害發(fā)生時，緊急物質(zhì)的調(diào)度是十分必要的#65377;應急決策的最顯著特點表現(xiàn)為時間的緊迫性，決策者應以較短的時間完成調(diào)度方案，該方案應使物質(zhì)能以盡可能小的代價到達應急地點，此時決策過程中最優(yōu)路徑的選擇尤為重要^[1]#65377;因此，最優(yōu)路徑的選擇問題直接關系到人民群眾生命財產(chǎn)安全，具有很強的現(xiàn)實意義#65377;基于此，本文給出了一套基于優(yōu)化層次分析法的應急救援最優(yōu)路徑算法，能夠?qū)崟r反應出當前事故發(fā)生地與救援單位之間的道路情況，并主動搜索出兩者之間的最短路徑，以滿足消防#65380;醫(yī)療#65380;安全等部門的需求#65377;

2 層次分析法

2.1 層次分析的概念

美國運籌學家T.L.Saaty教授在20世紀70年代提出的層次分析法(Analytic Hierarchy Process，AHP)是一種確定權向量行之有效的方法#65377;這一方法基于對問題的全面考慮，將定性與定量分析相結(jié)合，將決策者的經(jīng)驗予以量化，是比較實用的決策方法之一^[2]#65377;

運用層次分析法解決問題時，首先對問題所涉及到的所有因素進行分類，找出相互關系，構(gòu)造層次結(jié)構(gòu)#65377;全部因素分為目標類#65380;準則類#65380;方案類，再求出各個評價準則對最終目標的重要程度(權重)，再分析各個待選方案對各個評價準則的重要程度(權重)#65377;最后，計算出各個待選方案對最終目標的重要程度(權重)^[3]#65377;

2.2 層次分析的特點

AHP(層次分析)具有十分廣泛的應用，這與它在理論上的合理及應用上的簡便分不開的#65377;它主要具有以下幾個特點:

1)系統(tǒng)性

AHP方法的思想基礎與系統(tǒng)分析的原則是一致的#65377;它要求決策者在對問題進行決策分析時，首先要姜分析對象的諸因素建立彼此相關的層次遞階系統(tǒng)結(jié)構(gòu)#65377;這種層次遞階的系統(tǒng)結(jié)構(gòu)可以清晰地反映出諸相關因素(目標#65380;準則#65380;對象)地彼此關系#65377;

2)綜合性

AHP方法在對事物進行決策分析時，能對定性問題與定量問題進行綜合分析處理，并能得到明確的定量化結(jié)論，以優(yōu)劣排序的形式表現(xiàn)出來#65377;

3)簡便性

AHP方法對事物的評判決策過程十分簡便，若有計算機及相關程序，則整個計算就更方便#65380;更迅速了#65377;

4)準確性

AHP的準確性表現(xiàn)在它豐富的數(shù)學原理為該方法的準確性提供了可信的基礎#65377;同時，AHP方法還能吸取決策者個人或集團的閱歷#65380;經(jīng)驗#65380;智慧#65380;判斷能力，從而使得決策建立在更扎實的基礎上#65377;

2.3 層次分析的步驟

層次分析法的基本計算問題是計算判斷矩陣的最大特征值λmax和相應的特征矢量W#65377;按照經(jīng)典的層次分析法，一般分析步驟如下:

計算技術與自動化2007年6月第26卷第2期樊 玲:基于層次分析法的GIS應急救援最優(yōu)路徑優(yōu)化法1)定義問題，確定要完成的目標;

2)從最高層(管理目標)，通過中間層(判斷標準)到最低層(方案)構(gòu)成一個層次結(jié)構(gòu)模型;

3)構(gòu)造一系列下層各因素對上一層準則的二二比較判斷矩陣;

4)在第3步里建立判斷矩陣所需要的n(n-1)/2個判斷;

5)完成所有的二二比較，輸入數(shù)據(jù)，計算最大特征值，計算一致性指標CR;

6)對各層次完成第3#65380;4#65380;5步的計算;

7)層次合成計算;

8)如整個層次綜合一致性不通過，要對某些判斷作適當?shù)母纳?，例如修改成對比較判斷時所提出的問題#65377;如一定要修改問題的結(jié)構(gòu)，則就要回到第二步，不過只要對層次結(jié)構(gòu)中有問題的部分作相應修改即可^[4]#65377;

3 應用層次分析

3.1 建立層次結(jié)構(gòu)

在本系統(tǒng)中，認為最近的交叉路口之間的一段為一條道路，救援或事故單位到任意最近的一個交叉路口之間的一段為一條道路#65377;依據(jù)層次分析法分析步驟，找出每條道路因為道路等級#65380;擁堵#65380;天氣#65380;地址災害等可變因素造成汽車在這條道路上行駛的權值，進一步計算出汽車行駛的速度，然后利用已知確定的道路長度，計算得到在這條道路上行駛的時間#65377;

在實際情況下，對道路交通的影響因素有很多，為了方便我們模擬計算，在這里我們只選擇其中相對重要的三項，下面我們按照層次分析的步驟構(gòu)建層次結(jié)構(gòu)模型如下:

道路權值確定

↓

天氣情況 道路等級 擁堵狀況

↓↓↓

道路1 道路2 道路… 道路N

假設三者影響因素之間的相對重要關系見表1#65377;

表1 影響因素之間的關系

天氣

情況道路

等級擁堵

狀況排序

矢量天氣情況11/71/50.072道路等級7130.652擁堵狀況51/310.278

這是一個齊次線性方程，它有非零平凡解的充要條件是行列式|A-nI|為零，即n是矩陣A的一個特征值#65377;由于A的每一行等于A的第一行和某個常數(shù)的乘積，因此矩陣A的秩為1，A的n個特征值λi(在本例中i=1，2，3)，除了一個以外都為零#65377;而我們知道矩陣的所有特征值之和應等于對角元素之和，即=n#65377;所以矩陣A只有一個特征值(最大特征值) λmax=n，其余皆為零#65377;我們再把A的各列經(jīng)過規(guī)范化處理(即分量和為1)，得到的解是唯一的^[5]#65377;

在這個簡單問題中，矩陣A具有正互反性，即aji=1/aij， aij>0，而且A的元素還滿足ajk=aik/aj，，即A具有規(guī)范一致性#65377;由Perron定理，矩陣A存在最大特征值λmax#65377;我們可以證明:

λmaxn

當A是一致時λmax=n，當A不一致時λmax>n#65377;

為了測試評判的可靠性或一致性，可以建立一個一致性指標^[4]#65377;在層次分析中引入判斷矩陣A的最大特征值λmax和n之差與n-1的比，作為度量判斷矩陣偏離一致性的指標，即用

CI=λmɑx-nn-1

來檢查決策者判斷思維的一致性#65377;

為了和一致性指標作相對比較，以判斷矩陣是否具有滿意一致性，引入判斷矩陣的平均隨機一致性指標RI#65377;即隨機地用1-9標度中地1，2，3，4，5，6，7，8，9及其倒數(shù)填滿樣本矩陣的上三角各項，至對角線各個元素始終為1，對應轉(zhuǎn)置位置項為上述對應位置的隨機數(shù)的倒數(shù)#65377;對500個隨機樣本矩陣分別計算一致性指標CI值，然后取平均值，得到平均隨機一致性指標RI^[4]#65377;判斷矩陣一致性指標CI和同階平均隨機性一致性指標RI之比稱為隨機一致性比率CR#65377;當CR在10%左右時，認為判斷矩陣具有滿意地一致性#65377;

因此上面表格表示的矩陣

經(jīng)過計算，其:λmax=3.065，CI=0.032，CR=0.056#65377;經(jīng)過規(guī)范化處理后的向量W=(0.072，0.652，0.278)#65377;可見選擇的數(shù)據(jù)具有較高的滿意一致性，符合精度要求#65377;

3.2 優(yōu)化層次法確定道路權值

由于實際情況下涉及的道路很多，按照經(jīng)典的層次分析法的成對比較分析將會使得計算數(shù)據(jù)成幾何級上升，并且最后得不到統(tǒng)一標準的有向權圖，這不符合實現(xiàn)本系統(tǒng)的初衷#65377;

在此，本系統(tǒng)對經(jīng)典的層次分析法進行了改進#65377;系統(tǒng)舍棄了成對比較方法，每次只考慮三條道路，其中固定的選擇兩條情況一般的道路作為標準道路，其他道路和兩條標準道路分別做比較，得到各自的權值#65377;為了說明設計思路，我們假設當時兩條標準道路和道路X狀況為表2，表3，表4三種道路狀況#65377;

這樣得到三條道路最終合成排序矢量W=(0.372，0.302，0.328)T，即道路X與標準道路的比值(權值)#65377;

3.3 確定道路交通速度

為了表征在該道路上的速度大小，根據(jù)實際測量標準道路1平均行駛車速為v1，標準道路2平均行駛車速為v2，利用三條道路的排序矢量，根據(jù)插值公式^[6]得到道路權值所對應的道路行駛速度值#65377;再分別對其他道路按照此方法進行插值計算，最后得到所有道路的速度值#65377;為了進一步加強插值計算數(shù)據(jù)與實際道路權值的一致性，可以適當增加標準道路的數(shù)量，但是會相應增加數(shù)據(jù)的計算量，減慢系統(tǒng)應急救援的反應速度，因此標準道路的選定和數(shù)量要根據(jù)實際情況做相應的調(diào)整#65377;同理也可增加對道路交通影響因素的個數(shù)，增加如地質(zhì)災害#65380;突發(fā)事故等因素，這同樣也會加大系統(tǒng)計算量#65377;

最后分別用道路的長度除以該道路的速度值，即得到該條道路行駛的時間值#65377;由此得到整個道路交通網(wǎng)的行駛時間有向權圖，為最優(yōu)路徑的搜索奠定基礎#65377;

4 系統(tǒng)算法實現(xiàn)

4.1 系統(tǒng)架構(gòu)

為了盡量減少算法實現(xiàn)的困難，我們舍棄了傳統(tǒng)的C/S模式，整個系統(tǒng)采用B/S架構(gòu)，使得整個系統(tǒng)具有很好的操作性和安全性#65377;并且在開發(fā)的時候使用.net#65380;SQL Server作為工具軟件，因為.net具有較強的靈活性，而且容易擴展其他功能#65377;矢量圖形系統(tǒng)是GIS系統(tǒng)最重要的組成部分，也是.net開發(fā)GIS系統(tǒng)的重點所在#65377;SQL Server作為GIS系統(tǒng)的數(shù)據(jù)庫，和.net一樣都是微軟公司的產(chǎn)品，因此二者具有很好的通用型和兼容性#65377;而且SQL Server具有很好的穩(wěn)定性和對.net方便的數(shù)據(jù)接口#65377;

4.2 搜索方法

根據(jù)上面建立的有向權圖，我們采用一般圖最短路問題的Dijkstra算法來實現(xiàn)路徑搜索#65377;該算法是解單源最優(yōu)路徑問題的貪心算法^[7]#65377;

基本思想是，給定帶權有向圖G=(V，E)，設置頂點集合S并不斷地做貪心選擇來擴充這個集合#65377;一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知#65377;初始時，S中僅含有源#65377;設u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當前每個頂點所對應的最短特殊路徑長度#65377;Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到s中，同時對數(shù)組dist進行必要的修改#65377;一旦s包含了所有V中頂點，dist就記錄了從源到所有其他頂點之間的最短路徑長度(具體代碼略)#65377;

4.3 運行結(jié)果

通過對系統(tǒng)在實際運行情況下的測評，車輛在道路上的實際運行時間與系統(tǒng)計算時間具有較高的一致性#65377;而且系統(tǒng)計算給定的路線，在實際情況下，有相當高的參考價值，為應急救援提供了第一手的信息#65377;系統(tǒng)運行界面如圖1所示#65377;

5 結(jié)束語

通過對層次分析法基本原理的研究，將層次分析的思想引入到應急救援系統(tǒng)中來解決最優(yōu)路徑問題，詳細討論了算法的實現(xiàn)和性能，提出了算法的改進，即舍棄了傳統(tǒng)的成對比較法，提出了標準道路概念，不但實現(xiàn)了算法的應用，而且加強了實用性#65377;仿真實驗證明該算法在解決決策支持系統(tǒng)中的最優(yōu)路徑是可行的，對提高應急決策的效率有一定幫助，但是該算法還有待于在更廣泛的應用問題上加以測試#65377;

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。