汽車導(dǎo)航路徑規(guī)劃算法研究

王 運

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

汽車導(dǎo)航路徑規(guī)劃算法研究

王 運

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

文章系統(tǒng)分析了汽車導(dǎo)航路徑規(guī)劃算法迪杰斯特拉和A*算法的基本原理和各自的優(yōu)劣勢，另分析了路徑規(guī)劃軟件架構(gòu)及導(dǎo)航數(shù)據(jù)格式模型，并結(jié)合汽車導(dǎo)航實際使用情況，闡述了導(dǎo)航路徑規(guī)劃實施的過程及策略，最終根據(jù)距離、時間、費用等權(quán)值評估模型等到用戶常用的距離最短、時間最短、節(jié)油經(jīng)濟的可選擇路線。

導(dǎo)航；路徑規(guī)劃；迪杰斯特拉；數(shù)據(jù)格式模型；權(quán)值評估模型

1 路徑規(guī)劃算法原理

1.1 迪杰斯特拉算法

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

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

圖1

1.2 A＊算法

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

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

圖2

1.3 綜合算法

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

圖3

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

2 路徑規(guī)劃算法軟件架構(gòu)

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

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

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

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

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

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

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

3 導(dǎo)航數(shù)據(jù)格式模型

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

圖4

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

圖5

4 路線規(guī)劃實施及策略

上面講述了最基本的算法原理、軟件架構(gòu)和導(dǎo)航數(shù)據(jù)格式模型，接下來說明下導(dǎo)航中的路線規(guī)劃是如何利用算法規(guī)劃路線的。

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

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

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

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

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