汽车导航路径规划算法研究

王 运

（安徽江淮汽车集团股份有限公司，安徽 合肥 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

王运，就职于安徽江淮汽车股份有限公司。