【正文】 ........... 18 4. 7 Oracle 中 GlS 數(shù)據(jù)的維護(hù) ................................. 18 4． 8 本章小結(jié) .................................................. 19 5 路徑優(yōu)化算法系統(tǒng)實(shí)現(xiàn) ...................................... 19 5． 1 電子地圖制作 .............................................. 19 5． 2 仿真結(jié)果與分析 ........................................... 19 5． 3 本章小結(jié) .................................................. 21 6 結(jié)論 .......................................................... 21 參考文獻(xiàn) ........................................................ 22 致 謝 .......................................................... 23 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 1 1 緒論 隨著改革開放經(jīng)濟(jì)的發(fā)展，人口數(shù)量的不斷增多，城市的數(shù)量和規(guī)模不斷增大和增多，城市化程度和趨勢十分明顯，城市交通 問題成為目前影響和制約我國經(jīng)濟(jì)發(fā)展和社會進(jìn)步的主要因素。 這就要求我們擁有的便利交通系統(tǒng)， 隨著計(jì)算機(jī)技術(shù)和電子技術(shù)的不斷發(fā)展，以及電子地圖測繪技術(shù)的不斷進(jìn)步，這使得地理信息系統(tǒng)也得到了長足的進(jìn)步，這些技術(shù)的發(fā)展都給智能交通系統(tǒng)的發(fā)展奠定 了 良好的基礎(chǔ)。智能交通系統(tǒng) (ITS)通過充分發(fā)揮現(xiàn)有交通資源潛力和系統(tǒng)內(nèi)部協(xié)同作用產(chǎn)生的效力，能夠?yàn)槌鞘薪煌ㄌ峁└踩?、更舒適、更高效率和更高品質(zhì)的新型城市交通系統(tǒng)嘲。在交通、計(jì)算機(jī)、電子通信、信息技術(shù)和系統(tǒng)科學(xué)與工程應(yīng)用領(lǐng)域中，智能交通系統(tǒng)是日前許多國內(nèi)外學(xué)者和研究機(jī)構(gòu)集中、深入的 研究 領(lǐng)域之一，具有非常好的發(fā)展前景。如果能夠?qū)囕v導(dǎo)航系統(tǒng)提供行之有效的最佳路徑選擇算法，就能為人們出行提供有效、合理有效的出行路徑，從而提高交通系 統(tǒng)運(yùn)行的效率。因此最優(yōu)路徑選武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 2 擇與優(yōu)化問題是實(shí)時(shí)的動(dòng)態(tài)交通系統(tǒng)中具有具有重要現(xiàn)實(shí)意義的研究課題。道路交通系統(tǒng)中最佳路徑選擇的研究能夠?yàn)榫C合信息管理和只能決策提供先進(jìn)、科學(xué)和行之有效的判決依據(jù)；為人們出行提供便利的交通運(yùn)輸條件；為車輛的運(yùn) 行提供安全保障：提高了現(xiàn)代交通道路的利用效率；幫助車輛減少尾氣排放和燃油等資源的消耗：對于建設(shè)資源節(jié)約型社會具有劃時(shí)代的意義。日前網(wǎng)絡(luò)發(fā)展十分迅速，而網(wǎng)絡(luò)的構(gòu)成類似交通道路系統(tǒng)，可以利用最優(yōu)路徑算法來解決很多網(wǎng)絡(luò)方面的問題。國內(nèi)外大量研究機(jī)構(gòu)和相關(guān)學(xué)者對最優(yōu)路徑問題的解決進(jìn) 行過深入研究與探討。自從 Dijkstra 算法面世以后，又歷經(jīng)了很多學(xué)者對該算法的改進(jìn)與發(fā)展，因此有關(guān)最優(yōu)路徑選擇問題的研究成果不斷涌現(xiàn)，使其求解速度和求解效率不斷提高 。如按照時(shí)間順序來分類，分為動(dòng)態(tài)最優(yōu)路徑選擇問題和靜態(tài)最優(yōu)路徑選擇問題；如果按照確定性和非確定性來劃分，分為確定型和隨機(jī)型最優(yōu)路徑選擇問題；如果按照網(wǎng)絡(luò)規(guī)模大小 劃分，可分為小規(guī)模網(wǎng)絡(luò)和大規(guī)模網(wǎng)絡(luò)最優(yōu)路徑選擇問題：如果按照計(jì)算方式來劃分，可分為串行和并行最優(yōu)路徑選擇算法。最優(yōu)路徑問題按照是否是單源問題還可以分為單源最優(yōu)路徑選擇問題及全源最優(yōu)路徑選擇問題。 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 3 2 基礎(chǔ)知識 2． 1 路徑優(yōu)化算法概述 國內(nèi)外的研究機(jī)構(gòu)和學(xué)者對 不同的路徑優(yōu)化算法進(jìn)行了研究、分析、比較和論證，比較經(jīng)典的路徑優(yōu)化算法有 Floyd 算法、 Dijkstra 算法、 GPSR 算法、遺傳算法、蟻群算法等。路徑優(yōu)化的效率和速度室友所建立模型的準(zhǔn)確程度來決定的。最短路徑算法求出的僅僅是在空間距離最短的路徑，但在實(shí)際應(yīng)用中人們需要的是最優(yōu)路徑，最優(yōu)路徑不一定是距離最短，還要考慮交通阻抗的問題，比如想要求得從 A 地到 B 地的最優(yōu)路徑，這個(gè)問題是指在所有從 A 地到 B 地的所有路線當(dāng)中選擇最優(yōu)的一條，包括最節(jié)省時(shí)問，最節(jié)省資源，是駕駛者最舒適，對交通工具的各項(xiàng)消耗最小等。實(shí)際情況下最優(yōu)路徑選擇問題包括兩層含義：首先最優(yōu)路徑是一條可以從 A 地到達(dá) B 地的暢通的路徑；其次這條路徑在所有路徑當(dāng) 中是最佳的。 2． 1． 1 Floyd 算法 Floyd 算法是由 Floyd 在 1962 年提出的?；舅枷耄罕热缜髨D中兩節(jié)點(diǎn) Vi 到 Vj的之問的最短路徑問題。此算法思路簡單，該算法對于稠密圖來說，效率要高于經(jīng)典的 Dijkstra 算法。 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 4 2． 1． 2 Dijkstra 算法 Dijkstra 算法由荷蘭數(shù)學(xué)家 Edsger Wybe Dijkstra 在 1959 年提出來的，是一種單源最短路算法適用于非負(fù)權(quán)值網(wǎng)絡(luò)的計(jì)算，是目前在求解最短路徑問題較為完備且應(yīng)用廣泛的算法之一，可以計(jì)算出圖中從指定結(jié)點(diǎn)到圖中其他任意節(jié)點(diǎn)之問的最短路徑。 Dijkstra 算法 的缺點(diǎn)就是當(dāng)網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)量較大時(shí)，就會增加算法的復(fù)雜度，降低了效率。在初始狀態(tài)下，原始節(jié)點(diǎn) S 的路徑長度值被賦為 0即 dis 的值為 0， 同時(shí)假設(shè)其他所有節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑長度為無窮大，用無窮大長度的路徑表示任何其他節(jié)點(diǎn)到該結(jié)點(diǎn)的路徑是未知的。 Dijkstra 算法的操作對邊進(jìn)行了拓展：如果從 U 到 v 的路徑 是存在的，將邊 (u， v)添加到(s， v)尾部，則這條新的路徑的長度為 dM+w(u， v)。這種拓展邊的迭代運(yùn)算一直進(jìn)行，一直運(yùn)行到所有的 dM都代表從 S到 v 最短路徑為止。集合 P 初始狀態(tài)為空，而后每一步都有一個(gè)結(jié)點(diǎn)從集合 Q 中轉(zhuǎn)移到集合 P 中，并相應(yīng)的在 Q 中刪除該節(jié)點(diǎn)信息。當(dāng)節(jié)點(diǎn) s 向 D 轉(zhuǎn)發(fā)數(shù)據(jù)分組時(shí)，他首先找到與相鄰節(jié)點(diǎn)中距離最小的那個(gè)節(jié)點(diǎn)，然后將數(shù)據(jù)分組轉(zhuǎn)發(fā)給那個(gè)節(jié)點(diǎn)，將距離最小的那個(gè)節(jié)點(diǎn)稱為跳點(diǎn)，然后將 S 的數(shù)據(jù)傳送給這個(gè)跳點(diǎn)，該過程需要一直迭代計(jì)算，直到分組數(shù)據(jù)全部到達(dá)節(jié)點(diǎn) D。在發(fā)生生無法傳送數(shù)據(jù)時(shí)，節(jié)點(diǎn)能夠 探測到周圍的空洞，并利用右手法則沿著空洞周圍的節(jié)點(diǎn)傳輸數(shù)據(jù)來解決這類問題。但該算法存在這一定的缺點(diǎn)，當(dāng)網(wǎng)絡(luò)中的某節(jié)點(diǎn)與源點(diǎn)集中在兩個(gè)區(qū)域時(shí)，由于通信的不平衡能夠?qū)е虏糠止?jié)點(diǎn)無效，從而是網(wǎng)絡(luò)的連通性遭到破壞；另一方面是該方法需要 GPS 定位系統(tǒng)的輔助來計(jì)算幾點(diǎn)的位置信息 。在實(shí)際的路線選取過程中，我們將路口與上述的結(jié)點(diǎn)對用。 2． 2 圖論簡介 圖論 (Graph Theory)是組合數(shù)學(xué)的一個(gè)分支，它源于瑞士數(shù)學(xué)家歐(Euler)1736 年對于著名的哥尼斯堡七橋問題的解決，從而使歐拉成為了圖論 的創(chuàng)始人。在圖論被提出后的兩百年中，圖論的發(fā)展相對緩慢，但自從圖論與大量的實(shí)際問題相結(jié)合，在物理學(xué)、化學(xué)、信息論、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、控制論、社會科學(xué)，經(jīng)濟(jì)管理等各種學(xué)科中找到了更廣泛的應(yīng)用，使圖論在近幾十年來得到了快速的的發(fā)展。前者主要研究圖的性質(zhì)，后者主要討論與圖有關(guān)的優(yōu)化問題。圖論中的圖是由若干節(jié)點(diǎn)以及兩節(jié)點(diǎn)之間的連線所構(gòu)成 的圖形，圖論的研究對象是圖，這種圖形不考慮點(diǎn)的大小、形狀和邊的形狀、長度、大小以及邊與邊的角度等幾何問武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 6 題，而主要表達(dá)的是點(diǎn)點(diǎn)之間通過線的連通關(guān)系，通?？梢杂脕砻枋瞿承┦挛镏g的相互關(guān)系，即用點(diǎn)來代表事件發(fā)生，用連接兩點(diǎn)的邊表示兩個(gè)事件之間的關(guān)系。 2. 2. 1 圖的概念 無向圖是指有序三元組 (V， E,F)中邊沒有方向，其中集合 y 被稱為結(jié)點(diǎn)集，y中的元素稱為結(jié)點(diǎn)：集合 E被稱為邊集， E中的元素被稱為邊；而函數(shù)是邊集E到無序結(jié)點(diǎn)對兒所構(gòu)成的 集合的一個(gè)映射關(guān)系，稱之為關(guān)聯(lián)函數(shù)。兩個(gè)結(jié)點(diǎn)，且滿足 F(E)=uv，那么就可稱為 e連接：并且稱Ⅳ， y為 E 的端點(diǎn)。每個(gè)結(jié)點(diǎn)度數(shù)相同的簡單圖稱為正則圖，最大度與最小度恰好相差 1 的簡單圖被稱為幾乎正則圖。 2． 2． 2 圖的表示 由點(diǎn)集合 V 和點(diǎn)與 點(diǎn)之間的連線的集合 E 所組成的集合對 (V， E)可以構(gòu)成圖，用 G(V,E)來表示。也由它的結(jié)點(diǎn)對兒之間的鄰接關(guān)系唯一確定。節(jié)點(diǎn)集合 V 與邊集合 E 均為有限的圖稱為有限圖。在鄰接表中，圖中的每個(gè)節(jié)點(diǎn)都會有一個(gè)單鏈表與之對應(yīng)，第 i 個(gè)單鏈表中的結(jié)點(diǎn)數(shù)據(jù)表示依附于結(jié)點(diǎn) v。每個(gè)鏈表都會有一個(gè)表頭結(jié)點(diǎn)與之對應(yīng)，在表頭結(jié)點(diǎn)中，設(shè)有存儲結(jié)點(diǎn) q 的各個(gè)域及與該信息有關(guān)的相關(guān)數(shù)據(jù)域。 (2)十字鏈表 十字鏈表針對有向圖的另一種存儲結(jié)構(gòu)。在十字鏈表中，每一條邊都有一個(gè)節(jié)點(diǎn)與之對應(yīng)，每一個(gè)節(jié)點(diǎn)也有一個(gè)節(jié)點(diǎn)與之對應(yīng)。對幾個(gè)經(jīng)典的最優(yōu)路徑選擇算法進(jìn)行了介紹，如 Floyd 算法、 Dijkstra 算法、 GPSR 算法，并分析了他們的優(yōu)點(diǎn)和不足。 adfvex nextarc info data firstarc 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 8 3 最優(yōu)路徑 最優(yōu)路徑選擇和交通系統(tǒng)優(yōu)化的目的就是是交通流均衡化，合理的在交通系統(tǒng)中分配，提高交通運(yùn)輸效率。一般地，交通網(wǎng)絡(luò)有如下特點(diǎn)： (1)線性分布，交通網(wǎng)絡(luò)結(jié)構(gòu)在空問分布中一般呈現(xiàn)線性特征，因此交通網(wǎng)絡(luò)建模可以依靠圖論的相關(guān)理論和知識； (2)網(wǎng)絡(luò)分布，交通網(wǎng)絡(luò)是一個(gè)負(fù)載的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，連通性好，結(jié)構(gòu)復(fù)雜： (3)分段分布，交通系統(tǒng)中不同路段的特征一般不同，表現(xiàn)為空間的差異性，且同一路段的不同時(shí)間的交通網(wǎng)絡(luò)特征也可能不同，表現(xiàn)為時(shí)間差異性； (4)動(dòng)態(tài)性特點(diǎn)，交通網(wǎng)絡(luò)上交通狀況不是一層不變的，隨時(shí)間的變化而變化，失意 是 時(shí)變系統(tǒng)： (5)車輛行駛的主觀性，交通網(wǎng)絡(luò)不同于其它網(wǎng)絡(luò)，交通網(wǎng)絡(luò)的主體可以自主的選擇交通路徑，行駛時(shí)間和行駛路線等是他的一個(gè)最顯著特征。以完整的交通道路作為建模的基本單元，但在交通應(yīng)用當(dāng)中，交通特征的變化在交通系統(tǒng)的具體應(yīng)用當(dāng)中經(jīng)常和車道關(guān)聯(lián)密切。 3． 1 建立城市交通模型 利用圖論 的相關(guān)理論和知識，對圖中的節(jié)點(diǎn)和邊設(shè)法加入車道信息用于模擬就哀痛系統(tǒng)。首先，在同一條道路上不同的車道在不同的行駛方向的交通特征可能不同，如交通量變化和交通規(guī)則等。其次， 不同方向的 車道由于具有不同的拓?fù)潢P(guān)系，因此交通規(guī)則有可能不同。為建立點(diǎn)線各個(gè)元素之間的空間拓?fù)潢P(guān)系，使他們構(gòu)成有機(jī)整體，需要分別在存儲點(diǎn)線信息的兩張表文件中擴(kuò)展一定長度的字段，用對象的屬性字段之問的相互聯(lián)系來建立交通網(wǎng)絡(luò)圖的拓?fù)潢P(guān)系，這樣就建立了交通網(wǎng)絡(luò)系統(tǒng)的有機(jī)整體即他們的拓?fù)潢P(guān)系結(jié)構(gòu)圖。在實(shí)際情 況中人民出行是從一個(gè)地方到另一個(gè)地方，這種不能簡單的歸結(jié)在圖中從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的轉(zhuǎn)移，實(shí)際情況的交通網(wǎng)絡(luò)運(yùn)行是非常復(fù)雜的，所以不能簡單的把某一個(gè)具體的地方當(dāng)成是圖中的某個(gè)節(jié)點(diǎn)，把道路信息抽象成圖中帶有權(quán)值的邊，而是要將具體的地址信息抽象為節(jié)點(diǎn)以及其附屬信息并加入到交通網(wǎng)絡(luò)系統(tǒng)中。 3． 1． 2 交叉口和道路模型