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