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

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

9、統(tǒng)的發(fā)展歷程2</p><p>　　1.1.2GPS導(dǎo)航技術(shù)應(yīng)用的發(fā)展趨勢2</p><p>　　1.2研究內(nèi)容及安排3</p><p>　　1.2.1研究的內(nèi)容3</p><p>　　1.2.2本文的安排4</p><p>　　第二章GPS車載導(dǎo)航系統(tǒng)的結(jié)構(gòu)與關(guān)鍵技術(shù)5</p>&

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

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

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

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

14、　　4.1算法的實驗結(jié)果25</p><p>　　4.2算法實驗結(jié)果的比對及優(yōu)缺點分析26</p><p><b>　　第五章結(jié)論29</b></p><p>　　5.1論文小結(jié)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)代化建設(shè)有著密不可分的關(guān)系，并且對人們的日常生活有

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

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

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

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

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

21、;　　20世紀60年代末，美國開始著手研制新的衛(wèi)星導(dǎo)航系統(tǒng)，以滿足陸?？杖姾兔裼貌繉?dǎo)航的高要求。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)”（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ā)射信號，以獲得必要的導(dǎo)航和定位信息，經(jīng)數(shù)據(jù)處理，完成導(dǎo)航和定

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

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

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

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

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

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

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

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

31、t;<b>　　本文共分為五章：</b></p><p>　　第一章是“緒論”，說明了本文的研究背景及意義，簡要介紹了GPS的發(fā)展概況和發(fā)展趨勢，并對論文的研究內(nèi)容和章節(jié)安排做了介紹。</p><p>　　第二章是“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)分析和各模塊的功能。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

53、立在二維表上的操作，包括對一張表及多張表間的查詢、刪除、插入及修改等操作。</p><p>　　2.面向?qū)ο蟮恼w數(shù)據(jù)結(jié)構(gòu)</p><p>　　面向?qū)ο蟮恼w數(shù)據(jù)模型是將面向?qū)ο螅╫bject oriented）思想和面向?qū)ο蟮姆治鲈O(shè)計方法應(yīng)用到空間數(shù)據(jù)模型的設(shè)計中，將各種空間實體抽象為某一類具有公共屬性的對象，如點、線、面等對象，每個具體的地理實體是該對象的一個實例，具有自己的屬性，各種

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

55、繼承和傳播），利用這些技術(shù)所構(gòu)造的數(shù)據(jù)模型要比傳統(tǒng)的數(shù)據(jù)模型豐富的多，更適用于定義復(fù)雜的地理實體和對復(fù)雜對象的直接操作。因此，面向?qū)ο蟮恼w數(shù)據(jù)模型是一種有效的空間數(shù)據(jù)模型。</p><p>　　面向?qū)ο蟮姆椒槊枋鰪?fù)雜的空間信息提供了一種直觀有效的方法。與傳統(tǒng)的導(dǎo)航電子地圖數(shù)據(jù)模型相比，面向?qū)ο蟮臄?shù)據(jù)模型具有的優(yōu)點是：結(jié)構(gòu)清晰、組織有序，所有空間實體都以對象的形式封裝；可以定義和處理復(fù)雜的空間實體；易于擴充和二

56、次開發(fā)；面向?qū)ο蟮挠脩艚缑娓阌谟脩舨僮骱褪褂谩?lt;/p><p>　　導(dǎo)航電子地圖數(shù)據(jù)庫的設(shè)計原則</p><p>　　在智能車輛導(dǎo)航系統(tǒng)中，導(dǎo)航電子地圖工作于實時、多任務(wù)的環(huán)境，圖形的顯示、刷新、信息查詢、拓撲關(guān)系等是數(shù)據(jù)結(jié)構(gòu)設(shè)計必須考慮的重要因素。一般設(shè)計導(dǎo)航電子地圖數(shù)據(jù)庫應(yīng)遵循以下原則：</p><p>　　①圖形結(jié)構(gòu)簡單。由于導(dǎo)航電子地圖主要包含點、線、面等

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

58、p><p>　?、輸?shù)據(jù)接口開放。電子地圖中的非空間數(shù)據(jù)具有良好的數(shù)據(jù)接口，能夠兼容商用的非空間數(shù)據(jù)庫。</p><p>　　導(dǎo)航電子地圖數(shù)據(jù)庫的結(jié)構(gòu)設(shè)計與實現(xiàn)</p><p>　　導(dǎo)航電子地圖數(shù)據(jù)庫是整個系統(tǒng)的基石，系統(tǒng)中幾乎所有的模塊都直接或間接的與其相關(guān)，其結(jié)構(gòu)設(shè)計的好壞將直接影響整個系統(tǒng)的最終性能。綜合考慮各方面因素，采用三層結(jié)構(gòu)模式，以便充分利用面向?qū)ο蟪绦蛟O(shè)計

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

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

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

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

63、組成的折線段來代替和逼近真實的道路曲線，將其中小段的直線段稱作Arc，Arc的端點稱為Node,這樣，整個道路網(wǎng)絡(luò)將由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 ——道路網(wǎng)絡(luò)；</p><p>　　Ns ——道路網(wǎng)絡(luò)的節(jié)點集；</p><p>　　NR——道路網(wǎng)絡(luò)中任意兩節(jié)點間拓撲關(guān)系的集合；</p><p>　　＜x,y＞——節(jié)點x和y之間存在的一條?。?lt;/p><p>　　L(x,y)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

83、;<b>　?。?）鄰接矩陣法</b></p><p>　　根據(jù)上面對算法原理的分析，可以得到如下描述的單源點最短路徑算法：</p><p>　　步驟一，假設(shè)用帶權(quán)的鄰接矩陣cost來表示帶權(quán)有向圖，cost(i,j)表示弧〈vi,vj〉上的權(quán)值，其中，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>　　步驟四，重復(fù)操作步驟二、步驟三共n-1次，由此求得按路徑長度遞增次序排列的從v出發(fā)到圖上其余各節(jié)點的最短路徑。</p><p>　　以上算法求解的是從源點出發(fā)到其余各

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

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

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

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

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

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

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

94、lt;/p><p>　　步驟二，根據(jù)起始點S，標記初始判斷矩陣DJ的第s行，Mark(s)=0，記最短距離 MinDist=0。</p><p>　　步驟三，根據(jù)終點D，判斷DJ的第d行是否已經(jīng)標記，是則轉(zhuǎn)步驟五；否則繼續(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)元素為∞。然后轉(zhuǎn)步驟三。</p><p>　　步驟五，從終點D開始，由標記向量Mark的分量尋前點，知道起始點S，查得

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

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

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

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

100、啟發(fā)，在對實際城市道路網(wǎng)絡(luò)中的給定兩點進行最短路徑規(guī)劃時，起點到終點的連線方向基本上代表了最短路徑的大致走向。在進行最短路徑搜索時，我們可以利用該啟發(fā)式信息來構(gòu)造方向啟發(fā)式搜索方法，合理縮小算法的空間，提高算法的搜索效率。</p><p>　　2.限制搜索區(qū)域的確定方法</p><p>　　利用方向搜索策略合理限制算法的搜索區(qū)域是設(shè)計本算法的關(guān)鍵。</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é)點數(shù)據(jù)結(jié)構(gòu)存儲的矢量化城市道路網(wǎng)絡(luò)，路徑規(guī)劃的起點S，終點D，閾值T1和T2。</p&

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

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

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

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

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

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

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

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