基于分層區(qū)域限制的車輛導(dǎo)航路徑規(guī)劃問題研究.pdf

1、車輛導(dǎo)航系統(tǒng)作為智能交通系統(tǒng)核心的內(nèi)容之一，旨在減少交通擁擠和交通事故，但是隨著城市交通路網(wǎng)規(guī)模度、復(fù)雜度日益增大，交通擁擠和交通事故壓力日益增大。尤其面對越來越龐大的城市道路網(wǎng)，最短路徑算法計算量大，而且交通擁堵實時變化，現(xiàn)有導(dǎo)航系統(tǒng)無法滿足出行者對躲避擁堵道路的要求。因此，考慮大規(guī)模路網(wǎng)交通擁堵的最短路徑規(guī)劃問題已成為當(dāng)前研究的熱點問題。本文從三個方面開展研究:
　　(1)針對時間依賴路網(wǎng)模型不能完全體現(xiàn)道路屬性信息的缺點，建

2、立基于邊成本分析的時間依賴路網(wǎng)模型。模型中的道路屬性及路口屬性以集合形式表現(xiàn)，道路屬性集合依附于路網(wǎng)模型邊集合，路口屬性集合依附于路網(wǎng)模型節(jié)點集合;定義道路屬性集合內(nèi)參數(shù)及路口屬性集合內(nèi)參數(shù)，給出參數(shù)綜合影響邊成本的公式，并以邊屬性的路段平均行駛速度參數(shù)為標(biāo)準(zhǔn)確定路段不同程度擁堵狀態(tài)并將擁堵狀態(tài)分成五個等級。
　　(2)針對多層級路網(wǎng)每層路網(wǎng)均需逐層參與搜索且不能動態(tài)躲避通行能力差道路的缺點，通過建立矩形限制區(qū)域降低參與路徑搜索的

3、路網(wǎng)節(jié)點數(shù)量以提高算法運(yùn)算效率;基于道路空間分布特點和不同等級道路通行能力劃分高低層路網(wǎng)，算法優(yōu)先搜索高層路網(wǎng)達(dá)到保證路徑行程時間最短目的;基于實時變化的交通擁堵動態(tài)切換算法搜索的高層、低層路網(wǎng)，在高層規(guī)劃路徑出現(xiàn)交通擁堵情況下，根據(jù)交通擁堵程度適時轉(zhuǎn)入低層路網(wǎng)重新規(guī)劃路徑，達(dá)到躲避交通不便道路的目的。
　　(3)針對分層限制區(qū)域單種群蟻群算法運(yùn)算時間長、局部收斂的劣勢提出多種群蟻群路徑優(yōu)化改進(jìn)算法。通過改進(jìn)基于分層限制區(qū)域單種群

4、蟻群算法狀態(tài)轉(zhuǎn)移公式，建立多種群蟻群信息素共享與更新策略，設(shè)計了種群內(nèi)部信息交流、種群間信息交流、擁堵路段信息交流結(jié)合的策略，使多個種群共同維護(hù)一個相同的路網(wǎng)結(jié)構(gòu)圖完成一次路徑搜索，通過聚集所有子種群最優(yōu)路徑確定信息素的更新方案，并將更新信息素傳遞給子種群實現(xiàn)信息素共享達(dá)到全局最優(yōu)的目的。
　　本文實驗仿真采用速度擬合函數(shù)隨機(jī)分配速度值方案，將分層限制搜索區(qū)域Dijkstra算法、不分層不限制搜索區(qū)域單種群蟻群算法、分層限制搜索區(qū)

5、域單種群蟻群算法、分層限制區(qū)域多種群蟻群算法進(jìn)行對比，從算法運(yùn)行時間和規(guī)劃路徑質(zhì)量兩個方面分析。結(jié)果表明，在大規(guī)模路網(wǎng)情況下，基于分層限制搜索區(qū)域的策略具有一定優(yōu)勢，而同樣采用分層限制搜索區(qū)域策略，蟻群算法平均搜索時間明顯小于Dijkstra算法的搜索時間。實驗也表明，雖然多種群蟻群算法規(guī)劃路徑長度較長，但是時間要小于其它算法，原因是考慮了交通擁堵因素，出現(xiàn)交通擁堵適時轉(zhuǎn)入低層路網(wǎng)選擇走擁堵道路附近的支路或次干路，從而節(jié)省了因擁堵造成的