城市道路網(wǎng)絡(luò)最短路徑的統(tǒng)計(jì)學(xué)特征及實(shí)用算法研究.pdf

1、本文運(yùn)用新的技術(shù)路線和方法對(duì)傳統(tǒng)的最短路徑問(wèn)題進(jìn)行了系統(tǒng)研究。通過(guò)對(duì)上海地區(qū)隨機(jī)抽取的最短路徑統(tǒng)計(jì)特征的分析和樣本路徑空間分布特征的觀察，構(gòu)建了適用于一般道路網(wǎng)絡(luò)的橢圓模型和適合于上海道路特征的橢圓模型參數(shù)。該模型將兩點(diǎn)之間的最短路徑搜索范圍限定在橢圓范圍內(nèi)，這種算法大幅度減少了冗余節(jié)點(diǎn)，減輕了網(wǎng)絡(luò)傳輸實(shí)時(shí)路況數(shù)據(jù)的負(fù)擔(dān)，提高了算法的性能和效率。使用橢圓模型改進(jìn)后的算法在理論上搜索掃描過(guò)的空間范圍約為經(jīng)典算法的1/5。 同時(shí)，針

2、對(duì)上海市道路網(wǎng)絡(luò)，在大量隨機(jī)抽樣的基礎(chǔ)上，研究了歐氏距離、馬氏距離和最短路徑之間的關(guān)系。研究發(fā)現(xiàn)最短路徑的長(zhǎng)度分別與路徑的起終點(diǎn)連線的歐氏距離和馬氏距離之間存在著顯著的線性關(guān)系。通過(guò)回歸分析，分別得到最短路徑長(zhǎng)度與兩者的直線回歸方程。用歐氏距離擬合的最短路徑長(zhǎng)度與樣本最短路徑長(zhǎng)度的相對(duì)誤差分布集中在-7.5％至7.5％之間，通過(guò)F檢驗(yàn)，在α=0.01的置信水平下顯著。而使用馬氏距離擬合精度偏低。因此，在只需要求解兩點(diǎn)之間最短路徑長(zhǎng)度的情

3、況下，可以將兩點(diǎn)連線的歐氏距離代入方程直接計(jì)算。 對(duì)于上海的道路網(wǎng)，通過(guò)典型抽樣選取有代表性的節(jié)點(diǎn)，將本文提出的橢圓模型與經(jīng)典的Dijkstra算法、其他學(xué)者提出的限制搜索范圍模型計(jì)算最短路徑算法，進(jìn)行了準(zhǔn)確度、搜索規(guī)模和搜索性能3個(gè)方面的比較，結(jié)果表明：本文研究的橢圓模型準(zhǔn)確率達(dá)到99.8％，搜索規(guī)模和算法執(zhí)行時(shí)間分別為經(jīng)典算法的50％和16.6％。相比于另外兩種橢圓模型，本文的橢圓模型比陸鋒(1999)的算法具有更高的效率，