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

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

2、統(tǒng)的發(fā)展歷史和國(guó)內(nèi)外研究現(xiàn)狀，以及GPS車載導(dǎo)航系統(tǒng)的組成、功能、實(shí)現(xiàn)過(guò)程、路徑規(guī)劃算法以及地理信息系統(tǒng)的功能。并以MaoInfo為工具，在路徑規(guī)劃系統(tǒng)中實(shí)現(xiàn)了地圖的基本操作。本文重點(diǎn)研究了車載導(dǎo)航系統(tǒng)的路徑規(guī)劃問(wèn)題。綜合考慮并比較了多種最短路徑的選擇算法,并對(duì)其優(yōu)缺點(diǎn)進(jìn)行了分析。</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ā)展趨勢(shì)2</p><p>　　1.2研究?jī)?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è)計(jì)9</p><p>　　3.1導(dǎo)航電子地圖數(shù)據(jù)庫(kù)的設(shè)計(jì)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ù)庫(kù)的設(shè)計(jì)原則10</p><p>　　3.1.3導(dǎo)航電子

12、地圖數(shù)據(jù)庫(kù)的結(jié)構(gòu)設(shè)計(jì)與實(shí)現(xiàn)11</p><p>　　3.2導(dǎo)航電子地圖中道路網(wǎng)絡(luò)的拓?fù)渖煞椒?2</p><p>　　3.2.1導(dǎo)航電子地圖中道路網(wǎng)絡(luò)的模型與儲(chǔ)存13</p><p>　　3.2.2折線道路網(wǎng)絡(luò)的拓?fù)渖煞?4</p><p>　　3.3路徑規(guī)劃的分析及設(shè)計(jì)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)缺點(diǎn)分析25</p><p>

14、　　4.1算法的實(shí)驗(yàn)結(jié)果25</p><p>　　4.2算法實(shí)驗(yàn)結(jié)果的比對(duì)及優(yōu)缺點(diǎn)分析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>　　參考文獻(xiàn)33</b></p><p><b>　　緒論</b></p><p><b>　　研究背景與意義</b></p><p>　　交通事業(yè)的發(fā)展與我國(guó)社會(huì)主義現(xiàn)代化建設(shè)有著密不可分的關(guān)系，并且對(duì)人們的日常生活有

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

32、</p><p>　　第三章是“路徑規(guī)劃的分析及設(shè)計(jì)”，主要研究了電子地圖的數(shù)據(jù)庫(kù)生成和道路的生成，以及路徑規(guī)劃的幾種算法，并舉例設(shè)計(jì)了幾個(gè)簡(jiǎn)單的路徑規(guī)劃。</p><p>　　第四章是“路徑規(guī)劃的優(yōu)缺點(diǎn)分析”，本章主要說(shuō)明了上一章介紹的幾種路徑規(guī)劃的優(yōu)缺點(diǎn)。</p><p>　　第五章是“結(jié)論”，對(duì)本論文的總結(jié)及對(duì)本研究今后可能的發(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āng)長(zhǎng)的歷史，最古老、最簡(jiǎn)單的導(dǎo)航方法是星歷導(dǎo)航，人們通過(guò)觀察天空上星星的位置變更來(lái)確定自己的位置和前進(jìn)方向。隨著科學(xué)技術(shù)的高速發(fā)展，將先進(jìn)的信息處理技術(shù)、數(shù)據(jù)通信技術(shù)、電子控制技術(shù)及

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

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

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

37、信息技術(shù)、控制技術(shù)、多媒體技術(shù)和計(jì)算機(jī)應(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終端、車載計(jì)算機(jī)、導(dǎo)航軟件、顯示器及GIS軟件等組成的（如圖2.1）。主要包括：①GPS接收機(jī)，它接受衛(wèi)星定位信號(hào)，確定車輛當(dāng)前所在的經(jīng)緯度信息。其主要功能是采集實(shí)時(shí)的位置

38、信息，進(jìn)行自身的定位，不斷的更新當(dāng)前數(shù)據(jù)，為交通管理提供最新的數(shù)據(jù)信息。②計(jì)算機(jī)，結(jié)合編程技術(shù)及地圖數(shù)據(jù)，為用戶提供了多媒體信息服務(wù)。③GIS電子地圖，把地理數(shù)據(jù)以圖形的方式顯示出來(lái)，提供了多種地圖服務(wù)，為用戶提供一個(gè)直觀清晰的界面。④車載手機(jī)、尋呼機(jī)，提供與控制中心的通信手段，接受、發(fā)送各種數(shù)據(jù)、命令、請(qǐng)求以及服務(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ù)字地圖：也稱電子地圖，是一個(gè)矢量化的地圖，即該地圖中應(yīng)該包括地圖上的基本對(duì)象的屬性數(shù)據(jù)。它是GPS導(dǎo)航系統(tǒng)和GIS的數(shù)據(jù)基礎(chǔ)。典型的數(shù)字地圖的標(biāo)準(zhǔn)格式有MapInfo的MIF/MID文件，AutoCAD的DXF文件等。</p><p>　?、?地圖匹配：即利用電子地圖中高精度的道路位置信息來(lái)修正定位系統(tǒng)給出的車輛位置信息，進(jìn)一步提高

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

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

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

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

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

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

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

47、t;p>　　路徑規(guī)劃的分析及設(shè)計(jì)</p><p>　　導(dǎo)航電子地圖數(shù)據(jù)庫(kù)的設(shè)計(jì)</p><p>　　導(dǎo)航電子地圖的數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)模型</p><p>　　1.常用導(dǎo)航電子地圖數(shù)據(jù)模型與結(jié)構(gòu)</p><p><b>　　（1）空間數(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)用空間坐標(biāo)及其關(guān)系描述空間對(duì)象，單個(gè)空間對(duì)象是圖形數(shù)據(jù)的基本邏輯單位。其優(yōu)點(diǎn)是對(duì)圖形數(shù)據(jù)表達(dá)良好、結(jié)構(gòu)緊湊、冗余度低。缺點(diǎn)是數(shù)據(jù)結(jié)構(gòu)復(fù)雜，對(duì)軟硬件要求高。根據(jù)數(shù)據(jù)結(jié)構(gòu)中空間對(duì)象的組織形式與聯(lián)系程度又分為描述結(jié)構(gòu)、整體多邊形結(jié)構(gòu)、對(duì)偶獨(dú)立地圖編碼結(jié)構(gòu)及ARC-N

49、ODE結(jié)構(gòu)。</p><p><b>　?、跂鸥窠Y(jié)構(gòu)</b></p><p>　　該結(jié)構(gòu)用點(diǎn)的像素表示空間對(duì)象。其優(yōu)點(diǎn)是結(jié)構(gòu)簡(jiǎn)單、顯示速度快。缺點(diǎn)是精度較差、網(wǎng)絡(luò)拓?fù)浣⒗щy。根據(jù)像素的存貯結(jié)構(gòu)及空間單元不同，具體又分為柵格編碼結(jié)構(gòu)、嵌套結(jié)構(gòu)、不規(guī)則結(jié)構(gòu)等多種形式。</p><p>　　③矢量柵格一體化結(jié)構(gòu)</p><p&g

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

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

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

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

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

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

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

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

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

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

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

61、戶層和接口層三部分。</p><p>　　圖 3.2 導(dǎo)航電子地圖數(shù)據(jù)庫(kù)實(shí)現(xiàn)流程</p><p>　　導(dǎo)航電子地圖中道路網(wǎng)絡(luò)的拓?fù)渖煞椒?lt;/p><p>　　導(dǎo)航電子地圖中道路網(wǎng)絡(luò)的模型與儲(chǔ)存</p><p>　　1.導(dǎo)航電子地圖中道路網(wǎng)絡(luò)的數(shù)據(jù)模型</p><p>　　道路網(wǎng)絡(luò)的數(shù)據(jù)模型，是指導(dǎo)航電子地圖道路網(wǎng)絡(luò)

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

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

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

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

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

68、便隨機(jī)訪問(wèn)圖中任一節(jié)點(diǎn)的單鏈表。因此，采用鄰接表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，很容易找到和圖中任一節(jié)點(diǎn)相關(guān)聯(lián)的邊。單鏈表的表頭節(jié)點(diǎn)和表節(jié)點(diǎn)的結(jié)構(gòu)如圖3.4所示，圖中，Name：節(jié)點(diǎn)編號(hào)；Position：節(jié)點(diǎn)位置坐標(biāo)；First：指向鏈表中的第一個(gè)表節(jié)點(diǎn)；Next：指向鏈表中的下一個(gè)表節(jié)點(diǎn)；Weight：邊的權(quán)值。</p><p>　　折線道路網(wǎng)絡(luò)的拓?fù)渖煞?lt;/p><p>　　1.折線道路網(wǎng)絡(luò)的組成

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

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

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

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

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

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

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

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

77、理及特點(diǎn)，并給出它的兩種具體實(shí)現(xiàn)方法，即鄰接矩陣法和鄰接節(jié)點(diǎn)法，作為后續(xù)幾個(gè)路徑規(guī)劃算法的基礎(chǔ)算法。</p><p><b>　　1.算法原理</b></p><p>　　給定帶權(quán)有向圖G=(V,E),其中V是包含n個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)集，E是包含m條弧的弧集，〈v,w〉是E中從v至w的弧，c〈v,w〉是弧〈v,w〉的非負(fù)權(quán)值，設(shè)a,b是V中的節(jié)點(diǎn)，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>　　所謂最短路徑問(wèn)題是指，在帶權(quán)的有向圖中尋找從指定起點(diǎn)到終點(diǎn)的一條權(quán)值總和最小路徑。如果把權(quán)值看成弧的長(zhǎng)度（即距離），則目標(biāo)路徑就是起點(diǎn)到終點(diǎn)的距離最短的路徑。<

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

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

81、不可能的。因?yàn)槲覀兪前绰窂介L(zhǎng)度遞增的次序來(lái)產(chǎn)生各條最短路徑的，故長(zhǎng)度比此路徑短的所有路徑均已產(chǎn)生，它們的終點(diǎn)必定是在S中，即假設(shè)不成立。因此，在一般情況下，下一條長(zhǎng)度次短的最短路徑的長(zhǎng)度必須是</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>　　從以上對(duì)Dijkstra算法原理分析可以看出，其最大特點(diǎn)是在最短路徑的求解過(guò)程中搜索算法具有很大的盲目性，隨時(shí)準(zhǔn)備向其四面八方展開(kāi)，最終的搜索區(qū)域基本上是以起始點(diǎn)為原點(diǎn)，以起始點(diǎn)與目標(biāo)點(diǎn)的連線長(zhǎng)度為半徑的一個(gè)圓。</p><p><b>　　2.算法實(shí)現(xiàn)</b></p><p>

83、;<b>　?。?）鄰接矩陣法</b></p><p>　　根據(jù)上面對(duì)算法原理的分析，可以得到如下描述的單源點(diǎn)最短路徑算法：</p><p>　　步驟一，假設(shè)用帶權(quán)的鄰接矩陣cost來(lái)表示帶權(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、點(diǎn)（終點(diǎn)）vi可能達(dá)到的最短路徑長(zhǎng)度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就是當(dāng)前求得的從v出發(fā)的最短路徑的終點(diǎn)，令</p><p>　　S=S∪{vj} (3-5)</p><p>　　步驟三，修改從v出發(fā)到集合V-S上任一節(jié)點(diǎn)vk可達(dá)的最短路徑長(zhǎng)度，如果</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次，由此求得按路徑長(zhǎng)度遞增次序排列的從v出發(fā)到圖上其余各節(jié)點(diǎn)的最短路徑。</p><p>　　以上算法求解的是從源點(diǎn)出發(fā)到其余各

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

104、t;p>　　步驟四，輸出S和D之間的一條距離最短路徑。</p><p>　　以上四步的關(guān)鍵是合理設(shè)定閾值T1和T2，構(gòu)造合適的限制搜索區(qū)域。設(shè)計(jì)中主要依據(jù)是前面提到的換向距離500m和矢量化道路網(wǎng)絡(luò)中邊的平均長(zhǎng)度，本算法中閾值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>　　事實(shí)上，最短路徑無(wú)論距離最短還是時(shí)間最短，都不一定是行車意義上的最短路徑。因?yàn)槌诵问骄嚯x或形式時(shí)間外，最優(yōu)路徑的選擇還需要考慮很多無(wú)法

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

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

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

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

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