详情

原文传递基于时间最短原则的路径规划算法研究

论文题名：	基于时间最短原则的路径规划算法研究
关键词：	车载导航系统;行程时间;最短路径规划;地图数据存储;Linux系统
摘要：	车载智能导航终端是车联网中的重要节点，在汽车数量日益增加、路况条件逐渐紧张的情况下，具有提高出行效率的作用。它通过路径规划的方式辅助驾驶员选择行车路线。路径规划可以按照距离和时间等条件选择最佳路线。随着国家对车联网的重视以及人们生活节奏的加快，研究基于时间最短原则的路径规划算法以及它在车载导航系统上的实现方法，有助于满足人们的实际出行需求并为车联网的具体开展提供依据。论文在研究地图数据存储技术的基础上，重点对路网数据存储结构和基于时间最短原则的路径规划算法展开研究，并在车载导航系统中实现和验证路径规划算法。　　论文的主要研究内容如下：　　1.地图数据存储技术研究。　　在分析地图数据模型和实际需求基础上，本文设计一种二进制数据存储方式存储地图数据，数据占用的存储空间较小。分开存储属性信息和几何数据信息，建立两种数据的交互索引关系。针对经纬度坐标到平面坐标转换计算较为复杂的情况，本文建立线性转化模型实现地心地固(Earth-centered, Earth-fixed, ECEF)坐标系下经纬度坐标到本地坐标系下平面坐标的快速转换。在保证地图精度的条件下，提出整型数据代替浮点数据的存储方式，在进一步减小数据存储的物理空间的同时，提高了地图几何数据到屏幕坐标的转换效率，加快了地图绘制的速度。　　2.路网数据存储方法研究。　　基于地图数据形成的路网是路径规划的基础，路网的质量直接影响路径规划算法的效率。为了加快拓展速度和减小存储空间，设计了一种节点向后拓展结构来存储路网的拓扑关系数据结构。分析以时间为基础的路段不同类型权值的计算方法，将时间作为路网数据的一部分实现路网数据存储，支持路径规划算法中对路段时间权值的解算。　　3.路径规划算法研究。　　重点研究Dijkstra和A路径规划算法原理，对比其在搜索空间和执行时间上的差异；针对实际应用中始点和终点为具体目标点而与道路独立的情况，分析始点和终点到道路节点的匹配全过程。在此基础上，针对课题需求，通过建立路况数据库模拟实时路况，将实时路况信息与属性数据结合进行路段动态行驶时间的预测，研究并提出了一种改进的A算法，并建立了改进算法的节点估计、时间预测算法和实现流程。　　4.车载导航系统中行程时间最短的路径规划算法实现。　　以ARM为控制核心基于Linux系统设计完成了车载导航系统，主要功能包括地图显示、地图缩放和漫游、目标点和兴趣点搜索、实时定位、地图匹配、路径规划以及路径引导。作为车载导航系统的核心功能，在完成常用的以最短距离等效的行程时间最短路径规划功能的基础上，通过路况数据库提供的数据和道路固有数据结合解算路段行驶时间的方式，实现了基于路况数据库的行程时间最短的路径规划。比较常用的行程时间最短路径规划与本文的基于路况数据库的行程时间最短路径规划，表明本文的路径规划路线所需要的行程时间更短，验证了该算法的优越性，进一步测试表明，该算法在所设计的车载导航系统上搜索最优路径所耗费的时间平均仅为2.9秒。最后，基于路径规划结果的路径引导实验证明了本文的研究成果具有较强的实用性。
作者：	宣丙龙
专业：	导航、制导与控制
导师：	赵琳
授予学位：	硕士
授予学位单位：	哈尔滨工程大学
学位年度：	2014
正文语种：	中文