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

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

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

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