基于Bellman-Ford算法的動態最優路徑算法設計

宮恩超，李魯群

(上海師范大學信息與機電工程學院，上海200234)

基于Bellman-Ford算法的動態最優路徑算法設計

宮恩超，李魯群

(上海師范大學信息與機電工程學院，上海200234)

針對動態變化交通流下的最優路徑問題，提出基于Bellman-Ford算法的動態最優路徑算法。并用試驗與仿真說明該算法可以迅速完成動態最優路徑的計算。結果顯示，在處理該路段突發的交通堵塞狀況時，該算法可以節約行駛權重百分比大約在30%～60%。

動態;Bellman-Ford算法;最優路徑

一、引 言

GIS對空間最優路徑分析主要基于Dijkstra算法，如ArcInfo中的Network采用二叉堆優先級隊列來實現Dijkstra算法，GeoStar的網絡分析采用快速排序的FIFO隊列來實現Dijkstra算法。隨著計算機網絡、數據采集系統的技術進步，人們已經可以快捷地實時獲取瞬息萬變的動態交通路況信息，在這種情況下，實時進行空間分析規劃動態最優路徑已經成為當今亟待解決的問題之一。傳統靜態的Dijkstra算法已無法解決交通網絡中的實時導航、通勤、調度等時刻變化的交通流量情況。針對該問題，本文提出基于Bellman-Ford算法的動態最優路徑算法來實現動態交通流量下的最優路徑計算。

二、國內外研究現狀

目前針對動態最優路徑問題的研究主要集中在兩方面:①從算法本身分析并改進，力求在算法時間復雜度上不斷取得突破;②對交通網絡結構進行相應的預處理工作，例如將交通網絡分層，高層次的網絡是主干道，用主干道將整個網絡分成多個自然網絡。在路徑查詢時逐步削減初始圖，即網絡低層次的起點或終點總是向毗鄰的高層次上溯。每當找到進入毗鄰高層次的最合理的出入口時，就在高層次的子網中繼續搜索出入點之間的路徑［1］。相關研究主要以啟發式搜索算法為代表。啟發式搜索算法就是一種針對實時動態改變的網絡特征，從傳統最優路徑算法衍生的動態最優路徑算法。在搜索過程中盡量利用目前已知的諸如迭代步數以及從初始狀態和當前狀態估價所需要的費用等信息，采用限制搜索范圍、分解搜索目標等策略［2］。雖然它是一種以精度換速度的搜索方法［3］，但在動態最優路徑的實現上提供了精確的解決方案，使最優路徑的選擇具有智能性。subgoals method［4-5］最優路徑解決思路就是啟發式搜索的一個典型代表，subgoals在最優路徑中可被看做源點與目標節點之間的中間節點或鏈接，這樣最優路徑問題就被分解為2個或多個子問題。一個被用來尋找從源點到subgoals節點的最優路徑，另一個被用來尋找從subgoals節點到目標節點的最優路徑。

三、提出算法

1.Bellman-Ford算法流程

1)初始化:將除源點外的所有頂點的最優距離估計值d［v］←+∞，d［s］←0。

2)分布式迭代求解:反復對邊集E中的每條邊進行松弛操作，使得頂點集V中的每個頂點v的最優距離估計值逐步逼近其最優距離(運行|v|－1次)。

3)檢驗負權回路:判斷邊集E中的每一條邊的兩個端點是否收斂。如果存在未收斂的頂點，則算法返回false，表明問題無解;否則算法返回true，并且從源點可達的頂點v的最優距離保存在d［v］中。

2.Bellman-Ford算法的優勢

1)Bellman-Ford算法可以處理交通網絡中出現的負權回路問題，如將向某一方向行駛的車輛的權值設為正，與此方向相反的權值就為負，Dijkstra算法在處理此類負權回路問題時會陷入無限死循環。

2)與Dijkstra算法相比，雖然Bellman-Ford算法的復雜度較大，然而需要進行實時動態的路徑規劃時，Bellman-Ford算法又呈現出其他算法所不具備的優點。如迭代次數少，迭代過程靈活，可以進行異步、實時、分布式的規劃，當威脅概率發生變化時，無需終止和重啟算法，只需更新帶權圖G(V，E)的各邊的權即可［6］。

3.動態最優路徑算法

基于啟發式搜索的思想，本文將subgoals method的思想融入到Bellman-Ford算法的搜索判斷過程中，并提出了動態最優路徑算法。通過考察源點與待選點之間，以及待選點與目標點之間的路況變化情況，利用下一個點到目標點之間的最優距離作為選擇啟發步。在所有起始點到待選點實際花費時間與待選點到目標點的評估時間之和中選擇最小的一個，則對應的待選點為當前點，繼續考慮下一步的起始節點，直到選到目標點為止［7］。

四、算法實現

1.實時交通流量模擬

實時變化的交通流量的模擬使用1～100的隨機數，將其作為附加權重附加到路徑的長度權重中，一起作為動態最優路徑算法的權重選項參與最優路徑計算，在交通網絡中用路徑上數量不同的點來體現該路段上的實時交通路徑，點越多表示交通流量越大。在實際應用中可以將路徑上的車的數量、道路平整度、寬度等影響因子作為考察對象并作為附加權重，車數量的統計可以使用GPS對每一輛車進行定位，這樣就可以方便、實時地統計出路徑上車的數量信息。

2.使用的關鍵函數及數據結構

(1)Bellman-Ford函數

int［］bellmanFord(Vector＜Edge＞edges，int nnodes，int source，int dest)

其中的參數代表的意義分別是邊、節點數量、最優路徑的源點、目標點。返回的是最優路徑經過的路徑數組，用來在地圖窗口中描繪出最優路徑。

(2)路徑數據存儲結構

Edge(int source，int dest，double weight)3個參數值分別代表邊的起點、終點、權重。通過有向圖的方式將交通路徑數據存儲起來。

3.動態最優路徑選擇解決思路

在車輛行駛到達新的路徑后根據啟發算法的one-step-look-ahead策略［8］，將新路徑的起點作為動態最優路徑算法的源點參數，與此同時對交通網絡的附加權重重新模擬實現實時變化的交通流量，這樣由動態最優路徑算法得到了不斷更新的最優路徑，從而實現了最優路徑的實時動態選擇。

五、實際應用及試驗結果對比分析

1.實際應用

京藏高速公路堵車現象頻繁發生，長時間的交通堵塞不僅對當地的出行造成了嚴重的影響，而且對當地的旅游業、郵政等也造成諸多影響。這一路段堵車現象頻發的主要原因有兩方面:一是由于這一路段的車流量大、關卡較多容易引起車輛堵塞;二是車流量的調度出現了問題。在出現了交通擁堵情況時，由于司機不知道前方的交通已經出現了問題，交管部門又未能及時地發出警告信息，導致車輛源源不斷地駛向擁堵路段。針對車流量的合理調度問題，本文提出的動態最優路徑選擇算法提供了有效的解決方法，在面對突發的交通堵塞情況時能及時對車流進行分流，在節約司機行駛時間、提升行駛效率、合理利用交通道路等方面表現突出。

2.試驗結果對比分析

(1)各路徑權重與實時交通流量的模擬

具體模擬如表1所示。

表1 各路徑權重與實時交通流量的模擬

(2)程序運行過程及結果說明

1)程序運行的過程是判斷從node1到node13之間的最優路徑(如圖1所示)。

圖1 程序運行過程

2)圖1(a)中灰線表示車輛行駛的最優路徑，黑線表示模擬的擁堵路徑。灰線上的不同數量的節點意義是模擬行駛路徑上的實時交通流量情況，越多表示交通流量越大。

3)從圖1(a)上可以看出車輛行駛到Node3時，遇到了交通堵塞(圖1(a)上用黑線標明的路段)，于是程序進行了路徑的重新動態選擇，車輛選擇了避讓。從命令窗口程序(如圖1(b)所示)具體執行情況可以看出，車輛在行駛到Node3時由于路徑path17的擁堵，進行了實時的動態路徑選擇，將行駛路徑由原來的path17→path2變成了path19→path18→path8→path13→path15。

4)動態最優路徑選擇過程如表2所示。

表2 動態最優路徑選擇過程

3.當遇到交通堵塞時，靜態與動態路徑選擇結果的對比分析

1)前提條件為當遇到交通堵塞時，堵塞路徑上的實時權重模擬賦值為1 000+(100～200)之間的隨機數，未被堵塞的路徑上的實時權重模擬賦值為100～200之間的隨機數。

2)若按照原來的路徑(path17→path22)行駛，即沒有實行路徑的動態選擇過程則總權重為weight1=pw17+pw22+apw17+apw22=158.6 +102.1+1154.0+129.0=1 543.7。

3)實際進行了路徑動態選擇的最優路徑的總權重為weight2=1 107。

4)實施了動態最優路徑算法節約的權重為weight1-weight2=436.7。

5)節約權重大約百分比為(weight1-weight2)/ weitht1=28.28%。

6)多次路徑動態運行結果及對比分析如表3所示。

表3 多次路徑動態運行結果對比分析

六、結束語

本文提出的動態最優路徑算法，可以迅速計算出在發生交通堵塞情況時的動態最優徑。從多次的試驗結果可以看出，由于路徑長度的不同動態最優路徑算法較傳統靜態最優路徑算法節約權重大約在30%～60%之間，由此可以說明該算法在針對突發的交通堵塞情況下可以給出一個更加快速的最優路徑解決方案。

［1］ 翁敏，毋河海，杜清運，等.基于道路網絡知識的啟發式層次路徑尋找算法［J］.武漢大學學報:信息科學版，2006，31(4):360-363.

［2］ FUA L，SUNB D，RILETTC L R.Heuristic Shortest Path Algorithms for Transportation Applications:State of The Art［J］.Computers＆ Operations Research，2006，33(11):3324-3343.

［3］ 任剛，王煒，李巖.交通建模中的最優路徑算法研究綜述［C］∥第一屆中國交通地理信息系統(GIS-T)技術研討會論文集.武漢:武漢大學交通研究中心，2007: 1-8.

［4］ BANDER J L，WHITE C C III.A New Route Optimization Algorithm for Rapid Decision Support［C］∥Proceedings of Vehicle Navigation Information Systems Conference.Detroit:［s.n.］，1991:709-728.

［5］ DILLENBURG J F，NELSON P C.Improving Search Efficiency Using Possible Subgoals［J］.Mathematical and Computer Modelling，1995，22(4-7):397-414.

［6］ 張沖，朱凡.基于Bellman-Ford算法的無人機路徑規劃研究［J］.彈箭與制導學報，2007，27(5):249-251.

［7］ 章昭輝.一種基于離散變權網絡的動態最短路徑快速算法［J］.計算機科學，2010，37(4):238-240.

［8］ BASELAU S，HAHNE F，AMBROSI K.Operations Research Proceedings 2007［M］.Berlin:Springer，2008: 111-116.

The Optimal Path Algorithm Design Based on Bellman-Ford Algorithm

GONG Enchao，LI Luqun

0494-0911(2011)08-0026-03

P208

B

2011-01-26

宮恩超(1986—)，男，山東煙臺人，碩士生，主要研究方向為分布式GIS空間分析算法及空間信息相關無線傳感器網絡路由算法。