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

《汽车导航路径规划算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、10.16638/j.cnki.1671-7988.2017.21.069汽车导航路径规划算法研究王运（安徽江淮汽车集团股份有限公司，安徽合肥230601）摘要：文章系统分析了汽车导航路径规划算法迪杰斯特拉和A*算法的基本原理和各自的优劣势，另分析了路径规划软件架构及导航数据格式模型，并结合汽车导航实际使用情况，阐述了导航路径规划实施的过程及策略，最终根据距离、时间、费用等权值评估模型等到用户常用的距离最短、时间最短、节油经济的可选择路线。关键词：导航；路径规划；迪杰斯特拉；数据格式模型；权值评估模型中图分类号：U463.6文献标识码：A文章编号：

2、1671-7988(2017)21-202-03ResearchonVehicleNavigationPathPlanningAlgorithmWangYun(AnhuiJianghuaiAutomobileCo.,Ltd.,AnhuiHefei230601)Abstract:ThispapersystematicallyanalyzesthebasicprinciplesandtheadvantagesanddisadvantagesofthevehiclenavigationpathplanningalgorithmDijkstraandA*a

3、lgorithm,Thepaperalsoanalyzesthepathplanningsoftwarearchitectureandnavigationdataformatmodel,Combiningwiththeactualusageofcarnavigation,Theprocessandstrategyofnavigationpathplanningareexpounded,Finally,theevaluationmodelofdistance,time,costandsoonisusedtoselecttheroutewhichist

4、heshortest,theshortesttimeandeconomicaleconomy.Keywords:Navigation;Pathplanning;Dijkstra;Dataformatmodel;weightassessmentmodelCLCNO.:U463.6DocumentCode:AArticleID:1671-7988(2017)21-202-031路径规划算法原理1.1迪杰斯特拉算法路径寻路算法最典型的就是迪杰斯特拉算法，这也是目前应用最广泛的算法。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。这

5、是一种以广度优先的穷举算法。图1该算法是是从一个顶点到其余各顶点的最短路径算法，1.2A*算法解决的是有向图中最短路径问题。迪杰斯特拉算法能得出最A*算法是另一种应用比较广泛的寻路算法，该算法是一短路径的最优解，但由于它遍历计算的节点很多，所以效率种估值算法，当探索到一定程度，根据已有数据分析得出最低，如图1所示。优路，而不需要穷举。所以该算法比迪杰斯特拉算法效率高很多，不足就是可作者简介：王运，就职于安徽江淮汽车股份有限公司。能得到的不是最优解，如图2所示。2017年第21期王运：汽车导航路径规划算法研究203内部参数转化：该部分主要是对输入的参

6、数进一步细化，为接下来的最近路搜素算法做准备。收集开始link：根据路线计算时的出发地和道路的匹配的状态、出发地速度、走行的道路种别、前方的交差点有无等，通过出发地位置来决定道路data或者路线data上的开始点。连接层判定：因为数据分层的缘故，路径规划算法也会从经历一个从低层到高层的升层的过程，最终会根据远近，图2在某一层路网中进行连接探索，该模块主要就是确定连接层。1.3综合算法探索：按照迪杰斯特拉算法算法、A*算法等原理进行路考虑到车载导航硬件及系统性能的问题，目前导航软件径探索。中基本都是采用两种算法相结合的方式，既保证了规划的性路线编辑：

7、主要是将探索最终确定的最优路按照既定的能，又从一定程度上保障了路线质量，即分别从出发地和目输出格式进行编辑。的地开始，有方向性的向相对方向呈椭圆形探索，当两个方向都探索到同一条道路时，该道路就不继续探索，直到探索3导航数据格式模型出的同一条道路满足一定条件时，探索完全停止。如图3所首先导航数据是分层存储的，如图4所示，地图界面随示。着比例尺升高，显示的内容是不一样的，比例尺越高看到的范围越广，但看到的数据属性/种类会变少，包括道路、背景、名称、POI等，都是一样的效果，这不是软件过滤的结果，是地图数据为了达到这样的效果，做的分层存储的结果。图3当然

8、也有一些其他算法被利用，但基本都是解决特定问题引入的，例如遗传算法等。图42路径规划算法软件架构其次导航数据在分层数据的基