最優(yōu)路徑算法在交通地理信息系統(tǒng)中的運(yùn)用分析

胡衛(wèi)榮

北京晶眾智慧交通科技股份有限公司 北京 100012

城市化建設(shè)步伐加快，交通壓力一直困擾著城市交通發(fā)展，在這種情況，交通地理信息系統(tǒng)積極應(yīng)用最優(yōu)路徑算法。在交通地理信息系統(tǒng)及時(shí)在收集城市交通數(shù)據(jù)與存儲(chǔ)管理數(shù)據(jù)，詳細(xì)分析數(shù)據(jù)，協(xié)調(diào)城市交通空間基礎(chǔ)上，最優(yōu)路徑算法協(xié)助交通地理信息系統(tǒng)，能夠?qū)⒌貓D靈活變大或者縮小，并增加圖層控制功能，及時(shí)進(jìn)行地理信息查詢服務(wù)，進(jìn)一步完善交通信息查詢模式，保證為公眾提供實(shí)時(shí)準(zhǔn)確的交通信息。不僅如此，最優(yōu)路徑算法還能夠?qū)φ军c(diǎn)覆蓋率進(jìn)行準(zhǔn)確計(jì)算，科學(xué)分析交通緩沖區(qū)，為公眾了解交通信息提供更多方便。

1 交通地理信息系統(tǒng)中最優(yōu)路徑算法設(shè)計(jì)思路

最優(yōu)路徑算法在交通地理信息系統(tǒng)中的應(yīng)用，針對(duì)其具體特點(diǎn)與交通地理信息系統(tǒng)需要，積極進(jìn)行優(yōu)化設(shè)計(jì)。基本設(shè)計(jì)思路中，在交通地理信息系統(tǒng)中，設(shè)置好網(wǎng)絡(luò)標(biāo)號(hào)，以點(diǎn)（dj、pj）為中心，涉及起源點(diǎn)s、節(jié)點(diǎn)j之間的長(zhǎng)度，此為dj，若s、j點(diǎn)之間無距離，則將其稱之為零路。起點(diǎn)s、節(jié)點(diǎn)j相互連通中最短路徑為pj。由此為設(shè)計(jì)載體，計(jì)算兩點(diǎn)之間最優(yōu)路徑。

第一，提前將節(jié)點(diǎn)進(jìn)行初始化處理。所有點(diǎn)的值均設(shè)置為空值，其中起始點(diǎn)除外的節(jié)點(diǎn)，dj在初始狀態(tài)相當(dāng)于無窮大，pj則代表任意點(diǎn)的任意值。將起源點(diǎn)s進(jìn)行標(biāo)記，并調(diào)整為s=k，不需要標(biāo)注其他點(diǎn)[1]。

第二，將已標(biāo)記節(jié)點(diǎn)進(jìn)行統(tǒng)計(jì)，以k為代表，該點(diǎn)與其相連接的沒有進(jìn)行標(biāo)記的節(jié)點(diǎn)，以j為代表，計(jì)算兩者之間的距離，并得到：dj=min[dj,dk+1kj]，計(jì)算公式中，直接連接的距離為1kj。

第三，根據(jù)交通地理信息系統(tǒng)提供的信息，將下一節(jié)點(diǎn)提前選取完畢，其中dj的選擇一定要符合未標(biāo)記、最小要求。節(jié)點(diǎn)的選擇公式如下di=min[dj,未標(biāo)記點(diǎn)總和j]作為已標(biāo)記點(diǎn)i，其在交通地理信息系統(tǒng)中，屬于路徑最優(yōu)與最短點(diǎn)。連接節(jié)點(diǎn)i與其之前節(jié)點(diǎn)，結(jié)合已標(biāo)記節(jié)點(diǎn)，連接之前節(jié)點(diǎn)j*，這期間，之前階段與當(dāng)前節(jié)點(diǎn)是同等關(guān)系。

第四，根據(jù)當(dāng)前標(biāo)志的節(jié)點(diǎn)，將節(jié)點(diǎn)途徑位置全部納入到標(biāo)記點(diǎn)中，及時(shí)完成最優(yōu)路徑計(jì)算，并得到最終地理想路徑。

2 最優(yōu)路徑算法進(jìn)一步優(yōu)化

最優(yōu)路徑算法在交通地理信息系統(tǒng)中的應(yīng)用，根據(jù)其設(shè)計(jì)思路進(jìn)一步簡(jiǎn)化，將標(biāo)記點(diǎn)劃分為未標(biāo)記、永久標(biāo)記與臨時(shí)標(biāo)記，方便最優(yōu)路徑計(jì)算與資料整理。初始化狀態(tài)下，所有點(diǎn)均屬于未標(biāo)記類型，根據(jù)交通地理信息系統(tǒng)的搜索以及統(tǒng)計(jì)分析，選擇出接近最短路徑的點(diǎn)，設(shè)置為臨時(shí)標(biāo)記，因?yàn)樽顑?yōu)路徑計(jì)算具有循環(huán)性特點(diǎn)，所以臨時(shí)標(biāo)記點(diǎn)是計(jì)算參考的關(guān)鍵點(diǎn)。在搜索中尋找最優(yōu)路徑位置，并標(biāo)注出最短位置，此標(biāo)記類型為永久標(biāo)記[2]。在循環(huán)標(biāo)記過程中，不斷增加臨時(shí)標(biāo)記點(diǎn)，將最優(yōu)路徑所有點(diǎn)均標(biāo)記完畢，最優(yōu)路徑算法運(yùn)行結(jié)束。改變臨時(shí)標(biāo)記無序存儲(chǔ)的不足，打破最優(yōu)路徑算法運(yùn)行瓶頸，可以更迅速地鎖定需要搜索節(jié)點(diǎn)，不需要將全部臨時(shí)標(biāo)注一一過濾[3]。以最短路徑為出發(fā)點(diǎn)將臨時(shí)標(biāo)記節(jié)點(diǎn)進(jìn)行排序，減少臨時(shí)標(biāo)記過濾時(shí)間與數(shù)量，從而更快的得到最終的目標(biāo)節(jié)點(diǎn)。

3 最優(yōu)路徑算法中的直線優(yōu)化運(yùn)用

針對(duì)最優(yōu)路徑算法在交通地理信息系統(tǒng)中的應(yīng)用，采取直線優(yōu)化的方式，將最優(yōu)路徑中的搜索范圍有效縮減，減少冗余搜索，迅速確定目標(biāo)節(jié)點(diǎn)。在平面網(wǎng)絡(luò)基礎(chǔ)上，起源點(diǎn)與臨時(shí)標(biāo)記點(diǎn)之間的距離，屬于臨時(shí)標(biāo)記點(diǎn)重要屬性值，同時(shí)目標(biāo)點(diǎn)與臨時(shí)標(biāo)記點(diǎn)之間的距離同樣屬于臨時(shí)標(biāo)記點(diǎn)屬性值。結(jié)合臨時(shí)標(biāo)記點(diǎn)屬性值為永久標(biāo)記點(diǎn)的選取重要依據(jù)，永久標(biāo)記點(diǎn)盡可能選擇屬性值中的最小值。最優(yōu)路徑算法的直線優(yōu)化升級(jí)，將搜索手段進(jìn)行智能化處理，不僅節(jié)點(diǎn)數(shù)量明顯減少，同時(shí)在很大程度上將搜索速度加快。

3.1 對(duì)比搜索過程的優(yōu)勢(shì)

最優(yōu)路徑算法的直線優(yōu)化處理，改變?cè)兴惴☉?yīng)用期間，以起源點(diǎn)作為基礎(chǔ)圓心，隨后搜索過程中會(huì)生成很多同心圓，但是在過程中并沒有對(duì)終點(diǎn)位置或者方向有過多地考慮，從圓心開始進(jìn)行搜索，搜索速度與概率并相對(duì)較慢。但是直線優(yōu)化后的最優(yōu)路徑算法，其在終點(diǎn)搜索期間，會(huì)設(shè)定終點(diǎn)、起源點(diǎn)之間的臨時(shí)點(diǎn)作為搜索焦點(diǎn)，形成同心橢圓搜索路徑，搜索速度明顯加快。結(jié)合測(cè)試可以發(fā)現(xiàn)，整個(gè)搜索中，所有搜索目的均迅速集中在終點(diǎn)，根據(jù)臨時(shí)節(jié)點(diǎn)的引導(dǎo)，搜索節(jié)點(diǎn)減少，搜索效率更高。

3.2 直線優(yōu)化應(yīng)用范圍

最優(yōu)路徑算法中，直線優(yōu)化處理后，相對(duì)原有算法，非常適用于弧長(zhǎng)度計(jì)算，尤其是權(quán)值以網(wǎng)絡(luò)中弧為主。設(shè)定網(wǎng)絡(luò)系統(tǒng)這個(gè)整體為一個(gè)平面，在這個(gè)平面通過起源點(diǎn)、臨時(shí)節(jié)點(diǎn)等計(jì)算最短路徑。交通地理信息系統(tǒng)中，直線優(yōu)化的最優(yōu)路徑算法更適合小范圍地理搜索。在不同方面將搜索范圍與速度進(jìn)行了明顯調(diào)整。以起源點(diǎn)為中心，在系統(tǒng)運(yùn)行過程中逐漸向網(wǎng)絡(luò)邊界靠近，忽略掉不必要節(jié)點(diǎn)，以最快速度完成系統(tǒng)搜索。從節(jié)點(diǎn)數(shù)量上來講，直線優(yōu)化節(jié)點(diǎn)數(shù)量減少基礎(chǔ)上，結(jié)合網(wǎng)絡(luò)以及交通地理信息系統(tǒng)運(yùn)行，及時(shí)進(jìn)行差異性分析，調(diào)整更加靈活，搜索更加便利。在相同范圍條件下，若起源點(diǎn)與終結(jié)點(diǎn)之間并不是連通狀態(tài)，則需要將搜索范圍調(diào)整到全部，節(jié)點(diǎn)不能作為終結(jié)點(diǎn)之間的媒介，而是全面性搜索。提前對(duì)節(jié)點(diǎn)數(shù)進(jìn)行確定，根據(jù)節(jié)點(diǎn)數(shù)去確定計(jì)算最短與最優(yōu)距離的數(shù)值，積極進(jìn)行最優(yōu)路徑計(jì)算。

4 結(jié)束語(yǔ)

綜上所述，交通地理信息中積極應(yīng)用最優(yōu)路徑算法，其不僅能夠幫助交通地理信息實(shí)現(xiàn)疊層搜索，同時(shí)在很多方面提高交通地理信息系統(tǒng)信息收縮與數(shù)據(jù)處理的效率。當(dāng)然在實(shí)際應(yīng)用中，根據(jù)交通地理信息需要，及時(shí)對(duì)最優(yōu)路徑算法進(jìn)行升級(jí)處理，其中直線優(yōu)化方式的實(shí)用性更高，搜索速度更快，具有非常大的應(yīng)用空間。