張 慧

（重慶交通大學(xué)交通運(yùn)輸學(xué)院，重慶400074）

0 引言

應(yīng)急救援系統(tǒng)中最重要的問(wèn)題之一就是如何使救援車輛在最短時(shí)間內(nèi)到達(dá)事故現(xiàn)場(chǎng)，這就涉及到應(yīng)急救援系統(tǒng)中最短路徑選擇問(wèn)題。相關(guān)資料表明，高效的應(yīng)急救援系統(tǒng)可以將事故損失降低到無(wú)應(yīng)急系統(tǒng)的6%[1]。而最短路徑不僅僅指一般意義上的距離最短，還可以引申到其他的度量，如時(shí)間、費(fèi)用、線路容量、路況等。傳統(tǒng)的最短路徑算法主要有Dijkstra算法和Floyd算法。前者用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑，后者是用于計(jì)算所有節(jié)點(diǎn)之間的最短路徑。但這兩種算法的時(shí)間花費(fèi)很大。Dijstra 算法對(duì)于有k個(gè)節(jié)點(diǎn)的圖，計(jì)算一個(gè)節(jié)點(diǎn)到其余節(jié)點(diǎn)最短路徑的算法時(shí)間復(fù)雜度是O（k2）。

由于最短路徑算法的復(fù)雜性，國(guó)內(nèi)外許多學(xué)者對(duì)此進(jìn)行了大量的研究。文獻(xiàn)[2]根據(jù)起始點(diǎn)和終止點(diǎn)的方向，在最短路徑計(jì)算中限制了一定的方向，減少了計(jì)算時(shí)間。文獻(xiàn)[3]以要計(jì)算的最短路徑的起始點(diǎn)和終止點(diǎn)為焦點(diǎn)，畫(huà)出一個(gè)橢圓，最短路徑的計(jì)算限制在這個(gè)橢圓中。在這些算法中增加了一些約束條件，使得最短路徑解并不一定是精確解。本文在傳統(tǒng)的Dijkstra 算法基礎(chǔ)上結(jié)合實(shí)際的交通情況提出了一種新的算法稱為最優(yōu)路徑算法，主要思想就是應(yīng)用Dijkstra 算法探索了應(yīng)急救援新的路徑權(quán)重計(jì)算方法，提出一套最優(yōu)路徑?jīng)Q策方法。

1 最短路徑算法的實(shí)現(xiàn)

最短路徑問(wèn)題的求解方法主要有Dijkstra 標(biāo)號(hào)法、灰色理論、蟻群算法、Floyd 算法、遺傳算法等。本文根據(jù)解決應(yīng)急救援最優(yōu)路徑問(wèn)題的需求，應(yīng)用MATLAB 仿真，以Dijkstra 標(biāo)號(hào)法為基礎(chǔ)，求解應(yīng)急救援最優(yōu)路徑選擇問(wèn)題。

1.1 Dijkstra算法原理

Dijkstra 算法是圖論中求解最短路徑的一個(gè)著名的算法，用于求圖中一個(gè)節(jié)點(diǎn)到其他各個(gè)節(jié)點(diǎn)的最短路徑。將道路抽象為網(wǎng)絡(luò)中的邊，以邊的權(quán)值來(lái)表示與道路相關(guān)的參數(shù)，權(quán)是廣泛的，可以表示速度、天氣情況、交通情況、距離等。最短路徑的衡量是通過(guò)計(jì)算路徑的邊權(quán)來(lái)決定的，所以邊的權(quán)值都是非負(fù)數(shù)。網(wǎng)絡(luò)中所有節(jié)點(diǎn)初始化為未記節(jié)點(diǎn)，在搜索過(guò)程中和最短路徑中的節(jié)點(diǎn)相連通的節(jié)點(diǎn)設(shè)置為臨時(shí)標(biāo)記節(jié)點(diǎn)，每次循環(huán)都是從臨時(shí)標(biāo)記節(jié)點(diǎn)中搜索距源點(diǎn)最短的路徑長(zhǎng)度的節(jié)點(diǎn)標(biāo)記為永久標(biāo)記節(jié)點(diǎn)，直到所有節(jié)點(diǎn)或目標(biāo)節(jié)點(diǎn)都成為永久標(biāo)記節(jié)點(diǎn)，算法結(jié)束。

1.2 Dijkstra算法的實(shí)現(xiàn)步驟

假設(shè)每個(gè)點(diǎn)都有一堆標(biāo)號(hào)（dj，pj），其中dj是從起源點(diǎn)s到點(diǎn)j的最短路徑的長(zhǎng)度（從頂點(diǎn)到其本身的最短路徑是零路（沒(méi)有弧的路），其長(zhǎng)度等于零）；pj則是從點(diǎn)s到點(diǎn)j的最短路徑中點(diǎn)j的前一點(diǎn)。求解從起源點(diǎn)s到點(diǎn)j的最短路徑算法的基本過(guò)程如下。

（1）初始化，起源點(diǎn)設(shè)置為：

①ds=0，ps為空；

②所有其他點(diǎn)：di=$，pi=？；

③標(biāo)記起源點(diǎn)s，記k=s，其他所有點(diǎn)設(shè)為未標(biāo)記的。

（2）檢驗(yàn)從所有已標(biāo)記的點(diǎn)k到其直接連接的未標(biāo)記的點(diǎn)j的距離，并設(shè)置：

式中，lkj為從點(diǎn)k到j(luò)的直接連接距離。

（3）選取下一個(gè)點(diǎn)，從所有未標(biāo)記的結(jié)點(diǎn)中，選取dj中最小的一個(gè)i：di=min[di，所有未標(biāo)記的點(diǎn)j]，點(diǎn)i就被選為最短路徑中的一點(diǎn)，并設(shè)為已標(biāo)記的。

（4）找到點(diǎn)i的前一點(diǎn)，從已標(biāo)記的點(diǎn)中找到直接連接點(diǎn)i的點(diǎn)j*，作為前一點(diǎn)。

（5）設(shè)置：i=j*，如果所有點(diǎn)已標(biāo)記，則算法完全退出；否則，記k=i，轉(zhuǎn)到第（2）步再繼續(xù)。

2 建立層次模型

每個(gè)因素對(duì)尋求最優(yōu)路徑的影響不一樣，也就是各自所占權(quán)重不一樣。各層指標(biāo)權(quán)重的確定是最優(yōu)路徑選擇的關(guān)鍵的一個(gè)步驟，直接影響救援效率。確定指標(biāo)權(quán)重的方法有很多種，包括層次分析法（AHP法）、德?tīng)柗品ā㈧貦?quán)法和模糊聚類分析法等。相對(duì)于其他方法，AHP 法不需要具備樣本數(shù)據(jù)[4]，專家僅憑對(duì)評(píng)價(jià)指標(biāo)內(nèi)涵與外延的理解即可作出判斷，且結(jié)合了定量分析和定性分析，可以把定性分析的結(jié)果量化。另外，AHP 法的使用范圍比較廣泛，且簡(jiǎn)單易行。因此，本文采用層次分析法來(lái)確定各指標(biāo)的權(quán)重是比較適合的。

2.1 建立層次結(jié)構(gòu)模型

AHP 法首先把問(wèn)題層次化，按照問(wèn)題性質(zhì)和總目標(biāo)將此問(wèn)題分解成不同層次，構(gòu)成一個(gè)多層次的分析結(jié)構(gòu)模型。本文將層次結(jié)構(gòu)分為三層（見(jiàn)圖1）。目標(biāo)層A計(jì)算路徑權(quán)重，準(zhǔn)則層B是影響權(quán)重的因子，方案層C是關(guān)于道路的使用功能。任務(wù)和交通量等分為5個(gè)等級(jí)，由高到低分別為道路1、道路2、道路3、道路4、道路5。

圖1 路徑權(quán)重層次結(jié)構(gòu)模型

2.2 權(quán)重值的解算過(guò)程

先利用層次分析法對(duì)準(zhǔn)則層各指標(biāo)對(duì)于目標(biāo)層的權(quán)重進(jìn)行計(jì)算，再用層次分析法對(duì)方案層各指標(biāo)對(duì)于準(zhǔn)則層的權(quán)重進(jìn)行計(jì)算。步驟如下：

（1）構(gòu)造判斷矩陣。構(gòu)造下層各因素對(duì)于上一層準(zhǔn)則的兩兩比較判斷矩陣，依據(jù)表1 進(jìn)行取值。

表1 1-9標(biāo)度的含義

（2）完成所有的兩兩比較，計(jì)算權(quán)重，權(quán)重的計(jì)算方法有根法、合法、對(duì)數(shù)最小二乘法、特征根法。本文選用特征根法：

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

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

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

表2 平均一致性指標(biāo)RI

當(dāng)CR＜0.1 時(shí)，判斷矩陣一致性是可靠的；當(dāng)CR≥0.1時(shí)，必須對(duì)判斷矩陣作修正。

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

（5）層次合層計(jì)算。

（6）整個(gè)層次進(jìn)行整體一致性檢驗(yàn)。不通過(guò)就對(duì)部分判斷作適當(dāng)?shù)母纳疲蛊錆M足一致性檢驗(yàn)標(biāo)準(zhǔn)[5]。

建立各層對(duì)目標(biāo)層的判斷矩陣，如表3所示。

表3 準(zhǔn)則層對(duì)目標(biāo)層的判斷矩陣

運(yùn)用MATLAB 軟件求得判斷矩陣A 的最大特征值Kmax=3.0940，對(duì)應(yīng)的歸一化特征向量為W（2）,其值見(jiàn)表3。

CI（2）=0.047＜0.1；CR（2）=0.09＜0.1 滿足一致性檢驗(yàn)標(biāo)準(zhǔn)。表明A通過(guò)一致性檢驗(yàn)，各個(gè)指標(biāo)的權(quán)重系數(shù)為歸一化的特征向量。

建立方案層對(duì)準(zhǔn)則層B1的判斷矩陣，如表4所示。

表4 方案層對(duì)準(zhǔn)則層B1的判斷矩陣

運(yùn)用MATLAB 軟件求得判斷矩陣B1的最大特征值Kmax=5.0681，對(duì)應(yīng)的歸一化特征向量為其值見(jiàn)表4。性檢驗(yàn)標(biāo)準(zhǔn)。

方案層對(duì)準(zhǔn)則層B2的判斷矩陣，如表5所示。

表5 方案層對(duì)準(zhǔn)則層B2的判斷矩陣

運(yùn)用MATLAB 軟件求得判斷矩陣B2的最大特征值Kmax=5.3136，對(duì)應(yīng)的歸一化特征向量為其值見(jiàn)表5。性檢驗(yàn)標(biāo)準(zhǔn)。

方案層對(duì)準(zhǔn)則層B3的判斷矩陣，如表6所示。

表6 方案層對(duì)準(zhǔn)則層B3的判斷矩陣

運(yùn)用MATLAB 軟件求得判斷矩陣B3的最大特征值Kmax=5.0681，對(duì)應(yīng)的歸一化特征向量為其值見(jiàn)表6。致性檢驗(yàn)標(biāo)準(zhǔn)。

C層對(duì)A層的總排序如表7所示。

表7 C層對(duì)A層的總排序

C層對(duì)目標(biāo)層的一致性檢驗(yàn)：故滿足一致性檢驗(yàn)要求。表明C通過(guò)一致性檢驗(yàn)，各個(gè)指標(biāo)權(quán)重系數(shù)為歸一化后的特征向量。

3 最優(yōu)路徑仿真實(shí)驗(yàn)

圖2為某地區(qū)發(fā)生一起交通事故后，醫(yī)院到救援事故點(diǎn)的路徑情況。其中V1表示醫(yī)院，V5表示事故發(fā)生點(diǎn)。通過(guò)上述計(jì)算，可以獲得各影響因子的權(quán)重值，然后利用式（4）計(jì)算路徑權(quán)值。其中整個(gè)網(wǎng)絡(luò)圖中各路徑的s/v取相同單位，最終對(duì)路徑權(quán)重W進(jìn)行等值的無(wú)量綱處理。

表8 該地區(qū)的各參數(shù)取值

將表8中的各數(shù)據(jù)代入式（4），可得到每個(gè)路徑的取值（見(jiàn)圖2）。

運(yùn)用Dijkstra 算法在MATLAB 軟件中實(shí)現(xiàn)，可求得醫(yī)院到事故的最短路徑為：V1—V2—V5，最短路徑長(zhǎng)為2.5。

4 結(jié)語(yǔ)

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

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

[2] 嚴(yán)寒冰，劉迎春.基于GIS的城市道路網(wǎng)最短路徑算法探討[J].計(jì)算機(jī)學(xué)報(bào)，2000，（2）：210-215.

[3] 陸峰，施曉東，朱大奎.GIS中使用改進(jìn)的Dijkstra算法實(shí)現(xiàn)最短路徑的計(jì)算[J]. 中國(guó)圖形圖象學(xué)報(bào)：A 輯，1999，（10）：1019-1023.

[4] 王靖，張金鎖.綜合評(píng)價(jià)中確定權(quán)重向量的幾種方法比較[J].河北工業(yè)大學(xué)學(xué)報(bào)，2001，30（2）：52-57.

[5] 同濟(jì)大學(xué)出版社. 線性代數(shù)[M]. 成都：四川大學(xué)出版社，2003：25-29.