分層路徑誘導(dǎo)算法與策略研究.pdf

1、在智能交通系統(tǒng)中的路徑誘導(dǎo)子系統(tǒng)中，查詢最優(yōu)路徑是其中的一項基本的功能。許多研究者已經(jīng)從理論上和實驗上對該問題進(jìn)行了廣泛的研究。目前為止，道路網(wǎng)中的路徑誘導(dǎo)算法主要有平面算法和分層算法兩大類。平面算法是指如Dijkstra算法、A算法和A<'*>算法等的圖搜索算法，而分層算法由平面算法和一組在層次數(shù)據(jù)結(jié)構(gòu)上進(jìn)行推理的規(guī)則組成。在分層算法的每一層可使用某種平面算法，而推理規(guī)則將規(guī)定如何運用層次數(shù)據(jù)結(jié)構(gòu)。與平面算法相比，分層算法通常在搜索一

2、條滿意的路徑時具有較好的性能，這是因為分層數(shù)據(jù)結(jié)構(gòu)使得某個搜索過程在子網(wǎng)中進(jìn)行，子網(wǎng)的小數(shù)據(jù)規(guī)?？墒沟盟阉鬟^程高效執(zhí)行。而隨著問題規(guī)模的變大，平面算法卻會較快地產(chǎn)生“組合爆炸”問題。已有的最近E節(jié)點分層算法在提升低層節(jié)點時不夠準(zhǔn)確，而最佳E節(jié)點分層算法又效率太低。為此，本文提出了一種分層A棗算法。其實質(zhì)是在低層向高層過渡時采用啟發(fā)式定向搜索的方法確定E節(jié)點，而在高層路網(wǎng)中搜索時采用A<'*>算法。目的是在求解速度較快的前提下，搜索出相對

3、可靠的E節(jié)點。西安市道路網(wǎng)的測試數(shù)據(jù)表明，分層A<'*>算法的平均求解效率是Diikstra算法的75.48倍，平均路徑長度與平均最短路徑長度的偏差僅為0.865km，平均高層路徑比重達(dá)到69.7％。通過比較分層A<'*>算法、最近E節(jié)點分層算法和Diikstra算法的性能，筆者認(rèn)為分層A<'*>算法具有較好的實用性。 另外，在中心式路徑誘導(dǎo)系統(tǒng)中，計算中心需要傳送必要的地圖數(shù)據(jù)給車輛。為了縮短計算中心與車輛之間的數(shù)據(jù)傳送時間，

4、本文提出并實現(xiàn)了一種TMSCR數(shù)據(jù)準(zhǔn)備模型，即在包含起止點的一個網(wǎng)格集合的外接矩形區(qū)域中，提取起點網(wǎng)格內(nèi)的低層路段、終點網(wǎng)格內(nèi)的低層路段和所有高層路段的并集，發(fā)送給車輛。實驗表明，實現(xiàn)該模型的時間代價很小，TMSCR模型與傳統(tǒng)的方法相比，可以大大節(jié)省通信時間，從而為車輛提供優(yōu)質(zhì)的服務(wù)。 最后，筆者基于MapXtreme2005 6.6和.net 2005設(shè)計并實現(xiàn)了西安市路徑查詢原型系統(tǒng)。該系統(tǒng)由三部分組成，即空間數(shù)據(jù)庫、核心算