基于车载导航系统的路径规划方法研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于车载导航系统的路径规划方法研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要： 机动车数量日益增多为交通、环境、能源等带来了巨大的压力，为此提出一种改进的路径规划算法――胶囊形限制搜索区域路径规划算法。该方法在很大程度上减少了传统路径规划方法的搜索范围，并且通过设置动态搜索参数保证了最短路径规划的成功率。以拓扑结构路网数据为实验载体，对椭圆限制区域算法及改进算法进行了深入的对比和研究，并通过实验验证了改进算法的高效性和稳定性。最后，给出了中心监控式车载导航系统的初步设计方案，其由监控中心子系统、车载子系统和通信子系统三部分组成。

关键词： 车载导航系统； 电子地图； 拓扑结构； 路径规划； 限制搜索区域

中图分类号： TN96?34； TM417 文献标识码： A 文章编号： 1004?373X（2016）13?0133?04

Abstract： The increasing quantity of motor vehicles brings huge pressure for traffic， environment， energy， etc. An improved path planning algorithm is proposed， which is called capsule?like restricted searching area path planning algorithm. This method can greatly reduce the searching range of traditional path planning methods， and ensure the success rate of shortest path planning by means of setting the dynamic searching parameter. The ellipse restricted area algorithm and improved algorithm are deeply compared and studied by taking the road network data of the topology structure as the experimental platform. The high efficiency and stability of the improved algorthm were verified by experiment. The preliminary design scheme of the vehicle?mounted navigation system with center mo?nitoring is given， which is composed of monitoring center subsystem， vehicle?mounted subsystem and communication subsystem.

Keywords： vehicle?mounted navigation system； electronic map； topology structure； path planning； restricted searching area

仅仅通过道路基础设施建设来解决交通问题，已经不能满足快速增长的机动车数量对交通的需求，而智能交通系统的出现大大改善了交通状况，合理利用现有道路资源，就可以大幅度提高路网的使用率和使用质量，从而达到减少交通堵塞现象的目的。车载导航系统，作为ITS的关键组成部分之一，不仅能够为用户准确地提供一条前往目标地点的合理道路，还使得单个车体与城市交通系统网络有机融合，从而能够顺利避开堵塞的道路，使得外出效率大为提高。

1 车载导航系统电子地图的实现

1.1 电子地图中道路网络数据模型

道路网络的数据模型是生成具有拓扑结构道路网络的基础。车载导航电子地图是由点、线和面三个基本元素组成。整个道路网络的表示一般采用Arc?Node模型，该模型的特点是易于表达实际路网的拓扑关系，且形式简洁。考虑到实际电子地图的面是由弧段组成，故可以将路网归结为节点和弧段两个基本元素的组合。Arc?Node模型的基本原理是在一定的精度范围之内，采用以直代曲的思想，由连续的小段直线代替和逼近真实的道路曲线，这样就形成了Arc?Node数据模型，其形式化定义为：

式中：为路网；为路网的节点集；为路网的有向路段集；和为路段的起点和终点；为路段的属性集，可表示为距离、时间和花费等。

同时，根据实际交通网络的特点，做如下的分析假设：所有的边都是线段，对于弯曲弧度数较大的路段，可通过在该路段上插入一系列节点使该路段由一些弧度较小的路段构成，把弧度较小的路段假设为一条线段。如图1所示，节点1和2之间的路径弧度较大，在原路径上插入节点3和4，将原路段分割成弧度相对较小的三个路段。边长通常是双向可通的，边的权值为正值。

网络中有较多的节点和边，与节点相关联的边数为常数，且远小于网络中总的节点数。

1.2 导航电子地图中折线网络拓扑化算法实现

算法实现的原理可以简单的描述为：依据折线道路网络的组成特点及Arc?Node数据模型，由给定的折线道路网络生成表示其拓扑结构的Arc?Node数据模型。生成过程基本可以分成两个步骤：第一步是完善给定的折线道路网络数据，即对1.1节中介绍的道路网络的几个情况进行相应的处理；第二步是在第一步的基础上，由完善后的折线数据网络数据生成表示其拓扑结构的Arc?Node数据结构。整个算法流程如图2所示。

2 车载导航系统路径规划搜索算法

2.1 椭圆限制搜索区域路径规划算法

椭圆限制区域的最短路径算法思想如下：以起始点和终点为焦点，以为长轴长画一个椭圆，然后在椭圆区域内的站点间寻找最短路径。其中，为起始点到终点的欧式距离，是一个与城市路网信息有关的统计参数。所以，椭圆限制区域的最短路径算法是依赖于城市的统计参数的，统计数据表明对于北京路网的值为1.417。构造椭圆限制区域的方法如下：

（1） 建立直角坐标系：轴为轴为与其垂直的方向。

（2） 以起始点为圆心，的连线为半径，作圆该圆内的区域就是传统最短路径规划算法Dijkstra算法的搜索区域。

（3） 以起始点终点为焦点，作椭圆椭圆内的区域就是椭圆限制搜索区域路径规划算法的搜索区域。其中椭圆的长半轴与椭圆相交于点和点形成的椭圆阴影区域就是算法的搜索范围。

椭圆限制搜索区域路径规划算法的实现步骤比较简单，具体如下：输入起始点终点完成道路的网络数据加载及程序运行环境设置等；根据起始点构造椭圆限制搜索的区域；在构造的限制搜索区域内，调用Dijkstra算法进行最短路径计算；输出起始点和终点之间的最短路径。

2.2 改进的限制搜索区域路径规划算法

胶囊形限制搜索区域路径规划算法的原理与椭圆限制搜索区域路径规划算法类似，搜索起始点到终点的最短路径时，只需要考虑中间胶囊形阴影部分的路段和节点，该胶囊形限制搜索区域路径规划算法的搜索范围比Dijkstra搜索算法和椭圆限制搜索区域算法都大大缩小；并且以线段作为上下边界的限制，在一定程度上减少了判定节点是否落在限制区域内时椭圆算法需要进行的大量乘积和开方运算，从而提高了整个搜索过程的效率。具体的搜索区域设置方法如下：

（1） 轴为轴为与其垂直的方向，以起始点为原点建立一个直角坐标系；

（2） 以起始点为圆心，的连线为半径，作圆该圆内的区域就是传统最短路径规划算法Dijkstra算法的搜索区域；

（3） 以起始点终点为焦点，作椭圆椭圆内的区域就是椭圆限制搜索区域路径规划算法的搜索区域。其中椭圆的长半轴与椭圆相交于点和点

（4） 分别以起始点终点为圆心，线段AS（DK）为半径作两个半圆EAF和VKG，连接点和点形成了如图3所示的阴影的胶囊形限制区域，该区域即为改进算法的路径规划搜索范围。

由上面提到的道路路网统计参数可知，椭圆限制搜索区域路径规划算法搜索的成功建立在95%的置信水平之上，也就是还有5%的可能性，实际最短路径上的节点落在限制区域之外，这就可能导致搜索的失败，胶囊形限制搜索区域路径规划跟椭圆限制搜索区域路径规划存在同样可能导致搜索失败的情况，因此就必须通过调节半圆的参数半径扩大搜索范围，保证搜索成功，提高算法的可靠性。修正后的算法步骤如下：

第1步：输入搜索起始点和终点完成拓扑化路网数据加载及程序运行环境设置等；

第2步：根据起始点构造初始胶囊形限制区域算法的搜索区域，阈值半径为

第3步：在构造完成的胶囊形限制区域中调用Dijkstra算法，进行最短路径规划，若搜索成功则转步骤5，否则继续；

第4步：设置动态变化参数以起始点终点为圆心，以上一次搜索的阈值半径加上为半圆半径构造新的胶囊形限制搜索区域，如图4中虚线包围区域所示，构造完成后转第3步；

第5步：输出搜索得出的最短路径，算法结束。

3 中心监控式车载导航系统初步设计

3.1 中心监控式车载导航系统构成

中心监控式车载导航系统除具有导航功能外，通过借助通信网络，还能够采集信息、分析信息，路径规划在中心根据实时交通情况完成。实际应用时，通常需要根据车载终端的具体需要进行配置，通常至少应包含监控中心子系统、车载子系统和通信子系统三部分。

监控中心子系统：系统接收车载子系统发送的车辆速度、位置、报警等信息，然后在导航电子地图拓扑路网基础上对车辆状态进行实时显示、并且进行车载子系统的路径查询、数据分析处理要求。处理完成之后，并对系统和车载子系统进行参数设置及控制。

车载子系统：车载子系统负责与监控中心子系统通信，把车辆位置信息、报警状态发送给监控中心子系统，同时接收监控中心子系统的反馈指令对车辆进行相关控制。车载子系统结构组成如图5所示。

通信子系统：中心监控式车载导航系统的关键部分之一。选择正确的通信方式，连接车载子系统和监控中心子系统十分重要。首先必须考虑到通信系统网覆盖范围，其次还必须考虑车辆行驶过程中可能遭遇的恶劣环境影响。

3.2 中心监控式车载导航工作原理

车载GPS接收机接收定位卫星发来的定位数据，并且根据4颗不同卫星发来的星历数据计算出自身所处地理位置的坐标，该坐标数据通过符合GSM标准的无线模块，采用SMS形式，由车载终端将车辆的位置状态、报警器输入信息发送至GSM网，GSM网将接收到的车辆定位信息通过互联网或者通信接发设备送至中心控制子系统，以便监控中心及时掌握车辆的动态位置信息，进一步控制车载终端。其中的定位信息传输功能实现所需软件为通信服务器软件，主要完成车辆和监控中心之间的数据传输与通信，实现数据收发、编码、解码、数据入库等工作。监控中心则完成车辆位置信息的可视化、车辆行驶的最优路径规划及各种控制指令的发送等功能。基于GPS和GSM短消息业务的中心监控式车载导航系统的工作示意图如图6所示。

3.3 中心监控式车载导航软件实现

中心监控式车载导航系统的软件设计具有良好的人机交互界面和数据处理能力。首先构建一个客户端/服务器结构，数据库安装在控制中心子系统上，数据库管理采用结构化查询语言，客户端采用Windows操作系统，应用程序采用VC 2010进行开发。中心监控式导航监控中心软件设计通常要考虑5个功能模块组成：

地图显示模块：为达到对车辆监控的目的，能够显示车辆轨迹、车速等；

信息点管理模块：信息点被分类存储后，在管理用户界面中体现，用户可以对信息点数据库进行管理，如删除、添加或修改等；

数据显示模块：解码信息显示于终端；

指令下载模块：将路径导航指令实时下载到车载终端；

系统隐私保护模块：车辆管理数据库，存有车辆的电子编号用于计算机检索和处理，保证车辆信息的安全。

4 实验验证及结果分析

为了验证提出的胶囊形限制搜索区域路径规划算法的有效性和可靠性，使用125 000比例尺下MapInfo格式的北京2011年交通图作为电子地图数据源（该地图道路网络共有97 773个地理特征数量），在WIN 7平台Microsoft Visual Studio 2010编程环境下对椭圆限制搜索区域以及胶囊形限制搜索区域最短路径规划算法的性能进行测试。为了简洁，这里用SF1表示椭圆限制搜索区域路径规划算法；SF2表示胶囊形限制搜索区域路径规划算法。

为了保证两种算法的可靠性，反复给定不同的搜索起点和终点，对比各种算法的搜索时间和规划路径长度等实验数据。考虑到论文篇幅的限制，这里仅给出起点编号为797，终点编号为2 195情况下的算法的实际路径规划结果图。图7表示算法SF1路径规划结果，图8表示算法SF2路径规划结果。

两种算法的性能对比如表1所示。表中ST表示测试给定的起点，DT表示测试的目标终点；分别表示算法SF1，SF2在相同情况下所用的搜索时间（单位：s）。分别表示算法SF1，SF2在相同情况下所规划出的最短路径长度（单位：m）。

由表1可以看出，在相同的起点和终点下，在搜索的高效性方面，启发式搜索算法SF2明显比传统算法SF1优越很多，提出的改进路径规划方法比算法SF1的搜索效率有20%左右的提升；改进算法SF2，通过设置动态参数避免了此种情况的发生，很好的保证了搜索的可靠性。综上所述，可见本文提出的改进路径规划算法在搜索效率和搜索可靠性方面都具有相当的优越性。

5 结 论

本文在拓扑化路网数据基础上，提出了一种改进的路径规划算法――胶囊形限制搜索区域路径规划算法。该方法在很大程度上减少了传统路径规划方法的搜索范围，再通过设置动态搜索参数保证了路径规划的成功率。并且以拓扑结构路网数据为实验载体，对椭圆限制区域算法及提出的改进算法进行了深入的对比和研究，通过实验验证了改进算法的高效性和稳定性。最后，给出了中心监控式车载导航系统的初步设计方案。

参考文献

[1] 屈展.车载导航系统中路径规划问题的研究[D].兰州：兰州理工大学，2012：253?257.

[2] 高星.浅论车载导航系统的现状及发展趋势[J].计算机光盘软件与应用，2011（6）：76?77.

[3] 陈圣，董林飞.Dijkstra和A*算法在智能导航中的应用分析[J].重庆科技学院学报，2010，12（6）：159?161.

[4] 尹路明，张志恒，张小朋.一种新型GPS/DR组合导航系统[J].现代电子技术，2014，37（13）：136?138.

[5] 罗国青.车辆定位导航系统动态路径规划研究[D].长沙：湖南大学，2011：321?323.

[6] CHEN Heping， LI Xianqin， GU Jinguan， et al. Research of path planning algorithms based on vector map data structure [J]. Computer engineering and applications， 2010， 39（19）： 238?245.

[7] ZHAO Yilin. Vehicle location and navigation systems [M]. Boston： Artech House， 2010： 108?111.

[8] ABBOTT E， POWELL D. Land?vehicle navigation using GPS [J]. Proceedings of the IEEE， 1999， 87（1）： 145?162.