汽車導航路徑規劃算法研究

王 運

（安徽江淮汽車集團股份有限公司，安徽 合肥 230601）

汽車導航路徑規劃算法研究

王 運

（安徽江淮汽車集團股份有限公司，安徽 合肥 230601）

文章系統分析了汽車導航路徑規劃算法迪杰斯特拉和A*算法的基本原理和各自的優劣勢，另分析了路徑規劃軟件架構及導航數據格式模型，并結合汽車導航實際使用情況，闡述了導航路徑規劃實施的過程及策略，最終根據距離、時間、費用等權值評估模型等到用戶常用的距離最短、時間最短、節油經濟的可選擇路線。

導航；路徑規劃；迪杰斯特拉；數據格式模型；權值評估模型

1 路徑規劃算法原理

1.1 迪杰斯特拉算法

路徑尋路算法最典型的就是迪杰斯特拉算法，這也是目前應用最廣泛的算法。迪杰斯特拉算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。這是一種以廣度優先的窮舉算法。

該算法是是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法能得出最短路徑的最優解，但由于它遍歷計算的節點很多，所以效率低，如圖1所示。

圖1

1.2 A＊算法

A*算法是另一種應用比較廣泛的尋路算法，該算法是一種估值算法，當探索到一定程度，根據已有數據分析得出最優路，而不需要窮舉。

所以該算法比迪杰斯特拉算法效率高很多，不足就是可能得到的不是最優解，如圖2所示。

圖2

1.3 綜合算法

考慮到車載導航硬件及系統性能的問題，目前導航軟件中基本都是采用兩種算法相結合的方式，既保證了規劃的性能，又從一定程度上保障了路線質量，即分別從出發地和目的地開始，有方向性的向相對方向呈橢圓形探索，當兩個方向都探索到同一條道路時，該道路就不繼續探索，直到探索出的同一條道路滿足一定條件時，探索完全停止。如圖3所示。

圖3

當然也有一些其他算法被利用，但基本都是解決特定問題引入的，例如遺傳算法等。

2 路徑規劃算法軟件架構

RD：該部分主要是處理外部下發的算路請求，將出發地、目的地、路線偏好等設置轉換成算路引擎內部可用的格式，并發送到算路引擎。

接受請求和結果處理：該部分主要是管理RD下發的算路請求和路線規劃引擎計算的結果，負責整個路線引擎的輸入和輸出。

內部參數轉化：該部分主要是對輸入的參數進一步細化，為接下來的最近路搜素算法做準備。

收集開始 link：根據路線計算時的出發地和道路的匹配的狀態、出發地速度、走行的道路種別、前方的交差點有無等，通過出發地位置來決定道路data或者路線data上的開始點。

連接層判定：因為數據分層的緣故，路徑規劃算法也會從經歷一個從低層到高層的升層的過程，最終會根據遠近，在某一層路網中進行連接探索，該模塊主要就是確定連接層。

探索：按照迪杰斯特拉算法算法、A*算法等原理進行路徑探索。

路線編輯：主要是將探索最終確定的最優路按照既定的輸出格式進行編輯。

3 導航數據格式模型

首先導航數據是分層存儲的，如圖4所示，地圖界面隨著比例尺升高，顯示的內容是不一樣的，比例尺越高看到的范圍越廣，但看到的數據屬性/種類會變少，包括道路、背景、名稱、POI等，都是一樣的效果，這不是軟件過濾的結果，是地圖數據為了達到這樣的效果，做的分層存儲的結果。

圖4

其次導航數據在分層數據的基礎上對數據進行分塊存儲，便于數據的讀取和管理。直觀點說，一版地圖數據中道路、背景、名稱會存儲在一起，大概有2G左右，即使在電腦上，也不可能把這么大的數據一次性讀取上來。如圖5所示：

圖5

4 路線規劃實施及策略

上面講述了最基本的算法原理、軟件架構和導航數據格式模型，接下來說明下導航中的路線規劃是如何利用算法規劃路線的。

導航規劃引擎做是事遠遠不止算法描述的那么簡單，整個的流程如下：規劃引擎從 HMI側獲取到了起點和目的地/途徑地信息，但這只是一個點信息，需要從地圖中匹配到相應的道路，因為數據是分塊存儲的，根據坐標可以很容易定位到相關的塊數據，接下來只需要讀取相應的數據，并找到最近的道路即可。

一般出發地或目的地都是投影到路的中間，這時需要進行shape點的形狀探索，主要就是考慮出發地和目的地距離很近的情況，利用的算法就是迪杰斯特拉算法。當出發地和目的地離的不近的情況下，輸出的就是和投影點連接的完整的道路，接下來就是道路間的探索了。考慮到導航數據是分層存儲的，還要考慮的一件事就是探索升層和確定連接層。其中升層探索為了保證探索結果的準確性，使用的算法也是迪杰斯特拉算法。最后當升到判定的連接層探索后就開啟連接判定算路模式，該步驟使用的算法是迪杰斯特拉算法和A*算法相結合的算法。

另外整個過程中，所有探索都會用到權值評估模型，最終得到最短路徑是指的權值最小路徑。一般導航中會提供幾種條件的路線，例如距離最短的權值就是評估的距離；經濟路線評估的權值是是否收費路，而對于非收費路一般是屬性越高/道路越寬，權值越小。車載導航根據不同條件對應路徑規劃的功能有以下幾種：（1）單路線規劃：根據規劃條件，如高速道路優先、距離優先等，從出發地規劃出一條到目的地的最優路。（2）多路線規劃：從出發地規劃出多條不同條件的道路到目的地。目前支持四條，分別對應推薦、高速、經濟、距離四種條件。（3）繞行規劃：從出發地開始，在規劃時盡量不使用一定距離內的上次規劃出來的道路。（4）偏航規劃：在車真實行走時，行走路線偏離了已規劃出來的路線時，按照真實走行的路線規劃出新的道路。（5）自動繞行規劃：在車真實走行的時候，如果按照已規劃出來的路線行駛，會進入路況有問題(比如正在修路、擁堵)的道路，此時會自動繞行規劃。

Research on Vehicle Navigation Path Planning Algorithm

Wang Yun
( Anhui Jianghuai Automobile Co., Ltd., Anhui Hefei 230601 )

This paper systematically analyzes the basic principles and the advantages and disadvantages of the vehicle navigation path planning algorithm Dijkstra and A*algorithm, The paper also analyzes the path planning software architecture and navigation data format model, Combining with the actual usage of car navigation, The process and strategy of navigation path planning are expounded, Finally, the evaluation model of distance, time, cost and so on is used to select the route which is the shortest, the shortest time and economical economy.

Navigation; Path planning; Dijkstra; Data format model; weight assessment model

U463.6

A

1671-7988 (2017)21-202-03

10.16638/j.cnki.1671-7988.2017.21.069

CLC NO.: U463.6

A

1671-7988 (2017)21-202-03

王運，就職于安徽江淮汽車股份有限公司。