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

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