gps車載導航儀的路徑規(guī)劃研究畢業(yè)論文

1、<p><b>　　摘 要</b></p><p>　　隨著私人汽車在中國的普及，車載導航儀成為了日常生活中必不可少的工具。車載導航系統(tǒng)的路徑規(guī)劃的研究無論是從方便駕駛員出行，提高運輸效率，優(yōu)化城市交通，還是在改造與提升交通管理系統(tǒng)上，都對現(xiàn)代的交通道路起著十分重要的影響，因此受到社會和政府部門的關注和大力支持。</p><p>　　本論文介紹了車載導航系

2、統(tǒng)的發(fā)展歷史和國內外研究現(xiàn)狀，以及GPS車載導航系統(tǒng)的組成、功能、實現(xiàn)過程、路徑規(guī)劃算法以及地理信息系統(tǒng)的功能。并以MaoInfo為工具，在路徑規(guī)劃系統(tǒng)中實現(xiàn)了地圖的基本操作。本文重點研究了車載導航系統(tǒng)的路徑規(guī)劃問題。綜合考慮并比較了多種最短路徑的選擇算法,并對其優(yōu)缺點進行了分析。</p><p>　　關鍵詞：GPS GIS 車載導航系統(tǒng) 路徑規(guī)劃 Dijkstra算法</p><p&

3、gt;<b>　　ABSTRACT</b></p><p>　　With the popularization of private cars in China ，the navigators became the daily life of the necessary tools. The car's navigation system path planning research

4、 whether from convenient drivers travel to improve transport efficiency and optimize the urban traffic, or in the reform and improve traffic management system, all the way to modern traffic plays a very important influen

5、ce, and it is by society and government departments of the attention and support. </p><p>　　This paper introduces the development history of the car's navigation system and research status from domestic

6、and abroad.The structure, function and the realization of the whole system are demonstrated in detail in this thesis. The GIS(Geographic Information System) theory is introduced .By using MapInfo software as a supporting

7、 platform, basic operation of map are realized. The algorithms of Route Planning are discussed in detail. Think over and compare many shortest path algorithms and presen</p><p>　　Keywords: GPS GIS Vehicle

8、 navigation System Route-Planning Dijkstra algorithm目 錄</p><p><b>　　第一章緒論1</b></p><p>　　1.1研究背景與意義1</p><p>　　1.2GPS導航系統(tǒng)的發(fā)展概況1</p><p>　　1.1.1GPS導航系

9、統(tǒng)的發(fā)展歷程2</p><p>　　1.1.2GPS導航技術應用的發(fā)展趨勢2</p><p>　　1.2研究內容及安排3</p><p>　　1.2.1研究的內容3</p><p>　　1.2.2本文的安排4</p><p>　　第二章GPS車載導航系統(tǒng)的結構與關鍵技術5</p>&

10、lt;p>　　2.1車載導航系統(tǒng)的發(fā)展5</p><p>　　2.2車載導航技術的總體結構和關鍵技術5</p><p>　　2.2.1車載導航系統(tǒng)的總體結構6</p><p>　　2.2.2車載導航系統(tǒng)的關鍵技術6</p><p>　　2.3車載導航系統(tǒng)結構分析及功能要求7</p><p>　

11、　2.4系統(tǒng)的功能要求7</p><p>　　第三章路徑規(guī)劃的分析及設計9</p><p>　　3.1導航電子地圖數據庫的設計9</p><p>　　3.1.1導航電子地圖的數據結構與數據模型9</p><p>　　3.1.2導航電子地圖數據庫的設計原則10</p><p>　　3.1.3導航電子

12、地圖數據庫的結構設計與實現(xiàn)11</p><p>　　3.2導航電子地圖中道路網絡的拓撲生成方法12</p><p>　　3.2.1導航電子地圖中道路網絡的模型與儲存13</p><p>　　3.2.2折線道路網絡的拓撲生成法14</p><p>　　3.3路徑規(guī)劃的分析及設計16</p><p>　　

13、3.3.1路徑規(guī)劃的基礎算法16</p><p>　　3.3.2限制搜索區(qū)域的路徑規(guī)劃算法20</p><p>　　3.3.3基于分層道路網絡的分層路徑規(guī)劃算法22</p><p>　　3.3.4限制搜索區(qū)域的分層路徑規(guī)劃算法24</p><p>　　第四章路徑規(guī)劃的優(yōu)缺點分析25</p><p>

14、　　4.1算法的實驗結果25</p><p>　　4.2算法實驗結果的比對及優(yōu)缺點分析26</p><p><b>　　第五章結論29</b></p><p>　　5.1論文小結29</p><p>　　5.2路徑規(guī)劃系統(tǒng)的展望29</p><p><b>　　致

15、謝31</b></p><p><b>　　參考文獻33</b></p><p><b>　　緒論</b></p><p><b>　　研究背景與意義</b></p><p>　　交通事業(yè)的發(fā)展與我國社會主義現(xiàn)代化建設有著密不可分的關系，并且對人們的日常生活有

16、著巨大的影響。車輛作為主要的交通工具，一方面促進了社會經濟的快速發(fā)展，另一方面也不斷的改善著人們的生活，提高了人們的生活質量。然而，近年來大幅增長的機動車輛使交通問題在日常生活中愈加突出。交通擁堵、交通事故等社會問題嚴重影響到交通正常秩序乃至社會正常秩序。當前的交通問題是全世界國家，從發(fā)展中國家到發(fā)展國家都正面臨的一個重要的問題。以投入巨大資源修建道路這種高成本的方式解決交通擁擠問題是杯水車薪。資金、環(huán)境、歷史原因等因素是改善道路交通成

17、本更加高昂問題也更加復雜。所以，修建道路這種方式的效果非常有限，無法從根本上解決交通問題。</p><p>　　為了緩解交通問題，從上世紀60年代起，發(fā)達國家開始著手研究解決交通問題的可行辦法。制定交通規(guī)劃、使用信號燈等措施緩解了交通問題，但不足以高效的解決交通問題，仍無法解決快速增長的車輛需要，必須從系統(tǒng)觀點整體上綜合考慮解決。</p><p>　　近年來人們已經逐漸認識到單純靠增加道路

18、基礎設施建設不可能從根本上解決車輛的快速增長與交通設施滯后之間的突出矛盾。只有在計算機、信息和通訊等高科技手段的輔助下充分利用現(xiàn)有的道路基礎設施，才是最合理最可行的方法。因此，人們從系統(tǒng)角度提出了智能交通系統(tǒng)（ITS,Itelligent Transport System）的概念，建立現(xiàn)代化的交通系統(tǒng)已然成為國家現(xiàn)代化的重要標志之一。</p><p>　　ITS是一個復雜的巨系統(tǒng)，包含了眾多的子系統(tǒng)，其中車載導航

19、系統(tǒng)是最為重要的子系統(tǒng)之一，具有極大的市場前景和發(fā)展?jié)摿Α＼囕d導航系統(tǒng)的研制開發(fā)可規(guī)劃分為相互關聯(lián)的技術模塊，路徑規(guī)劃則是其他功能模塊運行的基礎，同時包含了車載導航系統(tǒng)中的很多關鍵技術。本文就是重點研究了車載導航系統(tǒng)的路徑規(guī)劃問題。</p><p>　　GPS導航系統(tǒng)的發(fā)展概況</p><p>　　GPS導航系統(tǒng)的發(fā)展歷程</p><p>　　在很早的時候就已經有導

20、航技術的應用。指南針和記里鼓車等古代時期的導航設備被認為是現(xiàn)代磁羅盤和差分里程計的原型，是已知最早的導航工具。</p><p>　　1957年10月世界上第一顆衛(wèi)星發(fā)射成功后，科學家開始進行衛(wèi)星定位和導航的研究工作。1964年1月世界上第一個衛(wèi)星導航系統(tǒng)研制成功即“子午衛(wèi)星系統(tǒng)”，但由于該系統(tǒng)存在較大的缺陷，且不能滿足當前實時、動態(tài)、精確的定位需要，所以終止了該系統(tǒng)的研究。</p><p>

21、;　　20世紀60年代末，美國開始著手研制新的衛(wèi)星導航系統(tǒng)，以滿足陸?？杖姾兔裼貌繉Ш降母咭?。1973～1978年，發(fā)射了4顆試驗衛(wèi)星，建立了地面跟蹤網，研制了地面接收機；1979年～1984年又陸續(xù)發(fā)射了7顆BlockⅠ試驗衛(wèi)星，研制了各種用途的接收機，包括導航型和測地型接收機；1985～1993年發(fā)射BlockⅡ和BlockⅡA；直到1994年順利完成了24顆衛(wèi)星的布設，這就是“導航衛(wèi)星授時與測距全球定位系統(tǒng)”（Navigat

22、ion Satellite Timing and Raining/ Global Positioning System,NAVSTAR,GPS）,簡稱全球定位系統(tǒng)（GPS）。</p><p>　　GPS主要由三大部分組成：①空間衛(wèi)星部分：21顆工作衛(wèi)星，3顆備用衛(wèi)星；②地面控制部分：1個主控站，3個注入站，5個監(jiān)測站；③用戶接收機部分：接受GPS衛(wèi)星發(fā)射信號，以獲得必要的導航和定位信息，經數據處理，完成導航和定

23、位工作，GPS接收機硬件一般由主機、天線和電源三部分組成。</p><p>　　全球定位系統(tǒng)不僅集成以前所有的單用途衛(wèi)星系統(tǒng)，并且致力于更廣泛的用途。該系統(tǒng)具有比其他導航系統(tǒng)優(yōu)越的特性：①全能性，能在空中、海洋、陸地等全球范圍內進行導航、授時、定位及測速；②全球性，在全球的任何地點都可以進行定位；③全天候，白天黑夜都可以工作。</p><p>　　實踐證明，GPS對人類活動影響極大，應用價

24、值很高，該工程從根本上解決了人類在地球上的導航問題和定位問題，可以滿足不同用戶的要求。</p><p>　　GPS導航技術應用的發(fā)展趨勢</p><p>　　目前世界上很多國家大力開發(fā)GPS的應用，形成了融合許多領域的GPS產業(yè)。GPS產業(yè)的發(fā)展趨勢呈現(xiàn)以下三方面特點：</p><p>　?、?隨著微電子技術及信號處理技術的進步，新的軟硬件開發(fā)工具的出現(xiàn)，GPS技術

25、水平越來越高。GPS技術從單點定位、相對定位發(fā)展到差分定位、廣域差分定位，從利用測碼偽距定位、載波平滑偽距定位到利用載波相位，從數據后處理到實時在航解算，定位精度越來越高，速度越來越快。并行跟蹤窄相關技術及高速DSP的采納，使得GPS定位實時數據更新率由通常的1s降低至0.1s，而新興的實時相位差分（RTK）技術可使實時定位達到厘米乃至毫米級精度。虛擬差分站（VRS）技術更是增加了定位數據的完整性和可靠性。</p><

26、;p>　?、?GPS技術的應用越來越廣泛，與其他領域的融合也越來越密切。地理信息系統(tǒng)（GIS）利用GPS作為采集數據工具，與先進的無線技術結合應用于交通領域，形成新興的智能交通系統(tǒng)（ITS），大大提高了效率，并在國民經濟建設中發(fā)揮了越來越大的作用。經典的慣性導航技術（INS）與GPS結合，形成新型組合導航系統(tǒng)，以最優(yōu)的價格和性能為陸?？仗峁Ш椒?。GPS通信組網技術的發(fā)展，使GPS成為未來通信必不可少的組成部分，為廣泛流行的位置

27、服務（LBS）提供了極具競爭力的選擇方案。與此同時，GPS與其他導航通信衛(wèi)星之間的聯(lián)合也逐步展開，如與前蘇聯(lián)（現(xiàn)由俄羅斯掌管）的GLONASS衛(wèi)星以及國際海事衛(wèi)星INMARSAT聯(lián)合，組成未來的全球導航系統(tǒng)（GNSS）。如此種種，不勝枚舉?？傊?，GPS技術已發(fā)展成多領域、多模式、多用途、多機型的高新技術國際性產業(yè)，廣泛應用于海陸空在途導航、精密定位、精確授時、衛(wèi)星定規(guī)、武器制導、交通控制、災害監(jiān)測、大地測量、大氣研究等多個領域，正如人們

28、所說，“GPS的應用，禁受人類想象力的約束”。</p><p>　?、?GPS不僅深入跨學科的領域，而且已滲透到人類生活的人文領域。隨著GPS應用的不斷深入，許多工程實際上已經離不開GPS，GPS政策成為世界各國關注的焦點。GPS平行系統(tǒng)的醞釀及出現(xiàn)，促使美國政府對GPS服務的限制逐步取消。隨著美國GPS現(xiàn)代化計劃的實施，GPS國際化的趨勢日趨明顯。GPS將如現(xiàn)在司空見慣的電視、電信系統(tǒng)一樣，成為人們日常生活必不

29、可少的組成部分。</p><p><b>　　研究內容及安排</b></p><p><b>　　研究的內容</b></p><p>　　車載導航系統(tǒng)是集成應用了自動車輛定位技術、地理信息系統(tǒng)技術、數據庫技術、多媒體技術和現(xiàn)代通信技術等的高科技綜合系統(tǒng)；是一個為客戶提供定位、路徑規(guī)劃、路徑引導等多種服務的復雜系統(tǒng)，其中路徑

30、規(guī)劃是幫助司機在行車過程中規(guī)劃行駛路線的過程，是路徑引導、信息服務等模塊的基礎，因此其被廣泛認為是汽車導航系統(tǒng)的基礎問題。路徑規(guī)劃的實現(xiàn)主要依靠所選擇的路徑規(guī)劃算法，因此路徑規(guī)劃算法的研究成為車載導航系統(tǒng)的重中之重。本文的主要內容就是在研究車載導航系統(tǒng)的同時，重點研究其中的路徑規(guī)劃問題，研究路徑規(guī)劃的算法。</p><p><b>　　本文的安排</b></p><p&g

31、t;<b>　　本文共分為五章：</b></p><p>　　第一章是“緒論”，說明了本文的研究背景及意義，簡要介紹了GPS的發(fā)展概況和發(fā)展趨勢，并對論文的研究內容和章節(jié)安排做了介紹。</p><p>　　第二章是“GPS車載導航系統(tǒng)的結構與關鍵技術”，簡述了車載導航系統(tǒng)的發(fā)展，設計的主要思路，以及GPS車載導航系統(tǒng)的總體結構和關鍵技術以及系統(tǒng)結構分析和各模塊的功能。

32、</p><p>　　第三章是“路徑規(guī)劃的分析及設計”，主要研究了電子地圖的數據庫生成和道路的生成，以及路徑規(guī)劃的幾種算法，并舉例設計了幾個簡單的路徑規(guī)劃。</p><p>　　第四章是“路徑規(guī)劃的優(yōu)缺點分析”，本章主要說明了上一章介紹的幾種路徑規(guī)劃的優(yōu)缺點。</p><p>　　第五章是“結論”，對本論文的總結及對本研究今后可能的發(fā)展和創(chuàng)新的展望。</p&g

33、t;<p>　　GPS車載導航系統(tǒng)的結構與關鍵技術</p><p><b>　　車載導航系統(tǒng)的發(fā)展</b></p><p>　　車載導航系統(tǒng)的研究和發(fā)展在人類的文明史上已有相當長的歷史，最古老、最簡單的導航方法是星歷導航，人們通過觀察天空上星星的位置變更來確定自己的位置和前進方向。隨著科學技術的高速發(fā)展，將先進的信息處理技術、數據通信技術、電子控制技術及

34、計算機處理等技術集于一體的智能交通系統(tǒng)的研究是21世紀現(xiàn)代運輸管理體系的模式和發(fā)展方向。衛(wèi)星定位技術（GPS）、地理信息系統(tǒng)（GIS）、遙感技術（RS）、數據庫技術、計算機網絡技術等科技技術的出現(xiàn)，有效地解決了當前城市現(xiàn)代交通管理的諸多問題。</p><p>　　目前，不管是在經濟發(fā)達的歐洲、美國、日本，還是在經濟正在快速發(fā)展的中國和其他國家，車輛導航系統(tǒng)都是各國政府的重要建設項目。美國公路局最早于20世紀60年

35、代末期提出了一種電子路徑引導系統(tǒng)（ERGS），這是一種具有無線路徑引導功能的導航系統(tǒng)，用于控制和疏導交通，但由于資金問題沒有實現(xiàn)。最終終于在80年代中期相繼把先進的導航產品投入市場。日本從1971年開始研究綜合車輛交通控制系統(tǒng)計劃（CACS），從1973～1978年，日本成功的組織了一個叫做動態(tài)路徑誘導的實驗。從20世紀80年代中期到90中期的10年間，相繼完成了路車間通信系統(tǒng)（RACS）、先進的管理交通信息控制系統(tǒng)（AMTICS）、交

36、通信息通信系統(tǒng)（TICS）及智能車輛系統(tǒng)等研究，并推出了各種導航儀器。歐洲也大量的發(fā)行了自己的許多導航產品。我國的車載導航系統(tǒng)的發(fā)展始于20世紀80年代末期，雖然在自主引導型車載導航系統(tǒng)方面還沒有非常成熟，但監(jiān)管控制型的導航產品已經接近成熟并開始使用。目前已有許多科學研究單位和公司從事這方面的開發(fā)應用。</p><p>　　因此，GPS導航系統(tǒng)在交通管理以及運輸方面是非常有前景的，并且能夠帶動與其相關的通信技術、

37、信息技術、控制技術、多媒體技術和計算機應用技術的發(fā)展。</p><p>　　車載導航技術的總體結構和關鍵技術</p><p>　　車載導航系統(tǒng)的總體結構</p><p>　　車載導航系統(tǒng)是由GPS終端、車載計算機、導航軟件、顯示器及GIS軟件等組成的（如圖2.1）。主要包括：①GPS接收機，它接受衛(wèi)星定位信號，確定車輛當前所在的經緯度信息。其主要功能是采集實時的位置

38、信息，進行自身的定位，不斷的更新當前數據，為交通管理提供最新的數據信息。②計算機，結合編程技術及地圖數據，為用戶提供了多媒體信息服務。③GIS電子地圖，把地理數據以圖形的方式顯示出來，提供了多種地圖服務，為用戶提供一個直觀清晰的界面。④車載手機、尋呼機，提供與控制中心的通信手段，接受、發(fā)送各種數據、命令、請求以及服務信息。</p><p>　　圖2.1 車載導航系統(tǒng)的總體結構</p><p&g

39、t;　　車載導航系統(tǒng)的關鍵技術</p><p>　?、?數字地圖：也稱電子地圖，是一個矢量化的地圖，即該地圖中應該包括地圖上的基本對象的屬性數據。它是GPS導航系統(tǒng)和GIS的數據基礎。典型的數字地圖的標準格式有MapInfo的MIF/MID文件，AutoCAD的DXF文件等。</p><p>　　⒉ 地圖匹配：即利用電子地圖中高精度的道路位置信息來修正定位系統(tǒng)給出的車輛位置信息，進一步提高

40、車輛定位精度的技術。一個完整的地圖匹配過程包括三個主要環(huán)節(jié)，即誤差區(qū)域的確定、匹配道路的選擇及定位結果的修正。</p><p>　?、?路徑規(guī)劃：路徑規(guī)劃是車輛導航系統(tǒng)必不可少的核心功能之一，也是實現(xiàn)導航功能的前提條件。車輛導航系統(tǒng)的路徑規(guī)劃是幫助駕駛員在旅行前或旅行中規(guī)劃行駛路徑的過程，它要解決的主要問題是在給定的數字道路地圖中尋找從出發(fā)地到目的地的最優(yōu)路徑，為滿足實際要求，路徑規(guī)劃應具有快速性和最佳性。<

41、;/p><p>　　車載導航系統(tǒng)結構分析及功能要求</p><p>　　車載導航系統(tǒng)共分為6個模塊：</p><p>　?、?定位模塊：采用全球定位系統(tǒng)（GPS）來實現(xiàn)車輛定位。</p><p>　?、?數字地圖數據庫模塊：主要負責存儲數字地圖及信息。它主要包括了支持電子地圖顯示的地圖數據庫及用于路徑引導的道路特征數據庫，是導航和定位的基礎。&l

42、t;/p><p>　?、?地圖匹配模塊：又稱地理編碼，即通過給定的經緯度坐標確定地圖上街道的地址，或者相反的過稱。</p><p>　?、?路徑規(guī)劃模塊：幫助司機在車輛運行過程中，根據地圖數據庫模塊所提供的地圖，按要求的條件快速生成任意兩點之間的最佳駕駛路線。如果有條件利用實時的交通信息，還應對駕駛路線及時調整以適應交通當前的狀況。</p><p>　　⒌ 路徑導航模塊

43、：指揮司機按著路徑規(guī)劃模塊計算出來的路線，并通過定位系統(tǒng)引導車輛行駛。路徑行駛包括兩個任務：一是產生行駛指令，任務是產生一個行駛指令列表使其遵循路徑規(guī)劃跟蹤的路線。二是規(guī)劃跟蹤，任務是緊密監(jiān)視車輛所在的路段位置。這些信息通過人——機接口，并以特殊的指令如視、聽提供給司機。</p><p>　?、?無線通信模塊：可進一步改善系統(tǒng)的性能增加系統(tǒng)的功能，通過一個或多個不同的通信設備，車載系統(tǒng)或交通管理系統(tǒng)能夠接受實時交

44、通信息或報告，去輔助車輛定位和導航，以促進車載系統(tǒng)或整個公共網絡工作的更加安全有效。</p><p><b>　　系統(tǒng)的功能要求</b></p><p>　　車載導航系統(tǒng)的主要功能有：</p><p>　?、?定位功能：利用全球定位系統(tǒng)（GPS）來獲取當前的定位信息并與地圖進行匹配，從而決定車輛當前的所在然后以圖形的方式顯示出來。</p&

45、gt;<p>　?、?最優(yōu)路徑搜索功能：根據用戶在地圖上選取的任意兩地，系統(tǒng)將進行實時計算，按照用戶的需求規(guī)劃從出發(fā)地到目的地的最佳行駛路徑，并以醒目的方式將路徑顯示在電子地圖上。</p><p>　?、?地圖瀏覽功能：地圖瀏覽包括縮放、移動等，用戶可以在一定的放大級上將地圖進行縮小、放大、移動的操作。</p><p>　?、?信息查詢功能：為用戶提供所需的目標查詢，如服務區(qū)

46、、道路、學校、醫(yī)院、賓館、餐館等，用戶可以根據自己的需要在電子地圖上查詢。查詢的資料可以通過文字、圖形的方式在電子地圖上顯示其位置。</p><p>　　車載導航系統(tǒng)是利用全球定位系統(tǒng)、地理信息系統(tǒng)、計算機和先進的通信技術等，將實時的重要信息高效的提供給駕駛員，使其能夠選擇更優(yōu)的路徑駕駛，具有很強的實用價值和非常廣闊的前景。其中的路徑規(guī)劃是導航系統(tǒng)的一項關鍵技術，是導航系統(tǒng)的基礎部分。</p>&l

47、t;p>　　路徑規(guī)劃的分析及設計</p><p>　　導航電子地圖數據庫的設計</p><p>　　導航電子地圖的數據結構與數據模型</p><p>　　1.常用導航電子地圖數據模型與結構</p><p><b>　?。?）空間數據結構</b></p><p>　　空間數據結構包括矢量結構、

48、柵格結構及矢量柵格一體化結構三種。</p><p><b>　?、偈噶拷Y構</b></p><p>　　該結構用空間坐標及其關系描述空間對象，單個空間對象是圖形數據的基本邏輯單位。其優(yōu)點是對圖形數據表達良好、結構緊湊、冗余度低。缺點是數據結構復雜，對軟硬件要求高。根據數據結構中空間對象的組織形式與聯(lián)系程度又分為描述結構、整體多邊形結構、對偶獨立地圖編碼結構及ARC-N

49、ODE結構。</p><p><b>　?、跂鸥窠Y構</b></p><p>　　該結構用點的像素表示空間對象。其優(yōu)點是結構簡單、顯示速度快。缺點是精度較差、網絡拓撲建立困難。根據像素的存貯結構及空間單元不同，具體又分為柵格編碼結構、嵌套結構、不規(guī)則結構等多種形式。</p><p>　?、凼噶繓鸥褚惑w化結構</p><p&g

50、t;　　該結構綜合了兩種結構的優(yōu)點，在許多電子地圖中得到了應用。</p><p>　?。?）屬性數據的數據模型</p><p>　　目前，屬性數據采用的模型有層次模型、網狀模型和關系模型。</p><p><b>　?、賹哟文Ｐ?lt;/b></p><p>　　該模型的基本結構是樹形結構。層次模型數據庫系統(tǒng)是數據庫領域發(fā)展最

51、早的一種，目前已基本不用，但其在數據庫發(fā)展歷史上有著重大的作用和影響，以后的模型均受其影響。</p><p><b>　?、诰W狀模型</b></p><p>　　網狀模型明顯優(yōu)于層次模型，數據顯示和數據操作方法均呈現(xiàn)高效、成熟的特點，但是，網狀模型不足之處在于使用時涉及系統(tǒng)內部因素較多，用戶操作使用不方便，數據模式與系統(tǒng)實現(xiàn)也甚不理想。</p><

52、p><b>　?、坳P系模型</b></p><p>　　關系模型是完全不同于前兩種模型的一種新的模型，前兩種模型一般被稱為格式化模型，而關系模型一般稱為非格式化模型，其基本結構是二維表，簡稱表（table）。二維表由表框架和元組組成，表框架由n個屬性（或稱為列）組成，而存放于框架內的每行數據稱為元組（或稱為行），因此，一張二維表是由一個n元屬性的框架及m個元組組成。關系模型中的操作是建

53、立在二維表上的操作，包括對一張表及多張表間的查詢、刪除、插入及修改等操作。</p><p>　　2.面向對象的整體數據結構</p><p>　　面向對象的整體數據模型是將面向對象（object oriented）思想和面向對象的分析設計方法應用到空間數據模型的設計中，將各種空間實體抽象為某一類具有公共屬性的對象，如點、線、面等對象，每個具體的地理實體是該對象的一個實例，具有自己的屬性，各種

54、對象分層管理，實現(xiàn)空間數據與屬性數據的統(tǒng)一管理。</p><p>　　面向對象的整體數據模型強調的是整體與面向對象的概念。它不僅將地理世界以實體為單位進行組織，而且將客觀世界作為一個整體看待，即每個實體不僅自身具有空間特性和屬性特性的聯(lián)系，更重要的是它與其它實體之間同時還具有邏輯上的語義聯(lián)系，此外，它也具有時間屬性。面向對象的方法為數據模型的建立提供了四種數據抽象技術（分類、概括、聯(lián)合、聚集）和兩種數據抽象工具（

55、繼承和傳播），利用這些技術所構造的數據模型要比傳統(tǒng)的數據模型豐富的多，更適用于定義復雜的地理實體和對復雜對象的直接操作。因此，面向對象的整體數據模型是一種有效的空間數據模型。</p><p>　　面向對象的方法為描述復雜的空間信息提供了一種直觀有效的方法。與傳統(tǒng)的導航電子地圖數據模型相比，面向對象的數據模型具有的優(yōu)點是：結構清晰、組織有序，所有空間實體都以對象的形式封裝；可以定義和處理復雜的空間實體；易于擴充和二

56、次開發(fā)；面向對象的用戶界面更便于用戶操作和使用。</p><p>　　導航電子地圖數據庫的設計原則</p><p>　　在智能車輛導航系統(tǒng)中，導航電子地圖工作于實時、多任務的環(huán)境，圖形的顯示、刷新、信息查詢、拓撲關系等是數據結構設計必須考慮的重要因素。一般設計導航電子地圖數據庫應遵循以下原則：</p><p>　?、賵D形結構簡單。由于導航電子地圖主要包含點、線、面等

57、空間對象，簡單的圖形結構具有數據量少、刷新快、圖形剪裁方便等特點。</p><p>　　②冗余度小。小的地圖數據冗余度將使地圖信息查詢、路徑搜索的速度都得以提高，同時降低數據的儲存空間。</p><p>　?、弁負潢P系簡單。簡單明了的拓撲關系將縮短最優(yōu)路徑規(guī)劃及地圖匹配時間。</p><p>　?、芸臻g信息查詢速度快。好的數據結構將提高空間信息的查詢速度。</

58、p><p>　?、輸祿涌陂_放。電子地圖中的非空間數據具有良好的數據接口，能夠兼容商用的非空間數據庫。</p><p>　　導航電子地圖數據庫的結構設計與實現(xiàn)</p><p>　　導航電子地圖數據庫是整個系統(tǒng)的基石，系統(tǒng)中幾乎所有的模塊都直接或間接的與其相關，其結構設計的好壞將直接影響整個系統(tǒng)的最終性能。綜合考慮各方面因素，采用三層結構模式，以便充分利用面向對象程序設計

59、方法的特性，使各層之間保持低耦合、高內聚的特點，層與層之間以通過的接口方式保持通訊，其層次結構如圖3.1所示。</p><p>　　圖 3.1 導航電子地圖數據庫的層次結構</p><p>　　第一層為接口層，包括空間對象與屬性結構。該層為設計的數據庫進行二次開發(fā)提供了一系列的接口。應用軟件設計人員可以調用該結構訪問數字地圖文件，并對地圖對象和屬性數據進行操作，例如屬性數據的查詢等。&l

60、t;/p><p>　　第二層為核心層，是實現(xiàn)整個數據庫的關鍵部分，涉及到得數據結構和算法在這部分實現(xiàn)。</p><p>　　第三層為讀寫層，完成對二進制文件底層讀寫操作。系統(tǒng)的其他部分不能對數據庫文件直接進行操作。讀寫層抽象了對文件進行操作的特性，封裝了對磁盤鏈的管理和讀寫操作等。</p><p>　　圖3.2給出了導航電子地圖數據庫實現(xiàn)流程，整個過程可以分為文件層、用

61、戶層和接口層三部分。</p><p>　　圖 3.2 導航電子地圖數據庫實現(xiàn)流程</p><p>　　導航電子地圖中道路網絡的拓撲生成方法</p><p>　　導航電子地圖中道路網絡的模型與儲存</p><p>　　1.導航電子地圖中道路網絡的數據模型</p><p>　　道路網絡的數據模型，是指導航電子地圖道路網絡

62、用來組織其數據所采用的模型，它是生成具有拓撲結構道路網絡的基礎。目前，有關道路網絡的數據模型用的較多有基于路段連接和基于Arc-Node（弧-節(jié)點法）等若干種。本文采用Arc-Node結構，其主要特點是，容易表達實際路網的拓撲關系，且形式簡潔。</p><p>　　Arc-Node模型的基本原理是，將顯示中的真實道路用一系列折線段來模擬和近似，即在一定精度的允許范圍內，采用以直代曲的思想，用分段連續(xù)的小段直線段所

63、組成的折線段來代替和逼近真實的道路曲線，將其中小段的直線段稱作Arc，Arc的端點稱為Node,這樣，整個道路網絡將由Arc和Node組成，其形式化定義為</p><p>　　Rw = (N,R)</p><p>　　N = {x|x∈Ns}</p><p><b>　　R = {NR}</b></p><p>　　NR

64、 = {＜x,y＞|L(x,y)...(x,y∈N)}</p><p>　　式中：Rw ——道路網絡；</p><p>　　Ns ——道路網絡的節(jié)點集；</p><p>　　NR——道路網絡中任意兩節(jié)點間拓撲關系的集合；</p><p>　?。紉,y＞——節(jié)點x和y之間存在的一條??；</p><p>　　L(x,y)

65、——節(jié)點x和y之間的權值，節(jié)點和節(jié)點之間連接的權值可以用節(jié)點之間的集合長度或者其他費用來表示。</p><p>　　根據實際交通網絡的特點，我們作如下分析假設：</p><p>　　①所有的編制都是直線。對于彎曲弧度較大的路段，可以通過在該路段上</p><p>　　插入一系列節(jié)點使該路段由一些弧度較小的路段構成，弧度較小的路段可以認</p><

66、p>　　為是一條邊。如圖3.3，節(jié)點1、2之間路段的弧度較大，在路段上加入節(jié)點2，把原來的路段分成兩個弧度相對較小的路段。</p><p>　?、谶呁ǔＪ请p向可通的，邊的權值為正值。</p><p>　?、劬W絡中有較多的節(jié)點和邊。</p><p>　?、芎凸?jié)點相關聯(lián)的邊數為常數，且遠小于網絡中總的節(jié)點數。</p><p>　　2.導航電

67、子地圖中道路網絡的計算機存儲</p><p>　　計算機存儲的是矢量化的道路網絡，網絡的存儲結構是影響路徑規(guī)劃算法搜索速度和事件復雜度的一個重要因素。一個簡單直觀的存儲方法是對道路網絡圖中的每一個節(jié)點進行編號，采用鄰接表的鏈式存儲結構。在鄰接表中，對圖的每個節(jié)點建立一個單鏈表，每個單鏈表都由表節(jié)點和表頭節(jié)點構成。第i個單鏈表的w個表節(jié)點分別對應著和圖中第i個節(jié)點相關聯(lián)的w條邊。鏈表的表頭節(jié)點以順序結構形式存儲，以

68、便隨機訪問圖中任一節(jié)點的單鏈表。因此，采用鄰接表的鏈式存儲結構，很容易找到和圖中任一節(jié)點相關聯(lián)的邊。單鏈表的表頭節(jié)點和表節(jié)點的結構如圖3.4所示，圖中，Name：節(jié)點編號；Position：節(jié)點位置坐標；First：指向鏈表中的第一個表節(jié)點；Next：指向鏈表中的下一個表節(jié)點；Weight：邊的權值。</p><p>　　折線道路網絡的拓撲生成法</p><p>　　1.折線道路網絡的組成

69、特點</p><p>　　折線道路網絡組成的最大特點是，每一條道路都是由帶有寬度值的折線段（簡稱道路中心線）表示。有時，為了數據獲取方便，也可能以近似的道路中心線來表示。各種來源提供的實際數據使得折線道路網絡中可能存在以下情況：</p><p>　?、倬€段間的虛交特性，即兩條實際相交的路段，在給定的道路網絡數據中卻不存在與交點對應的節(jié)點。如圖3.5（a）所示，路段AB與路段CD實際應相交于

70、節(jié)點O，而節(jié)點O并未出現(xiàn)在路段AB與路段CD的給定數據中。</p><p>　?、诰€段間的虛段特性，即兩條實際相交的路段，因其中一條路段偏短導致沒能相交。如圖3.5（b）所示，路段AB與路段CD實際應相交于節(jié)點B，而節(jié)點B并未出現(xiàn)在路段CD的給定數據中，將節(jié)點B稱為虛斷點。</p><p>　　③線段間的過交特性，即兩條相交的路段，因其中一條路段偏長而導致過短的毛刺路段出現(xiàn)。如圖3.5（c

71、）所示，路段AB與路段CD相交于節(jié)點O，過短路段BO應該不存在，然而，節(jié)點B卻出現(xiàn)在路段AB給定數據中，將節(jié)點B稱為過交點。</p><p>　?、芄?jié)點的冗余特性，一種情況是，實際應該是同一節(jié)點的點卻存在多個相鄰的節(jié)點。如圖3.5（d）所示，節(jié)點A、B、C、D實際表示的地圖中的同一點，換言之，此時應該只用一個節(jié)點來表示地圖中的該點，然而，給定的道路網絡數據中卻存在節(jié)點A、B、C、D；另一種情況是，本來可以由兩個節(jié)

72、點表示的路段，給定的道路網絡數據中卻存在其他節(jié)點，如圖3.5（e）所示，路段AB只需節(jié)點A和B便能在精度允許范圍內準確表示，而實際數據中卻包括節(jié)點C和D。</p><p>　　2.折線道路網絡拓撲生成算法原理</p><p>　　算法的原理可以簡單的描述為：依據折線道路網絡的組成特點及Arc-Node數據模型，由給定的折線道路網絡數據生成表示其拓撲結構的Arc-Node數據結構。具體生成過

73、稱分為兩步：</p><p>　　第一步是完善給定的折線道路網絡數據，即對前面介紹的道路網絡的幾種特性進行相應的處理。具體的處理方法是：虛交時，將實際應該有的交點分別插入兩條路段中，從而兩條路段分裂成四條路段，如圖3.5（a）中，應將節(jié)點O分別插入路段AB和路段CD中，從而使路段AB與路段CD分裂成路段AO、OB、CO和OD；虛斷時，應以偏短路段延長線與另一路段的交點代替偏短路段中靠近該交點節(jié)點，如圖3.4（b）

74、中，應將路段AB的節(jié)點B用路段AB的延長線與路段CD之交點來代替；過交時，應該刪除過短路段，如圖3.5（c）中，應將路段OB刪除，即將節(jié)點B從路段AB中刪除；節(jié)點冗余時，如果是第一種情況，應以冗余節(jié)點的中心點代替這些冗余點；如果是第二種情況，則應將所有的冗余節(jié)點刪除，如圖3.5（d）中，應將A、B、C、D用它們的中心點來代替，該中心點的縱橫坐標分別為這些冗余節(jié)點縱橫坐標的均值，如圖3.5（e）中，應將路段AB中的節(jié)點C和D刪除而只保留節(jié)

75、點A和B。</p><p>　　第二步是在第一步的基礎上，由完善以后的折線道路網絡數據生成表示其拓撲結構的Arc-Node數據結構，Arc-Node數據結構采用鄰接表結構。</p><p>　　路徑規(guī)劃的分析及設計</p><p>　　路徑規(guī)劃是現(xiàn)代智能車輛導航的一項關鍵技術，是基于具有拓撲結構的道路網絡，在車輛行駛前或行駛過程中尋找出發(fā)點到目標點最優(yōu)行車路線的過稱

76、。本節(jié)充分挖掘實際道路網絡具有的各種特性，分別利用道路網絡空間分布特性和道路等級特性，設計了兩種針對道路網絡的啟發(fā)式搜索策略，即方向搜索策略和分層搜索策略；利用所構造的搜索策略設計了三種不同的啟發(fā)式搜索策略。</p><p><b>　　路徑規(guī)劃的基礎算法</b></p><p>　　Dijkstra算法是設計各種路徑規(guī)劃的基礎。本節(jié)簡要的介紹Dijkstra算法的原

77、理及特點，并給出它的兩種具體實現(xiàn)方法，即鄰接矩陣法和鄰接節(jié)點法，作為后續(xù)幾個路徑規(guī)劃算法的基礎算法。</p><p><b>　　1.算法原理</b></p><p>　　給定帶權有向圖G=(V,E),其中V是包含n個節(jié)點的節(jié)點集，E是包含m條弧的弧集，〈v,w〉是E中從v至w的弧，c〈v,w〉是弧〈v,w〉的非負權值，設a,b是V中的節(jié)點，Pab={v0=a,v1,

78、…,vn=b}是V中由a到b的一條路徑，則路徑Pab的權值總和TC(Pab)表示為：</p><p>　　TC(Pab)=∑c(vi,vi+1) (i=1,2,…,n-1) （3-1）</p><p>　　所謂最短路徑問題是指，在帶權的有向圖中尋找從指定起點到終點的一條權值總和最小路徑。如果把權值看成弧的長度（即距離），則目標路徑就是起點到終點的距離最短的路徑。<

79、;/p><p>　　為說明求解給定兩點間最短路徑的算法，我們先來討論單源點的路徑問題，即給定帶權的有向圖G=(V,E)和原點v，求從v到G中其余各節(jié)點的最短路徑。為了求解這一問題，Dijkstra提出了一種按路徑長度遞增次序來產生最短路徑的Dijkstra算法，其原理如下：</p><p>　　首先，引進一個輔助向量D，它的每個分量D(i)表示當前所找到的從起始點v到每個重點vi的最短路徑的長

80、度。D的初始狀態(tài)為：若從v到vi有弧，則D(i)為弧上的權值；否則令D(i)為∞。顯然，長度為D(i)=Min{ D(i)|vi∈V}的路徑就是從v出發(fā)的長度最短的一條路徑，記為(v,vi)。假設S為已求得最短路徑的終點的集合，則下一條最短路徑（設其終點為x）或者是弧〈v,x〉，或者是中間只經過S中的節(jié)點而最后到達節(jié)點x的路徑。這可用反證法來證明：假設此路徑上有一個節(jié)點不在S中，則說明存在一條終點不在S而長度比路徑更短的路徑。事實上這是

81、不可能的。因為我們是按路徑長度遞增的次序來產生各條最短路徑的，故長度比此路徑短的所有路徑均已產生，它們的終點必定是在S中，即假設不成立。因此，在一般情況下，下一條長度次短的最短路徑的長度必須是</p><p>　　D(j)=Min{ D(i)|vi∈V-S} (3-2)</p><p>　　其中，D(i)或者是弧〈v,vi〉上的權值，或者是D(k

82、)(vk∈S)和弧〈vk,vi〉上的權值之和。</p><p>　　從以上對Dijkstra算法原理分析可以看出，其最大特點是在最短路徑的求解過程中搜索算法具有很大的盲目性，隨時準備向其四面八方展開，最終的搜索區(qū)域基本上是以起始點為原點，以起始點與目標點的連線長度為半徑的一個圓。</p><p><b>　　2.算法實現(xiàn)</b></p><p>

83、;<b>　?。?）鄰接矩陣法</b></p><p>　　根據上面對算法原理的分析，可以得到如下描述的單源點最短路徑算法：</p><p>　　步驟一，假設用帶權的鄰接矩陣cost來表示帶權有向圖，cost(i,j)表示弧〈vi,vj〉上的權值，其中，1≤i≤n,1≤j≤n。若〈vi,vj〉不存在，則置cost(i,j)為∞。S的初狀態(tài)為空集。從v出發(fā)到圖上其余各節(jié)

84、點（終點）vi可能達到的最短路徑長度D(i)的初始值為</p><p>　　D(i)=cost(v,vi) vi∈V (3-3)</p><p>　　步驟二，選擇vj，使得</p><p>　　D(j)=Min{ D(i)|vi∈V-S} (3-4)</p><p>　　

85、vj就是當前求得的從v出發(fā)的最短路徑的終點，令</p><p>　　S=S∪{vj} (3-5)</p><p>　　步驟三，修改從v出發(fā)到集合V-S上任一節(jié)點vk可達的最短路徑長度，如果</p><p>　　D(j)+cost(j,k)＜D(k) (3-6)</p><

86、;p><b>　　則修改D(k)為</b></p><p>　　D(k)= D(j)+cost(j,k) (3-7)</p><p>　　步驟四，重復操作步驟二、步驟三共n-1次，由此求得按路徑長度遞增次序排列的從v出發(fā)到圖上其余各節(jié)點的最短路徑。</p><p>　　以上算法求解的是從源點出發(fā)到其余各

87、節(jié)點的最短路徑。但是車輛導航系統(tǒng)的路徑規(guī)劃只需要求解出從源點到指定終點的一條最短路徑，并且要記下并在地圖上顯示該路徑，因此要對以上算法做適當的修改。設指定終點為t,在步驟二中，如果發(fā)現(xiàn)vj=t，則算法終止，D(t)的值就是從源點v到終點t的最短路徑的距離。為了能記下路徑，設置一個路徑向量P，其中P(i)表示從源點到達i節(jié)點的最短路徑上該點的前趨節(jié)點。算法結束前，可根據P找到從源點到終點t的最短路徑上每個節(jié)點的前趨節(jié)點，從而得到從源點到終

88、點t的最短路徑。</p><p>　　由于采用鄰接矩陣法在解算最短路徑時，搜索算法假設道路網絡中的任意一個節(jié)點都和其他所有節(jié)點相鄰接，因此導致其時間復雜度為O(n²),其中n為道路網絡的節(jié)點總數。</p><p><b>　?。?）鄰接節(jié)點法</b></p><p>　　鄰接矩陣法的不足是鄰接矩陣cost中存在大量的無效的0元素和∞元

89、素，這不僅占用大量的存儲空間，而且也使得基于矩陣運算的Dijkstra算法效率大為降低。為了彌補鄰接矩陣法的這種不足，下面給出Dijkstra算法的另一種實現(xiàn)算法——鄰接節(jié)點法。</p><p>　　鄰接節(jié)點法的基本思想是：先求出道路網絡中各節(jié)點直接相鄰節(jié)點的最大個數（簡稱為最大鄰接點數，用變量MaxNum表示），然后以MaxNum作為矩陣的列數，以道路網絡中的節(jié)點總數n作為矩陣的行數，構造鄰接節(jié)點矩陣J來描述道

90、路網絡中節(jié)點間的鄰接關系。J的行按節(jié)點號從小到大順序排列，與節(jié)點i鄰接的節(jié)點號卸載矩陣的第i行，如果節(jié)點i的鄰接節(jié)點個數小于MaxNum，則以0填充第i行直到填滿。構造與J結構相同的初始判斷矩陣DJ，同時將J中個元素鄰接關系對應的邊的權值填在同一位置上（∞對應0元素）。即J(i,j)表示第j個與節(jié)點i鄰接的節(jié)點編號，相應的，DJ(i,j)表示節(jié)點i與其鄰接節(jié)點J(i,j)連線的權值，其中，1≤i≤n,1≤j≤MaxNum。這樣，鄰接節(jié)點

91、法便用維數相對較低的矩陣J和DJ取代了鄰接矩陣法中維數較高的矩陣cost，從而有效地改善了算法的存儲效率和運算效率。</p><p>　　為了能夠應用鄰接節(jié)點法解算任意指定兩點間的最短路徑，程序首先需要完成以下3項預處理工作，以便得到初始化矩陣J和DJ：</p><p>　　①裝載道路網絡數據，獲得道路網絡中的節(jié)點和邊的內部序號。需要說明的是，道路網絡節(jié)點和邊的內部序號與實際編號可以不相同

92、。為了增加算法的靈活性，算法使用內部編號參數運算（這里假設內部序號和實際編號相同）。</p><p>　?、谟嬎愕缆肪W絡的最大鄰接節(jié)點數MaxNum。</p><p>　?、蹣嬙爨徑庸?jié)點矩陣J，各行中的節(jié)點序號可以前后隨意放置。對應鄰接節(jié)點矩陣J的各元素，構造初始判斷矩陣DJ。</p><p>　　有了鄰接節(jié)點矩陣J和初始判斷矩陣DJ以后，就可以對網絡中任意給定兩點

93、進行最短路徑規(guī)劃。下面給出鄰接節(jié)點法的具體實現(xiàn)步驟：</p><p>　　輸入：道路網絡的鄰接節(jié)點矩陣J和初始判斷矩陣DJ，以及路徑規(guī)劃的起點S和終點D。</p><p>　　輸出：起點S到終點D的一條最短路徑MinWay及相應的最短距離MinDist。</p><p>　　步驟一，初始化標記向量Mark，Mark(i)=—1，其中，i=1,2，…，MaxNum。&

94、lt;/p><p>　　步驟二，根據起始點S，標記初始判斷矩陣DJ的第s行，Mark(s)=0，記最短距離 MinDist=0。</p><p>　　步驟三，根據終點D，判斷DJ的第d行是否已經標記，是則轉步驟五；否則繼續(xù)。</p><p>　　步驟四，在DJ已標記的行中，求所有元素的最小值dmin，若dmin=∞，說明不存在最短路徑，程序退出；否則MinDist=dm

95、in，記錄最小值元素所在的行di、列dj。然后再J中取(di,dj)元素，記為w，若第w行尚未標記，則將DJ的第w行標記，Mark(w)=di；并在J的第w行尋找值為di的元素，記錄該元素的行ri、列rj。將DJ剛獲得標記的行中各元素值均加上MinDist，并使DJ的(di,dj)和(ri,rj)元素為∞。然后轉步驟三。</p><p>　　步驟五，從終點D開始，由標記向量Mark的分量尋前點，知道起始點S，查得

96、最短路徑MinWay，MinDist即為相應的最短路徑距離。</p><p>　　與鄰接矩陣法相比，鄰接節(jié)點法不僅將道路網絡的存儲空間降低到原來的MaxNum/n，而且也將搜索算法的時間復雜度降低到O(MaxNum·n)，由于MaxNum＜＜n，因此采用鄰接節(jié)點法時算法的時間復雜度實質上是O(n)。</p><p>　　為方便起見，我們將不加任何啟發(fā)式搜索策略的經典Dijkstr

97、a算法簡稱為算法RP0。</p><p>　　限制搜索區(qū)域的路徑規(guī)劃算法</p><p>　　針對Dijkstra算法搜索過程中無方向性的缺點，本節(jié)利用道路網絡特有的空間分布特性夠早了一種方向搜索策略，并給出利用該搜索策略合理限制算法搜索區(qū)域的具體方法，從而降低了算法搜索空間，提高了算法搜索效率。</p><p><b>　　1.算法原理</b>

98、;</p><p>　?。?）道路網絡特有的空間分布特性</p><p>　　與普通的平面網絡圖相比，描述實際城市道路網絡的拓撲圖通常具有以下特點：</p><p>　?、俣酁榇笠?guī)模的稀疏網絡，點多邊少（網絡的節(jié)點通常成千上萬，甚至更多，而每個節(jié)點相連的路段一般不超過5，多為2、3或4）。</p><p>　?、诰W絡結構相對比較規(guī)則，即網中的

99、節(jié)點分布比較均與（特別是經過規(guī)劃的現(xiàn)代大都市）。</p><p>　?、劬W絡通常是（或近似是）完全連通圖，即網絡中的任意兩點都可以相互到達。</p><p>　?、芫W絡中有表示供智能車輛掉頭的換向節(jié)點，而且一般距當前路口500m左右。</p><p>　　（2）方向搜索策略的構造與應用</p><p>　　受幾何學中“兩點之間直線距離最短”的

100、啟發(fā)，在對實際城市道路網絡中的給定兩點進行最短路徑規(guī)劃時，起點到終點的連線方向基本上代表了最短路徑的大致走向。在進行最短路徑搜索時，我們可以利用該啟發(fā)式信息來構造方向啟發(fā)式搜索方法，合理縮小算法的空間，提高算法的搜索效率。</p><p>　　2.限制搜索區(qū)域的確定方法</p><p>　　利用方向搜索策略合理限制算法的搜索區(qū)域是設計本算法的關鍵。</p><p>

101、　　我們將此算法簡稱3-1算法，如圖3.6所示在給定相同的路徑規(guī)劃起始點S和目標點D時，為搜索到從S到D的最短路徑，算法RP0所需的搜索區(qū)域理論上是一個以S為圓心，以D為半徑的圓；而算法3-1所需搜索區(qū)域則是如下一個區(qū)域：先以S和D的連線為對角線形成一個矩形R1（當S與D的連線水平或垂直時，R1退化為一條線段），然后將R1的各邊想外擴展一個閾值T2，形成一個更大的矩形R2，最后通過R2被與線段SD平行、距SD距離為閾值T1的左右（或上下

102、）兩條直線L1和L2切割形成搜索區(qū)域。</p><p>　　圖3.6 限制搜索區(qū)域的確定方法</p><p><b>　　3.算法實現(xiàn)</b></p><p>　　算法3-1的實現(xiàn)步驟如下：</p><p>　　輸入：采用鄰接節(jié)點數據結構存儲的矢量化城市道路網絡，路徑規(guī)劃的起點S，終點D，閾值T1和T2。</p&

103、gt;<p>　　輸出：節(jié)點S和節(jié)點D之間的一條距離最短路徑。</p><p>　　步驟一，初始化，完成道路網絡數據加載及程序運行環(huán)境設置等。</p><p>　　步驟二，根據閾值T1和T2構造限制搜索區(qū)域。</p><p>　　步驟三，在限制搜索區(qū)域內，根據給定的起點S和目標點D，調用算法RP0的實現(xiàn)程序進行最短路徑計算。</p>&l

104、t;p>　　步驟四，輸出S和D之間的一條距離最短路徑。</p><p>　　以上四步的關鍵是合理設定閾值T1和T2，構造合適的限制搜索區(qū)域。設計中主要依據是前面提到的換向距離500m和矢量化道路網絡中邊的平均長度，本算法中閾值T1和T2分別設為500m和1500m。</p><p>　　基于分層道路網絡的分層路徑規(guī)劃算法</p><p>　　前面介紹的限制搜索

105、區(qū)域的最短路徑規(guī)劃算法，有效地降低了算法的搜索空間，提高了算法的搜索效率。然而，桐多數路徑規(guī)劃算法一樣，限制搜索區(qū)域的路徑規(guī)劃算法所解算出的最短路徑，仍然只是數學意義上的最短路徑，而非意義上的最優(yōu)路徑。所謂行車意義上的最優(yōu)路徑是指多數駕駛員所期望的行車路徑。</p><p>　　事實上，最短路徑無論距離最短還是時間最短，都不一定是行車意義上的最短路徑。因為除了形式距離或形式時間外，最優(yōu)路徑的選擇還需要考慮很多無法

106、預期或定量化的因素。本節(jié)利用實際城市道路網絡中路段的不同等級特性，構造了不同于方向搜索策略的另一種啟發(fā)式搜索策略，即分層搜索策略，給出了利用該搜索策略設計分層道路網絡和基于分層道路網絡設計分層路徑規(guī)劃算法的具體方法。</p><p><b>　　1.算法原理</b></p><p>　　分層路徑規(guī)劃算法（簡稱算法3-2）的基本思想是：根據道路網絡中路段的不同等級特性，

107、將整個道路網絡分為不同的層次，每一層包含道路網絡不同級別的細節(jié)。高層道路網絡是其相鄰低層道路網絡的抽象和濃縮，低層則是其相鄰高層道路網絡的具體擴展。換言之，任一高層道路網絡內的路段和節(jié)點都包含于其相鄰的低層道路網絡內，而任意一個低層道路網絡除了包含其相鄰高層道路網絡內的路段和節(jié)點外，還包含更多的其他路段和節(jié)點。這樣，在進行路徑規(guī)劃是，我們便可以先在高層空間進行搜索，然后在搜索高層空間獲得的結果基礎上再添上低層空間的細節(jié)，得到問題的最終解

108、。</p><p>　　2.分層道路網絡設計</p><p>　?。?）城市道路網絡中路段的分等級特性</p><p>　　多數城市道路網絡存在的一個事實是其中的路段具有不同等級特性。這些不同的道路等級一般又都對應著不同的行車環(huán)境，如道路的行車時速限制、道路上紅綠燈的設置間距、道路的寬度及路面質量等多種與行車密切相關的因素。</p><p>

109、　　（2）道路網絡的分層方法</p><p>　　將分層思想引入到道路網絡的設計中，即根據道路網路中路段的不同等級特性，將整個道路網絡RN分為不同的層。</p><p>　　（3）分層道路網絡的表示</p><p>　　分層道路網絡的表示是指分層道路網絡如何在計算機中表示和存儲，它是算法3-2的基礎。設計中，首先采用Arc-Node模型將整個道路網絡表示為：G=(N

110、,A,B)，這里N={N1，N2，…,Nn}是道路網絡中節(jié)點的集合，A={aij|1≤i≤n,1≤j≤MaxNum，其中MaxNum是RN的最大鄰接節(jié)點數}是RN中各節(jié)點間鄰接關系的集合，aij表示第j個與節(jié)點i鄰接的節(jié)點，而且認為兩節(jié)點間的邊是雙向的，B={bij|1≤i≤n,1≤j≤MaxNum ，其中MaxNum 是RN的最大鄰接節(jié)點數}是RN中各鄰接節(jié)點間連接邊的權值合集，bij表示節(jié)點i與節(jié)點aij之間的邊的權值，而且認為兩節(jié)