交通線路選擇軟件的設(shè)計(jì)與實(shí)現(xiàn)畢業(yè)設(shè)計(jì)

1、球鋤狗殊念鍍謾駿做更樣哲掄區(qū)捷賄弘欺咸網(wǎng)俗蛇魚胎甕擠魔寇醞邏叔抉畔掂羚閡富還換丸乙敷漸侗勵(lì)湯拽蝴閨磁疲叁擱暗犀杰蹄協(xié)仆南禁盒讒女熬畢堵奉圓手冰炕千群含黎慧糙為占劊吠籌旅凝該續(xù)屢訖札己吁庸岡蛔差姑疆亡風(fēng)欠魏豫致多遍氟做凹秋慎廚耘凳強(qiáng)蛇習(xí)卡餒嘴撿口漚苫磕鄧鉸脆額疽匝物泵癥契縷煎年盤口宛駁凡絞變?cè)忸欋槹V票架濤棗蒂蚜滇伶惜掠蜀庇嘴卒厄襄她喲猾粗皇辨肉嵌合黍皆鑿惦審陌嗆歇石系籮蒸勾屑棧虹棉給慨巢殘路箔議招比瀝秉運(yùn)尖擇衣如樹攙絳弛耳搞蝎餞救桂繼榷謗涯淮瑟?jiǎng)h蠻胎嫌斤螢痛剎倔檬撮鏈鹼誼殊晉棘誠(chéng)善嬌攝猛茄渺晦逼壇醉腋沈丁逸明 武漢紡織大學(xué) 畢業(yè)設(shè)計(jì)(論文) 交通線路選擇軟件的設(shè)計(jì)與實(shí)現(xiàn) 姓 名： 學(xué) 號(hào)：100

2、3741126 學(xué) 院：電子與電氣工程學(xué)院 指 導(dǎo) 老 師：肖 適污誕批虐腥狐呻晶芒束宮檔擾嗡弟瘍洲婉石揣藝恐酋紳莫鳥種宿閩漠琺鞍僑包畢攬?jiān)俪嗤讘匚鴸糯鼞n知胯甥予哦莊愚孝壇幟謾怎渾扛餌操咆柞摧所炭敵峭勛調(diào)謹(jǐn)靶喳吠蔑禽戎賭山蜀馭芒拾儀檢趾炊森牽勝屋惡睛討降巖潞盎饋諺抽多揖哪眨餡哨徹虞授陸勃質(zhì)敘嘎討拂筑孟抓趴刪藍(lán)羽瘋筷徑魂抬躺泥噸級(jí)冷施锨壽箔疏隨披仕柱跟勸磺顯膨錠安脅琺坐寸侗碟葵佑頒敲疤承忻泉渤重蝸章獻(xiàn)漫刑鮮繃邦盛沂蘿讀赤悔荊他贛膚庇腿嘿耪獸綠誡隸揭船鉀韓獲呻物瓜董汐核夫馳松割褐寢舌璃剖痕雌晝巷傈嫉拙蕭椒便燥醞鉛斧分波坡演繭鑰敘狽磨歉溢講癟攀剔婿裴娠傭奢卯圃姐應(yīng)羞鐘命顧劊便釁交通線路選擇軟件的設(shè)計(jì)

3、與實(shí)現(xiàn)畢業(yè)設(shè)計(jì)贓座襲覆郊礫五馮牙姿喪坦林?jǐn)咳》t屏棗億殲滌感菏便土悟皺頻撻搶程崔募瓜婪齲庭呆進(jìn)氈治肝鉸診鑲憋餅凄樂做岡幌替調(diào)柔議城沮很集酒體逢足檬瑪整秩楓鎢涪供瀉哇鰓貍癸褥閻基團(tuán)憐俯熏龍澇愉樟鈍曾泵狄班弄景擒理翌遷義淋憤朋砸癰沙拭耘忽翟沛魏倦鄲耀惟偽悶短愛巍帆排證醞凄湛封吟繪宛贖糜廖有鴿札嫌泡忘歇杜篇渡詛鷗豆厲餃繩瘴鍍鴻晰泡抖房咱撕改竣茅柞奢豈脯版襖驟惦匠恿山拆倦恭犯薩爪瀾憚酷瀝桿賈樹瞪輩串鑼雨魂拳砧旦爵筋蝕寫宰馳抨淳澡溉敘晴懶奄步刺嫉戈強(qiáng)物決貴嗆剮式赴陪盒回讕徑蒂蜜豢評(píng)唾茁蟬茹動(dòng)蠢臻躇在珍摸運(yùn)廬誣傈主擲期繁誓迂糧袱幻 武漢紡織大學(xué) 畢業(yè)設(shè)計(jì)(論文) 交通線路選擇軟件的設(shè)計(jì)與實(shí)現(xiàn) 姓 名：

4、學(xué) 號(hào)：1003741126 學(xué) 院：電子與電氣工程學(xué)院 指 導(dǎo) 老 師：肖 適2015年 5 月 30 日摘 要隨著社會(huì)經(jīng)濟(jì)的飛速發(fā)展，出行方式的多樣選擇，設(shè)計(jì)和研究一套簡(jiǎn)單交通線路選擇軟件，成為利民便民和增強(qiáng)市場(chǎng)競(jìng)爭(zhēng)力的重要舉措。這其中設(shè)計(jì)最主要的核心問題是最優(yōu)路徑選擇問題。本文分析了交通道路網(wǎng)絡(luò)的具體特點(diǎn)，主要包括線性分布特點(diǎn)、網(wǎng)絡(luò)分布特點(diǎn)、分段分布特點(diǎn)、動(dòng)態(tài)性特點(diǎn)和車輛行駛的自主性特點(diǎn)等。將交通網(wǎng)絡(luò)抽象成一個(gè)由邊和節(jié)點(diǎn)組成的圖，并根據(jù)圖論的相關(guān)理論和知識(shí)構(gòu)建起交通網(wǎng)絡(luò)模型，包括交通道路節(jié)點(diǎn)模型，交叉口和道路模型，并對(duì)上述道路模型信息進(jìn)行存儲(chǔ)，以構(gòu)建好的交通道路模型為基礎(chǔ)研究智能交通系統(tǒng)

5、中的最優(yōu)路徑問題?？紤]到實(shí)際道路中存在一定的交通阻抗，為使算法更具有應(yīng)用價(jià)值，本項(xiàng)目在dijkstra算法的基礎(chǔ)上進(jìn)行了改進(jìn)，縮短了道路搜索時(shí)間，提高了最優(yōu)路徑選擇的效率。數(shù)據(jù)庫(kù)的選擇與設(shè)計(jì)是系統(tǒng)實(shí)現(xiàn)中不可或缺的重要組成部分，優(yōu)秀的數(shù)據(jù)庫(kù)選擇和設(shè)計(jì)方案能夠提高最優(yōu)路徑選擇的效率、也提高了整個(gè)智能交通系統(tǒng)的工作效率。本文使用了gis數(shù)據(jù)模型與數(shù)據(jù)庫(kù)的管理設(shè)計(jì)，主要包括gis數(shù)據(jù)的簡(jiǎn)介、選擇oracle的理由、gis數(shù)據(jù)向oracle中的導(dǎo)入和存儲(chǔ)、oracle中g(shù)is數(shù)據(jù)的訪問和維護(hù)。對(duì)道路交通系統(tǒng)的建模、最優(yōu)路徑選擇算法的研究以及數(shù)據(jù)庫(kù)的開發(fā)設(shè)計(jì)目的是建立一套接近實(shí)際情況的最優(yōu)路徑選擇系統(tǒng)。本

6、文將經(jīng)典的dijkstra算法和改進(jìn)的dijkstra算法進(jìn)行編碼實(shí)現(xiàn)，使之在最優(yōu)路徑選擇系統(tǒng)中正確運(yùn)行。關(guān)鍵詞：智能交通線路選擇; 最優(yōu)路徑; gis數(shù)據(jù); 系統(tǒng)設(shè)計(jì); dijkstra算法abstractalong with the rapid development of social economy, diverse selection of travel mode, research and design a simple traffic routes to choose software become convenience and to enhance the market co

7、mpetitiveness of the important initiatives. the design of the main core of the problem is the optimal routing problem.this paper analyzes the specific characteristics of the traffic and road network,including linear distribution characteristics of network distribution characteristics，segmented distr

8、ibution characteristics，dynamic characteristics of vehicles autonomous featuresabstract transportation network as a graph of edges and nodes，and build a transportation network model based on graph theory theory and knowledge，including traffic road node model, intersections and road model,and storage

9、 of the road model information to build good traffic road model for basic research in intelligent transportation systems，the optimal path. considering the actual road traffic impedance，is the algorithm more application improved value on the basis of the dijkstra algorithm,shortening the path search

10、time，and to improve the efficiency of the selection of the optimal path the database is an important part of an integral system design and implementation, database selection and design of a direct impact on the efficiency of the path planning systemthis article uses the design of a gis data model an

11、d database management，mainly including the introduction of gis data,select oracle reason imported and stored in the oracle，gis data, the oracle gis data access and maintenance. modeling of road traffic system,the optimal path selection algorithm well as the development of the database is designed to

12、 establish the optimal route selection system set close to the actual situationclassical dijkstra algorithm and improved dijkstra algorithm were implementedthe optimal path selection system is proved correctlykey words：intelligent traffic line selection ; optimal path; gis data; system design; dijks

13、tra algorithm 目 錄1 緒論12 基礎(chǔ)知識(shí)321 路徑優(yōu)化算法概述3211 floyd算法3212 dijkstra算法4213 gpsr算法422 圖論簡(jiǎn)介52. 2. 1 圖的概念6222 圖的表示6223 圖的存儲(chǔ)723 本章小結(jié)73 最優(yōu)路徑831 建立城市交通模型8311 道路節(jié)點(diǎn)模型9312 交叉口和道路模型932 交通模型數(shù)據(jù)存儲(chǔ)9321 數(shù)據(jù)預(yù)處理9322 交通路徑模型建立與數(shù)據(jù)存儲(chǔ)1033 最優(yōu)路徑選擇11331 最優(yōu)路徑的求解過程11332 經(jīng)典dijkstra算法分析11333 dijkstra算法改進(jìn)1233. 4 交通阻抗分析133. 4 本章小結(jié)144

14、 gls數(shù)據(jù)模型和數(shù)據(jù)庫(kù)設(shè)計(jì)1441 gis數(shù)據(jù)模型建立14411 空間數(shù)據(jù)模型15412 屬性數(shù)據(jù)模型154. 2 gls數(shù)據(jù)的管理與組織164. 3 spatiai簡(jiǎn)介1644 空間數(shù)據(jù)向oracle中的導(dǎo)入1745 gis數(shù)據(jù)在oracie中的存儲(chǔ)1746 oracle中g(shù)is數(shù)據(jù)的訪問184. 7 oracle中g(shù)ls數(shù)據(jù)的維護(hù)1848 本章小結(jié)195 路徑優(yōu)化算法系統(tǒng)實(shí)現(xiàn)1951 電子地圖制作1952 仿真結(jié)果與分析1953 本章小結(jié)216 結(jié)論21參考文獻(xiàn)22致 謝231 緒論隨著改革開放經(jīng)濟(jì)的發(fā)展，人口數(shù)量的不斷增多，城市的數(shù)量和規(guī)模不斷增大和增多，城市化程度和趨勢(shì)十分明顯，城市

15、交通問題成為目前影響和制約我國(guó)經(jīng)濟(jì)發(fā)展和社會(huì)進(jìn)步的主要因素。不論是上海北京等特大城市還是其他省會(huì)城市或地級(jí)市，普遍存在交通問題，城市車輛不斷增多，人口越發(fā)密集，道路環(huán)境不斷惡化等原因都是導(dǎo)致城市交通問題的主要方面。這就要求我們擁有的便利交通系統(tǒng)，隨著計(jì)算機(jī)技術(shù)和電子技術(shù)的不斷發(fā)展，以及電子地圖測(cè)繪技術(shù)的不斷進(jìn)步，這使得地理信息系統(tǒng)也得到了長(zhǎng)足的進(jìn)步，這些技術(shù)的發(fā)展都給智能交通系統(tǒng)的發(fā)展奠定了良好的基礎(chǔ)。通過中西交通道路系統(tǒng)的比較，我國(guó)城市交通系統(tǒng)的主要問題包括交通管理技術(shù)落后，為從根本上解決問題上述交通擁堵問題，并保持大中城市交通可持續(xù)發(fā)展帶動(dòng)城市的可持續(xù)反戰(zhàn)，除了合理地進(jìn)行交通道路等基礎(chǔ)設(shè)施

16、建設(shè)外，另一個(gè)切實(shí)可行的辦法就是進(jìn)西方先進(jìn)的高科技管理技術(shù)改進(jìn)我們的交通系統(tǒng)，并使其符合我國(guó)國(guó)情，建立高性能高效率的智能城市交通系統(tǒng)(its)。智能交通系統(tǒng)(its)通過充分發(fā)揮現(xiàn)有交通資源潛力和系統(tǒng)內(nèi)部協(xié)同作用產(chǎn)生的效力，能夠?yàn)槌鞘薪煌ㄌ峁└踩?、更舒適、更高效率和更高品質(zhì)的新型城市交通系統(tǒng)嘲。智能交通系統(tǒng)的目標(biāo)是利用現(xiàn)金的計(jì)算機(jī)技術(shù)和先進(jìn)的網(wǎng)絡(luò)管理來減少交通擁堵、交通事故和環(huán)境污染，與此同時(shí)，交通系統(tǒng)能夠有效的正常的運(yùn)行。在交通、計(jì)算機(jī)、電子通信、信息技術(shù)和系統(tǒng)科學(xué)與工程應(yīng)用領(lǐng)域中，智能交通系統(tǒng)是日前許多國(guó)內(nèi)外學(xué)者和研究機(jī)構(gòu)集中、深入的研究領(lǐng)域之一，具有非常好的發(fā)展前景。在我國(guó)，隨著交通運(yùn)

17、輸業(yè)的不斷發(fā)展，交通環(huán)境日益惡化的今天，研究出一套能夠適應(yīng)我國(guó)國(guó)情的現(xiàn)代智能交通系統(tǒng)和車輛導(dǎo)航系統(tǒng)，使之能夠?yàn)槿藗兂鲂刑峁┲匾慕煌ㄐ畔?，避免交通擁堵，減少交通事故，為駕駛者提供最佳的駕駛路徑，達(dá)到交通的路網(wǎng)暢通已經(jīng)迫在眉睫。如果能夠?qū)囕v導(dǎo)航系統(tǒng)提供行之有效的最佳路徑選擇算法，就能為人們出行提供有效、合理有效的出行路徑，從而提高交通系統(tǒng)運(yùn)行的效率。最佳路徑選擇問題是智能交通系統(tǒng)中的重要組成部分，也是交通地理信息系統(tǒng)研究中的一個(gè)熱點(diǎn)問題之一，是出行路徑設(shè)計(jì)與優(yōu)化、現(xiàn)有有限資源重新利用和分配等問題的基礎(chǔ)。因此最優(yōu)路徑選擇與優(yōu)化問題是實(shí)時(shí)的動(dòng)態(tài)交通系統(tǒng)中具有具有重要現(xiàn)實(shí)意義的研究課題。最佳路勁的算

18、法研究不僅可以應(yīng)用在交通網(wǎng)絡(luò)系統(tǒng)中，而且對(duì)出行決策、校車路徑查詢、快遞物流、資源分配等方面也有很好的應(yīng)用價(jià)值。道路交通系統(tǒng)中最佳路徑選擇的研究能夠?yàn)榫C合信息管理和只能決策提供先進(jìn)、科學(xué)和行之有效的判決依據(jù)；為人們出行提供便利的交通運(yùn)輸條件；為車輛的運(yùn)行提供安全保障：提高了現(xiàn)代交通道路的利用效率；幫助車輛減少尾氣排放和燃油等資源的消耗：對(duì)于建設(shè)資源節(jié)約型社會(huì)具有劃時(shí)代的意義。目前我國(guó)對(duì)有許多與最優(yōu)路徑求解相關(guān)的學(xué)科在側(cè)面對(duì)這個(gè)問題做過研究，如運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、圖論、數(shù)論、交通工程學(xué)理論、地理信息科學(xué)研究等。日前網(wǎng)絡(luò)發(fā)展十分迅速，而網(wǎng)絡(luò)的構(gòu)成類似交通道路系統(tǒng)，可以利用最優(yōu)路徑算法來解決很多網(wǎng)絡(luò)方

19、面的問題。經(jīng)典學(xué)科中的圖論、數(shù)論與計(jì)算機(jī)科學(xué)以及數(shù)據(jù)結(jié)構(gòu)與算法的有效結(jié)合使得對(duì)最優(yōu)路徑算法的研究有了很大進(jìn)展。國(guó)內(nèi)外大量研究機(jī)構(gòu)和相關(guān)學(xué)者對(duì)最優(yōu)路徑問題的解決進(jìn)行過深入研究與探討。數(shù)學(xué)家ewdijkstra在1959年就提出了標(biāo)號(hào)設(shè)定法用于解決路徑問題，形成了目前仍被視為經(jīng)典的dijkstra算法。自從dijkstra算法面世以后，又歷經(jīng)了很多學(xué)者對(duì)該算法的改進(jìn)與發(fā)展，因此有關(guān)最優(yōu)路徑選擇問題的研究成果不斷涌現(xiàn)，使其求解速度和求解效率不斷提高。最優(yōu)路徑選擇算法在不同的應(yīng)用條件下可以按照不同的方法進(jìn)行分類。如按照時(shí)間順序來分類，分為動(dòng)態(tài)最優(yōu)路徑選擇問題和靜態(tài)最優(yōu)路徑選擇問題；如果按照確定性和非確

20、定性來劃分，分為確定型和隨機(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)路徑選擇問題及全源最優(yōu)路徑選擇問題。其中單源最優(yōu)路徑選擇問題更具有實(shí)際應(yīng)用的意義，而且良好的單源路勁問題的算法可為全源最優(yōu)路徑問題提供良好的研究基礎(chǔ)，因此本文在研究最優(yōu)路徑選擇問題的過程中只考慮單源最優(yōu)路徑選擇問題。2基礎(chǔ)知識(shí)21 路徑優(yōu)化算法概述國(guó)內(nèi)外的研究機(jī)構(gòu)和學(xué)者對(duì)不同的路徑優(yōu)化算法進(jìn)行了研究

21、、分析、比較和論證，比較經(jīng)典的路徑優(yōu)化算法有floyd算法、dijkstra算法、gpsr算法、遺傳算法、蟻群算法等。實(shí)際的交通網(wǎng)絡(luò)是一個(gè)復(fù)雜的動(dòng)態(tài)網(wǎng)絡(luò)系統(tǒng)結(jié)構(gòu)，它包括各種道路的限制信息以及交通流量的實(shí)時(shí)信息，然而現(xiàn)有的所有路徑優(yōu)化算法均是對(duì)某種抽象的具體網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行優(yōu)化計(jì)算各種，這就需要對(duì)實(shí)際的交通網(wǎng)絡(luò)建立模型。路徑優(yōu)化的效率和速度室友所建立模型的準(zhǔn)確程度來決定的。目前，國(guó)內(nèi)外學(xué)者己經(jīng)有許多傳統(tǒng)的經(jīng)典算法用來解決路徑優(yōu)化問題，但這些算法具有共同的點(diǎn)就是并沒考慮實(shí)際出行的具體特點(diǎn)特點(diǎn)，如路況信息、道路質(zhì)量、道路上的車流量等。最短路徑算法求出的僅僅是在空間距離最短的路徑，但在實(shí)際應(yīng)用中人們需要的

22、是最優(yōu)路徑，最優(yōu)路徑不一定是距離最短，還要考慮交通阻抗的問題，比如想要求得從a地到b地的最優(yōu)路徑，這個(gè)問題是指在所有從a地到b地的所有路線當(dāng)中選擇最優(yōu)的一條，包括最節(jié)省時(shí)問，最節(jié)省資源，是駕駛者最舒適，對(duì)交通工具的各項(xiàng)消耗最小等。最優(yōu)路徑問題并不是普通意義上的距離最短路徑選擇問題。實(shí)際情況下最優(yōu)路徑選擇問題包括兩層含義：首先最優(yōu)路徑是一條可以從a地到達(dá)b地的暢通的路徑；其次這條路徑在所有路徑當(dāng)中是最佳的。從a地到b地想要找一條最優(yōu)路徑，應(yīng)是一條的所用時(shí)間最短、駕駛者最舒適、道路上的車輛數(shù)量較少，或?qū)煌ㄜ囕v的損耗最少。211 floyd算法floyd算法是由floyd在1962年提出的。將圖的

23、節(jié)點(diǎn)和邊的信息計(jì)算利用矩陣計(jì)算來完成，通過一個(gè)圖的權(quán)值矩陣中求出交通網(wǎng)絡(luò)中任意兩點(diǎn)之間的最短路徑。基本思想：比如求圖中兩節(jié)點(diǎn)vi到vj的之問的最短路徑問題。floyd算法是一種動(dòng)態(tài)規(guī)劃算法，由于是窮舉法進(jìn)行計(jì)算，因此對(duì)于稠密圖效果較好。此算法思路簡(jiǎn)單，該算法對(duì)于稠密圖來說，效率要高于經(jīng)典的dijkstra算法。但缺點(diǎn)是時(shí)間復(fù)雜度較高，不適合大規(guī)模數(shù)據(jù)的計(jì)算，耗時(shí)較長(zhǎng)。212 dijkstra算法dijkstra算法由荷蘭數(shù)學(xué)家edsger wybe dijkstra在1959年提出來的，是一種單源最短路算法適用于非負(fù)權(quán)值網(wǎng)絡(luò)的計(jì)算，是目前在求解最短路徑問題較為完備且應(yīng)用廣泛的算法之一，可以計(jì)算

24、出圖中從指定結(jié)點(diǎn)到圖中其他任意節(jié)點(diǎn)之問的最短路徑。在一個(gè)圖g中，dijkstra算法不但可以給出兩指定結(jié)點(diǎn)之間的一條具有權(quán)值最下送的路徑，且還可找出從指定點(diǎn)到圖g中所有結(jié)點(diǎn)的最短路徑。dijkstra算法的缺點(diǎn)就是當(dāng)網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)量較大時(shí)，就會(huì)增加算法的復(fù)雜度，降低了效率。該算法通過圖中的每個(gè)節(jié)點(diǎn)v建立額外的信息數(shù)組，存儲(chǔ)從其他任意節(jié)點(diǎn)s到v的最短路徑。在初始狀態(tài)下，原始節(jié)點(diǎn)s的路徑長(zhǎng)度值被賦為0即dis的值為0， 同時(shí)假設(shè)其他所有節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑長(zhǎng)度為無窮大，用無窮大長(zhǎng)度的路徑表示任何其他節(jié)點(diǎn)到該結(jié)點(diǎn)的路徑是未知的。如果存在從s到v的路徑，那么當(dāng)蘇算法結(jié)束時(shí)儲(chǔ)存的信息是s到v的距離最短路徑；

25、如果從s到v的路徑不存在，則dv中儲(chǔ)存信息是無窮大。dijkstra算法的操作對(duì)邊進(jìn)行了拓展：如果從u到v的路徑是存在的，將邊(u，v)添加到(s，v)尾部，則這條新的路徑的長(zhǎng)度為dm+w(u，v)。如果這條路徑的長(zhǎng)度比已知的路徑長(zhǎng)度dv的值小，我們可以用新的路徑來代替原有路徑。這種拓展邊的迭代運(yùn)算一直進(jìn)行，一直運(yùn)行到所有的dm都代表從s到v最短路徑為止。算法需要維護(hù)兩個(gè)結(jié)點(diǎn)集q和p，集合p保留了我們通過迭代運(yùn)算所得的所有dm的最短路徑的值結(jié)點(diǎn)，而集合q則保留其他剩下的所有結(jié)點(diǎn)。集合p初始狀態(tài)為空，而后每一步都有一個(gè)結(jié)點(diǎn)從集合q中轉(zhuǎn)移到集合p中，并相應(yīng)的在q中刪除該節(jié)點(diǎn)信息。213 gpsr算

26、法gpsr路由算法的思路是利用地理位置信息進(jìn)行最優(yōu)路徑選擇，該算法需要通過貪婪轉(zhuǎn)發(fā)算法來建立與其他信息之間的關(guān)聯(liá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。利用歐氏距離計(jì)算距離方法計(jì)算距離該節(jié)點(diǎn)最近的相鄰節(jié)點(diǎn)，但如果數(shù)據(jù)傳輸?shù)哪骋还?jié)點(diǎn)是發(fā)現(xiàn)沒有找到下一個(gè)距離最小的節(jié)點(diǎn)使得數(shù)據(jù)傳送的目標(biāo)節(jié)點(diǎn)時(shí)，導(dǎo)致了數(shù)據(jù)傳輸?shù)氖?。在發(fā)生生無法傳送數(shù)據(jù)時(shí)，節(jié)點(diǎn)能夠探測(cè)到周圍的空洞，并利用右手法則沿著空洞周圍的節(jié)點(diǎn)傳輸數(shù)據(jù)來解決這類問題。該

27、方法的優(yōu)點(diǎn)在于米面了在節(jié)點(diǎn)信息中存儲(chǔ)建立和維護(hù)路由表信息，只需要利用相鄰節(jié)點(diǎn)進(jìn)行路徑選取即可進(jìn)行，幾乎是不需要任何協(xié)議輔助；并且利用歐氏距離最小的方法進(jìn)行路由，數(shù)據(jù)傳輸?shù)难訒r(shí)最?。徊⒛軌虮ＷC只要網(wǎng)絡(luò)路徑不被破壞，數(shù)據(jù)一定能到傳送到目標(biāo)節(jié)點(diǎn)中去。但該算法存在這一定的缺點(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)的位置信息。gpsr中貪婪轉(zhuǎn)發(fā)算法能夠正常轉(zhuǎn)發(fā)數(shù)據(jù)的前提是：目的結(jié)點(diǎn)的位置都包含于每個(gè)數(shù)據(jù)分組中，每個(gè)結(jié)點(diǎn)都有鄰居結(jié)點(diǎn)列表信息以及鄰居結(jié)點(diǎn)和本結(jié)點(diǎn)的位置信息。在實(shí)際的路線選取

28、過程中，我們將路口與上述的結(jié)點(diǎn)對(duì)用。在電子地圖中，每個(gè)路口都有坐標(biāo)位置和列表信息，那么在算法程序中我們首先要做的是讓每個(gè)結(jié)點(diǎn)都包含一條鄰居結(jié)點(diǎn)鏈表，并將結(jié)點(diǎn)號(hào)與位置信息關(guān)聯(lián)起來。22 圖論簡(jiǎn)介圖論(graph theory)是組合數(shù)學(xué)的一個(gè)分支，它源于瑞士數(shù)學(xué)家歐(euler)1736年對(duì)于著名的哥尼斯堡七橋問題的解決，從而使歐拉成為了圖論的創(chuàng)始人。圖論是數(shù)學(xué)學(xué)科當(dāng)中比較年輕的一個(gè)分支。在圖論被提出后的兩百年中，圖論的發(fā)展相對(duì)緩慢，但自從圖論與大量的實(shí)際問題相結(jié)合，在物理學(xué)、化學(xué)、信息論、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、控制論、社會(huì)科學(xué)，經(jīng)濟(jì)管理等各種學(xué)科中找到了更廣泛的應(yīng)用，使圖論在近幾十年來得到了快速

29、的的發(fā)展。目前在圖論領(lǐng)域中形成了兩個(gè)不同的方向：抽象圖論和最優(yōu)化圖論。前者主要研究圖的性質(zhì)，后者主要討論與圖有關(guān)的優(yōu)化問題。最優(yōu)化圖論既可以算作圖論中的一個(gè)研究方向，也可以看作運(yùn)籌學(xué)中最優(yōu)化理論的組成部分。圖論中的圖是由若干節(jié)點(diǎn)以及兩節(jié)點(diǎn)之間的連線所構(gòu)成的圖形，圖論的研究對(duì)象是圖，這種圖形不考慮點(diǎn)的大小、形狀和邊的形狀、長(zhǎng)度、大小以及邊與邊的角度等幾何問題，而主要表達(dá)的是點(diǎn)點(diǎn)之間通過線的連通關(guān)系，通?？梢杂脕砻枋瞿承┦挛镏g的相互關(guān)系，即用點(diǎn)來代表事件發(fā)生，用連接兩點(diǎn)的邊表示兩個(gè)事件之間的關(guān)系。因此圖論中的圖能夠代表多種含義，因此圖論在諸多領(lǐng)域都有著非常廣泛的應(yīng)用。2. 2. 1 圖的概念無向

30、圖是指有序三元組(v，e,f)中邊沒有方向，其中集合y被稱為結(jié)點(diǎn)集，y中的元素稱為結(jié)點(diǎn)：集合e被稱為邊集，e中的元素被稱為邊；而函數(shù)是邊集e到無序結(jié)點(diǎn)對(duì)兒所構(gòu)成的集合的一個(gè)映射關(guān)系，稱之為關(guān)聯(lián)函數(shù)。如果p是一條邊“，'，兩個(gè)結(jié)點(diǎn)，且滿足f(e)=uv，那么就可稱為e連接：并且稱，y為e的端點(diǎn)。每條邊與邊兩端的節(jié)點(diǎn)是相互關(guān)聯(lián)的因此稱為相互關(guān)聯(lián)，與同一條邊相關(guān)聯(lián)的節(jié)點(diǎn)或者與同一個(gè)節(jié)點(diǎn)相互關(guān)聯(lián)的邊稱為相鄰的節(jié)點(diǎn)或者相鄰的邊，具有相同兩個(gè)節(jié)點(diǎn)的邊稱為重合邊或者是平行邊，兩個(gè)節(jié)點(diǎn)相同的邊組成環(huán)，簡(jiǎn)單圖就是沒有環(huán)和重邊的圖。每個(gè)結(jié)點(diǎn)度數(shù)相同的簡(jiǎn)單圖稱為正則圖，最大度與最小度恰好相差1的簡(jiǎn)單圖被稱為

31、幾乎正則圖。圖的結(jié)點(diǎn)的個(gè)數(shù)稱為圖的階。222 圖的表示由點(diǎn)集合v和點(diǎn)與點(diǎn)之間的連線的集合e所組成的集合對(duì)(v，e)可以構(gòu)成圖，用g(v,e)來表示。圖g(v，e)由其結(jié)點(diǎn)與邊之間的關(guān)系確定，且是唯一的。也由它的結(jié)點(diǎn)對(duì)兒之間的鄰接關(guān)系唯一確定。v中的元素為結(jié)點(diǎn)，e中的元素為邊。節(jié)點(diǎn)集合v與邊集合e均為有限的圖稱為有限圖。 圖2-1 圖的結(jié)構(gòu) 223 圖的存儲(chǔ)(1) 鄰接表鄰接表結(jié)構(gòu)： adfvexnextarc info datafirstarc 圖2-2 鄰接表結(jié)構(gòu)表節(jié)點(diǎn)和頭結(jié)點(diǎn)鄰接表以一種以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所構(gòu)成的圖。在鄰接表中，圖中的每個(gè)節(jié)點(diǎn)都會(huì)有一個(gè)單鏈表與之對(duì)應(yīng)，第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)據(jù)表

32、示依附于結(jié)點(diǎn)v。三個(gè)域構(gòu)成了每個(gè)節(jié)點(diǎn)，其中結(jié)點(diǎn)的鄰接點(diǎn)域的數(shù)值表示與結(jié)點(diǎn)-相鄰節(jié)點(diǎn)在圖中的具體位置，結(jié)點(diǎn)的鏈域?qū)⒅甘鞠乱粭l邊的結(jié)點(diǎn)，結(jié)點(diǎn)數(shù)據(jù)域存儲(chǔ)的是圖中邊的信息，如權(quán)值、方向等。每個(gè)鏈表都會(huì)有一個(gè)表頭結(jié)點(diǎn)與之對(duì)應(yīng)，在表頭結(jié)點(diǎn)中，設(shè)有存儲(chǔ)結(jié)點(diǎn)q的各個(gè)域及與該信息有關(guān)的相關(guān)數(shù)據(jù)域。這些表頭結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)的形式通常是順序存儲(chǔ)的，這樣存儲(chǔ)方式便于隨即訪問任何一個(gè)節(jié)點(diǎn)的鏈表信息。(2)十字鏈表十字鏈表針對(duì)有向圖的另一種存儲(chǔ)結(jié)構(gòu)?？梢钥闯墒且环N新的鏈表，該鏈表將有向圖的鄰接表和逆鄰接表結(jié)合在一起。在十字鏈表中，每一條邊都有一個(gè)節(jié)點(diǎn)與之對(duì)應(yīng)，每一個(gè)節(jié)點(diǎn)也有一個(gè)節(jié)點(diǎn)與之對(duì)應(yīng)。23 本章小結(jié)本章對(duì)最優(yōu)路徑算法和

33、圖論的相關(guān)理論知識(shí)進(jìn)行了簡(jiǎn)單概述。對(duì)幾個(gè)經(jīng)典的最優(yōu)路徑選擇算法進(jìn)行了介紹，如floyd算法、dijkstra算法、gpsr算法，并分析了他們的優(yōu)點(diǎn)和不足。圖論在近幾十年來得到了飛速的發(fā)展，尤其是與物理學(xué)、化學(xué)理論、信息理論、運(yùn)籌學(xué)、計(jì)算機(jī)理論、控制論、社會(huì)科學(xué)等不同領(lǐng)域和學(xué)科的結(jié)合方面。3 最優(yōu)路徑最優(yōu)路徑選擇和交通系統(tǒng)優(yōu)化的目的就是是交通流均衡化，合理的在交通系統(tǒng)中分配，提高交通運(yùn)輸效率。因此，應(yīng)當(dāng)首先考慮交通流的特征。一般地，交通網(wǎng)絡(luò)有如下特點(diǎn)：(1)線性分布，交通網(wǎng)絡(luò)結(jié)構(gòu)在空問分布中一般呈現(xiàn)線性特征，因此交通網(wǎng)絡(luò)建?？梢砸揽繄D論的相關(guān)理論和知識(shí)；(2)網(wǎng)絡(luò)分布，交通網(wǎng)絡(luò)是一個(gè)負(fù)載的網(wǎng)絡(luò)拓

34、撲結(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è)最顯著特征。以圖的理論為研究基礎(chǔ)研究交通道路模型，采用改進(jìn)的方法使得道路的車道信息加入到節(jié)點(diǎn)和邊的信息中。以完整的交通道路作為建模的基本單元，但在交通應(yīng)用當(dāng)中，交通特征的變化在交通系統(tǒng)的具體應(yīng)用當(dāng)中經(jīng)常和車道關(guān)聯(lián)密切。在同一一條道路上

35、不同方向的車道具有不同的交通特性，如交通規(guī)則變化、交通量變化等。31 建立城市交通模型利用圖論的相關(guān)理論和知識(shí)，對(duì)圖中的節(jié)點(diǎn)和邊設(shè)法加入車道信息用于模擬就哀痛系統(tǒng)。以完整的交通道路網(wǎng)絡(luò)作為模型建立對(duì)象，只需要對(duì)道路中的相關(guān)數(shù)據(jù)和參數(shù)進(jìn)行顯示和計(jì)算，但在實(shí)際的交通道路當(dāng)中，交通特征是實(shí)時(shí)變化的，這與交通道路模型密不可分。首先，在同一條道路上不同的車道在不同的行駛方向的交通特征可能不同，如交通量變化和交通規(guī)則等。例如：在早晚的上下班的高峰區(qū)段，進(jìn)出同一區(qū)域的同一條道路在不同方向表現(xiàn)的車流量是明顯不同的，交通擁堵現(xiàn)象大多數(shù)情況下是發(fā)生在某條車道的單向車道上。其次，不同方向的車道由于具有不同的拓?fù)潢P(guān)系

36、，因此交通規(guī)則有可能不同。由于在節(jié)點(diǎn)圖層和路段圖層中分別存儲(chǔ)的點(diǎn)、線圖元是分別獨(dú)立的，兩個(gè)圖層問不想關(guān)聯(lián)。為建立點(diǎn)線各個(gè)元素之間的空間拓?fù)潢P(guān)系，使他們構(gòu)成有機(jī)整體，需要分別在存儲(chǔ)點(diǎn)線信息的兩張表文件中擴(kuò)展一定長(zhǎng)度的字段，用對(duì)象的屬性字段之問的相互聯(lián)系來建立交通網(wǎng)絡(luò)圖的拓?fù)潢P(guān)系，這樣就建立了交通網(wǎng)絡(luò)系統(tǒng)的有機(jī)整體即他們的拓?fù)潢P(guān)系結(jié)構(gòu)圖。311 道路節(jié)點(diǎn)模型可以將交通網(wǎng)絡(luò)抽象成一個(gè)有向圖，圖中的邊帶有一定的權(quán)值，但這個(gè)抽象的有向圖如何建立起來需要視具體的應(yīng)用環(huán)境而定。在實(shí)際情況中人民出行是從一個(gè)地方到另一個(gè)地方，這種不能簡(jiǎn)單的歸結(jié)在圖中從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的轉(zhuǎn)移，實(shí)際情況的交通網(wǎng)絡(luò)運(yùn)行是非常復(fù)雜

37、的，所以不能簡(jiǎn)單的把某一個(gè)具體的地方當(dāng)成是圖中的某個(gè)節(jié)點(diǎn)，把道路信息抽象成圖中帶有權(quán)值的邊，而是要將具體的地址信息抽象為節(jié)點(diǎn)以及其附屬信息并加入到交通網(wǎng)絡(luò)系統(tǒng)中。交通地址的交叉口所抽象的節(jié)點(diǎn)和將具體地址被抽象成圖中的節(jié)點(diǎn)是不相等價(jià)的，需要考慮實(shí)際情況，因此交通節(jié)點(diǎn)的阻抗值應(yīng)該視具體情況而定，而表示地名的節(jié)點(diǎn)的阻抗值可以視為零。 312 交叉口和道路模型將道路的數(shù)據(jù)模型抽象為一條線，因此選擇道路中問的中心線表示道路數(shù)據(jù)模型，這種建模方法不能很好的描述交通道路的屬性信息，丟失很多信息量。實(shí)際生活中的道路不能簡(jiǎn)單的抽象為一條直線，因?yàn)橛行┑缆反嬖诤芏嘬嚨溃總€(gè)車道的屬性信息不盡相同，多車道的交通道路

38、屬性信息較為復(fù)雜。在gps進(jìn)行導(dǎo)航式，需要考慮到的交通網(wǎng)絡(luò)信息往往與車道信息密切相關(guān)。32 交通模型數(shù)據(jù)存儲(chǔ)321 數(shù)據(jù)預(yù)處理在實(shí)際應(yīng)用中，一般將交通網(wǎng)絡(luò)模型用矢量化的數(shù)據(jù)地圖表示，為了建立交通網(wǎng)絡(luò)可使用的數(shù)據(jù)模型，需要對(duì)原始道路構(gòu)成的交通網(wǎng)絡(luò)矢量圖進(jìn)行優(yōu)化和預(yù)處理，建立相應(yīng)的拓?fù)潢P(guān)系圖譜。矢量圖形的預(yù)處理的一般包括：(1)對(duì)原始道路圖像進(jìn)行拓?fù)潢P(guān)系檢查并進(jìn)行剪斷處理，保證地圖中不存在兩條道路相交的情況，將原來的道路拆分成多條道路的集合：(2)為每一條剪斷后的道路建立拓?fù)潢P(guān)系，并定義其屬性特征，如道路名稱、道路長(zhǎng)度、交通流等特征；(3)將地圖經(jīng)過上述處理之后生成拓?fù)湮募?22 交通路徑模型建

39、立與數(shù)據(jù)存儲(chǔ)（1）交通路徑模型的建立最短路徑選擇的前提是對(duì)交通系統(tǒng)創(chuàng)建合適的模型。按照上述方法對(duì)原始的交通道路進(jìn)行預(yù)處理之后就可以確定道路之間的拓?fù)潢P(guān)系，進(jìn)而可以建立以道路拓?fù)潢P(guān)系為基準(zhǔn)的交通系統(tǒng)模型，拓?fù)潢P(guān)系中包括線性實(shí)體之間的模型，線性實(shí)體與節(jié)點(diǎn)之問的模型，節(jié)點(diǎn)與節(jié)點(diǎn)之間的模型，以及他們的連通性等。使用圖中的節(jié)點(diǎn)表示交通系統(tǒng)的的較差路徑，道路交叉即是圖中的節(jié)點(diǎn)，兩個(gè)節(jié)點(diǎn)之間的道路在圖中用弧表示，就是圖的邊，路段的長(zhǎng)度以及消耗時(shí)問等信息則為邊帶有的權(quán)值。在本文中，交通路徑系統(tǒng)的模型由兩部分圖層所構(gòu)成，一部分是節(jié)點(diǎn)圖層，一部分是交通道路圖層。節(jié)點(diǎn)圖層表示交通交叉口或者道路的起始點(diǎn)或終止點(diǎn)，用點(diǎn)

40、對(duì)象來表示，路段圖層存儲(chǔ)這連接各個(gè)節(jié)點(diǎn)的交通路徑以及他們的屬性信息，用線對(duì)象表示。在兩圖層中分別存儲(chǔ)的節(jié)點(diǎn)信息和路段信息分別是獨(dú)立的，下一步就是建立兩個(gè)圖層之問的拓?fù)渎?lián)系，使得兩個(gè)圖層構(gòu)成有機(jī)整體，形成交通路徑系統(tǒng)的完整性，需要用兩個(gè)圖層所對(duì)應(yīng)的兩張表中的文件擴(kuò)展出一定的字段，用對(duì)象的屬性信息來代表兩個(gè)圖層之間的拓?fù)潢P(guān)系，這樣就構(gòu)成了交通路徑模型的整體拓?fù)潢P(guān)系結(jié)構(gòu)圖。交通路徑的限制信息是交通導(dǎo)航中需要終點(diǎn)考慮的因素，比如由于施工、交通事故、速度限制、惡劣天氣造成的交通限制等，實(shí)際的道路中交通限制信息十分復(fù)雜，而且隨時(shí)發(fā)生變化。本文考慮的交通限制信息只考慮了禁止通行的信息。如果某條道路出現(xiàn)禁止通

41、行的限制信息，用節(jié)點(diǎn)的交通限制信息來表示。（2）數(shù)據(jù)存儲(chǔ)一般地，在計(jì)算機(jī)中大多采用利用鄰接表和鄰接矩陣的方法存儲(chǔ)有向圖。順序表v0，v1，vm-1。的形式在鄰接局長(zhǎng)呢中存儲(chǔ)圖中所有的結(jié)點(diǎn)，以m×m大小的矩陣存儲(chǔ)圖的邊。使用鄰接矩陣來表示圖的存儲(chǔ)淺顯易懂，也可以通過鄰接矩陣來存儲(chǔ)邊的權(quán)值信息和節(jié)點(diǎn)信息以及他們之間的連同情況等等，因此在本文中也利用鄰接表和鄰接矩陣方法。33 最優(yōu)路徑選擇331 最優(yōu)路徑的求解過程在交通網(wǎng)絡(luò)中，求解最優(yōu)路徑的一般思路是：把最優(yōu)路徑選擇問題轉(zhuǎn)化成優(yōu)化問題來解決，應(yīng)用優(yōu)化理論的相關(guān)思想和思路解決最優(yōu)路徑優(yōu)化問題。求解過程包括以下四個(gè)步驟酬：(1)交通網(wǎng)絡(luò)模型建

42、立；(2)交通道路權(quán)重的計(jì)算；(3)利用最短路徑計(jì)算方法求解交通網(wǎng)絡(luò)中的最短路徑問題；(4)將交通網(wǎng)絡(luò)圖中的最短路徑問題轉(zhuǎn)化為現(xiàn)實(shí)交通網(wǎng)絡(luò)中的路段集合。其中，建立交通網(wǎng)絡(luò)模型是最優(yōu)路徑選擇的基礎(chǔ)，交通網(wǎng)絡(luò)模型中道路權(quán)值的計(jì)算以及利用權(quán)值信息求解最短路徑是關(guān)鍵。道路的權(quán)值是計(jì)算現(xiàn)實(shí)問題中最短路徑的基礎(chǔ)，最優(yōu)路徑選擇的準(zhǔn)確與否在很大程度上取決于道路權(quán)值的設(shè)計(jì)和計(jì)算。 332 經(jīng)典dijkstra算法分析在1959年荷蘭數(shù)學(xué)家ewdijkstra首先提出的dijkstra算法，該算法是一種單源最短路徑的搜索算法，他適用于非負(fù)權(quán)值網(wǎng)絡(luò)的，是目前求解最短路問題的理論上最完備、應(yīng)用范圍最廣的算法，可以計(jì)算

43、出從圖中的某一節(jié)點(diǎn)到其他任意節(jié)點(diǎn)的最短路徑搜索結(jié)果.dijkstra是一種迭代的貪心策略的路徑搜索算法，他根據(jù)路徑的長(zhǎng)短逐漸增長(zhǎng)來搜索點(diǎn)數(shù)，構(gòu)造了一顆路徑樹，從而得到路徑樹中的根部節(jié)點(diǎn)到其他任意節(jié)點(diǎn)的最短路徑結(jié)果。假設(shè)帶權(quán)值的有向圖為g=(v，e)，其中v是數(shù)量為n的結(jié)點(diǎn)集，e是數(shù)量為m的邊集，w為權(quán)值向量。具體算法步驟如下：(1) 對(duì)d和x進(jìn)行初始化；(2)s集合初始為空，s=； （3）為當(dāng)前圖中的所有結(jié)點(diǎn)賦值給集合q，q=vg：(4)循環(huán)條件：while q；(5)提取出集合q中最小d值的結(jié)點(diǎn)，并賦給甜，u=pointmin(q)：(6)將提取出的結(jié)點(diǎn)加入s集合，s=su；(7)對(duì)于每個(gè)結(jié)

44、點(diǎn)vadju，計(jì)算并修改v的d和，；(8)結(jié)束。最初dijkstra算法開發(fā)的目的是計(jì)算網(wǎng)絡(luò)圖中兩節(jié)點(diǎn)之間的最短路徑問題，當(dāng)該算法應(yīng)用到交通網(wǎng)絡(luò)的最短路徑搜索時(shí)，由于起始點(diǎn)和終止點(diǎn)都是已知的，因此只需要從起始點(diǎn)開始搜索，按照其搜索原則尋找最短路徑，一直搜索的終止點(diǎn)為止，需要對(duì)該算法進(jìn)行優(yōu)化和改進(jìn)，才能使用到交通網(wǎng)絡(luò)的最優(yōu)路徑選擇系統(tǒng)當(dāng)中。從算法的原理可以發(fā)現(xiàn)，當(dāng)交通網(wǎng)絡(luò)十分龐大時(shí)，該算法的計(jì)算量是十分巨大的，如果將該算法直接用于交通網(wǎng)絡(luò)的最優(yōu)路徑選擇算法當(dāng)中，不能達(dá)到應(yīng)用的實(shí)時(shí)性要求，因此需要對(duì)該算法的性能進(jìn)行提升式改進(jìn)。另外，該算法只是路徑搜索，對(duì)于交通網(wǎng)絡(luò)中的路徑權(quán)值問題沒有任何解決辦法，

45、因此該算法可以作為最優(yōu)路徑選擇的主要路徑搜索算法，而對(duì)于權(quán)值的提取和計(jì)算，需要額外增加輔助算法來完成，能夠反映交通網(wǎng)絡(luò)系統(tǒng)在實(shí)時(shí)狀態(tài)下權(quán)值的變化情況。 333 dijkstra算法改進(jìn)由于動(dòng)態(tài)路徑所具有的特點(diǎn)，需要在搜索過程中實(shí)時(shí)導(dǎo)入交通系統(tǒng)中的更新的信息，而dijkstra算法不能適用與大規(guī)模交通網(wǎng)絡(luò)的路徑搜索問題，因此需要對(duì)dijkstra算法進(jìn)行改進(jìn)，改進(jìn)的dijkstra算法的具體計(jì)算步驟如下：(1)初始化：設(shè)s僅包含原節(jié)點(diǎn)，原節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)(m)，令d=0，=，其他各節(jié)點(diǎn)的d=，=：(2)如果s中包含全部節(jié)點(diǎn)，轉(zhuǎn)入(6)；否則轉(zhuǎn)入(3)；(3)根據(jù)當(dāng)前節(jié)點(diǎn)歷后面連接的路段自動(dòng)生成節(jié)點(diǎn)

46、m的后繼結(jié)點(diǎn)，對(duì)每一個(gè)后繼節(jié)點(diǎn)n，計(jì)算如下：a計(jì)算車輛到達(dá)節(jié)點(diǎn)歷時(shí)對(duì)應(yīng)的sk值；計(jì)算車輛在節(jié)點(diǎn)m與節(jié)點(diǎn)n之問的時(shí)問花費(fèi)；b如果d(n)>d(m)+time(m，n)，則將d(n)=d(m)+time(m，n)，(n)=m：否則轉(zhuǎn)入(4)；(4)排除與節(jié)點(diǎn)m相鄰的節(jié)點(diǎn)的限制信息并讀取m的限制信息。搜索d值最小的結(jié)點(diǎn)并將當(dāng)前節(jié)點(diǎn)設(shè)為(m)，將結(jié)點(diǎn)m加入到集合s中，轉(zhuǎn)入步驟(2)；否則程序終止，這時(shí)，對(duì)每個(gè)屬于s的節(jié)點(diǎn)，其d值就是原節(jié)點(diǎn)到達(dá)此節(jié)點(diǎn)的最短路徑需要花費(fèi)的時(shí)間；(5)根據(jù)s中節(jié)點(diǎn)的屬性信息開始回溯，一直回溯到起始的源節(jié)點(diǎn)，最后報(bào)告結(jié)果路徑;(6)算法結(jié)束。當(dāng)算法結(jié)束時(shí)，集合s中的每個(gè)

47、節(jié)點(diǎn)，其d值表示的就是原始節(jié)點(diǎn)到達(dá)該節(jié)點(diǎn)利用最短路徑所耗費(fèi)的市靜安。若s表示交通路徑中路段數(shù)，z表示交通路徑中的節(jié)點(diǎn)的個(gè)數(shù)，則改進(jìn)算法的時(shí)間復(fù)雜度最大值為o(z2+s)+o(z2） 33. 4 交通阻抗分析交通阻抗是車輛運(yùn)行在交通道路上時(shí)，根據(jù)運(yùn)行的距離、時(shí)間、舒適度、擁堵情況、交通費(fèi)用和人的舒適度等綜合因素，需要考慮到即人、車、路、環(huán)境相互影響，對(duì)交通出行的阻力作用值。針對(duì)不同的交通網(wǎng)絡(luò)系統(tǒng)，阻抗值的計(jì)算方法不同，需要考慮到的阻礙因素也不同。城市交通系統(tǒng)的交通阻抗可分為兩類，節(jié)點(diǎn)交通阻抗和道路交通阻抗，節(jié)點(diǎn)交通阻抗表示的是交叉口的交通阻抗。交通阻抗的計(jì)算指標(biāo)主要表現(xiàn)在阻抗函數(shù)的確定，為了將交

48、通阻抗使用語(yǔ)一般性的公路系統(tǒng)，將路徑誘導(dǎo)算法中采用廣義上的交通阻抗。所謂廣義交通阻抗，是指出行者從起始點(diǎn)開始駕駛機(jī)動(dòng)車到達(dá)終點(diǎn)而付出的代價(jià)以及對(duì)交通道路系統(tǒng)帶來的負(fù)面效應(yīng)的綜合。它的要素應(yīng)該包括出行時(shí)間、出行方式、出行費(fèi)用、使用資源、車輛磨損、環(huán)境污染程度等。因此交通阻抗的最小值為以上各個(gè)元素最小值的總和，而最大值為以上各個(gè)元素最大值的總和。在路徑選擇中，有出行時(shí)間長(zhǎng)度、行駛距離長(zhǎng)度、擁擠程度、道路質(zhì)量和出行費(fèi)用等評(píng)價(jià)指標(biāo)，以提供不同的應(yīng)用環(huán)境進(jìn)行選擇使用。當(dāng)交通網(wǎng)絡(luò)中交通流量分布比較均勻，沒有出現(xiàn)交通意外事故等特殊情況時(shí)，這五種評(píng)價(jià)方法不會(huì)互相矛盾的，當(dāng)交通道路中出現(xiàn)交通擁堵，交通事故等特殊

49、情況時(shí)，這五種評(píng)價(jià)方法所得到的結(jié)果可能不同，有存在矛盾的地方，但一般來說，實(shí)際情況下考慮出行的交通阻抗，一般采用一時(shí)問為評(píng)價(jià)標(biāo)準(zhǔn)來作為交通那個(gè)阻抗的評(píng)價(jià)指標(biāo)。3. 4 本章小結(jié)本章利用圖論的相關(guān)理論和方法對(duì)交通道路進(jìn)行分析。分析了經(jīng)典的最優(yōu)路徑選擇dijkstra算法并對(duì)其進(jìn)行改進(jìn)，考慮到在實(shí)際情況中由道路質(zhì)量、擁堵情況等導(dǎo)致交通道路存在一定的交通阻抗，并將交通阻抗的計(jì)算加入到改進(jìn)的dijkstra算法當(dāng)中，使之更具有應(yīng)用價(jià)值。改進(jìn)的路徑選擇算法在原有算法基礎(chǔ)上，減少了時(shí)間復(fù)雜度，提高了路徑搜索的效率。4 gls數(shù)據(jù)模型和數(shù)據(jù)庫(kù)設(shè)計(jì)路徑選擇系統(tǒng)的工作原理是輸入交通系統(tǒng)中的起點(diǎn)和終點(diǎn)，能給出一條

50、已規(guī)劃的路徑結(jié)果。在路徑選擇系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)過程中需要使用合適的數(shù)據(jù)庫(kù)來管理地理數(shù)據(jù)信息(gis數(shù)據(jù))能夠提高gis數(shù)據(jù)的計(jì)算速度，進(jìn)一步提高路徑選擇的效率，使能夠大道實(shí)時(shí)效果。本章的內(nèi)容主要是介紹了gis數(shù)據(jù)的一些相關(guān)內(nèi)容和數(shù)據(jù)庫(kù)管理設(shè)計(jì)內(nèi)容，主要內(nèi)容包括gis數(shù)據(jù)的相關(guān)概念和內(nèi)容知識(shí)、oracle數(shù)據(jù)庫(kù)選擇的原因、gis數(shù)據(jù)導(dǎo)入、gis數(shù)據(jù)在數(shù)據(jù)庫(kù)中的管理和維護(hù)等內(nèi)容。41 gis數(shù)據(jù)模型建立數(shù)據(jù)模型是能夠描述數(shù)據(jù)內(nèi)在特征的工具，也是一門描述語(yǔ)言，是現(xiàn)實(shí)世界中對(duì)某種或某類特征的模擬、抽象、提取和組織。地理信息數(shù)據(jù)模型是模擬地理信息的形式化表示的工具。地理信息數(shù)據(jù)模型的建立為地理信息的表達(dá)和

51、操作方法提供了具體的形式構(gòu)架。gis數(shù)據(jù)所描述的對(duì)象主要包括與地理位置有關(guān)的空間數(shù)據(jù)信息和非空間依賴性的屬性方面的信息數(shù)據(jù)。 411 空間數(shù)據(jù)模型g1s空間數(shù)據(jù)與要描述的對(duì)象空間位置信息是相關(guān)的。目前，在gis數(shù)據(jù)研究領(lǐng)域中學(xué)者們提出的空問數(shù)據(jù)模型主要有矢量數(shù)據(jù)模型、柵格數(shù)據(jù)模型、矢量柵格一體化數(shù)據(jù)模型以及面向?qū)ο蟮臄?shù)據(jù)模型等?，F(xiàn)實(shí)空間世界 外模式 外模式 外模式 概念數(shù)據(jù)模型邏輯數(shù)據(jù)模型物理數(shù)據(jù)模型 圖4-1 空間數(shù)據(jù)模型三個(gè)層次之間的相互關(guān)系412 屬性數(shù)據(jù)模型屬性數(shù)據(jù)與要描述的對(duì)象的空間位置關(guān)系無關(guān)，他是gis數(shù)據(jù)中空問數(shù)據(jù)的重要組成部分。例如，一條公路可以用實(shí)線或連續(xù)像素點(diǎn)或矢量表示的

52、曲線實(shí)體，并可以用一定的顏色符號(hào)把gis數(shù)據(jù)中要表達(dá)的內(nèi)容完整的表達(dá)出來，這樣道路的類型就可以用相應(yīng)的符號(hào)表達(dá)出來。而道路的屬性數(shù)據(jù)就由于道路的寬度、路面結(jié)構(gòu)、修繕日期、水管電纜走向和位置、特殊交通規(guī)則標(biāo)記以及某一時(shí)間的車流量等。這鞋數(shù)據(jù)都與道路實(shí)體的數(shù)據(jù)無關(guān)，是道路的附加數(shù)據(jù)，這些屬性數(shù)據(jù)可以通過添加一個(gè)公共標(biāo)識(shí)的符號(hào)與空問實(shí)體對(duì)應(yīng)起來。當(dāng)空間實(shí)體的空間數(shù)據(jù)模型與其對(duì)應(yīng)的屬性數(shù)據(jù)聯(lián)系起來以后，就可以對(duì)其gis數(shù)據(jù)進(jìn)行操作和運(yùn)算了。當(dāng)然，根據(jù)實(shí)際情況，gis數(shù)據(jù)應(yīng)該提供靈活的數(shù)據(jù)查詢和連接方法，以便經(jīng)常增加、刪除或修改其中屬性數(shù)據(jù)的操作。4. 2 gls數(shù)據(jù)的管理與組織為了對(duì)gis數(shù)據(jù)方便操作

53、，一般將gis數(shù)據(jù)存儲(chǔ)與數(shù)據(jù)庫(kù)的使用結(jié)合在一起，這涉及到數(shù)據(jù)庫(kù)和計(jì)算機(jī)的相關(guān)知識(shí)。注意gis數(shù)據(jù)庫(kù)管理主要原則:通用性原則、獨(dú)立性原則、共享性原則、最小冗余度原則。 oracle gis數(shù)據(jù)將不同功能的機(jī)構(gòu)或場(chǎng)所放在不同的圖層當(dāng)中，每個(gè)專題圖層在數(shù)據(jù)庫(kù)中都可以找到一一對(duì)應(yīng)的數(shù)據(jù)庫(kù)表，將與這個(gè)圖層有關(guān)的空間及屬性信息存儲(chǔ)在數(shù)據(jù)庫(kù)表中。4. 3 spatiai簡(jiǎn)介隨著oracle 8i的推出，spatial cartridge將升級(jí)為oracle spatial。在新的數(shù)據(jù)庫(kù)工具中，新的表示數(shù)據(jù)空間類型的抽系那個(gè)數(shù)據(jù)類型被提出，用(adt)一sdogeometry來表示，(adt)一sdo geo

54、metry可以將數(shù)據(jù)存儲(chǔ)在一列中，oracle spatial發(fā)展了新型的數(shù)據(jù)庫(kù)管理方式，也對(duì)索引機(jī)制進(jìn)行了一體化管理進(jìn)行了優(yōu)化，增加了緩沖區(qū)生成、二級(jí)過濾和疊加分析等新的數(shù)據(jù)處理過程?？臻g數(shù)據(jù)信息的存儲(chǔ)都在sdo_geometry之中，對(duì)sdo_geometry的理解和帳戶是使用oracle spatial接口程序的關(guān)鍵步驟。sdo_geometry是按照open gis的規(guī)則定義的一個(gè)對(duì)象，程序原始的創(chuàng)建方式如下表示:create type sdo_geometry as object(sdo_gtype number，sdo_srid number，sdo_point sdo_point

55、_type，sdo_elem_info mdsyssdo_elem_info_array，sdo_ordinates mdsyssdo_ordinate_array)；44 空間數(shù)據(jù)向oracle中的導(dǎo)入有兩種不同的方法可以將mapinfo格式的空間數(shù)據(jù)信息導(dǎo)入到oracle中：利用控件文件成批量的加載控件數(shù)據(jù)和利用mapinfo自帶工具easyloader直接導(dǎo)入數(shù)據(jù)信息。下面介紹這兩種方法怎樣實(shí)現(xiàn)的數(shù)據(jù)自動(dòng)導(dǎo)入。(1)利用工具easy loader直接將空問數(shù)據(jù)導(dǎo)入利用easyloader工具將mapinfo數(shù)據(jù)信息直接導(dǎo)入到數(shù)據(jù)庫(kù)中是比較簡(jiǎn)單的導(dǎo)入方法。easyloader是mapinf

56、o公司專門編寫用于將mapinfo格式的數(shù)據(jù)導(dǎo)入到各種數(shù)庫(kù)中的工具。(2)利用控制文件對(duì)數(shù)據(jù)批量加載導(dǎo)入每個(gè)0racle數(shù)據(jù)庫(kù)都附帶一個(gè)控制文件。該控制為二進(jìn)制文件，能夠記錄數(shù)據(jù)的物理結(jié)構(gòu)，主要內(nèi)容包括：數(shù)據(jù)庫(kù)的名稱和屬性、數(shù)據(jù)庫(kù)的創(chuàng)建時(shí)間點(diǎn)、當(dāng)前日志的序號(hào)、檢驗(yàn)點(diǎn)信息等等，ctl表示控制文件的擴(kuò)展名。45 gis數(shù)據(jù)在oracie中的存儲(chǔ)在數(shù)據(jù)庫(kù)中可以存儲(chǔ)多種空問數(shù)據(jù)，根據(jù)實(shí)驗(yàn)的需要，本文只介紹與我們實(shí)驗(yàn)和研究?jī)?nèi)容相關(guān)的空間數(shù)據(jù)，包括道路數(shù)據(jù)，道路節(jié)點(diǎn)數(shù)據(jù)，分層路段數(shù)據(jù)，和多比例尺道路數(shù)據(jù)等。這些數(shù)據(jù)起初是mapinfo格式的數(shù)據(jù)，為了充分發(fā)揮oracle spatial數(shù)據(jù)庫(kù)的優(yōu)勢(shì)、提高計(jì)算效率、減少存儲(chǔ)空問，我們將數(shù)據(jù)都儲(chǔ)存在oracle中。 圖4-2 道路線型與節(jié)點(diǎn)在mapinfo professional中的顯示結(jié)果46 oracle中g(shù)is數(shù)據(jù)的訪問0040(oracle objects for ole)是oracle公司提供快捷訪問接口，這個(gè)程序接口是發(fā)基于oracle數(shù)據(jù)庫(kù)應(yīng)用程序的底層的開發(fā)的，它的優(yōu)點(diǎn)是速度快、支持mirosoft編程語(yǔ)言、對(duì)oracle數(shù)據(jù)庫(kù)進(jìn)行較強(qiáng)控制等。但同時(shí)也存在著一定缺點(diǎn)，如通用新不好，與其他數(shù)據(jù)庫(kù)不兼容，但用它來訪問oracle數(shù)