王 運(yùn)

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

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

王 運(yùn)

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

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

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

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

1.1 迪杰斯特拉算法

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

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

圖1

1.2 A＊算法

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

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

圖2

1.3 綜合算法

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

圖3

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

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

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

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

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

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

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

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

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

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

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

圖4

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

圖5

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

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

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

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

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

王運(yùn)，就職于安徽江淮汽車股份有限公司。