【正文】 簡(jiǎn)介 .............................................. 16 4． 4 空間數(shù)據(jù)向 Oracle 中的導(dǎo)入 ............................... 17 4． 5 GIS 數(shù)據(jù)在 OracIe 中的存儲(chǔ) ............................... 17 4． 6 Oracle 中 GIS 數(shù)據(jù)的訪問(wèn) ................................. 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ī)模不斷增大和增多，城市化程度和趨勢(shì)十分明顯，城市交通 問(wèn)題成為目前影響和制約我國(guó)經(jīng)濟(jì)發(fā)展和社會(huì)進(jìn)步的主要因素。不論是上海北京等特大城市還是其他省會(huì)城市或地級(jí)市，普遍存在交通問(wèn)題，城市車輛不斷增多，人口越發(fā)密集，道路環(huán)境不斷惡化等原因都是導(dǎo)致城市交通問(wèn)題的主要方面。 這就要求我們擁有的便利交通系統(tǒng)， 隨著計(jì)算機(jī)技術(shù)和電子技術(shù)的不斷發(fā)展，以及電子地圖測(cè)繪技術(shù)的不斷進(jìn)步，這使得地理信息系統(tǒng)也得到了長(zhǎng)足的進(jìn)步，這些技術(shù)的發(fā)展都給智能交通系統(tǒng)的發(fā)展奠定 了 良好的基礎(chǔ)。通過(guò)中西交通道路系統(tǒng)的比較，我國(guó)城市交通系統(tǒng)的主要問(wèn)題包括交通管理技術(shù)落后， 為 從根本上解決問(wèn)題上述交通擁堵問(wèn)題 ，并保持大中城市交通可持續(xù)發(fā)展帶動(dòng)城市的可持續(xù)反戰(zhàn)，除了合理地進(jìn)行交通道路等基礎(chǔ)設(shè)施建設(shè)外，另一個(gè)切實(shí)可行的辦法就是進(jìn)西方先進(jìn)的高科技管理技術(shù)改進(jìn)我們的交通系統(tǒng)，并使其符合我國(guó)國(guó)情，建立高性能高效率的智能城市交通系統(tǒng) (ITS)。智能交通系統(tǒng) (ITS)通過(guò)充分發(fā)揮現(xiàn)有交通資源潛力和系統(tǒng)內(nèi)部協(xié)同作用產(chǎn)生的效力，能夠?yàn)槌鞘薪煌ㄌ峁└踩⒏孢m、更高效率和更高品質(zhì)的新型城市交通系統(tǒng)嘲。智能交通系統(tǒng)的目標(biāo)是利用現(xiàn)金的計(jì)算機(jī)技術(shù)和先進(jìn)的網(wǎng)絡(luò)管理來(lái)減少交通擁堵、交通事故和環(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)輸業(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)行的效率。最佳路徑選擇問(wèn)題是智能交通系統(tǒng)中的重要組成部分，也是交通地理信息系統(tǒng)研究中的一個(gè)熱點(diǎn)問(wèn)題之一，是出行路徑設(shè)計(jì)與優(yōu)化、現(xiàn)有有限資源重新利用和分配等問(wèn)題的基礎(chǔ)。因此最優(yōu)路徑選武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 2 擇與優(yōu)化問(wèn)題是實(shí)時(shí)的動(dòng)態(tài)交通系統(tǒng)中具有具有重要現(xiàn)實(shí)意義的研究課題。最佳路勁的算法研究不僅可以應(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è)問(wèn)題做過(guò)研究，如運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、圖論、數(shù)論、交通工程學(xué)理論、地理信息科學(xué)研究等。日前網(wǎng)絡(luò)發(fā)展十分迅速，而網(wǎng)絡(luò)的構(gòu)成類似交通道路系統(tǒng)，可以利用最優(yōu)路徑算法來(lái)解決很多網(wǎng)絡(luò)方面的問(wèn)題。經(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)路徑問(wèn)題的解決進(jìn) 行過(guò)深入研究與探討。數(shù)學(xué)家 E． W． Dijkstra 在 1959 年就提出了標(biāo)號(hào)設(shè)定法用于解決路徑問(wèn)題，形成了目前仍被視為經(jīng)典的 Dijkstra 算法。自從 Dijkstra 算法面世以后，又歷經(jīng)了很多學(xué)者對(duì)該算法的改進(jìn)與發(fā)展，因此有關(guān)最優(yōu)路徑選擇問(wèn)題的研究成果不斷涌現(xiàn)，使其求解速度和求解效率不斷提高 。 最優(yōu)路徑選擇算法在不同的應(yīng)用條件下可以按照不同的方法進(jìn)行分類。如按照時(shí)間順序來(lái)分類，分為動(dòng)態(tài)最優(yōu)路徑選擇問(wèn)題和靜態(tài)最優(yōu)路徑選擇問(wèn)題；如果按照確定性和非確定性來(lái)劃分，分為確定型和隨機(jī)型最優(yōu)路徑選擇問(wèn)題；如果按照網(wǎng)絡(luò)規(guī)模大小 劃分，可分為小規(guī)模網(wǎng)絡(luò)和大規(guī)模網(wǎng)絡(luò)最優(yōu)路徑選擇問(wèn)題：如果按照計(jì)算方式來(lái)劃分，可分為串行和并行最優(yōu)路徑選擇算法。各種不同類別的最優(yōu)路徑選擇算法相互組合可以成為解決不同問(wèn)題的各種各樣算法。最優(yōu)路徑問(wèn)題按照是否是單源問(wèn)題還可以分為單源最優(yōu)路徑選擇問(wèn)題及全源最優(yōu)路徑選擇問(wèn)題。其中單源最優(yōu)路徑選擇問(wèn)題更具有實(shí)際應(yīng)用的意義，而且良好的單源路勁問(wèn)題的算法可為全源最優(yōu)路徑問(wèn)題提供良好的研究基礎(chǔ)，因此本文在研究最優(yōu)路徑選擇問(wèn)題的過(guò)程 中 只考慮單源最優(yōu)路徑選擇問(wèn)題。 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 3 2 基礎(chǔ)知識(shí) 2． 1 路徑優(yōu)化算法概述 國(guó)內(nèi)外的研究機(jī)構(gòu)和學(xué)者對(duì) 不同的路徑優(yōu)化算法進(jìn)行了研究、分析、比較和論證，比較經(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)確程度來(lái)決定的。目 前，國(guó)內(nèi)外學(xué)者己經(jīng)有許多傳統(tǒng)的經(jīng)典算法用來(lái)解決路徑優(yōu)化問(wèn)題，但這些算法具有共同的點(diǎn)就是并沒考慮實(shí)際出行的具體特點(diǎn) 特點(diǎn)，如路況信息、道路質(zhì)量、道路上的車流量等。最短路徑算法求出的僅僅是在空間距離最短的路徑，但在實(shí)際應(yīng)用中人們需要的是最優(yōu)路徑，最優(yōu)路徑不一定是距離最短，還要考慮交通阻抗的問(wèn)題，比如想要求得從 A 地到 B 地的最優(yōu)路徑，這個(gè)問(wèn)題是指在所有從 A 地到 B 地的所有路線當(dāng)中選擇最優(yōu)的一條，包括最節(jié)省時(shí)問(wèn)，最節(jié)省資源，是駕駛者最舒適，對(duì)交通工具的各項(xiàng)消耗最小等。最優(yōu)路徑問(wèn)題并不是普通意義上的距離最短路徑選擇問(wèn)題。實(shí)際情況下最優(yōu)路徑選擇問(wèn)題包括兩層含義：首先最優(yōu)路徑是一條可以從 A 地到達(dá) B 地的暢通的路徑；其次這條路徑在所有路徑當(dāng) 中是最佳的。從 A 地到 B 地想要找一條最優(yōu)路徑，應(yīng)是一條的所用時(shí)間最短、駕駛者最舒適、道路上的車輛數(shù)量較少，或?qū)煌ㄜ囕v的損耗最少。 2． 1． 1 Floyd 算法 Floyd 算法是由 Floyd 在 1962 年提出的。將圖的節(jié)點(diǎn)和邊的信息計(jì)算利用矩陣計(jì)算來(lái)完成，通過(guò)一個(gè)圖的權(quán)值矩陣中求出交通網(wǎng)絡(luò)中任意兩點(diǎn)之 間 的最短路徑?；舅枷耄罕热缜髨D中兩節(jié)點(diǎn) Vi 到 Vj的之問(wèn)的最短路徑問(wèn)題。 Floyd算法是一種動(dòng)態(tài)規(guī)劃算法，由于是窮舉法進(jìn)行計(jì)算，因此對(duì)于稠密圖效果較好。此算法思路簡(jiǎn)單，該算法對(duì)于稠密圖來(lái)說(shuō)，效率要高于經(jīng)典的 Dijkstra 算法。但缺點(diǎn)是時(shí)間復(fù)雜度較高，不適合大規(guī)模數(shù)據(jù)的計(jì)算，耗時(shí)較長(zhǎng)。 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 4 2． 1． 2 Dijkstra 算法 Dijkstra 算法由荷蘭數(shù)學(xué)家 Edsger Wybe Dijkstra 在 1959 年提出來(lái)的，是一種單源最短路算法適用于非負(fù)權(quán)值網(wǎng)絡(luò)的計(jì)算，是目前在求解最短路徑問(wèn)題較為完備且應(yīng)用廣泛的算法之一，可以計(jì)算出圖中從指定結(jié)點(diǎn)到圖中其他任意節(jié)點(diǎn)之問(wè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ù)雜度，降低了效率。該算法通過(guò)圖中的每個(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)度為無(wú)窮大，用無(wú)窮大長(zhǎng)度的路徑表示任何其他節(jié)點(diǎn)到該結(jié)點(diǎn)的路徑是未知的。如果存在從 S 到 v 的路徑，那么當(dāng)蘇算法結(jié)束時(shí)儲(chǔ)存的信息是 S到 v 的距離最短路徑；如果從 S 到 v的路徑不存在，則 d[V]中儲(chǔ)存信息是無(wú)窮大。 Dijkstra 算法的操作對(duì)邊進(jìn)行了拓展：如果從 U 到 v 的路徑 是存在的，將邊 (u， v)添加到(s， v)尾部，則這條新的路徑的長(zhǎng)度為 dM+w(u， v)。如果這條路徑的長(zhǎng)度比已知的路徑長(zhǎng)度 d[v]的值小，我們可以用新的路徑來(lái)代替原有路徑。這種拓展邊的迭代運(yùn)算一直進(jìn)行，一直運(yùn)行到所有的 dM都代表從 S到 v 最短路徑為止。算法需要維護(hù)兩個(gè)結(jié)點(diǎn)集 Q 和 P，集合 P 保留了我們通過(guò)迭代運(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)信息。 2． 1． 3 GPSR 算法 GPSR 路 由算法的思路是利用地理位置信息進(jìn)行最優(yōu)路徑選擇，該算法需要通過(guò)貪婪轉(zhuǎn)發(fā)算法來(lái)建立與其他信息之間的關(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)，該過(guò)程需要一直迭代計(jì)算，直到分組數(shù)據(jù)全部到達(dá)節(jié)點(diǎn) D。利用歐氏距離武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 5 計(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ā)生生無(wú)法傳送數(shù)據(jù)時(shí)，節(jié)點(diǎn)能夠