基于区域划分策略的动态实时路径导航研究

摘要

随着城市道路交通的复杂化以及车辆的剧增，交通拥塞情况越来越严重，车辆导航系统越来越受到人们的重视，路径导航也成为热门的研究方向。
　　目前对车辆路径导航系统的研究主要从静态路径导航和动态路径导航两个方面进行。静态路径对于真实的道路导航没有实际意义，现阶段主要研究的是动态实时路径导航。而现阶段广泛应用的动态路径导航算法是A*算法，它是一种启发式算法，通过启发函数对路径进行估值，得到最优路径。但是A*算法在路径导航中存在的问题，即 A*算法是采用欧几里德距离计算当前节点与终点的直线距离，以此作为选择下一节点的依据，但是地理上的直线距离并无法反应真实的交通环境。同时动态实时路径导航会产生大量的动态实时数据，怎样才能减少数据量，都将成为重要问题。
　　针对以上算法的缺点及问题，本论文提出了一种基于区域划分策略的动态实时路径导航。主要研究内容包括：首先是路网模型的构建，建立区域层次划分的路网模型；其次根据不同时间段历史统计数据和交通灯信号两方面因素，对动态实时路况进行分析，对本算法提供一个启发式路径，依据初始启发路径，对局部区域求最优路径。最后，本论文以Android为平台，利用百度地图 API实现了基于该算法的路径导航系统，并且在该系统中进行实验对比。将基于区域划分策略路径算法与Dijkstra算法对比和A*启发式算法进行对比，路径搜索精度提高。本论文主要贡献是实现一个路径导航系统，将该算法应用在本系统中。算法通过减少动态更新数据的计算，来考虑更多约束因素对路径进行优化，进而得到最优路径。实验结果表明基于区域划分策略算法不但能减少搜索节点，通过多因素控制，能够有效提高搜索精度。

目录

封面

中文摘要

英文摘要

目录

第1章 绪 论

1.1 课题研究背景及意义

1.2 国内外相关技术研究现状

1.3 主要研究内容及组织结构

第2章 相关路径算法介绍

2.1算法介绍

2.2路网模型

2.3本章小结

第3章 基于区域划分策略算法

3.1数据来源及数据结构

3.2算法设计方案

3.3模块及算法实现

3.4时间对路况的影响

3.5交通灯对路况的影响

3.6全局路径搜索

3.7 本章小结

第4章 实验结果与分析

4.1软硬件设备

4.2系统数据与性能分析

4.3 本章小结

结论

参考文献

攻读硕士学位期间发表的学术论文

声明

致谢