聶宸菡

（北京建筑大學 測繪與城市空間信息學院,北京100044）

當發(fā)生油氣管道發(fā)生事故時，將不可避免地會對社會、環(huán)境等造成損害。建立應急救援系統(tǒng)是減少造成損害的有效方法，其中緊迫性是最顯著的特征。當救援物資要求以最短時間到達事故現(xiàn)場時，決策者必須選擇最佳路徑，因此有人提出了啟發(fā)式搜索算法: A*算法[1]。層次分析法（AHP）是由Saaty 開發(fā)的一種多標準決策（MCDM）技術(shù)，用于復雜的決策問題。 它采用多層次的層次結(jié)構(gòu)，最終目標和實現(xiàn)這一目標的替代方案。AHP 不僅可以幫助決策者制定正確的決策，而且可以幫助他們找到最適合他們需求的解決方案以及他們對問題的理解[2]。在本文中，我們使用AHP 方法分析和比較影響最佳路線選擇的四個阻抗因子，并給出每個因子的權(quán)重（優(yōu)先級）。 然后，我們?yōu)檠芯繀^(qū)域的道路網(wǎng)絡(luò)中的每個路段分配了權(quán)重值，通過使用該權(quán)重值而不是經(jīng)典算法的距離權(quán)重值來改變經(jīng)典A*算法。

1 A*算法

A*算法屬于一種最經(jīng)典的啟發(fā)式搜索算法之一，是建立在Dijkstra 和BFS 算法基礎(chǔ)上的，也屬于遍歷搜索算法，但因為采用了啟發(fā)式方法來估計地圖上任意點到目標點的代價, 從而可以智能地評估每個相關(guān)節(jié)點，只按照最可能最正確的方向去搜索，而忽略其他不相關(guān)的節(jié)點或者背離目標節(jié)點的方向。A*算法引入了當前節(jié)點n 的啟發(fā)函數(shù)f(n),當前節(jié)點n 的啟發(fā)函數(shù)定義為:

其中g(shù)(n)是從起點到當前節(jié)點n 的實際費用的量度,h(n)是從當前節(jié)點n 到終點的最小費用的估計。

經(jīng)典的A*算法中f 函數(shù)的構(gòu)造為距離權(quán)重為主，而在實際尋找最佳路徑中，大多數(shù)使用距離作為權(quán)重來解決最佳路徑問題，在緊急情況下選出最佳路徑，必須考慮其他因素。分析這些元素所占比重，將用到層次分析法，下節(jié)將介紹層次分析法的步驟。

2 層次分析法

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

首先，構(gòu)建層次結(jié)構(gòu)模型。模型中有三個級別：

（1）最高級別是引發(fā)的問題，稱為目標級別。

（2）中間層是來自分解的復雜問題的元素，稱為準則級別。

（3）最低級別是問題的度量和方案，稱為方案級別。

在本文中，通過調(diào)查實時交通狀況來選擇阻抗因素。在我們的方法中，我們選擇了影響最佳路徑選擇的四個阻抗因子：道路質(zhì)量、交通流量、交通狀況、天氣。

2.2 成對比較

在層次分析法過程中，在確定各層次各因素之間的權(quán)重時，如果只是定性的結(jié)果，則常常不容易被別人接受，因此兩兩相互比較，對此時采用相對尺度，以盡可能減少性質(zhì)不同的諸因素相互比較的困難，以提高準確度。（如表1 所示）。

表1 元素之間的相對重要性

2.3 建立比較矩陣

在進行兩兩比較后，輸出的為一個比較矩陣，它包含了每對因素的比率，比較矩陣是nxn 矩陣，n 為因素數(shù)量。比較矩陣A為：

為了更接近實際狀況，在上述所建立的比較矩陣中，每個元素采用三角模糊數(shù)構(gòu)造的比較矩陣A 和道路數(shù)據(jù)調(diào)查分析出最小值和最大值取值，因此最終模糊比較矩陣Af為：

2.4 歸一化、計算權(quán)重

通過使用幾何平均方法對前一步驟的比較矩陣進行歸一化來計算每個因素的總權(quán)重。如下等式：

其中aij是比較矩陣Af的元素值。

在計算歸一化的比較矩陣之后，可以如下等式所示計算總權(quán)重向量。

2.5 一致性檢驗

層次分析法的最后一步是計算成對比較矩陣的檢驗系數(shù)。檢驗系數(shù)（C.R.）是根據(jù)人為判斷和感知衡量比較矩陣的一致性。如果C.R.＜0.1 ，則認為該比較矩陣通過一致性檢驗，否則就不具有滿意一致性。檢驗系數(shù)可以計算為：

λ 為比矩陣的最大特征值，用最大特征值對應的特征向量作為被比較因素對上層某因素影響程度的權(quán)向量。CI 越大，不一致越嚴重。由此可得比較矩陣最大特征值λ=4.0263，C.I.=0.0088，C.R.=0.0097。根據(jù)結(jié)果，當C.R. ＜0.10 時，比較矩陣的一致性是可以接受的，否則應該修改比較矩陣。所以Af是可以接受的，對應于A 的最大特征值的單位特征向量為：

因此得出影響程度的大小順序為：交通狀況、交通流量、道路質(zhì)量和天氣狀況。

2.6 權(quán)重的運用

在通過一致性檢驗后，計算出阻抗因素權(quán)重向量，將使用此權(quán)重向量計算出每條路線的總權(quán)重，把總權(quán)重代替經(jīng)典A*算法中權(quán)重因子[4]。但由于各個阻抗因素的測量單位不一致，因此需要對阻抗因素進行歸一化。為了更接近實際情況，每個阻抗因素需根據(jù)實際情況采用不同的方式進行歸一化，如天氣因素所占比重低，說明在進行歸一化時需最小化來選擇最佳路徑。交通狀況因素所占比重高，說明在進行歸一化時需最大化來選擇最佳路徑。對于那些需要最大化的因素，歸一化公式如下：

最小化所采取的的歸一化公式：

最終道路權(quán)重為：

3 實驗與分析

本文利用改進的A*算法對交通網(wǎng)絡(luò)圖進行加權(quán)搜索。測試的地圖，包括周邊城市區(qū)域，來自于地理信息系統(tǒng)。搜索結(jié)果如下所示：

表2 結(jié)果對比

我們改進了經(jīng)典的A*算法，將其權(quán)重因子替換為層次分析法法中的總權(quán)重因子。此外，我們還對改進后的算法進行了測試，并與經(jīng)典的A*算法進行了比較。結(jié)果表明，該方法比經(jīng)典的A*算法更有效。