張 媛，劉 峰

　　（南京郵電大學 圖像處理與圖像通信江蘇省重點實驗室，江蘇 南京 210003）

　　摘  要： 采用改進的層次分析法分析道路狀況的多種因素，得出了當道路發生緊急事故時，符合時效性、安全性、經濟性的路段權值。然后根據實時交通信息，利用改進的Dijkstra算法，探索了路徑權重計算方法，建立了交通網絡的運行時間的加權圖，驗證了本方法在實際交通網絡中的應用，證實了方法的有效性和可行性。

　　關鍵詞： 智能交通系統；最優路徑；層次分析法；Dijkstra算法

0 引言

　　隨著城鎮人口的增長和可用物理空間的日益缺乏，交通管理面臨的挑戰越來越嚴峻，繼續擴大道路網絡來解決日益增長的交通需求已經被視為一個不可持續的方案。本文利用智能交通的動態路徑選擇思想，為駕駛員提供實時最優路徑，避開擁擠路段，或根據駕駛員需求提供最優路徑，實現智能且人性化的路徑誘導。在實際車輛行駛時，由A地到達B地的最佳路徑的標準不只是道路距離、路面質量、交通擁堵、駕駛習慣等因素中的某單一標準，從駕駛員心理角度出發，依據每個人內心的不同的標準，綜合考慮多種影響因素以后得出最能夠接受的方案，從而獲得車輛行駛的最佳選擇。

　　目前，有十多種計算最優路徑的方法，其中Dijkstra算法是理論上最完善的方法，已被GIS系統廣泛采用。同時它也存在以下缺點：（1）它的計算僅僅基于道路的長度，而不考慮影響道路交通的實際因素，如道路等級、道路上的交通擁堵等其他因素，所以在復雜的交通環境中結果往往并非最優。（2）在有大量節點的交通網絡中，拓撲結構中占用大量的存儲空間，且遍歷算法的搜索效率很低。

　　本文提出了層次分析法（Analytic Hierarchy Process，AHP）[1]的最優路徑選擇模型，運用運籌學中的AHP計算路徑的權重，然后利用改進的Dijkstra算法獲得最佳路徑。這種復雜的路徑決策算法可應用于復雜路況的選路，尤其適用于應急救援、多目標決策的情況。

1 路段權重的判定

　　1.1 層次分析法介紹

　　層次分析法是一種解決復雜、模糊問題的簡單決策方法，特別是如本文討論的“最優路徑”等難以進行定量分析的問題。現實情況是不僅道路的長度不同，受到交通狀況、路面質量、天氣條件等因素的影響，各道路上的車輛行駛時間都會不同。采用層次分析法，所有這些因素都被考慮，通過各自不同的重要性影響路徑權重。于是得到了一個更貼近現實的交通網絡有向圖加權圖。

　　通常，該方法可分為三個步驟：

　　（1）建立層次結構模型；

　　（2）構造各層次的判斷矩陣；

　　（3）實施層次排序和一致性檢驗。

　　1.2 建立層次分析法模型

　　本文考慮了現實條件下可能影響駕駛員路徑選擇的因素，除了一些常見的因素（如路徑距離，道路等級，車輛限制，交通流量，氣候條件）[2-4]以外，如果車輛前方路段突然發生車禍、坍塌等嚴重事故，可能造成交通完全癱瘓，嚴重影響車輛行駛的時間成本，所以獲得的實時前方路況需要實時更新。此外在復雜道路情況下，駕駛員對道路的熟悉程度也部分地影響了行駛時間。所以設定集合：S={路徑距離/車速，道路等級，交通流量，車輛限制，氣候條件，實時路況信息，駕駛熟悉度}。根據層次分析法的思想，將層次結構分為3層（如圖1所示），最上層為目標層：路徑權重W；中間層是準則層，即集合S中的各項指標；底層是方案層，即計算所得的最優路徑。

　　在使用AHP時，必須注意矩陣的一致性。如果不滿足一致性，則結果錯誤。Jiang Hua[5]提出的AHM方法可以避免檢測一致性，從而能確保決策不會出現：a>b，b>c，得出c>a這種情況。

　　1.3 計算基于實時交通信息的權重值

　　步驟1：利用層次分析法計算準則層各指標對于目標層的權重w1、w2、w3、w4、w5、w6、w7。

　　對準則層的各因素按1~9標度思想分別賦值，含義見表1[6]。

　　準則層的各個準則占最終結果的比重不一定相同，從駕駛員的需求出發，給它們設定不同的比例。由此構造出判斷矩陣，如表2所示。

　　步驟2：計算權重的方法有幾何平均法、算術平均法、特征向量法和最小二乘法。本文選用特征向量法，公式為：

　　AW=λmaxW（1）

　　λmax為判斷矩陣的最大特征值，存在唯一的W的分量為正分量，將求得的W作歸一化處理即為特征向量。

　　步驟3：上述方法計算的判斷矩陣通常是不一致的，為了獲得它對應于最大特征值的特征向量，被比較因素的權重向量不一致程度應在容許的范圍內，以保證其可靠性，所以必須進行一致性檢驗[7]。

　　一致性指標：

　　CI=（λmax-n）/（n-1）（2）

　　其中，n是A的階數。RI為平均隨機一致性指標，取值參考表3。

　　對判斷矩陣的一致性進行檢驗：

　　CR=CI/RI（3）

　　當CR小于10%時，認為判斷矩陣的一致性是令人滿意的，否則應當進一步修正判斷矩陣。

　　步驟4：在獲得了各因素的權重值以后，計算路段權重，并對路段權重進行等值的無量綱處理[8]。

　　W=s/v（w2r+w3l+w4f+w5w+w6m+w7c）（4）

　　其中s是實際路段長度，v是車輛平均行駛速度，s/v則是理想情況下車輛勻速行駛所用的時間；r是道路等級，根據公路的使用任務、功能和流量劃分為5個等級（0.2、0.4、0.6、0.8、1.0）；l是交通流量，與設計交通流量作比較，比值由低到高賦以[0，1]區間內的實數；f為車輛限制，表示不同類型車輛的通行是否受限于該路段，受限則f=1，否則f=0；w是天氣狀況，根據車輛行駛的適宜程度賦以[0，1]區間內的實數；m是實時路況信息，根據車輛獲得實時路況的能力賦以[0，1]區間的實數；c是駕駛員對路段的熟悉程度，駕駛員通常主觀傾向于自己較熟悉的道路，賦以（0，1）區間的實數，若取值在0附近，則選取的可能性較小。

　　步驟5：實時更新交通信息。

　　信息采集系統包括車輛信息采集設備和路邊信息采集設備，將采集的信息發送到信息監控中心。為了獲取各路徑交通信息，更好地實現交通誘導，本文設計了一種基于socket通信[9]的模擬車輛運行狀態采集方法，將車輛作為客戶機，采集中心作為服務器，采用TCP/IP通信協議。通信流程圖如圖2。

　　每一個客戶機代表一輛車，客戶機程序產生以下信息，向服務器發送，如表4。

　　服務器接收以上客戶機發送的數據，得出某一路段的實時道路信息，若大量車聚集在某一個路段，則可判斷該路段的權重增大。結合路邊信息采集設備獲得的數據和駕駛員自身判斷因素，可以得到準則層7個影響判決因素的模擬數值。

2 綜合最優路徑算法

　　2.1 Dijkstra算法介紹

　　Dijkstra[10]算法是圖論中求解最短路徑的一個著名的算法，用于求圖中一個節點到其他各個節點的最短路徑。將道路抽象為圖論中的邊，交叉口抽象為節點。道路相關的參數影響邊的權值，權值是廣泛的，可以表示速度、天氣情況、交通情況、距離等。衡量最短路徑的準則是計算出的路徑權值W的大小，并且邊的權值都是非負數。網絡中所有節點初始化為未標記節點，在搜索過程中與最短路徑中的節點相連通的節點稱為臨時標記節點，每次循環都從臨時標記節點開始搜索距源點最短的路徑長度的節點，將其變為永久標記節點。直到所有節點都成為永久標記節點，算法運行結束。

　　傳統的Dijkstra算法是從起點V到圖的剩余頂點的最短路徑的長度增加的序列，它用于解決有向加權圖的問題[11]。其基本思想是：首先建立一個節點集S，選擇貪婪算法不斷擴展集合S。假設所有節點的集合是V，S的初始值是源節點，T是存在于V中但不在S中的節點集，T的初始值是除源節點外的所有節點。T中的節點根據路徑長度的升序逐個進入S，直到可以從源節點到達的節點全部進入S。然而，把Dijkstra算法應用到基于GIS的應急救援體系，仍存在一定的不足：（1）該算法使用O（N2）的時間找到單源最短路徑，使其低效地處理GIS系統中的海量數據[12]。（2）在路徑信息不變的情況下，搜索相同一對源點和目的節點時，得到的路線應該是一樣的。但此算法每次尋路都要重新計算最短路徑，浪費時間。（3）在傳統圖論網絡分析中，每個路徑正反向權值是相同的。而實際交通中同一條道路兩個方向的路況可能差別非常大，所以在仿真時采用不同的權重因子更加符合現實情況。

　　2.2 對選路算法的改進

　　本論文對此提出以下改進：

　　（1）在GIS應急救援系統中因為交通網絡特征的動態變化特性，一般順序計算產生的最短路徑樹不能完全滿足需要。例如，當汽車到達節點3，發現道路L35交通堵塞非常嚴重時，必須重新尋路。這時，應重新選擇3的鄰接結點來計算最短路徑樹T。從動態變化的特性出發，本文采用了逆向運行的方法，即構建一個逆向的最短路徑樹[13]，使源節點是終節點，且起始節點設在分支節點。此改進適用于在行車至某一節點遇到前方路段突然發生車禍、坍塌等嚴重事故，造成交通完全癱瘓的情況。

　　（2）由于相同始末節點仍然會重新搜索，造成資源浪費，每次使用Dijkstra算法搜索完最優路徑后，將所有路段信息和最短路徑的信息加入到數據庫中。用戶需要選擇路線時，程序先搜索數據庫，將之前保存的路線反饋出來。當城市中道路狀況改變時，重新執行Dijkstra算法，更新數據庫中之前所有最短路徑信息[14]。

　　（3）在各指標對于目標層的權重系數中，交通流量、實時路況信息受到行駛方向影響較大，所以將這兩個因子根據路況靈活選取，其他因子在同一條道路上數值相同。正反兩個方向的計算結果可能完全不同。本文將一段路徑正反向的某些參數設為不同值，這樣更符合實際交通狀況。

3 最優路徑選擇仿真實驗

　　在研究各種路徑算法后，本文選擇在MATLAB平臺上，實現利用AHP計算權重的改進的Dijkstra算法作為最優路徑算法。

　　首先，根據表2的判斷矩陣A，計算可得特征向量w和特征值k。經計算最大特征值為：k=7.339 2，對應的歸一化特征向量為：

　　wT={0.4048，0.1184，0.1119，0.1592，0.1257，0.0478，0.0322}

　　通過MATLAB編程計算得到：

　　CI=0.056 5

　　CR=0.041 6

　　說明此矩陣的一致性可以接受。

　　然后，結合以下某地區的交通示意圖3，譬如節點7到12的距離為15 km；設計平均時速為80 km/h；道路等級為一級，r=0.4；實際交通流量l=0.6；路段對車輛通行無限制，f=0；該時段天氣良好，能見度較高，a=0.1；路段可以及時獲得前方的路況信息，m=0.2；司機較熟悉此路段，c=0.85。本題s／v以min作為單位。利用公式（4），計算得節點7到12的權值為16.3，其余路徑的權值略。

　　本實驗由于節點數量較多，僅測試由節點9到節點12的路徑，仿真結果如下：

　　起始點（9）到終止點（12）的路徑為：9→10→6→12

　　路徑權重：44.4

　　根據實時采集的交通信息，若大量車輛行駛在10→6路段，則該路段極其擁堵，此路段的交通流量l無限接近于1，計算路徑權重變為56.5，數值明顯增大。

　　再測試一次選路結果：

　　起始點（9）到終止點（12）的路徑為：9→11→4→7→12

　　路徑權重：45

　　可以看出，新選擇的最優路徑權重遠小于56.5，本算法是方便可行的，并且同時可以得到任意起點i到終點j的最短路徑。

4 結論

　　對于最優路徑算法的研究，本文充分考慮了各因素對行駛速度的影響，將層次分析法引入應急救援系統，分析計算得出了各因子的相對重要度。據此提出了一種基于實時路況的路徑權重計算方法，采用基于經典Dijkstra算法進行改進的路徑搜索算法，使計算值更符合現實，實現了系統的時效性、安全性、經濟性。在本文中，該算法模型在遇到緊急情況時，結合交通實況能做出最佳決策，具有很強的現實意義。

參考文獻

　　[1] Yang Fujin， Tan Wenan， Shen Weiming， et al. A dynamic critical path computation algorithm for enterprise process cooperative scheduling[C]. Computer Supported Cooperative Work in Design （CSCWD）， 2010 14th International Conference on. IEEE， 2010：606-610.

　　[2] Li Caixia， ANAVATTI S G， RAY T. Analytical hierarchy process using fuzzy inference technique for real-time route guidance system[J]. Intelligent Transportation Systems， IEEE Transactions on， 2014， 15（1）：84-93.

　　[3] Yang Shu， Li Chunhua. An enhanced routing method with Dijkstra algorithm and AHP analysis in GIS-based emergency plan[C]. Geoinformatics， International Conference on， 2010：1-6.

　　[4] Qi Guanghui， Huang Ronggang， Zhe Zeng， et al. An AHP based multi-factors weight method for route selection of oil and gas pipelines[J]. Science of Surveying and Mapping， 2013， 38（5）：122-125.

　　[5] Zhou Binbin， Chen Xuebo. Path selection algorithm based on AHP for small-world with three-weight[C]. Control and Decision Conference， Chinese.IEEE， 2014：3627-3631.

　　[6] 張慧.基于層次分析法的應急救援最優路徑選擇分析[J].交通標準化，2014（3）：68-71.

　　[7] Ma Wenjing， Xu Yingzhuo， Xie Hui.The optimal path algorithm for emergency rescue for drilling accidents[C].Network Infrastructure and Digital Content， 2009.IC-NIDC 2009.IEEE International Conference on. IEEE， 2009：866-870.

　　[8] 江文奇.無量綱化方法對屬性權重影響的敏感性和方案保序性[J].系統工程與電子技術，2012，34（12）：2520-2523.

　　[9] Song Guoqing. The study and design of network traffic monitoring based on socket[C]. Computational and Information Sciences （ICCIS）， 2012 Fourth International Conference on， 2012：845-848.

　　[10] YERSHOV D S， LAVALLE S M. Simplicial Dijkstra and A*algorithms： from graphs to continuous spaces[J]. Advanced Robotics， 2012， 26（17）：2065-2085.

　　[11] Yin Tieyuan， Yang Jianyong. Dynamic application of the path selection in the road[C]. Proceedings of 2010 IEEE International Conference on Software Engineering and Service Sciences， 2010.

　　[12] 李寬榮，陸通，高勇.一種基于STL的高效最短路徑算法[J].科技創新導報，2014（12）：37-37.

　　[13] 任剛，王煒.轉向約束網絡中的對偶最短路徑樹原理及其原型算法[J].交通運輸工程學報，2008，8（4）：84-89.

　　[14] 劉帥修.智能交通中的路徑選擇及其移動終端信息展示系統[D].南京：南京郵電大學，2012.