原文传递
车辆导航系统中的路径规划算法研究
| 论文题名： | 车辆导航系统中的路径规划算法研究 |
| 关键词： | 车辆导航系统;最优路径算法;路径规划;软件仿真 |
| 摘要： | 随着城市化进程的推动和城市规模的扩大，交通中存在的问题如交通拥堵、交通事故等在一定程度上制约着城市化的发展。要改善这一问题，最有效的方法之一就是通过高效的导航系统来提高驾驶员的出行效率。最优路径规划技术是车辆导航系统中的关键性技术，高性能的路径查询算法以及其有效实现，对车辆导航系统来说是很重要的。算法的优越程度，在很大程度上影响着导航设备的性能。 目前，国内外学者对此已作出了大量的研究。传统的以Dijkstra算法为代表最优路径规划算法，大都属于贪心搜索算法的范畴，存在局部最小问题，而且计算量过大，随着数据规模的增大，这种现象将更加突出；即使带有启发性搜索的A*算法也存在局部最优等特点，很难从整体上找到最优解，并且启发函数的确定也是件不容易的事；新兴的仿生型蚁群算法，很大程度上依赖于参数的设置，而且易于陷入局部最优解等。当前大多数算法在进行路径查询时，搜索是建立在整个数据集上，没提前对数据集进行较为合理的优化，降低了算法的执行效率。可见研究更高效的、高质量的、易于实现的路径规划算法是很必要的。 论文综合分析了交通中存在的问题、导航系统的国内外研究现状及其相关技术，并对路径算法做了深入的研究，重点研究了Dijkstra算法、A*算法、遗传算法和蚁群算法。并对上述算法的优缺点、应用条件及运用范围进行了深入研究和分析。A*算法通过引入启发函数，启发函数由代表从起点到当前结点的实际代价和当前结点到目标的估计代价两部分组成，在执行过程中，通过比较当前结点的启发函数值来决定下一个被扩散的结点；燃烧算法是一种类似于点扩散的算法，算法从指定的点开始逐渐蔓延到周围的临接点，直到找到另一点为止。在此基础上，通过引入虚的起始点、中心点等方法建立了预处理模型，以实现对数据集的快速优化，使最有可能成为最优路径上的数据进入将被搜索的数据集合：在路径更新阶段引入结点互换策略等，综合燃烧算法和A*算法的思想，提出了改进的路径算法-A-燃算法，A-燃算法在执行上分为预处理阶段和处理阶段，前者实现对有效数据的快速界定，后者实现对路段的计算更新。通过软件仿真来验证改进后的算法，得出的结论表明该算法在CPU执行时间以及准确性方面是一种更优的算法。 |
| 作者： | 梁新发 |
| 专业： | 计算机应用技术 |
| 导师： | 邹永贵 |
| 授予学位： | 硕士 |
| 授予学位单位： | 重庆邮电大学 |
| 学位年度： | 2010 |
| 正文语种： | 中文 |
检索历史
应用推荐
