【正文】 中 GIS 數(shù)據(jù)的訪問和維護(hù)。 最優(yōu) 路徑 。 Optimal path。不論是上海北京等特大城市還是其他省會(huì)城市或地級(jí)市，普遍存在交通問題，城市車輛不斷增多，人口越發(fā)密集，道路環(huán)境不斷惡化等原因都是導(dǎo)致城市交通問題的主要方面。智能交通系統(tǒng)的目標(biāo)是利用現(xiàn)金的計(jì)算機(jī)技術(shù)和先進(jìn)的網(wǎng)絡(luò)管理來減少交通擁堵、交通事故和環(huán)境污染，與此同時(shí)，交通系統(tǒng)能夠有效的正常的運(yùn)行 。最佳路徑選擇問題是智能交通系統(tǒng)中的重要組成部分，也是交通地理信息系統(tǒng)研究中的一個(gè)熱點(diǎn)問題之一，是出行路徑設(shè)計(jì)與優(yōu)化、現(xiàn)有有限資源重新利用和分配等問題的基礎(chǔ)。 目前 我國(guó) 對(duì)有許多與最優(yōu)路徑求解相關(guān)的學(xué)科在側(cè)面對(duì)這個(gè)問題做過研究，如運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、圖論、數(shù)論、交通工程學(xué)理論、地理信息科學(xué)研究等。數(shù)學(xué)家 E． W． Dijkstra 在 1959 年就提出了標(biāo)號(hào)設(shè)定法用于解決路徑問題，形成了目前仍被視為經(jīng)典的 Dijkstra 算法。各種不同類別的最優(yōu)路徑選擇算法相互組合可以成為解決不同問題的各種各樣算法。實(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)路徑問題并不是普通意義上的距離最短路徑選擇問題。將圖的節(jié)點(diǎn)和邊的信息計(jì)算利用矩陣計(jì)算來完成，通過一個(gè)圖的權(quán)值矩陣中求出交通網(wǎng)絡(luò)中任意兩點(diǎn)之 間 的最短路徑。但缺點(diǎn)是時(shí)間復(fù)雜度較高，不適合大規(guī)模數(shù)據(jù)的計(jì)算，耗時(shí)較長(zhǎng)。該算法通過圖中的每個(gè)節(jié)點(diǎn) v 建立額外的信息數(shù)組，存儲(chǔ)從其他任意節(jié)點(diǎn) S 到 v 的最短路徑。如果這條路徑的長(zhǎng)度比已知的路徑長(zhǎng)度 d[v]的值小，我們可以用新的路徑來代替原有路徑。 2． 1． 3 GPSR 算法 GPSR 路 由算法的思路是利用地理位置信息進(jìn)行最優(yōu)路徑選擇，該算法需要通過貪婪轉(zhuǎn)發(fā)算法來建立與其他信息之間的關(guān)聯(lián)和路由。該方法的優(yōu)點(diǎn)在于米面了在節(jié)點(diǎn)信息中存儲(chǔ)建立和維護(hù)路由表信息，只需要利用相鄰節(jié)點(diǎn)進(jìn)行路徑選取即可進(jìn)行，幾乎是不需要任何協(xié)議輔助；并且利用歐氏距離最小的方法進(jìn)行路由，數(shù)據(jù)傳輸?shù)难訒r(shí)最??；并能夠保證只要網(wǎng)絡(luò)路徑不被破壞，數(shù)據(jù)一定能到傳送到目標(biāo)節(jié)點(diǎn)中去。在電子地圖中，每個(gè)路口都有坐標(biāo)位置和列表信息，那么在算法程序中我們首先要做的是讓每個(gè)結(jié)點(diǎn)都包含一條鄰居結(jié)點(diǎn)鏈表，并將結(jié)點(diǎn)號(hào)與位置信息關(guān)聯(lián)起來。目前在圖論領(lǐng)域中形成了兩個(gè)不同的方向：抽象圖論和最優(yōu)化圖論。因此圖論中的圖能夠代表多種含義，因此圖論在諸多領(lǐng)域都有著非常廣泛的應(yīng)用。每條邊與邊兩端的節(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(V， E)由其結(jié)點(diǎn)與邊之間的關(guān)系確定，且是唯一的。 圖 21 圖的結(jié)構(gòu) 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 7 2． 2． 3 圖的存儲(chǔ) (1)鄰接表 鄰接表結(jié)構(gòu)： 圖 22 鄰接表結(jié)構(gòu)表節(jié)點(diǎn)和頭結(jié)點(diǎn) 鄰接表以一種以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所構(gòu)成的圖。這些表頭結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)的形式通常是順序存儲(chǔ)的，這樣存儲(chǔ)方式便于隨即訪問任何一個(gè)節(jié)點(diǎn)的 鏈表信息。 2． 3 本章小結(jié) 本章對(duì)最優(yōu)路徑算法和圖論的相關(guān)理論知識(shí)進(jìn)行了簡(jiǎn)單概述。因此，應(yīng)當(dāng)首先考慮交通流的特征。在同一一條道路上不同方向的車道具有不同的交通特性，如交通規(guī)則變化、交通量變化等。例如：在早晚的上下班的高峰區(qū)段，進(jìn)出同一區(qū)域的同一條道路在不同方向表現(xiàn)的車流量是明顯不同的，交通擁堵現(xiàn)象大多數(shù)情況下是發(fā)生在某條車道的單向車道上。 3． 1． 1 道路節(jié)點(diǎn)模型 可以將交通網(wǎng)絡(luò)抽象成一個(gè)有向圖，圖中的邊帶有一定的權(quán)值，但這個(gè)抽象的有向圖如何建立起來需要視具體的應(yīng)用環(huán)境而定。實(shí)際生活中的道路不能簡(jiǎn)單的抽象為一條直線，因?yàn)橛行┑缆反嬖诤芏嘬嚨?，每個(gè)車道的屬性信息不盡相同，多車道的交通道路屬性信息較為復(fù)雜。 3． 2． 2 交通路徑模型建立與數(shù)據(jù)存儲(chǔ) （ 1）交通路徑模型的建立 最短路徑選擇的前提是對(duì)交通系統(tǒng)創(chuàng)建合適的模型。節(jié)點(diǎn)圖層表示交通交叉口或者道路的起始點(diǎn)或終止點(diǎn)，用點(diǎn)對(duì)象來表示，路段圖層存儲(chǔ)這連接各個(gè)節(jié)點(diǎn)的交通路徑以及他們的屬性信息，用線對(duì)象表示。如果某條道路出現(xiàn)禁止 通行的限制信息，用節(jié)點(diǎn)的交通限制信息來表示 。使用鄰接矩陣來表示圖的存儲(chǔ)淺顯易懂，也可以通過鄰接矩陣來存儲(chǔ)邊的權(quán)值信息和節(jié)點(diǎn)信息以及他們之間的連同情況等等，因此在本文中也利用鄰接表和鄰接矩陣方法 。道路的權(quán)值是計(jì)算現(xiàn)實(shí)問題中最短路徑的基礎(chǔ)，最優(yōu)路徑選擇的準(zhǔn)確與否在很大程度上取決于道路權(quán)值的設(shè)計(jì)和計(jì)算。 最初 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)中。搜索 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é)果路徑 。針對(duì)不同的交通網(wǎng)絡(luò)系統(tǒng)，阻抗值的計(jì)算方法不同，需要考慮到的阻礙因素也不同。它的要素應(yīng)該包括出行時(shí)間、出行方式、出武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 14 行費(fèi)用、使用資源、車輛磨損、環(huán)境污染程度等。 3. 4 本章小結(jié) 本章利用圖 論的相關(guān)理論和方法對(duì)交通道路進(jìn)行分析。在路徑選擇系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)過程中需要使用合適的數(shù)據(jù)庫(kù)來管理地理數(shù)據(jù)信息 (GIS數(shù)據(jù) )能夠提高 GIS 數(shù)據(jù)的計(jì)算速度，進(jìn)一步提高路徑選擇的效率，使能夠大道實(shí)時(shí)效果。地理信息數(shù)據(jù)模型的建立為地理信息的表達(dá) 和操作方法提供了具體的形式構(gòu)架。 圖 41 空間數(shù)據(jù)模型三個(gè)層次之間的相互關(guān)系 4． 1． 2 屬性數(shù)據(jù)模型 屬性數(shù)據(jù)與要描述的對(duì)象的空間位置關(guān)系無關(guān)，他是 GIS 數(shù)據(jù)中空問數(shù)據(jù)的重要組成部分。 當(dāng)空間實(shí)體的空間數(shù)據(jù)模型與其對(duì)應(yīng)的屬性數(shù)據(jù)聯(lián)系起來以后，就可以對(duì)其 GIS 數(shù)據(jù)進(jìn)行操作和運(yùn)算了。 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ù)表 中。 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_TYPE， SDO_ELEM_INFO MDSYS． SDO_ELEM_INFO_ARRAY， SDO_ORDINATES MDSYS． SDO_ORDINATE_ARRAY)； 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 17 4． 4 空間數(shù)據(jù)向 Oracle 中的導(dǎo)入 有兩種不同的方法可以將 MapInfo 格式的空間數(shù)據(jù)信息導(dǎo)入到 Oracle 中：利用控件文件成批量的加載控件數(shù)據(jù)和利用 MapInfo 自帶工具 EasyLoader 直接導(dǎo)入數(shù)據(jù)信息。 (2)利用控制文件對(duì)數(shù)據(jù)批量加載導(dǎo)入每個(gè) 0racle 數(shù)據(jù)庫(kù)都附帶一個(gè)控制文件。 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 18 圖 42 道路線型與節(jié)點(diǎn)在 MapInfo Professional 中的顯示結(jié)果 4． 6 Oracle 中 GIS 數(shù)據(jù)的訪問 0040(Oracle Objects for OLE)是 Oracle 公司 提供快捷訪問接口，這個(gè)程序接口是發(fā)基于 Oracle 數(shù)據(jù)庫(kù)應(yīng)用程序的底層的開發(fā)的，它的優(yōu)點(diǎn)是速度快、支持 Mirosoft 編程語言、對(duì) Oracle 數(shù)據(jù)庫(kù)進(jìn)行較強(qiáng)控制等。 通過 Oracle 的 Enterprise Manager Console 打開數(shù)據(jù)庫(kù)表 road，即可進(jìn)行數(shù)據(jù)庫(kù)記錄的添加刪除和修改。具體說來，路徑優(yōu)化問題對(duì)電子地圖信息的需求有以 下幾點(diǎn)：每條道路的準(zhǔn)確位置與坐標(biāo)；道路的靜態(tài)屬性：道路名稱、道路等級(jí)、道路寬度、車道數(shù)、道路長(zhǎng)度、路面狀況；道路與交通相關(guān)的靜態(tài)信息：速度限制信息、轉(zhuǎn)彎限制信息、單行線信息；特殊道路特征的抽象與表示：主要指各種形式交叉口、立交橋等等；道路周圍重要建筑物的信息。圖 52的出發(fā)地點(diǎn)和目標(biāo)地點(diǎn)一樣，是按照分層 A*算法進(jìn)行路徑優(yōu)化的，道路被分成一級(jí)、二級(jí)、三級(jí)以及高架幾種層次，圖中可以看出起點(diǎn)在三級(jí)道路上，終點(diǎn)是在二級(jí)道路上，起點(diǎn)向高層尋找相交點(diǎn)，然后再在二級(jí)道路上選用 A*算法搜索 二級(jí)道路上的最優(yōu)路徑，最終的最優(yōu)路徑是由兩段組成。根據(jù)用戶的需求，如何在獲得交通系統(tǒng)各項(xiàng)信息的同時(shí)制定出一組合理的出行方案是解決交通堵塞的新的研究思路。其次利用圖論的相關(guān)理論和方法對(duì)交通道路建立模型。 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 22 參考文獻(xiàn) [1] 劉學(xué)軍，徐鵬．交通地理信息系統(tǒng) [M]．北京：科學(xué)出版社 ,20xx． [2] 張國(guó)伍．交通運(yùn)輸系統(tǒng)分析 [J]．成都：西南交通大學(xué)出版社， 1991． [3] 張建國(guó)．電子政務(wù)建設(shè)中的政府信息資源整合明 [J]．中國(guó)信息界， 20xx,4(10) [4] 謝軍等．交通信息化發(fā)展評(píng) 價(jià) [J]．長(zhǎng)安大學(xué)學(xué)報(bào) (自然科學(xué)版 ),20xx， 2． 7(6)： 7679． [5] 陳茜，裘紅妹，林群等．全國(guó)智能交通系統(tǒng)示范城市建設(shè)示例 [J]．城市交通， 20xx，6(1)： 33— 55． [6] 王行風(fēng)，賈凌． GIS 支持下的城市交通網(wǎng)絡(luò)最短路徑研究 [M]．計(jì)算機(jī)與現(xiàn)代化， 20xx， [7] 陸鋒．最短路徑算法：分類體系與研究進(jìn)展 [J]。在此對(duì) 肖 老師表示崇高的敬意和真摯的感謝。 。 最后，感謝 曾幫助我的那些同學(xué)， 謝謝你們 對(duì)我論文寫作中的給予的意 見建議， 感謝你們 對(duì)于我書寫論文不懂地方給予 的 無私的幫助，由衷的想對(duì)你們說聲謝謝，對(duì)于論文部分引用的有關(guān)專家學(xué)者的研究，敬請(qǐng)諒解。 [8] 李威武，王慧，錢積新．智能交通系統(tǒng)中路徑誘導(dǎo)算法研究進(jìn)展 [J]．浙江大學(xué)學(xué)報(bào) 工學(xué)版 ,20xx， 39(6)： 81 9825． [9] 陸鋒，盧冬梅，崔偉宏．道路網(wǎng)絡(luò)限制搜索區(qū)域時(shí)間最短路徑算法 [J]．中國(guó)圖象圖 形學(xué)報(bào)， 1999,4(10)： 849853． [10] 陸化普．智能交通系統(tǒng) [M]．北京：人民交通出版社 ,20xx． [11] 徐俊明．圖論及其應(yīng)用 [M]．合肥：中國(guó)科