摘 要：Dijkstra算法是在道路網(wǎng)中選取最短路徑，這是一個事先的選擇過程，是理想的靜止?fàn)顟B(tài)下的計算，所得的最短路徑在現(xiàn)實中往往不會是最佳的路徑。在車輛實際運行中，路況信息也就是道路權(quán)重值是隨時動態(tài)變化的，這就要求能對最短路徑進(jìn)行重新的計算。針對Dijkstra算法存在的弊端，本文利用動態(tài)最短路徑搜索方法進(jìn)行了優(yōu)化改進(jìn)。

關(guān)鍵詞：Dijkstra算法；最短路徑；優(yōu)化

1 Dijkstra算法分析

Dijkstra算法的計算是從路段長度的集合S中進(jìn)行最短路徑的對比選取，算法的速度與集合S的大小有直接的關(guān)系。城市的道路網(wǎng)中從V到Vi的最短路徑為d（V，Vi），則d（V，Vi）中包含了所有滿足d（V，r）< d（V，Vi）的頂點r，也就是集合S。在這個算法中，不僅僅計算了點V到Vi的最短路徑，而且也計算得出了V到S集合中全部頂點的最短路徑，這就產(chǎn)生了大量的無用頂點r，集合S越大則所需要計算的頂點r的數(shù)量越多，所占用的時間也就越多。如果城市的道路網(wǎng)比較大，兩目的地之間的距離越遠(yuǎn)，在Dijkstra算法中所計算的頂點r甚至?xí)椴汲鞘械缆肪W(wǎng)中所有的頂點，這就增加了算法的額外運算量，降低了效率。

2 Dijkstra算法改進(jìn)

現(xiàn)在的城市救援車輛基本上已經(jīng)全部安裝了GPS定位裝置，可以實時的確定車輛的位置，這就為動態(tài)最短路徑搜索方法的實現(xiàn)提供了設(shè)備上的支持。

動態(tài)最短路徑搜索方法簡單來說就是在車輛運行過程中，根據(jù)實時的車輛位置和路況信息進(jìn)行最短路徑的搜索，它的搜索范圍僅局限在車輛所在位置周圍一定的距離。在這種算法中雖然有固定的起點和目的地，但是在路徑的選取中主要是根據(jù)車輛在道路上實際運行情況來確定每段道路的終點，也就是將起點與最終的目的地之間劃分成一個個的短的區(qū)間，求解每個區(qū)間之間的最短路徑。在車輛實際運行中經(jīng)常會遇到兩種情況：一種是車輛偏離預(yù)定路線比如走錯路轉(zhuǎn)錯方向，無法按照預(yù)定的路線行駛；另一種是在車輛運行中路況發(fā)生變化如發(fā)生擁堵，在動態(tài)最短路徑選擇的方法下可以很好的解決此類問題。

動態(tài)最短路徑搜索方法具有很大的靈活性和實用性，它的搜索范圍僅在車輛周圍所涉及的道路節(jié)點長度信息要比Dijkstra算法中少得多，因此計算所用的時間要短的多，而且所的到的最終路徑可以認(rèn)為是一條最佳的路徑。

本文在動態(tài)最短路徑選擇方法下對Dijkstra算法進(jìn)行了優(yōu)化改進(jìn)。

在該方法中首先要確定一個車輛道路通行時間的計算公式，本文采用如下公式進(jìn)行計算：

（1）

式中：

--車輛在a路段的通行時間；

--a路段的長度；

--車輛平均車速；

α、β--道路參數(shù)；

--a路段的交通流量；

--單位時間內(nèi)a路段最大通過車輛數(shù)。

改進(jìn)后的計算方法步驟如下：

（1）將道路網(wǎng)數(shù)據(jù)進(jìn)行劃分

將起點V與目的地Vi之間的路段劃分成n個區(qū)域，n的取值由兩點之間的直線距離決定，距離越遠(yuǎn)n越大。劃分成n個區(qū)域后，按照一定的范圍將每個區(qū)域內(nèi)的所有路段長度用集合Dn（li）分別存儲。

（2）提取道路通行時間最短的路段

先在第一個路段區(qū)域內(nèi)的路段長度集合D1（li）中，運用上述公式（1）計算得出每段路當(dāng)前路況下的通行時間[ti]，將[ti]按照時間的長短進(jìn)行序列排隊，則通行時間最短的ta所代表的路段a就是最佳的路徑選擇。依次類推可以求的n個區(qū)域內(nèi)的n條最佳路徑。

（3）動態(tài)調(diào)節(jié)

車輛由上步確定的第一條最佳路徑出發(fā)后，根據(jù)車輛GPS的實時定位信息和實際的車輛運行情況進(jìn)行路徑的動態(tài)調(diào)節(jié)。如果沒有遇到影響通行時間的情況，車輛就按照既定的路線行駛。當(dāng)車輛在道路行駛中遇到擁堵或偏移預(yù)定路線的情況時，將此時GPS定位的車輛位置點作為新的出發(fā)點，重復(fù)（1）操作重新進(jìn)行區(qū)域劃分，然后實施步驟（2），計算新的最佳路徑，并反饋給道路上的車輛進(jìn)行及時的調(diào)節(jié)。

（4）重復(fù)步驟（3）的操作，直到車輛到達(dá)目的地。

這種算法將路網(wǎng)信息進(jìn)行了分區(qū)劃分，并且只選取一定范圍內(nèi)的道路信息，這樣就使的在計算過程中所要計算的數(shù)據(jù)量大大減少，調(diào)高了算法的效率。并且在該算法中是按照車輛實時前進(jìn)方向的道路位置進(jìn)行道路數(shù)據(jù)的選取，避免了對已通過路段信息的重復(fù)計算。Dijkstra算法的路徑搜索范圍可以看成是以起點和目的地之間距離為半徑的圓形區(qū)域，而改進(jìn)后的算法則可以看成是以起點和目的地為頂點的橢圓形區(qū)域如圖1所示，由圖可以很直觀的看出改進(jìn)后的算法要明顯比原Dijkstra算法的數(shù)據(jù)搜索和處理量少很多。

圖1 Dijkstra算法與改進(jìn)算法搜索范圍對比

3 小結(jié)

本文針對城市救援中的最短路徑Dijkstra算法進(jìn)行了分析，針對其弊端采用動態(tài)最短路徑搜索的方法進(jìn)行了改進(jìn)，當(dāng)然這種算法求得的最終路徑長度并不是最短的，但它以道路通行時間最短為標(biāo)準(zhǔn)，是符合城市應(yīng)急救援車輛要求的一種算法，這對救援最佳路線的選擇具有重要的現(xiàn)實意義和應(yīng)用價值。

參考文獻(xiàn)

[1]劉根生，蘇飛，趙娣.基于Dijkstra算法的兩點間多目標(biāo)最優(yōu)路徑問題建模和優(yōu)化[J].池州師專學(xué)報.2007.21（3）：17-22.

[2]周玉清，張紅梅.多源最短路徑Floyd算法的分析與實現(xiàn)[C].第四屆海峽兩岸GIS發(fā)展研討會暨中國GIS協(xié)會第十屆年會，云南，2006.

作者簡介：

王廷（1985.6--）男，漢族，山東泰安人，助教，碩士，主要從事工程測量教育教學(xué)研究。