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