路網(wǎng)分層的改進A芯算法在智能交通系統(tǒng)中的應用論文
車輛最短路徑規(guī)劃是智慧交通的重要體現(xiàn)，而高效的算法是路徑規(guī)劃的核心。本文在經(jīng)典A*算法的基礎(chǔ)上，將當前節(jié)點、預選節(jié)點、目標節(jié)點之間的夾角做為估價函數(shù)的參數(shù)，這樣規(guī)劃出來的路徑不會出現(xiàn)比較大的道路轉(zhuǎn)向；同時整個道路網(wǎng)絡分為兩層，快速路和主干路做為高層，次干路和支路做為低層。
1路網(wǎng)分層的改進A*算法及實現(xiàn)1.1經(jīng)典A*算法
1.1一般的A1*算法公式為f(n)=g(n)+h(n)⑴
n為預選節(jié)點，其中f(n)是起點經(jīng)過n節(jié)點到終點的估價函數(shù)，g(n)為從起點到n節(jié)的實際代價函數(shù)，h(n)為從n節(jié)點到終點的'估算代價函數(shù)。h(n)的估算方式有多種，可以為歐氏距離，曼哈頓距離，切比雪夫距離等來估算，此次實驗中我們采用的是歐式距離除以路網(wǎng)平均車速（按各等級道路所占路網(wǎng)權(quán)重計算）。
1.2改進A*算法
改進A*算法⑴主要考慮經(jīng)過節(jié)點數(shù)較少的方式，來找到通行時間最短的路徑，此時采用路徑行駛中的角度偏轉(zhuǎn)值做為h(n)的參數(shù)⑵。算法公式為：
f(n)=g(n)+arg(n)'h(n)(2)
其中f(n)是起點經(jīng)過n節(jié)點到終點的估價函數(shù)；g(n)為從起點到n節(jié)點的實際代價函數(shù)，計算方法為在路段的行駛時間(行駛時間與路段等級、道路長度有關(guān)）與車輛在路口的紅綠燈等待時間（等待時間可設(shè)置為紅燈總時長的一半）之和；h(n)為從n節(jié)點到終點的估價函數(shù)，計算方法為n節(jié)點到終點的歐氏距離除以路網(wǎng)平均車速；arg(n)為從當前節(jié)點到預選節(jié)點的直線與預選節(jié)點到終點所形成的直線的夾角，夾角范圍為（0，7)。為了防止各預選節(jié)點間的夾角差值太大，如預選節(jié)點與終點為相反方向時a「g(n)為n，相同方向為0，為a「g(n)設(shè)置一個上下閾值（7^6，5n/6)。
1.3路網(wǎng)分層的改進A*算法
路網(wǎng)分層B-5]是將整個路網(wǎng)按照行車速度分為兩層：次干路和支路為低層路網(wǎng)，快速路和主干路分為高層路網(wǎng)?"7]。在高層路網(wǎng)中，一般交叉口密度較少，采用經(jīng)典A*算法規(guī)劃路徑；而在低層路網(wǎng)中，交叉口密度較大，且車流量較大[|?]，采用改進A*算法。路網(wǎng)分層的改進A*算法的步驟如下：
1)初始化道路數(shù)據(jù)，獲得起點O和終點D所在節(jié)點層次；
2)若O和D同在高層路網(wǎng)，則忽略低層路網(wǎng)，按經(jīng)典A1*算法選擇下一節(jié)點，直到達到D為止；否則轉(zhuǎn)到3);
3)0和D在低層網(wǎng)絡，按歐式距離找出距離O和D最近的高層節(jié)點0*和D*，采用改進A*算法規(guī)劃出0到0*路徑R1，D到D*路徑R2(若0與D有一節(jié)點在高層，算法類似）；
4)按經(jīng)典A*算法得到的方式得到0*到D*的路徑R3;
5)組合三條路徑：R=R1+R3+R2，即為所求最優(yōu)路徑，算法結(jié)束。
2算法仿真
本文使用的繪圖軟件為MaplnfoProfessional10，以杭州江干區(qū)下沙經(jīng)濟技術(shù)開發(fā)區(qū)的重要路段進行提取繪制成電子地
193各種算法路徑搜索結(jié)果圖，其中截取了共215個節(jié)點，690條路段。采用的仿真平合為Linux平合下的GDB編譯框架，用C語言編程。主要存儲的數(shù)據(jù)有各節(jié)點坐標和等級、節(jié)點之間路段信息、各路口的紅燈時長，所有信息由杭州下沙交通控制中心提供。將道路分為四個等級、兩個網(wǎng)層，對應速度40、60、80、100km/h。行車平均速度由各等級道路所占路網(wǎng)權(quán)重確定，經(jīng)計算得該路網(wǎng)平均速度v為58.6km/h。
為了體現(xiàn)出規(guī)劃效果，每次規(guī)劃中隨機選取4個節(jié)點，兩個為起點和終點，另外兩為個中間節(jié)點，即實現(xiàn)3次路徑規(guī)劃，路徑顏色依次為紅、棕、綠。
從以上圖與表的搜索節(jié)點數(shù)和經(jīng)過節(jié)點數(shù)可知，由于改進算法的路徑軌跡相對比較平滑，不會出現(xiàn)大的轉(zhuǎn)彎，采用改進A*算法經(jīng)過的節(jié)點數(shù)總體要少于經(jīng)典A*算法，如圖1中節(jié)點104到38減少了2個，節(jié)點38到15節(jié)點數(shù)相同，節(jié)點15到b改進A*算法路徑93減少了5個，總節(jié)點數(shù)減少了7個，減少10%，表2中總節(jié)點數(shù)減少4個，減少8%。經(jīng)過節(jié)點數(shù)減少后，搜索次數(shù)則變小，搜索節(jié)點數(shù)相應減少。對于分層改進A*算法，將路徑分成了三段處理，使得經(jīng)過節(jié)點數(shù)增加；在低層節(jié)點搜索高層節(jié)點時，屏蔽了高層節(jié)點，高層節(jié)點之間搜索時屏蔽了底層節(jié)點，因而搜索節(jié)點數(shù)減少，表2中搜索節(jié)點數(shù)較改進A*算法減少了有14%,經(jīng)過節(jié)點數(shù)增加了25%。
由運算時間可以看出，改進A*算法的估價函數(shù)前有系數(shù)運算，增加了每次運算時長，又算法經(jīng)過節(jié)點數(shù)少，減少了運算次數(shù)，所以總運算時間較經(jīng)典算法差別不大。分層改進算法將路徑劃歸為三段處理，規(guī)劃時三段運算并發(fā)執(zhí)行，當最后一條路徑規(guī)劃完搜索結(jié)束，相對于改進A*算法表1中運算時間減少了44%，表2中減少了60%，算法效率得到很大提高。
由路徑長度和實際行駛時間可以看出，改進A*算法與A*c路網(wǎng)分層改進A*算法路徑圖2節(jié)點3-181-210-127各種算法路徑搜索結(jié)果表1節(jié)點104-38-15-193的相關(guān)參數(shù)表2節(jié)點3-181-210-127的相關(guān)參數(shù)算法路徑長度相差不大，甚至改進后路徑變長，如表1中由22660m變?yōu)?3140m，但考慮到經(jīng)過節(jié)點時的路口延誤時間，總行駛時間減少了7%。分層改進A*算法的路徑長度有明顯增加,如表2中路徑長度為26860m，相比改進算法增加了53%，但整個路徑中高層路段所占比例較大，反而行駛時間降低了31%。
從總體上來看，路網(wǎng)分層的改進A*算法較經(jīng)典A*算法而言，雖然加大了路徑長度，但能夠從減少經(jīng)過節(jié)點數(shù)和增加高層路段比例兩個方面縮短最短行駛時間，且運算速度也有所降低,符合實際交通情況，總體效果優(yōu)于經(jīng)典A*算法。
3結(jié)束語
結(jié)合實例進行仿真，實驗有效的證明該算法不僅可以保證經(jīng)典A*算法的精度和效率，而且縮短了行程時間。此算法可以做為動態(tài)路徑規(guī)劃時的底層算法來運用，若在車輛導航系統(tǒng)中采用此算法，將給人們的出行帶來方便。
【路網(wǎng)分層的改進A芯算法在智能交通系統(tǒng)中的應用論文】相關(guān)文章：