交通網(wǎng)絡限制條件下的最短路問題研究.pdf

1、一直以來，最短路算法是計算機科學、數(shù)學、地理信息系統(tǒng)和交通科學研究的熱點，與最短路算法相關的問題多種多樣，近年來隨著地理信息系統(tǒng)(GIS)與智能交通系統(tǒng)(ITS)的結合，最短路問題在交通地理信息系統(tǒng)中有著十分重要的位置，尤其是對于出行者信息服務系統(tǒng)(ATIS)更是不可或缺的一部分。
　　 本文以交通網(wǎng)絡為研究對象，研究城市道路交通網(wǎng)絡在限制條件下的單源最短路徑問題，探求在不同限制條件下最短路徑探索的實現(xiàn)方法，并基于此方法給出程序

2、實現(xiàn)。本文涉及的限制條件，不僅包括了道路交通網(wǎng)絡本身的限制條件(通行限制、轉向限制(延誤)以及道路等級、道路交通狀況)，還包括了面向用戶服務的可供最短路探索需求者自定義的限制條件(限高、限寬和限載)。
　　 程序所采用的最短路算法是基于鄰接表網(wǎng)絡存儲結構和單隊列的程序運行結構的Dijkstra算法，程序在實現(xiàn)上分兩個部分，程序l用于最短路探索方法的研究，實現(xiàn)在自建的虛擬路網(wǎng)下的最短路探索，其網(wǎng)絡的存儲方式為完全意義上的拓撲結構存

3、儲，點與邊的關系在拓撲文件中嚴格對應，當網(wǎng)絡拓撲結構發(fā)生改變時，必須改變拓撲文件的存儲才能夠使得最短路探索得以正確執(zhí)行；程序2采用了拓撲存儲與路徑探索相分離的方式，使得路徑探索可以不完全依賴于拓撲結構，當實際路網(wǎng)拓撲結構發(fā)生變化的時候，可以僅僅通過對路段屬性的調整來實現(xiàn)探索過程的變更，同時程序結合了GIS二次開發(fā)組件提供的讀取和顯示圖層的功能，開發(fā)了可視化的應用程序，將文中所涉及的各種交通網(wǎng)絡限制條件下的最短路探索一一實現(xiàn)，并對其以具備