【正文】 一個衛(wèi)星導(dǎo)航系統(tǒng)研制成功即“子午衛(wèi)星系統(tǒng)” ，但由于該系統(tǒng)存在較大的缺陷，且不能滿足當前實時、動態(tài)、精確的定位需要，所以終止了該系統(tǒng)的研究。1973～1978 年，發(fā)射了 4 顆試驗衛(wèi)星，建立了地面跟蹤網(wǎng)，研制了地面接收機；1979 年～1984 年又陸續(xù)發(fā)射了 7 顆 BlockⅠ試驗衛(wèi)星，研制了各種用途的接收機，包括導(dǎo)航型和測地型接收機；1985～1993 年發(fā)射BlockⅡ和 BlockⅡA；直到 1994 年順利完成了 24 顆衛(wèi)星的布設(shè)，這就是“導(dǎo)航衛(wèi)星授時與測距全球定位系統(tǒng)” （Navigation Satellite Timing and Raining/ Global Positioning System,NAVSTAR,GPS）,簡稱全球定位系統(tǒng)（GPS） 。全球定位系統(tǒng)不僅集成以前所有的單用途衛(wèi)星系統(tǒng)，并且致力于更廣泛的用途。實踐證明，GPS 對人類活動影響極大，應(yīng)用價值很高，該工程從根本上解決了人類在地球上的導(dǎo)航問題和定位問題，可以滿足不同用戶的要求。GPS 產(chǎn)業(yè)的發(fā)展趨勢呈現(xiàn)以下三方面特點：⑴ 隨著微電子技術(shù)及信號處理技術(shù)的進步，新的軟硬件開發(fā)工具的出現(xiàn)，第一章 緒論 3GPS 技術(shù)水平越來越高。并行跟蹤窄相關(guān)技術(shù)及高速 DSP 的采納，使得 GPS 定位實時數(shù)據(jù)更新率由通常的 1s 降低至 ，而新興的實時相位差分（RTK）技術(shù)可使實時定位達到厘米乃至毫米級精度。⑵ GPS 技術(shù)的應(yīng)用越來越廣泛，與其他領(lǐng)域的融合也越來越密切。經(jīng)典的慣性導(dǎo)航技術(shù)（INS）與 GPS 結(jié)合，形成新型組合導(dǎo)航系統(tǒng)，以最優(yōu)的價格和性能為陸?？仗峁?dǎo)航服務(wù)。與此同時，GPS 與其他導(dǎo)航通信衛(wèi)星之間的聯(lián)合也逐步展開，如與前蘇聯(lián)（現(xiàn)由俄羅斯掌管）的 GLONASS 衛(wèi)星以及國際海事衛(wèi)星INMARSAT 聯(lián)合，組成未來的全球?qū)Ш较到y(tǒng)（GNSS） ?？傊珿PS 技術(shù)已發(fā)展成多領(lǐng)域、多模式、多用途、多機型的高新技術(shù)國際性產(chǎn)業(yè)，廣泛應(yīng)用于海陸空在途導(dǎo)航、精密定位、精確授時、衛(wèi)星定規(guī)、武器制導(dǎo)、交通控制、災(zāi)害監(jiān)測、大地測量、大氣研究等多個領(lǐng)域，正如人們所說， “GPS 的應(yīng)用，禁受人類想象力的約束” 。隨著GPS 應(yīng)用的不斷深入，許多工程實際上已經(jīng)離不開 GPS，GPS 政策成為世界各國關(guān)注的焦點。隨著美國 GPS 現(xiàn)代化計劃的實施，GPS 國際化的趨勢日趨明顯。 研究內(nèi)容及安排 研究的內(nèi)容 車載導(dǎo)航系統(tǒng)是集成應(yīng)用了自動車輛定位技術(shù)、地理信息系統(tǒng)技術(shù)、數(shù)據(jù)庫技術(shù)、多媒體技術(shù)和現(xiàn)代通信技術(shù)等的高科技綜合系統(tǒng)；是一個為客戶提供定位、GPS 車載導(dǎo)航儀的路徑規(guī)劃研究4路徑規(guī)劃、路徑引導(dǎo)等多種服務(wù)的復(fù)雜系統(tǒng)，其中路徑規(guī)劃是幫助司機在行車過程中規(guī)劃行駛路線的過程，是路徑引導(dǎo)、信息服務(wù)等模塊的基礎(chǔ)，因此其被廣泛認為是汽車導(dǎo)航系統(tǒng)的基礎(chǔ)問題。本文的主要內(nèi)容就是在研究車載導(dǎo)航系統(tǒng)的同時，重點研究其中的路徑規(guī)劃問題，研究路徑規(guī)劃的算法。第二章是“GPS 車載導(dǎo)航系統(tǒng)的結(jié)構(gòu)與關(guān)鍵技術(shù)” ，簡述了車載導(dǎo)航系統(tǒng)的發(fā)展，設(shè)計的主要思路，以及 GPS 車載導(dǎo)航系統(tǒng)的總體結(jié)構(gòu)和關(guān)鍵技術(shù)以及系統(tǒng)結(jié)構(gòu)分析和各模塊的功能。第四章是“路徑規(guī)劃的優(yōu)缺點分析” ，本章主要說明了上一章介紹的幾種路徑規(guī)劃的優(yōu)缺點。第二章 GPS 車載導(dǎo)航系統(tǒng)的結(jié)構(gòu)與關(guān)鍵技術(shù) 5第二章 GPS 車載導(dǎo)航系統(tǒng)的結(jié)構(gòu)與關(guān)鍵技術(shù) 車載導(dǎo)航系統(tǒng)的發(fā)展 車載導(dǎo)航系統(tǒng)的研究和發(fā)展在人類的文明史上已有相當長的歷史，最古老、最簡單的導(dǎo)航方法是星歷導(dǎo)航，人們通過觀察天空上星星的位置變更來確定自己的位置和前進方向。衛(wèi)星定位技術(shù)（GPS） 、地理信息系統(tǒng)（GIS） 、遙感技術(shù)（RS） 、數(shù)據(jù)庫技術(shù)、計算機網(wǎng)絡(luò)技術(shù)等科技技術(shù)的出現(xiàn)，有效地解決了當前城市現(xiàn)代交通管理的諸多問題。美國公路局最早于 20 世紀 60 年代末期提出了一種電子路徑引導(dǎo)系統(tǒng)（ERGS） ，這是一種具有無線路徑引導(dǎo)功能的導(dǎo)航系統(tǒng)，用于控制和疏導(dǎo)交通，但由于資金問題沒有實現(xiàn)。日本從 1971 年開始研究綜合車輛交通控制系統(tǒng)計劃（CACS） ，從 1973～1978 年，日本成功的組織了一個叫做動態(tài)路徑誘導(dǎo)的實驗。歐洲也大量的發(fā)行了自己的許多導(dǎo)航產(chǎn)品。目前已有許多科學(xué)研究單位和公司從事這方面的開發(fā)應(yīng)用。 車載導(dǎo)航技術(shù)的總體結(jié)構(gòu)和關(guān)鍵技術(shù)GPS 車載導(dǎo)航儀的路徑規(guī)劃研究6 車載導(dǎo)航系統(tǒng)的總體結(jié)構(gòu)車載導(dǎo)航系統(tǒng)是由 GPS 終端、車載計算機、導(dǎo)航軟件、顯示器及 GIS 軟件等組成的（如圖 ） 。其主要功能是采集實時的位置信息，進行自身的定位，不斷的更新當前數(shù)據(jù)，為交通管理提供最新的數(shù)據(jù)信息。③GIS 電子地圖，把地理數(shù)據(jù)以圖形的方式顯示出來，提供了多種地圖服務(wù)，為用戶提供一個直觀清晰的界面。GIS 軟件DBMS 軟件空間數(shù)據(jù)庫屬性數(shù)據(jù)庫電子地圖數(shù)據(jù)庫顯示器車載計算機導(dǎo)航軟件GPS 終端圖 車載導(dǎo)航系統(tǒng)的總體結(jié)構(gòu) 車載導(dǎo)航系統(tǒng)的關(guān)鍵技術(shù)⒈ 數(shù)字地圖：也稱電子地圖，是一個矢量化的地圖，即該地圖中應(yīng)該包括地圖上的基本對象的屬性數(shù)據(jù)。典型的數(shù)字地圖的標準格式有 MapInfo 的 MIF/MID 文件，AutoCAD 的 DXF 文件等。一個完整的地圖匹配過程包括三個主要環(huán)節(jié)，即誤差區(qū)域的確定、匹配道路的選擇及定位結(jié)果的修正。車輛導(dǎo)航系統(tǒng)的路徑規(guī)劃是幫助駕駛員在旅行前或旅行中規(guī)劃行駛路徑的過程，它要解決的主要問題是在給定的數(shù)字道路地圖中尋找從第二章 GPS 車載導(dǎo)航系統(tǒng)的結(jié)構(gòu)與關(guān)鍵技術(shù) 7出發(fā)地到目的地的最優(yōu)路徑，為滿足實際要求，路徑規(guī)劃應(yīng)具有快速性和最佳性。⒉ 數(shù)字地圖數(shù)據(jù)庫模塊：主要負責(zé)存儲數(shù)字地圖及信息。⒊ 地圖匹配模塊：又稱地理編碼，即通過給定的經(jīng)緯度坐標確定地圖上街道的地址，或者相反的過稱。如果有條件利用實時的交通信息，還應(yīng)對駕駛路線及時調(diào)整以適應(yīng)交通當前的狀況。路徑行駛包括兩個任務(wù)：一是產(chǎn)生行駛指令，任務(wù)是產(chǎn)生一個行駛指令列表使其遵循路徑規(guī)劃跟蹤的路線。這些信息通過人——機接口，并以特殊的指令如視、聽提供給司機。 系統(tǒng)的功能要求車載導(dǎo)航系統(tǒng)的主要功能有：⒈ 定位功能：利用全球定位系統(tǒng)（GPS）來獲取當前的定位信息并與地圖進行匹配，從而決定車輛當前的所在然后以圖形的方式顯示出來。⒊ 地圖瀏覽功能：地圖瀏覽包括縮放、移動等，用戶可以在一定的放大級上將地圖進行縮小、放大、移動的操作。查詢的資料可以通過文字、圖形的方式在電子地圖上顯示其位置。其中的路徑規(guī)劃是導(dǎo)航系統(tǒng)的一項關(guān)鍵技術(shù)，是導(dǎo)航系統(tǒng)的基礎(chǔ)部分。①矢量結(jié)構(gòu)該結(jié)構(gòu)用空間坐標及其關(guān)系描述空間對象，單個空間對象是圖形數(shù)據(jù)的基本邏輯單位。缺點是數(shù)據(jù)結(jié)構(gòu)復(fù)雜，對軟硬件要求高。②柵格結(jié)構(gòu)該結(jié)構(gòu)用點的像素表示空間對象。缺點是精度較差、網(wǎng)絡(luò)拓撲建立困難。③矢量柵格一體化結(jié)構(gòu)該結(jié)構(gòu)綜合了兩種結(jié)構(gòu)的優(yōu)點，在許多電子地圖中得到了應(yīng)用。①層次模型該模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)。②網(wǎng)狀模型網(wǎng)狀模型明顯優(yōu)于層次模型，數(shù)據(jù)顯示和數(shù)據(jù)操作方法均呈現(xiàn)高效、成熟的特點，但是，網(wǎng)狀模型不足之處在于使用時涉及系統(tǒng)內(nèi)部因素較多，用戶操作使用不方便，數(shù)據(jù)模式與系統(tǒng)實現(xiàn)也甚不理想。二維表由表框架和元組組成，表框架由 n 個屬性（或稱為列）組成，而存放于框架內(nèi)的每行數(shù)據(jù)稱為元組（或稱為行） ，因此，一張二維表是由一個n 元屬性的框架及 m 個元組組成。面向?qū)ο蟮恼w數(shù)據(jù)模型是將面向?qū)ο螅╫bject oriented）思想和面向?qū)ο蟮姆治鲈O(shè)計方法應(yīng)用到空間數(shù)據(jù)模型的設(shè)計中，將各種空間實體抽象為某一類具有公共屬性的對象，如點、線、面等對象，每個具體的地理實體是該對象的一個實例，具有自己的屬性，各種對象分層管理，實現(xiàn)空間數(shù)據(jù)與屬性數(shù)據(jù)的統(tǒng)一管理。它不僅將地理世界以實體為單位進行組織，而且將客觀世界作為一個整體看待，即每個實體不僅自身具有空間特性和屬性特性的聯(lián)系，更重要的是它與其它實體之間同時還具有邏輯上的語義聯(lián)系，此外，它也具有時間屬性。因此，面向?qū)ο蟮恼w數(shù)據(jù)模型是一種有效的空間數(shù)據(jù)模型。與傳統(tǒng)的導(dǎo)航電子地圖數(shù)據(jù)模型相比，面向?qū)ο蟮臄?shù)據(jù)模型具有的優(yōu)點是：結(jié)構(gòu)清晰、組織有序，所有空間實體都以對象的形式封裝；可以定義和處理復(fù)雜的空間實體；易于擴充和二次開發(fā)；面向?qū)ο蟮挠脩艚缑娓阌谟脩舨僮骱褪褂?。一般設(shè)計導(dǎo)航電子地圖數(shù)據(jù)庫應(yīng)遵循以下原則：第三章 路徑規(guī)劃的分析及設(shè)計 11①圖形結(jié)構(gòu)簡單。②冗余度小。③拓撲關(guān)系簡單。④空間信息查詢速度快。⑤數(shù)據(jù)接口開放。 導(dǎo)航電子地圖數(shù)據(jù)庫的結(jié)構(gòu)設(shè)計與實現(xiàn)導(dǎo)航電子地圖數(shù)據(jù)庫是整個系統(tǒng)的基石，系統(tǒng)中幾乎所有的模塊都直接或間接的與其相關(guān)，其結(jié)構(gòu)設(shè)計的好壞將直接影響整個系統(tǒng)的最終性能?？臻g對象 屬性數(shù)據(jù)對象訪問 索引操作 屬性操作二進制文件讀寫模塊其他文件DBF 文件OBJ文件IDX文件圖 導(dǎo)航電子地圖數(shù)據(jù)庫的層次結(jié)構(gòu)第一層為接口層，包括空間對象與屬性結(jié)構(gòu)。應(yīng)用軟件設(shè)計人員可以調(diào)用該結(jié)構(gòu)訪問數(shù)字地圖文件，接口層核心層讀寫層GPS 車載導(dǎo)航儀的路徑規(guī)劃研究12并對地圖對象和屬性數(shù)據(jù)進行操作，例如屬性數(shù)據(jù)的查詢等。第三層為讀寫層，完成對二進制文件底層讀寫操作。讀寫層抽象了對文件進行操作的特性，封裝了對磁盤鏈的管理和讀寫操作等?？臻g對象/索引對象/ 屬性對象空間數(shù)據(jù)人機接口界面（地圖顯示、信息查詢、路徑規(guī)劃及地圖匹配等功）屬性數(shù)據(jù)地圖數(shù)據(jù)庫文件讀寫導(dǎo)航電子地圖數(shù)據(jù)庫文件（ 、.IDX、.DBF 文件）接口層用戶層文件層 圖 導(dǎo)航電子地圖數(shù)據(jù)庫實現(xiàn)流程 導(dǎo)航電子地圖中道路網(wǎng)絡(luò)的拓撲生成方法 導(dǎo)航電子地圖中道路網(wǎng)絡(luò)的模型與儲存道路網(wǎng)絡(luò)的數(shù)據(jù)模型，是指導(dǎo)航電子地圖道路網(wǎng)絡(luò)用來組織其數(shù)據(jù)所采用的格式轉(zhuǎn)換及拓撲生成數(shù)據(jù)格式分析/關(guān)鍵數(shù)據(jù)解析外部地圖數(shù)據(jù)源第三章 路徑規(guī)劃的分析及設(shè)計 13模型，它是生成具有拓撲結(jié)構(gòu)道路網(wǎng)絡(luò)的基礎(chǔ)。本文采用ArcNode 結(jié)構(gòu)，其主要特點是，容易表達實際路網(wǎng)的拓撲關(guān)系，且形式簡潔。 根據(jù)實際交通網(wǎng)絡(luò)的特點，我們作如下分析假設(shè)： ①所有的編制都是直線。如圖 ，節(jié)點 2 之間路段的弧度較大，在路段上加入節(jié)點 2，把原來的路段分成兩個弧度相對較小的路段。 ③網(wǎng)絡(luò)中有較多的節(jié)點和邊。GPS 車載導(dǎo)航儀的路徑規(guī)劃研究14節(jié)點 3節(jié)點 2節(jié)點 1圖 弧度較大的路段處理計算機存儲的是矢量化的道路網(wǎng)絡(luò)，網(wǎng)絡(luò)的存儲結(jié)構(gòu)是影響路徑規(guī)劃算法搜索速度和事件復(fù)雜度的一個重要因素。在鄰接表中，對圖的每個節(jié)點建立一個單鏈表，每個單鏈表都由表節(jié)點和表頭節(jié)點構(gòu)成。鏈表的表頭節(jié)點以順序結(jié)構(gòu)形式存儲，以便隨機訪問圖中任一節(jié)點的單鏈表。單鏈表的表頭節(jié)點和表節(jié)點的結(jié)構(gòu)如圖 所示，圖中，Name：節(jié)點編號；Position：節(jié)點位置坐標；First：指向鏈表中的第一個表節(jié)點；Next：指向鏈表中的下一個表節(jié)點；Weight：邊的權(quán)值。有時，為了數(shù)據(jù)獲取方便，也可能以近似的道路中心線來表示。如圖 （a）所示，路段 AB 與路段 CD 實際應(yīng)相交于節(jié)點 O，而節(jié)點 O 并未出現(xiàn)在路段 AB 與路段 CD 的給定數(shù)據(jù)中。如圖 （b）所示，路段 AB 與路段 CD 實際應(yīng)相交于節(jié)點 B，而節(jié)點 B并未出現(xiàn)在路段 CD 的給定數(shù)據(jù)中，將節(jié)點 B 稱為虛斷點。如圖 （c）所示，路段 AB 與路段 CD 相交于節(jié)點 O，過短路段 BO 應(yīng)該不存在，然而，節(jié)點 B 卻出現(xiàn)在路段 AB 給定數(shù)據(jù)中，將節(jié)點 B 稱為過交點。如圖 （d）所示，節(jié)點 A、B、C、D 實際表示的地圖中的同一點，換言之，此時應(yīng)該只用一個節(jié)點來表示地圖中的該點，然而，給定的道路網(wǎng)絡(luò)數(shù)據(jù)中卻存在節(jié)點 A、B、C、D；另一種情況是，本來可以由兩個節(jié)點表示的路段，給定的道路網(wǎng)絡(luò)數(shù)據(jù)中卻存在其他節(jié)點，如圖 （e）所示，路段 AB 只需節(jié)點 A和 B 便能在精度允許范圍內(nèi)準確表示，而實際數(shù)據(jù)中卻包括節(jié)點 C 和 D。具體生成過稱分為兩步：第一步是完善給定的折線道路網(wǎng)絡(luò)數(shù)據(jù)，即對前面介紹的道路網(wǎng)絡(luò)的幾種特(a)線段間的虛交特性(d)表示同一點的多個節(jié)點 (e)可以壓縮掉的中間節(jié)點(b)線段間的虛斷特性(c)線段間的過交特性 (c)線 段 間 的 過 交 特 性 D