【正文】 武漢紡織大學(xué) 畢 業(yè)設(shè)計 (論文 ) 交通線路選擇軟件的設(shè)計與實現(xiàn) 姓 名： 學(xué) 號： 1003741126 學(xué) 院： 電子與電氣工程學(xué)院 指 導(dǎo) 老 師： 肖 適 20xx 年 5 月 30 日 I 摘 要 隨著社會經(jīng)濟的飛速發(fā)展，出行方式的多樣選擇，設(shè)計和研究一套簡單交通線路選擇軟件，成為利民便民和增強 市場競爭力的重要舉措。將交通網(wǎng)絡(luò)抽象成一個由邊和節(jié)點組成的圖，并根據(jù)圖論的相關(guān)理論和知識構(gòu)建起交通網(wǎng)絡(luò)模型，包括交通道路節(jié)點模型，交叉口和道路模型，并對上述道路模型信息進行存儲，以構(gòu)建好的交通道路模型為基礎(chǔ)研究智能交通系統(tǒng)中的最優(yōu)路徑問題。對道路交通系統(tǒng)的建模、最優(yōu)路徑選擇算法的研究以及數(shù)據(jù)庫的開發(fā)設(shè)計目的是建立一套接近實際情況的最優(yōu)路徑選擇系統(tǒng)。 GIS 數(shù)據(jù) 。 GIS data。 這就要求我們擁有的便利交通系統(tǒng)， 隨著計算機技術(shù)和電子技術(shù)的不斷發(fā)展，以及電子地圖測繪技術(shù)的不斷進步，這使得地理信息系統(tǒng)也得到了長足的進步，這些技術(shù)的發(fā)展都給智能交通系統(tǒng)的發(fā)展奠定 了 良好的基礎(chǔ)。在交通、計算機、電子通信、信息技術(shù)和系統(tǒng)科學(xué)與工程應(yīng)用領(lǐng)域中，智能交通系統(tǒng)是日前許多國內(nèi)外學(xué)者和研究機構(gòu)集中、深入的 研究 領(lǐng)域之一，具有非常好的發(fā)展前景。因此最優(yōu)路徑選武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計論文 2 擇與優(yōu)化問題是實時的動態(tài)交通系統(tǒng)中具有具有重要現(xiàn)實意義的研究課題。日前網(wǎng)絡(luò)發(fā)展十分迅速，而網(wǎng)絡(luò)的構(gòu)成類似交通道路系統(tǒng)，可以利用最優(yōu)路徑算法來解決很多網(wǎng)絡(luò)方面的問題。自從 Dijkstra 算法面世以后，又歷經(jīng)了很多學(xué)者對該算法的改進與發(fā)展，因此有關(guān)最優(yōu)路徑選擇問題的研究成果不斷涌現(xiàn)，使其求解速度和求解效率不斷提高 。最優(yōu)路徑問題按照是否是單源問題還可以分為單源最優(yōu)路徑選擇問題及全源最優(yōu)路徑選擇問題。路徑優(yōu)化的效率和速度室友所建立模型的準(zhǔn)確程度來決定的。實際情況下最優(yōu)路徑選擇問題包括兩層含義：首先最優(yōu)路徑是一條可以從 A 地到達 B 地的暢通的路徑；其次這條路徑在所有路徑當(dāng) 中是最佳的?；舅枷耄罕热缜髨D中兩節(jié)點 Vi 到 Vj的之問的最短路徑問題。 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計論文 4 2． 1． 2 Dijkstra 算法 Dijkstra 算法由荷蘭數(shù)學(xué)家 Edsger Wybe Dijkstra 在 1959 年提出來的，是一種單源最短路算法適用于非負權(quán)值網(wǎng)絡(luò)的計算，是目前在求解最短路徑問題較為完備且應(yīng)用廣泛的算法之一，可以計算出圖中從指定結(jié)點到圖中其他任意節(jié)點之問的最短路徑。在初始狀態(tài)下，原始節(jié)點 S 的路徑長度值被賦為 0即 dis 的值為 0， 同時假設(shè)其他所有節(jié)點到該節(jié)點的路徑長度為無窮大，用無窮大長度的路徑表示任何其他節(jié)點到該結(jié)點的路徑是未知的。這種拓展邊的迭代運算一直進行，一直運行到所有的 dM都代表從 S到 v 最短路徑為止。當(dāng)節(jié)點 s 向 D 轉(zhuǎn)發(fā)數(shù)據(jù)分組時，他首先找到與相鄰節(jié)點中距離最小的那個節(jié)點，然后將數(shù)據(jù)分組轉(zhuǎn)發(fā)給那個節(jié)點，將距離最小的那個節(jié)點稱為跳點，然后將 S 的數(shù)據(jù)傳送給這個跳點，該過程需要一直迭代計算，直到分組數(shù)據(jù)全部到達節(jié)點 D。但該算法存在這一定的缺點，當(dāng)網(wǎng)絡(luò)中的某節(jié)點與源點集中在兩個區(qū)域時，由于通信的不平衡能夠?qū)е虏糠止?jié)點無效，從而是網(wǎng)絡(luò)的連通性遭到破壞；另一方面是該方法需要 GPS 定位系統(tǒng)的輔助來計算幾點的位置信息 。 2． 2 圖論簡介 圖論 (Graph Theory)是組合數(shù)學(xué)的一個分支，它源于瑞士數(shù)學(xué)家歐(Euler)1736 年對于著名的哥尼斯堡七橋問題的解決，從而使歐拉成為了圖論 的創(chuàng)始人。前者主要研究圖的性質(zhì)，后者主要討論與圖有關(guān)的優(yōu)化問題。 2. 2. 1 圖的概念 無向圖是指有序三元組 (V， E,F)中邊沒有方向，其中集合 y 被稱為結(jié)點集，y中的元素稱為結(jié)點：集合 E被稱為邊集， E中的元素被稱為邊；而函數(shù)是邊集E到無序結(jié)點對兒所構(gòu)成的 集合的一個映射關(guān)系，稱之為關(guān)聯(lián)函數(shù)。每個結(jié)點度數(shù)相同的簡單圖稱為正則圖，最大度與最小度恰好相差 1 的簡單圖被稱為幾乎正則圖。也由它的結(jié)點對兒之間的鄰接關(guān)系唯一確定。在鄰接表中，圖中的每個節(jié)點都會有一個單鏈表與之對應(yīng)，第 i 個單鏈表中的結(jié)點數(shù)據(jù)表示依附于結(jié)點 v。 (2)十字鏈表 十字鏈表針對有向圖的另一種存儲結(jié)構(gòu)。對幾個經(jīng)典的最優(yōu)路徑選擇算法進行了介紹，如 Floyd 算法、 Dijkstra 算法、 GPSR 算法，并分析了他們的優(yōu)點和不足。一般地，交通網(wǎng)絡(luò)有如下特點： (1)線性分布，交通網(wǎng)絡(luò)結(jié)構(gòu)在空問分布中一般呈現(xiàn)線性特征，因此交通網(wǎng)絡(luò)建?？梢砸揽繄D論的相關(guān)理論和知識； (2)網(wǎng)絡(luò)分布，交通網(wǎng)絡(luò)是一個負載的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，連通性好，結(jié)構(gòu)復(fù)雜： (3)分段分布，交通系統(tǒng)中不同路段的特征一般不同，表現(xiàn)為空間的差異性，且同一路段的不同時間的交通網(wǎng)絡(luò)特征也可能不同，表現(xiàn)為時間差異性； (4)動態(tài)性特點，交通網(wǎng)絡(luò)上交通狀況不是一層不變的，隨時間的變化而變化，失意 是 時變系統(tǒng)： (5)車輛行駛的主觀性，交通網(wǎng)絡(luò)不同于其它網(wǎng)絡(luò)，交通網(wǎng)絡(luò)的主體可以自主的選擇交通路徑，行駛時間和行駛路線等是他的一個最顯著特征。 3． 1 建立城市交通模型 利用圖論 的相關(guān)理論和知識，對圖中的節(jié)點和邊設(shè)法加入車道信息用于模擬就哀痛系統(tǒng)。其次， 不同方向的 車道由于具有不同的拓撲關(guān)系，因此交通規(guī)則有可能不同。在實際情 況中人民出行是從一個地方到另一個地方，這種不能簡單的歸結(jié)在圖中從一個節(jié)點到另一個節(jié)點的轉(zhuǎn)移，實際情況的交通網(wǎng)絡(luò)運行是非常復(fù)雜的，所以不能簡單的把某一個具體的地方當(dāng)成是圖中的某個節(jié)點，把道路信息抽象成圖中帶有權(quán)值的邊，而是要將具體的地址信息抽象為節(jié)點以及其附屬信息并加入到交通網(wǎng)絡(luò)系統(tǒng)中。在 GPS進行導(dǎo)航式，需要考慮到的交通網(wǎng)絡(luò)信息往往與車道信息密切相關(guān) 。按照上述方法對原始的交通道路進行預(yù)處理之后就可以確定道路之間的拓撲關(guān)系，進而可以建立以道路拓撲 關(guān)系為基準(zhǔn)的交通系統(tǒng)模型，拓撲關(guān)系中包括線性實體之間的模型，線性實體與節(jié)點之問的模型，節(jié)點與節(jié)點之間的模型，以及他們的連通性等。在兩圖 層中分別存儲的節(jié)點信息和路段信息分別是獨立的，下一步就是建立兩個圖層之問的拓撲聯(lián)系，使得兩個圖層構(gòu)成有機整體，形成交通路徑系統(tǒng)的完整性，需要用兩個圖層所對應(yīng)的兩張表中的文件擴展出一定的字段，用對象的屬性信息來代表兩個圖層之間的拓撲關(guān)系，這樣就構(gòu)成了交通路徑模型的整體拓撲關(guān)系結(jié)構(gòu)圖。 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計論文 11 （ 2）數(shù)據(jù)存儲 一般地，在計算機中大多采用利用鄰接表和鄰接矩陣的方法存儲有向圖。 3． 3 最優(yōu)路徑選擇 3． 3． 1 最優(yōu)路徑的求解過程 在交通網(wǎng)絡(luò)中，求解最優(yōu)路徑的一般思路是：把最優(yōu)路徑選擇問題轉(zhuǎn)化成優(yōu)化問題來解決 ，應(yīng)用優(yōu)化理論的相關(guān)思想和思路解決最優(yōu)路徑優(yōu)化問題。 3． 3． 2 經(jīng)典 Dijkstra 算 法分析 在 1959 年荷蘭數(shù)學(xué)家 EW． Dijkstra 首先提出的 Dijkstra 算法，該算法是一種單源最短路徑的搜索算法，他適用于非負權(quán)值網(wǎng)絡(luò)的，是目前求解最短路問題的理論上最完備、應(yīng)用范圍最廣的算法，可以計算出從圖中的某一節(jié)點到其他任意節(jié)點的最短路徑搜索結(jié)果 .Dijkstra 是一種迭代的貪心策略的路徑搜索算法，他根據(jù)路徑的長短逐漸增長來搜索點數(shù)，構(gòu)造了一顆路徑樹，從而得到路徑樹中的根部節(jié)點到其他任意節(jié)點的最短路徑結(jié)果。從算法的原理可以發(fā)現(xiàn)，當(dāng)交通網(wǎng)絡(luò)十分龐大時，該算法的計算量是十分巨大的，如果將該算法直接用于交通網(wǎng)絡(luò)的最優(yōu)路徑選擇算法當(dāng)中，不能達到應(yīng)用的實時性要求，因此需要對該算法的性能進行提升式改進。 (6)算法結(jié)束。城市交通系統(tǒng)的交通阻抗可分為兩類，節(jié)點交通阻抗和道路交通阻抗，節(jié)點交通阻抗表示的是交叉口的交通阻抗 。因此交通阻抗的最小值 為以上各個元素最小值的總和，而最大值為以上各個元素最大值的總和。分析了經(jīng)典的最優(yōu)路徑選擇 Dijkstra 算法并對其進行改進，考慮到在實際情況中由道路質(zhì)量、擁堵情況等導(dǎo)致交通道路存在一定的交通阻抗，并將交通阻抗的計算加入到改進的 Dijkstra 算法當(dāng)中，使之更具有應(yīng)用價值。本章的內(nèi)容主要是介紹了 GIS 數(shù)據(jù)的一些相關(guān)內(nèi)容和數(shù)據(jù)庫管理設(shè)計內(nèi)容，主要內(nèi)容包括 GIS 數(shù)據(jù)的相關(guān)概念和內(nèi)容知識、 Oracle 數(shù)據(jù)庫選擇的原因、 GIS 數(shù)據(jù)導(dǎo)入、 GIS 數(shù)據(jù)在數(shù)據(jù)庫中的管理和維護等內(nèi)容。 GIS 數(shù)據(jù)所描述的對象主要包括與地理位置有關(guān)的空間數(shù)據(jù)信息和非空間依賴性的屬性方面的信息 數(shù)據(jù)。例如，一條公路可以用實線或連續(xù)像素點或矢量表示的曲線實體，并可以用一定的顏色符號把 GIS 數(shù)據(jù)中要表達的內(nèi)容完整的表達出來，這樣道路的類型就可以用相應(yīng)的符號表達出來。當(dāng)然，根據(jù)實際情況， GIS 數(shù)據(jù)應(yīng)該提供靈活的數(shù)據(jù)查詢和連接方法，以便經(jīng)常增加、刪除或修改其中屬性數(shù)據(jù)的操作。4. 3 SpatiaI 簡介 隨著 Oracle 8i 的推出， Spatial Cartridge 將升級為 Oracle Spatial。下面介紹這兩種方法怎樣實現(xiàn)的數(shù)據(jù)自動導(dǎo)入。該控制為二進制文件，能夠記錄數(shù)據(jù)的物理結(jié)構(gòu)，主要內(nèi)容包括：數(shù)據(jù)庫的名稱和屬性、數(shù)據(jù)庫的創(chuàng)建時間點、當(dāng)前日志的序號、檢驗點信息等等，． ctl表示控制文件的擴展名。但同時也存在著一定缺點，如通用新不好，與其他數(shù)據(jù)庫不兼容，但用它來訪問 Oracle 數(shù)據(jù)庫比用其它方法訪問速度快很多 。 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計論文 19 4． 8 本章小結(jié) 本章介紹的是關(guān)于 GIS 數(shù)據(jù)模型與 Oracle 數(shù)據(jù)庫管理設(shè)計的相關(guān)內(nèi)容，主要包括以下幾個方面： GIS 數(shù)據(jù)模型的建立； GIS 數(shù)據(jù)的管理與組織；數(shù)據(jù)管理設(shè)計基礎(chǔ)知識； Oracle Spatial 簡介； GIS 數(shù)據(jù)向 Oracle 中的導(dǎo)入； GIS 數(shù)據(jù)在 Oracle 中的存儲； oracle 中 GIS 數(shù)據(jù)的訪問； Oracle 中 GIS 數(shù)據(jù)的維護。 5． 2 仿真結(jié)果與分析 本文的電子地圖圖層數(shù)據(jù)來源于南昌市的電子地圖，截取了其中的 一 部分，其結(jié)點圖層由九個結(jié)點組成且每個結(jié)點都具有結(jié)點權(quán)重。 5． 3 本章小結(jié) 本章的工作重點是首先依據(jù)電子地圖結(jié)合路徑優(yōu)化算法的實現(xiàn)改進的動態(tài)路徑優(yōu)化算法，證明其實時性、合理性。在交通 線路選擇軟件 中，如何根據(jù)實時的路況信息，尋找出最優(yōu)的出行路徑，以及構(gòu)建最有路徑選擇系統(tǒng)方面用戶使用是本論文主要的研究內(nèi)容。并詳細分析了經(jīng)典的最優(yōu)路徑選擇 Dijkstra 算法并對其進行改進，考慮到在實際情況中由道路質(zhì)量、擁堵情況等導(dǎo)致交通道路存在一定的交通阻抗， 并將交通阻抗的計算加入到改進的 Dijkstra 算法當(dāng)中，使之更具有應(yīng)用價值。測繪 學(xué)報， 2OOl， 30(3)： 269275。 另外， 感謝我的家人，在我 上學(xué) 期間和整理論文期問，他們無私的關(guān)心和照顧著我的生活，是我能夠順利完成學(xué)業(yè)的必要條