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