典型城市路網(wǎng)最短路徑算法研究及實(shí)現(xiàn).pdf

1、隨著現(xiàn)代生活節(jié)奏的加快和汽車數(shù)量的陡增，交通問(wèn)題日趨凸顯，為此，世界各國(guó)紛紛開展智能交通系統(tǒng)研究。作為智能交通系統(tǒng)的重要子系統(tǒng)，城市交通誘導(dǎo)系統(tǒng)歷來(lái)是業(yè)界專家學(xué)者研究的熱點(diǎn)和難點(diǎn)，也是解決現(xiàn)存交通問(wèn)題最行之有效的方式之一。
　　 路徑誘導(dǎo)的核心問(wèn)題是圖論中的最短路徑算法研究。因?yàn)閷?duì)于稀疏網(wǎng)絡(luò)，用堆可以使Dijkstra算法時(shí)間復(fù)雜度降至NlogN（N表示網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)），Dijkstra算法被廣泛用于解決城市路網(wǎng)的單源最短路徑問(wèn)

2、題。
　　 但是，Dijkstra算法在解決兩站點(diǎn)間的最短路徑問(wèn)題時(shí)，特別對(duì)于大規(guī)模的城市道路網(wǎng)絡(luò)，Dijkstra算法仍有很大冗余度，最短路徑查詢難以滿足人們對(duì)最短路徑查詢實(shí)時(shí)性和可靠性的要求。限制搜索區(qū)域的最短路徑算法的研究成為改進(jìn)城市路網(wǎng)中最短路徑算法，減少路徑查詢時(shí)間最為直接有效方法。
　　 本文的研究?jī)?nèi)容是典型城市路網(wǎng)中的橢圓限制搜索區(qū)域的改進(jìn)最短路徑算法的理論研究及實(shí)驗(yàn)驗(yàn)證，研究目的是保證查詢結(jié)果可靠的情況下

3、，最大程度降低最短路徑查詢時(shí)間，研究方法是充分研究和利用城市路網(wǎng)的特征參數(shù)，降低最短路徑算法冗余度和復(fù)雜度，算法性能指標(biāo)采用軟件仿真預(yù)測(cè)和實(shí)測(cè)數(shù)據(jù)統(tǒng)計(jì)雙重評(píng)估標(biāo)準(zhǔn)。
　　 研究?jī)?nèi)容主要包括以下幾個(gè)方面:
　　 (1)城市路網(wǎng)中典型特性研究及特征參數(shù)提取。具體包括路段長(zhǎng)度取值規(guī)律研究、路段站點(diǎn)比取值規(guī)律研究、最短路徑比規(guī)律研究等。
　　 (2)多尺度橢圓最短路徑算法研究及性能分析。具體包括不同尺度橢圓分割點(diǎn)取值研究

4、，多尺度算法搜索區(qū)域面積研究和最短路徑查詢時(shí)間研究等。
　　 (3)二樹橢圓最短路徑算法研究及其性能分析。具體包括二樹橢圓算法終止條件研究，二樹算法搜索區(qū)域面積研究和最短路徑查詢時(shí)間研究等。
　　 仿真推測(cè)和實(shí)驗(yàn)結(jié)果表明:與橢圓算法相比，當(dāng)起始站點(diǎn)和目的站點(diǎn)相距較遠(yuǎn)時(shí)，多尺度算法可以有效降低18％的最短路徑查詢時(shí)間，而且多尺度算法查的最短路徑是絕對(duì)可靠的;與單源算法相比，二樹算法可以有效降低約40％最短路徑查詢時(shí)間，而且