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

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

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

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

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