路徑規(guī)劃模塊和路徑引導(dǎo)模塊

電子地圖分析與導(dǎo)航路徑規(guī)劃模塊和路徑引導(dǎo)模塊《電子地圖分析與導(dǎo)航》課程組目錄CONTENTS路徑規(guī)劃模塊路徑引導(dǎo)模塊0102路徑規(guī)劃模塊01路徑規(guī)劃是在一個(gè)特定的道路網(wǎng)絡(luò)中為用戶規(guī)劃其目標(biāo)路徑。通常采用的技術(shù)是找到最小旅行代價(jià)路線，“最小”可泛指經(jīng)濟(jì)上的最省、時(shí)間上的最快、路程上的最短或是其他意義上的最優(yōu)，其核心問(wèn)題是最短路徑選取，實(shí)現(xiàn)其功能的關(guān)鍵取決于最短路徑算法。Dijkstra算法是目前系統(tǒng)解決最短路徑問(wèn)題所常用的方法，對(duì)于不同系統(tǒng)的Dijkstra算法采用了不同的實(shí)現(xiàn)方法。01路徑規(guī)劃模塊路徑規(guī)劃模塊的基本功能是：當(dāng)用戶在電子地圖上拾取起點(diǎn)和終點(diǎn)兩個(gè)方位后，系統(tǒng)采用實(shí)時(shí)計(jì)算——實(shí)時(shí)調(diào)用的模式，在較短的響應(yīng)時(shí)間內(nèi)從系統(tǒng)的數(shù)據(jù)庫(kù)中搜索出絕對(duì)最短路徑，并以閃爍形式顯示在電子地圖上。鑒于實(shí)際應(yīng)用要求，系統(tǒng)在基于Dijkstra算法中，綜合考慮時(shí)間一空間兩要素，采取幾點(diǎn)措施以達(dá)到快速搜索的目的。01路徑規(guī)劃模塊(1)采用基于矩形區(qū)域的遞增法確定搜索范圍。系統(tǒng)分別將用戶輸入的起點(diǎn)和終點(diǎn)為頂點(diǎn)擴(kuò)大一定的范圍，并在已擴(kuò)大的矩形區(qū)域內(nèi)搜索最短路徑，若不能得出一條最短路徑，則將范圍遞增性地再擴(kuò)大后繼續(xù)搜索，直至能得到一條最短路徑為止。采用這種劃分矩形區(qū)域和范圍遞增的方式進(jìn)行路徑搜索，可以過(guò)濾掉部分與當(dāng)前所要搜索的最短路徑無(wú)關(guān)的節(jié)點(diǎn)。而在判斷某點(diǎn)是否在區(qū)域范圍內(nèi)只需判斷兩個(gè)數(shù)的大小，減少了算法的規(guī)模和算法的復(fù)雜性，節(jié)省了計(jì)算時(shí)間。01路徑規(guī)劃模塊(2)采用動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。設(shè)計(jì)一個(gè)動(dòng)態(tài)記錄數(shù)組，用于存儲(chǔ)節(jié)點(diǎn)信息?？梢苑奖愕膶?shí)現(xiàn)集合的增加和刪除操作，在一定程度上減少了算法的循環(huán)次數(shù)。(3)采用動(dòng)態(tài)的在線計(jì)算策略。由于系統(tǒng)將移植用于PDA車載導(dǎo)航系統(tǒng)，而PDA的內(nèi)存容量很有限，有效解決時(shí)空問(wèn)題尤為關(guān)鍵。01路徑規(guī)劃模塊路徑引導(dǎo)模塊02路徑引導(dǎo)是幫助用戶沿預(yù)定路線行駛從而順利到達(dá)目的地的過(guò)程，它根據(jù)地圖數(shù)據(jù)庫(kù)中的道路信息和由定位模塊從地圖匹配模塊提供的當(dāng)前移動(dòng)目標(biāo)位置產(chǎn)生適當(dāng)?shù)膶?shí)時(shí)操作指令。02路徑引導(dǎo)模塊路徑引導(dǎo)模塊利用路徑規(guī)劃模塊和定位子系統(tǒng)引導(dǎo)車輛行駛。除地圖數(shù)據(jù)庫(kù)模塊外，定位子系統(tǒng)可以僅包括定位模塊，或者包括定位模塊和地圖匹配模塊。一旦由路徑規(guī)劃模塊計(jì)算出特定的路徑且定位子系統(tǒng)已經(jīng)確定了車輛的位置，路徑引導(dǎo)模塊與這些子系統(tǒng)協(xié)同工作以向用戶提供適當(dāng)?shù)囊龑?dǎo)。引導(dǎo)信息的表達(dá)借助于人機(jī)接口模塊。02路徑引導(dǎo)模塊引導(dǎo)模塊與其他模塊相互作用的簡(jiǎn)化功能框圖如圖所示。02路徑引導(dǎo)模塊隨著車輛行駛，實(shí)時(shí)路徑導(dǎo)航要求車輛的位置作為時(shí)間的函數(shù)不斷地與路徑規(guī)劃模塊產(chǎn)生的最佳路徑相比較。根據(jù)車輛當(dāng)前的位置、走向及行駛的道路信息，實(shí)時(shí)路徑引導(dǎo)系統(tǒng)不斷地更新這些信息。當(dāng)轉(zhuǎn)彎或者行駛指令到達(dá)時(shí)，路徑引導(dǎo)系統(tǒng)的可視信號(hào)、