淺述基于交通信息更新的變權(quán)值的最快路徑算法
相關(guān)鏈接： 中國安全網(wǎng) 中國質(zhì)量網(wǎng) 中國論文網(wǎng) 中國資訊網(wǎng)
【摘要】最短路徑分析是GIS網(wǎng)絡(luò)分析的基礎(chǔ)。在傳統(tǒng)的最短路徑算法中，Dijkstra算法是很經(jīng)典的算法。由于在最短路徑規(guī)劃中，影響規(guī)劃的外在因素較多，而且這些因素或者是隨時間變化的，或者是隨機發(fā)生的，為了得到當前最優(yōu)的規(guī)劃路徑，我們提出了基于交通信息更新的路徑規(guī)劃算法，當交通信息更新時，根據(jù)交通信息實時生成Dijkstra算法鄰接矩陣的權(quán)值，規(guī)劃當前的最優(yōu)路徑。
論文關(guān)鍵詞：交通信息更新,Dijkstra,鄰接矩陣,最短路徑
隨著計算機技術(shù)以及地理信息科學(xué)技術(shù)的發(fā)展，GIS（Geography Information System）因其強大的功能和方便性而得到日益廣泛的應(yīng)用，在電子導(dǎo)航、交通旅游、城市規(guī)劃以及電力、通訊等各種應(yīng)用布局中發(fā)揮了重要的作用。在GIS的應(yīng)用中，導(dǎo)航路徑的規(guī)劃即最短路徑問題是一個最基本最關(guān)鍵的問題。人們做了很多工作，提出了相當多的最短路徑算法，其中Dijkstra算法是一個相當經(jīng)典的算法。在Dijkstra算法中，算法依據(jù)一個權(quán)值矩陣對這些權(quán)值做相應(yīng)的計算得出最短路徑。但是我們知道GIS網(wǎng)絡(luò)是一種時變網(wǎng)絡(luò)，網(wǎng)絡(luò)的拓撲結(jié)構(gòu)、各邊的權(quán)值都可能隨著時間的變化而變化的[1]。在現(xiàn)有的已經(jīng)應(yīng)用的導(dǎo)航設(shè)備中，導(dǎo)航路徑規(guī)劃使用的地圖是設(shè)備上已經(jīng)存在的地圖[2]，規(guī)劃時不考慮外界的影響因素，或者即使有的設(shè)備在道路的屬性中新增加了幾個影響規(guī)劃的屬性值，但是這些屬性所在的地圖是沒有及時更新的，這些屬性值當然也是不會變化。影響道路規(guī)劃的因素極可能是突然變化的，如果在規(guī)劃的時候不實時考慮外在的因素影響，顯然做出的規(guī)劃不一定是最好最合理的，由此在規(guī)劃的過程中實時考慮外在因素的影響是必須的。本文在研究了影響網(wǎng)絡(luò)拓撲結(jié)構(gòu)、各邊權(quán)值的因素的前提下，提出了一種基于交通信息更新的Dijkstra最快路徑規(guī)劃算法。
2 影響導(dǎo)航路徑規(guī)劃的外在因素
影響導(dǎo)航路徑規(guī)劃的外在因素有很多，我們必須認真地對這些影響因素逐一進行分析，以確保高效實現(xiàn)最優(yōu)路徑規(guī)劃。而每個影響因素對路徑規(guī)劃的影響程度也不同，為此要對這些影響因子進行度的量化。
�。�1）交通擁擠度[3][4]。交通擁擠度是路徑規(guī)劃的最大影響因素，我們都有這樣的感受，特別是在城市里面上下班的高峰期，某些路口的交通擁擠程度是很大的，如果擁擠度足夠大，我們幾乎可以在導(dǎo)航路徑的規(guī)劃中不選擇這條路，也就是認為這個路口不同，最大限度的避開。
（2）交叉口延誤[3][4]。在實際出行中，擁堵和延誤常常發(fā)生在交叉口[5]，比如等待紅綠燈，據(jù)研究行駛在城市路網(wǎng)的車輛，在交叉口所耗費的時間大約占整個出行時間的20%--40%。
�。�3）道路等級[3][4]。在城市道路網(wǎng)中，不同級別道路的設(shè)計車速是存在差異的，這當然也影響著路徑的選擇。在相同的交通狀態(tài)下，選擇級別較高的道路應(yīng)該是最好最節(jié)省時間的。
（4）交通事件[[3][4]。交通事件主要指道路施工維修、臨時交通管制、車輛故障、路面損壞等有可能發(fā)展成為交通擁擠和交通事故的事件。道路施工、車輛故障、路面狀況的改變（損壞、積水、積雪）會占用車道，臨時交通管制會改變道路通行方式。這些交通事件的發(fā)生將會阻礙車輛通行的速度，降低道路的通行能力，增加出行延誤時間。在計算路段和節(jié)點權(quán)值時應(yīng)該考慮這些影響因素。
�。�5）交通組織[3][4]。交通組織主要是指交叉口的轉(zhuǎn)向限制（禁左、禁右）以及路段對車輛的限制（車輛類型、最大速度、路障等等），而現(xiàn)實中某些交通限制往往是與時間相關(guān)的，某些時間段可以通行，某些時間段卻又禁止通信等。
�。�6）氣象環(huán)境[3][4]。霧、雨、雪、風(fēng)和雷等氣象環(huán)境狀況，都會嚴重影響行車安全，特別是行駛在高速公路上的車輛。因此，有必要的在路段和節(jié)點的權(quán)值上加入天氣因素，以體現(xiàn)氣象環(huán)境對路徑選擇的權(quán)值確定和影響。
3 基于交通信息更新的最快路徑規(guī)劃算法
分析上述因素我們知道，這些因素幾乎都是隨著交通狀況或者天氣狀況或者時間變化的，最快路徑的規(guī)劃，都要考慮到這些因素的影響，而這些影響統(tǒng)統(tǒng)都反映在Dijkstra算法的鄰接矩陣的權(quán)值當中，所以如何計算權(quán)值，權(quán)衡各個因素的影響比重就成了問題的關(guān)鍵。下面給出我們的權(quán)值算法主要分兩步：（1）計算出各因素的固定影響值；（2）根據(jù)交通狀況實時計算路段此時的權(quán)值。
3.1 計算各個因素的固定權(quán)值
下圖給出了道路權(quán)值指標體系圖[3][4]，直觀反應(yīng)了影響道路權(quán)值的因素
圖1 道路權(quán)值指標體系圖
確定判定量化的標度，將影響因素兩兩比較，根據(jù)表1的原則，構(gòu)建判定矩陣表2。
表1 判定矩陣標度含義
標度
含義
1
兩個因素同等重要
2
兩個因素相比，一個比另一個較重要
3
兩個因素相比，一個比另一個重要
4
兩個因素相比，一個比另一個很重要
5
兩個因素相比，一個比另一個非常重要
倒數(shù)
因素Bj與Bi比較時，標度為aji=1/aij
表2 判定矩陣
B1
B2
B3
B4
B5
B6
B1
1
1
4
3
3
5
B2
1
1
4
3
3
5
B3
1/4
1/4
1
1/2
2
5
B4
1/3
1/3
2
1
2
5
B5
1/3
1/3
1/2
1/2
1
5
B6
1/5
1/5
1/5
1/5
1/5
1
用MATLAB計算出判定矩陣的特征值，最大特征值為6.3947，最大特征值相應(yīng)位置的值就是對應(yīng)因素的相對權(quán)重數(shù)據(jù)如下表：
表3 各因素相對權(quán)值
w1
w2
w3
w4
w5
w6
0.6363
0.6363
0.2292
0.3055
0.1971
0.0743
若影響道路權(quán)值確定的影響因素B1，B2，……B6的無量綱化的結(jié)果為b1，b2，……b6,則為道路增加六個屬性值，將di=wi*bi 作為對應(yīng)因素的固定影響值保存其中。
3.2 根據(jù)交通信息實時計算出當前的道路權(quán)值
為了體現(xiàn)各個因素的影響的實時性，對各個因素進行分級[6]，各個級別對道路權(quán)值的貢獻度是不一樣的，比如對道路的擁擠度我們可以分為表4級別并規(guī)定其各個級別的貢獻率：
表4 交通擁擠因素的擁擠度劃分以及各個擁擠度的貢獻率
擁擠度
暢通
正常
輕微擁擠
擁擠
嚴重擁擠
貢獻率
0
0.25
0.50
0.75
1
設(shè)貢獻率為參數(shù)m，貢獻值為n，固定影響值為d，則貢獻值為：
根據(jù)當前的交通信息，計算出各因素的貢獻值，再加上道路長度對時間的影響就是此時這段道路的權(quán)值：
（ni為因素i的貢獻值，L0為道路長度，V0為路段速度）
計算出每條道路的權(quán)值以后，就可以依據(jù)Dijkstra算法，規(guī)劃出當前最優(yōu)路徑，當交通信息再度發(fā)生變化時就觸發(fā)重新計算各個道路的貢獻值（其中只有貢獻率是可能變化的，固定權(quán)值是不會發(fā)生變化的），重新規(guī)劃當前最優(yōu)的路徑。當然，上述算法還可以做些優(yōu)化，比如對某一導(dǎo)航設(shè)備，離該設(shè)備很遠的交通信息的更新對設(shè)備導(dǎo)航幾乎是沒有影響的，設(shè)備也就無需進行路徑更新；路徑規(guī)劃過程中，與規(guī)劃相關(guān)的道路畢竟是離現(xiàn)在的源地址和目的地址較近的道路，所以沒有必要開始就更新所有道路的當前權(quán)值。
4 實際應(yīng)用
在基于移動GIS的旅游導(dǎo)航設(shè)備的開發(fā)中，用超圖公司的eSuperMap2008V5·3·0作為地圖操作組件。eSupermap是允許對地圖進行編輯的、增加屬性的，我們給每條道路增加六個非系統(tǒng)屬性來對應(yīng)存放六個因素的影響值，并且緩存當前的交通信息狀況。同時eSupermap允許繼承它的路徑分析類CSePathAnalyst，重載它的函數(shù)GetDistance。這樣在用函數(shù)CreateMatrix生成鄰接舉證的時候我們就把這六個影響因素考慮進去，生成算法對應(yīng)的鄰接矩陣，進行最快路徑分分析，一旦有交通信息的更新，就根據(jù)當前的交通狀況生成新的鄰接矩陣，得出當前的最快路徑。
為了更為直觀的展示算法，可以用圖2的道路交通網(wǎng)為一個實例進行驗證。
圖2 一個簡單的道路交通網(wǎng)
假定現(xiàn)在汽車行駛到了A點，目的地是B，道路AC、AB、CB的速度限制、轉(zhuǎn)向規(guī)則等都一樣，并且假設(shè)路段長度AB為10，AC為7，CB為8，限速為5，交通擁擠的影響值為3，事故影響值為3。在沒有任何交通擁堵和交通事故即交通擁擠和交通事故的貢獻率為0的情況下，走AB路段是最快的，因為AC+CB>AB。假設(shè)汽車行駛到A點時收到交通信息更新消息，路段AB中發(fā)生嚴重的交通事故，在以往不考慮影響因素的情況下，肯定還是走AB路段的，但是本算法考慮這些并且重新生成鄰接矩陣，生成當前的最快路徑，在此時，對于AB路段，顯然交通擁擠的貢獻率為1，交通事故的貢獻率也為1，此時AB的權(quán)值就為（1*3+1*3+10/5=8）,而走AC的權(quán)值是（7/5=1.4）。CB段的權(quán)值是（8/5=1.6）。很明顯此時走AC、CB路段比走AB路段更快。
5 結(jié)束語
傳統(tǒng)的導(dǎo)航路徑規(guī)劃中，影響道路最快路徑規(guī)劃的外在因素是沒有在考慮其中的，這樣規(guī)劃出來的道路不一定是最優(yōu)的，或者說可能是錯誤的。影響道路最快路徑規(guī)劃的外在因素是與時間有關(guān)的，也可能瞬時變化的，為了規(guī)劃出當前最優(yōu)的路徑，就必須把這些因素考慮在內(nèi)，當影響因素發(fā)生變化時候，重新進行路徑的規(guī)劃。本文就實時規(guī)劃的權(quán)值做了研究，將影響因素綜合起來考慮，實時計算道路的當前權(quán)值，規(guī)劃出當前的最快路徑，當然這其中很多的參數(shù)是可能發(fā)生變化的，比如相對權(quán)重是可能發(fā)生變化的，或者這個參數(shù)不是最優(yōu)的，這還需要我們繼續(xù)做深入的研究。
參考文獻
[1] 胡騰波，葉建栲. GIS時變權(quán)值玩過最短路徑算法研究[J]. 計算機與現(xiàn)代化,2008,2:22-24.
[2] 胡錢錢，李莉.導(dǎo)航電子地圖的更新機制與技術(shù)方法[J].地理信息世界，2008，1:77-82.
[3] 溫惠英，沈毅賢.基于層次分析法的物流配送車輛導(dǎo)航路徑規(guī)劃求權(quán)方法[J]. 公路交通科技,2008,25(8):114-118.
[4] 溫惠英，沈毅賢.適于物流配送車輛導(dǎo)航路徑規(guī)劃的路網(wǎng)阻抗確定方法研究[J]. 交通科技,2008,226:94-97.
[5] 瞿嶸，翁敏，杜清遠. 最簡單路徑尋找方法研究. 測繪科學(xué),2008,33(6):130-132.
[6] 靳引利，王軍.高速公路網(wǎng)中的Dijkstra最短路徑優(yōu)化算法[J]. 現(xiàn)代電子技術(shù),2008,21:188-191
