【正文】 最后再次衷心的感謝所有支持和幫助我的老師和同學們。致謝 31致 謝在本論文即將完成之際，我要感謝我的導師王文朋老師。（4）基礎道路數(shù)據(jù)的更新：在城市在不斷地發(fā)展變化中城市路網(wǎng)也在變化，GPS 車載導航儀的路徑規(guī)劃研究30因此系統(tǒng)所用的數(shù)字地圖也需要實時更新，所以實時更新 GIS 也需要進一步討論。本文規(guī)劃出的僅僅是最短路徑，沒有聯(lián)系實際的路況。 路徑規(guī)劃系統(tǒng)的展望鑒于個人的能力有限，本論文所進行的路徑規(guī)劃研究并不能完全解決車載導航系統(tǒng)的需求，因此還存在以下問題有待進一步研究和改進的地方：（1）顯示地圖上任意兩點間的最短距離：本文中是將用戶任意選擇的點與其最近的節(jié)點相匹配，求出的是匹配后兩點之間的最短距離，這樣顯示的時候不能以用戶所選的點為起始點和終止點，甚至在有些情況下會出現(xiàn)錯誤。從 DDD3 和D4 四列可以看出，算法 33 和算法 32 規(guī)劃出的最優(yōu)路徑相同，且其長度比算法RP0 和算法 31 規(guī)劃出的最短路徑長度稍長，這樣的規(guī)劃結果更符合實際系統(tǒng)要求，因為多數(shù)駕駛員都希望行車過程中能盡量走這種路徑。圖中，粗線為搜索出的最短路徑。步驟二，判斷節(jié)點 S 和 D 所在的路網(wǎng)層次，若節(jié)點 S 和 D 都已在 HRN 中，則算法直接轉入步驟三；否則，若節(jié)點 S 不在 HRN 中，則算法現(xiàn)在 S 附近小區(qū)域內(nèi)調用算法 RP0 子程序搜索由它進入 HRN 的最短路徑 L1及相應的位于 HRN 上的節(jié)點S′，然后，對節(jié)點 D 作同樣的處理，求得相應的最短路徑 L2及相應的位于 HRN上的節(jié)點 D′。與算法 32 不同的是，算法 33 在 HRN 中搜索時，只對落入限制區(qū)域范圍內(nèi)的 HRN 進行搜索，而不是在整個 HRN 中進行搜索，因此它只保證搜索結果與算法 32 相同的同時，搜索效率卻比算法 31 和算法 32 都高。步驟三，在 HRN 中對節(jié)點 S（或對應節(jié)點 S′）和 D（或對應節(jié)點 D′）調用算法 RP0 的實現(xiàn)程序解算其最短路徑 L0。輸入：具有拓撲結構矢量化道路網(wǎng)絡 RN 及其對應分層道路網(wǎng)絡 HRN 和 LRN，起點 S、終點 D 為道路網(wǎng)絡中任意指定的兩個節(jié)點。（2）道路網(wǎng)絡的分層方法第三章 路徑規(guī)劃的分析及設計 23將分層思想引入到道路網(wǎng)絡的設計中，即根據(jù)道路網(wǎng)路中路段的不同等級特性，將整個道路網(wǎng)絡 RN 分為不同的層。換言之，任一高層道路網(wǎng)絡內(nèi)的路段和節(jié)點都包含于其相鄰的低層道路網(wǎng)絡內(nèi)，而任意一個低層道路網(wǎng)絡除了包含其相鄰高層道路網(wǎng)絡內(nèi)的路段和節(jié)點外，還包含更多的其他路段和節(jié)點。因為除了形式距離或形式時間外，最優(yōu)路徑的選擇還需要考慮很多無法預期或定量化的因素。 基于分層道路網(wǎng)絡的分層路徑規(guī)劃算法前面介紹的限制搜索區(qū)域的最短路徑規(guī)劃算法，有效地降低了算法的搜索空間，提高了算法的搜索效率。步驟三，在限制搜索區(qū)域內(nèi)，根據(jù)給定的起點 S 和目標點 D，調用算法 RP0的實現(xiàn)程序進行最短路徑計算。圖 限制搜索區(qū)域的確定方法算法 31 的實現(xiàn)步驟如下：輸入：采用鄰接節(jié)點數(shù)據(jù)結構存儲的矢量化城市道路網(wǎng)絡，路徑規(guī)劃的起點S，終點 D，閾值 T1和 T2。（2）方向搜索策略的構造與應用受幾何學中“兩點之間直線距離最短”的啟發(fā)，在對實際城市道路網(wǎng)絡中的給定兩點進行最短路徑規(guī)劃時，起點到終點的連線方向基本上代表了最短路徑的大致走向。（1）道路網(wǎng)絡特有的空間分布特性與普通的平面網(wǎng)絡圖相比，描述實際城市道路網(wǎng)絡的拓撲圖通常具有以下特點：①多為大規(guī)模的稀疏網(wǎng)絡，點多邊少（網(wǎng)絡的節(jié)點通常成千上萬，甚至更多，而每個節(jié)點相連的路段一般不超過 5，多為 3 或 4） 。與鄰接矩陣法相比，鄰接節(jié)點法不僅將道路網(wǎng)絡的存儲空間降低到原來的MaxNum/n，而且也將搜索算法的時間復雜度降低到 O(MaxNum然后再 J 中取(di,dj)元素，記為 w，若第 w 行尚未標記，則將 DJ 的第 w 行標記，Mark(w)=di；并在 J 的第 w 行尋找值為 di的元素，記錄該元素的行GPS 車載導航儀的路徑規(guī)劃研究20ri、列 rj。步驟一，初始化標記向量 Mark，Mark(i)=—1，其中，i=1,2，…，MaxNum。對應鄰接節(jié)點矩陣 J 的各元素，構造初始判斷矩陣 DJ。需要說明的是，道路網(wǎng)絡節(jié)點和邊的內(nèi)部序號與實際編號可以不相同。構造與 J 結構相同的初始判斷矩陣 DJ，同時將 J 中個元素鄰接關系對應的邊的權值填在同一位置上（∞對應 0 元素） 。（2）鄰接節(jié)點法鄰接矩陣法的不足是鄰接矩陣 cost 中存在大量的無效的 0 元素和∞元素，這不僅占用大量的存儲空間，而且也使得基于矩陣運算的 Dijkstra 算法效率大為降低。為了能記下路徑，設置一個路徑向量 P，其中 P(i)表示從源點到達 i 節(jié)點的最短路徑上該點的前趨節(jié)點。從 v 出發(fā)到圖上其余各節(jié)點（終點）vi 可能GPS 車載導航儀的路徑規(guī)劃研究18達到的最短路徑長度 D(i)的初始值為D(i)=cost(v,vi) vi∈V (33)步驟二，選擇 vj，使得 D(j)=Min{ D(i)|vi∈VS} (34)vj就是當前求得的從 v 出發(fā)的最短路徑的終點，令 S=S∪{vj} (35)步驟三，修改從 v 出發(fā)到集合 VS 上任一節(jié)點 vk可達的最短路徑長度，如果 D(j)+cost(j,k)＜D(k) (36)則修改 D(k)為 D(k)= D(j)+cost(j,k) (37)步驟四，重復操作步驟二、步驟三共 n1 次，由此求得按路徑長度遞增次序排列的從 v 出發(fā)到圖上其余各節(jié)點的最短路徑。從以上對 Dijkstra 算法原理分析可以看出，其最大特點是在最短路徑的求解過程中搜索算法具有很大的盲目性，隨時準備向其四面八方展開，最終的搜索區(qū)域基本上是以起始點為原點，以起始點與目標點的連線長度為半徑的一個圓。這可用反證法來證明：假設此路徑上有一個節(jié)點不在 S 中，則說明存在一條終點不在 S 而長度比路徑更短的路徑。為了求解這一問題，Dijkstra 提出了一種按路徑長度遞增次序來產(chǎn)生最短路徑的Dijkstra 算法，其原理如下：首先，引進一個輔助向量 D，它的每個分量 D(i)表示當前所找到的從起始點v 到每個重點 vi的最短路徑的長度。本節(jié)簡要的介紹 Dijkstra 算法的原理及特點，并給出它的兩種具體實現(xiàn)方法，即鄰接矩陣法和鄰接節(jié)點法，作為后續(xù)幾個路徑規(guī)劃算法的基礎算法。第二步是在第一步的基礎上，由完善以后的折線道路網(wǎng)絡數(shù)據(jù)生成表示其拓撲結構的 ArcNode 數(shù)據(jù)結構，ArcNode 數(shù)據(jù)結構采用鄰接表結構。如圖 （d）所示，節(jié)點 A、B、C、D 實際表示的地圖中的同一點，換言之，此時應該只用一個節(jié)點來表示地圖中的該點，然而，給定的道路網(wǎng)絡數(shù)據(jù)中卻存在節(jié)點 A、B、C、D；另一種情況是，本來可以由兩個節(jié)點表示的路段，給定的道路網(wǎng)絡數(shù)據(jù)中卻存在其他節(jié)點，如圖 （e）所示，路段 AB 只需節(jié)點 A和 B 便能在精度允許范圍內(nèi)準確表示，而實際數(shù)據(jù)中卻包括節(jié)點 C 和 D。如圖 （b）所示，路段 AB 與路段 CD 實際應相交于節(jié)點 B，而節(jié)點 B并未出現(xiàn)在路段 CD 的給定數(shù)據(jù)中，將節(jié)點 B 稱為虛斷點。有時，為了數(shù)據(jù)獲取方便，也可能以近似的道路中心線來表示。鏈表的表頭節(jié)點以順序結構形式存儲，以便隨機訪問圖中任一節(jié)點的單鏈表。GPS 車載導航儀的路徑規(guī)劃研究14節(jié)點 3節(jié)點 2節(jié)點 1圖 弧度較大的路段處理計算機存儲的是矢量化的道路網(wǎng)絡，網(wǎng)絡的存儲結構是影響路徑規(guī)劃算法搜索速度和事件復雜度的一個重要因素。如圖 ，節(jié)點 2 之間路段的弧度較大，在路段上加入節(jié)點 2，把原來的路段分成兩個弧度相對較小的路段。本文采用ArcNode 結構，其主要特點是，容易表達實際路網(wǎng)的拓撲關系，且形式簡潔。讀寫層抽象了對文件進行操作的特性，封裝了對磁盤鏈的管理和讀寫操作等。應用軟件設計人員可以調用該結構訪問數(shù)字地圖文件，接口層核心層讀寫層GPS 車載導航儀的路徑規(guī)劃研究12并對地圖對象和屬性數(shù)據(jù)進行操作，例如屬性數(shù)據(jù)的查詢等。 導航電子地圖數(shù)據(jù)庫的結構設計與實現(xiàn)導航電子地圖數(shù)據(jù)庫是整個系統(tǒng)的基石，系統(tǒng)中幾乎所有的模塊都直接或間接的與其相關，其結構設計的好壞將直接影響整個系統(tǒng)的最終性能。④空間信息查詢速度快。②冗余度小。與傳統(tǒng)的導航電子地圖數(shù)據(jù)模型相比，面向對象的數(shù)據(jù)模型具有的優(yōu)點是：結構清晰、組織有序，所有空間實體都以對象的形式封裝；可以定義和處理復雜的空間實體；易于擴充和二次開發(fā)；面向對象的用戶界面更便于用戶操作和使用。它不僅將地理世界以實體為單位進行組織，而且將客觀世界作為一個整體看待，即每個實體不僅自身具有空間特性和屬性特性的聯(lián)系，更重要的是它與其它實體之間同時還具有邏輯上的語義聯(lián)系，此外，它也具有時間屬性。二維表由表框架和元組組成，表框架由 n 個屬性（或稱為列）組成，而存放于框架內(nèi)的每行數(shù)據(jù)稱為元組（或稱為行） ，因此，一張二維表是由一個n 元屬性的框架及 m 個元組組成。①層次模型該模型的基本結構是樹形結構。缺點是精度較差、網(wǎng)絡拓撲建立困難。缺點是數(shù)據(jù)結構復雜，對軟硬件要求高。其中的路徑規(guī)劃是導航系統(tǒng)的一項關鍵技術，是導航系統(tǒng)的基礎部分。⒊ 地圖瀏覽功能：地圖瀏覽包括縮放、移動等，用戶可以在一定的放大級上將地圖進行縮小、放大、移動的操作。這些信息通過人——機接口，并以特殊的指令如視、聽提供給司機。如果有條件利用實時的交通信息，還應對駕駛路線及時調整以適應交通當前的狀況。⒉ 數(shù)字地圖數(shù)據(jù)庫模塊：主要負責存儲數(shù)字地圖及信息。一個完整的地圖匹配過程包括三個主要環(huán)節(jié)，即誤差區(qū)域的確定、匹配道路的選擇及定位結果的修正。GIS 軟件DBMS 軟件空間數(shù)據(jù)庫屬性數(shù)據(jù)庫電子地圖數(shù)據(jù)庫顯示器車載計算機導航軟件GPS 終端圖 車載導航系統(tǒng)的總體結構 車載導航系統(tǒng)的關鍵技術⒈ 數(shù)字地圖：也稱電子地圖，是一個矢量化的地圖，即該地圖中應該包括地圖上的基本對象的屬性數(shù)據(jù)。其主要功能是采集實時的位置信息，進行自身的定位，不斷的更新當前數(shù)據(jù)，為交通管理提供最新的數(shù)據(jù)信息。目前已有許多科學研究單位和公司從事這方面的開發(fā)應用。日本從 1971 年開始研究綜合車輛交通控制系統(tǒng)計劃（CACS） ，從 1973～1978 年，日本成功的組織了一個叫做動態(tài)路徑誘導的實驗。衛(wèi)星定位技術（GPS） 、地理信息系統(tǒng)（GIS） 、遙感技術（RS） 、數(shù)據(jù)庫技術、計算機網(wǎng)絡技術等科技技術的出現(xiàn)，有效地解決了當前城市現(xiàn)代交通管理的諸多問題。第四章是“路徑規(guī)劃的優(yōu)缺點分析” ，本章主要說明了上一章介紹的幾種路徑規(guī)劃的優(yōu)缺點。本文的主要內(nèi)容就是在研究車載導航系統(tǒng)的同時，重點研究其中的路徑規(guī)劃問題，研究路徑規(guī)劃的算法。隨著美國 GPS 現(xiàn)代化計劃的實施，GPS 國際化的趨勢日趨明顯。總之，GPS 技術已發(fā)展成多領域、多模式、多用途、多機型的高新技術國際性產(chǎn)業(yè)，廣泛應用于海陸空在途導航、精密定位、精確授時、衛(wèi)星定規(guī)、武器制導、交通控制、災害監(jiān)測、大地測量、大氣研究等多個領域，正如人們所說， “GPS 的應用，禁受人類想象力的約束” 。經(jīng)典的慣性導航技術（INS）與 GPS 結合，形成新型組合導航系統(tǒng)，以最優(yōu)的價格和性能為陸?？仗峁Ш椒铡２⑿懈櫿嚓P技術及高速 DSP 的采納，使得 GPS 定位實時數(shù)據(jù)更新率由通常的 1s 降低至 ，而新興的實時相位差分（RTK）技術可使實時定位達到厘米乃至毫米級精度。實踐證明，GPS 對人類活動影響極大，應用價值很高，該工程從根本上解決了人類在地球上的導航問題和定位問題，可以滿足不同用戶的要求。1973～1978 年，發(fā)射了 4 顆試驗衛(wèi)星，建立了地面跟蹤網(wǎng)，研制了地面接收機；1979 年～1984 年又陸續(xù)發(fā)射了 7 顆 BlockⅠ試驗衛(wèi)星，研制了各種用途的接收機，包括導航型和測地型接收機；1985～1993 年發(fā)射BlockⅡ和