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