宮恩超，李魯群

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

基于Bellman-Ford算法的動態(tài)最優(yōu)路徑算法設(shè)計

宮恩超，李魯群

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

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

動態(tài);Bellman-Ford算法;最優(yōu)路徑

一、引 言

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

二、國內(nèi)外研究現(xiàn)狀

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

三、提出算法

1.Bellman-Ford算法流程

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

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

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

2.Bellman-Ford算法的優(yōu)勢

1)Bellman-Ford算法可以處理交通網(wǎng)絡(luò)中出現(xiàn)的負(fù)權(quán)回路問題，如將向某一方向行駛的車輛的權(quán)值設(shè)為正，與此方向相反的權(quán)值就為負(fù)，Dijkstra算法在處理此類負(fù)權(quán)回路問題時會陷入無限死循環(huán)。

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

3.動態(tài)最優(yōu)路徑算法

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

四、算法實現(xiàn)

1.實時交通流量模擬

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

2.使用的關(guān)鍵函數(shù)及數(shù)據(jù)結(jié)構(gòu)

(1)Bellman-Ford函數(shù)

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

其中的參數(shù)代表的意義分別是邊、節(jié)點數(shù)量、最優(yōu)路徑的源點、目標(biāo)點。返回的是最優(yōu)路徑經(jīng)過的路徑數(shù)組，用來在地圖窗口中描繪出最優(yōu)路徑。

(2)路徑數(shù)據(jù)存儲結(jié)構(gòu)

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

3.動態(tài)最優(yōu)路徑選擇解決思路

在車輛行駛到達(dá)新的路徑后根據(jù)啟發(fā)算法的one-step-look-ahead策略［8］，將新路徑的起點作為動態(tài)最優(yōu)路徑算法的源點參數(shù)，與此同時對交通網(wǎng)絡(luò)的附加權(quán)重重新模擬實現(xiàn)實時變化的交通流量，這樣由動態(tài)最優(yōu)路徑算法得到了不斷更新的最優(yōu)路徑，從而實現(xiàn)了最優(yōu)路徑的實時動態(tài)選擇。

五、實際應(yīng)用及試驗結(jié)果對比分析

1.實際應(yīng)用

京藏高速公路堵車現(xiàn)象頻繁發(fā)生，長時間的交通堵塞不僅對當(dāng)?shù)氐某鲂性斐闪藝?yán)重的影響，而且對當(dāng)?shù)氐穆糜螛I(yè)、郵政等也造成諸多影響。這一路段堵車現(xiàn)象頻發(fā)的主要原因有兩方面:一是由于這一路段的車流量大、關(guān)卡較多容易引起車輛堵塞;二是車流量的調(diào)度出現(xiàn)了問題。在出現(xiàn)了交通擁堵情況時，由于司機不知道前方的交通已經(jīng)出現(xiàn)了問題，交管部門又未能及時地發(fā)出警告信息，導(dǎo)致車輛源源不斷地駛向擁堵路段。針對車流量的合理調(diào)度問題，本文提出的動態(tài)最優(yōu)路徑選擇算法提供了有效的解決方法，在面對突發(fā)的交通堵塞情況時能及時對車流進(jìn)行分流，在節(jié)約司機行駛時間、提升行駛效率、合理利用交通道路等方面表現(xiàn)突出。

2.試驗結(jié)果對比分析

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

具體模擬如表1所示。

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

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

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

圖1 程序運行過程

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

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

4)動態(tài)最優(yōu)路徑選擇過程如表2所示。

表2 動態(tài)最優(yōu)路徑選擇過程

3.當(dāng)遇到交通堵塞時，靜態(tài)與動態(tài)路徑選擇結(jié)果的對比分析

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

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

3)實際進(jìn)行了路徑動態(tài)選擇的最優(yōu)路徑的總權(quán)重為weight2=1 107。

4)實施了動態(tài)最優(yōu)路徑算法節(jié)約的權(quán)重為weight1-weight2=436.7。

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

6)多次路徑動態(tài)運行結(jié)果及對比分析如表3所示。

表3 多次路徑動態(tài)運行結(jié)果對比分析

六、結(jié)束語

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

［1］ 翁敏，毋河海，杜清運，等.基于道路網(wǎng)絡(luò)知識的啟發(fā)式層次路徑尋找算法［J］.武漢大學(xué)學(xué)報:信息科學(xué)版，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］ 任剛，王煒，李巖.交通建模中的最優(yōu)路徑算法研究綜述［C］∥第一屆中國交通地理信息系統(tǒng)(GIS-T)技術(shù)研討會論文集.武漢:武漢大學(xué)交通研究中心，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算法的無人機路徑規(guī)劃研究［J］.彈箭與制導(dǎo)學(xué)報，2007，27(5):249-251.

［7］ 章昭輝.一種基于離散變權(quán)網(wǎng)絡(luò)的動態(tài)最短路徑快速算法［J］.計算機科學(xué)，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空間分析算法及空間信息相關(guān)無線傳感器網(wǎng)絡(luò)路由算法。