原文传递
基于GPS历史轨迹的路径规划技术研究
| 论文题名： | 基于GPS历史轨迹的路径规划技术研究 |
| 关键词： | GPS历史轨迹;路径规划;轨迹搜索;网格索引;区域地标;随机选择;RPBTS算法 |
| 摘要： | 随着GPS设备的普及，基于轨迹搜索的路径规划技术逐渐成为一个热门研究课题。给出一组有序的查询点，为了挖掘出先前用户对于路径选择的经验，传统算法致力于搜索出距离查询点最近的轨迹。然而这些轨迹往往不能满足用户的需求，它们存在两大问题。第一，这些轨迹可能只靠近部分查询点，而距离其余查询点较远；第二，这些轨迹可能经过了查询点以外的其他地点。如果用户沿着这些轨迹行驶，问题一会导致用户找不到某些查询点，问题二会导致用户承受额外的开销。 本文针对以上两个问题提出一种新的模型，称为基于轨迹分片的路径规划方法（RPBTS）。给出一系列查询点，首先将这些查询点转换成它们附近的道路，找出相交于这些道路的轨迹片段，并利用这些片段拼接出行车路径。这样，可以保证得到的路径接近每一个查询点。此外，本文还提出基于方差的方法用于判断轨迹片段在经过两个连续查询点时是否存在异常行为。通过排除异常轨迹片段，可以保证得到的路径在两个连续查询点之间没有去往其他地点。 接着，本文提出RPBTS的基础解决方案，并且引入贪心算法的思想以提高算法效率。然后，本文提出三种优化方法以进一步提高算法效率。第一，基于网格索引的优化方法，该方法可以快速定位到查询点附近的路段；第二，基于区域地标的优化方法，该方法将查询点转换成其附近的热门路段；第三，基于随机选择的优化方法，该方法有效地减少了多方案择优的开销。这些优化方法合理地降低了算法的复杂度，并且使得整个规划过程更加符合人们的常识。 最后，本文使用微软研究院提供的T-drive轨迹数据集和中科院软件所提供的北京地图数据，设计合理的实验对RPBTS算法的有效性和高效性做了分析。实验结果表明， RPBTS算法可以有效地避免传统轨迹搜索算法中存在的两大问题。此外，本文提出的算法达到了较高的效率。当查询点为4个时，RPBTS的平均运算时间为156ms，完全可以满足用户对于系统响应速度的要求。 |
| 作者： | 蒋金晟 |
| 专业： | 计算机技术 |
| 导师： | 徐建 |
| 授予学位： | 硕士 |
| 授予学位单位： | 杭州电子科技大学 |
| 学位年度： | 2016 |
| 正文语种： | 中文 |
检索历史
应用推荐
