基于GPS历史轨迹的路径规划技术研究

发布时间：2021-07-13 19:47

　　随着GPS设备的普及,基于轨迹搜索的路径规划技术逐渐成为一个热门研究课题。给出一组有序的查询点,为了挖掘出先前用户对于路径选择的经验,传统算法致力于搜索出距离查询点最近的轨迹。然而这些轨迹往往不能满足用户的需求,它们存在两大问题。第一,这些轨迹可能只靠近部分查询点,而距离其余查询点较远;第二,这些轨迹可能经过了查询点以外的其他地点。如果用户沿着这些轨迹行驶,问题一会导致用户找不到某些查询点,问题二会导致用户承受额外的开销。本文针对以上两个问题提出一种新的模型,称为基于轨迹分片的路径规划方法（RPBTS）。给出一系列查询点,首先将这些查询点转换成它们附近的道路,找出相交于这些道路的轨迹片段,并利用这些片段拼接出行车路径。这样,可以保证得到的路径接近每一个查询点。此外,本文还提出基于方差的方法用于判断轨迹片段在经过两个连续查询点时是否存在异常行为。通过排除异常轨迹片段,可以保证得到的路径在两个连续查询点之间没有去往其他地点。接着,本文提出RPBTS的基础解决方案,并且引入贪心算法的思想以提高算法效率。然后,本文提出三种优化方法以进一步提高算法效率。第一,基于网格索引的优化方法,该方法可以快... 

【文章来源】：杭州电子科技大学浙江省

【文章页数】：70 页

【学位级别】：硕士

【部分图文】：

T-Drive轨迹数据集分布

[57]由中科院软件所基础软件中心信息及新型计算研究室提供。图3.13展示了T-Drive轨迹数据集匹配到该路网之后的结果。该图与图3.11中的分布基本吻合，证明了该地图数据的正确性。0 2 4 6 8 10 1200.050.10.150.20.250.30.35minutesproportion0 1000 2000 3000 4000 5000 6000 7000 800000.10.20.30.40.50.60.7metersproportion

地标分布不均匀。提取top-k热门的路径作为地标并不合理。本文尝试提取最热门的20602个路段作为地标，并在图4.2中展示了其分布情况。从图中可以看出，地标普遍集中在市中心。当查询点iq 分布在郊区时，其附近往往不存在地标，查询点不能被转换成地标，那么查询路段序列QR 并不会因此减少。而当查询点 位于市区时，其附近存在过多的路标，算法需要额外开销去获取距离查询点最近的路标。因此，在实际应用中，只使用基于地标的优化方法，对GA算法的提高作用并不明显。图4.2：Top-20602地标分布为解决查询点转换效率低和地标分布不均匀的问题，本节将介绍网格索引，并在此基础上提出区域地标概念。首先介绍网格索引的构建过程。例如在图4.3中，在路网上构建一些网格。网格索引的左上角为原点，每个格子的对角线长度为b 。借助网格索引，就能通过两步快速找出满足 ( , )i i bdist r q 的路段。第一，快速定位查询点。网络索引的左上角为原点，即坐标为(0,0)。假设每个格子的边长为1

【参考文献】：
期刊论文
[1]一种基于LCSS的相似车辆轨迹查找方法[J]. 裴剑,彭敦陆.  小型微型计算机系统. 2016(06)
[2]基于GPS轨迹数据的地图匹配算法[J]. 李清泉,黄练.  测绘学报. 2010(02)
[3]基于编辑距离的轨迹相似性度量[J]. 刘坤,杨杰.  上海交通大学学报. 2009(11)

硕士论文
[1]基于Voronoi图的路网轨迹数据查询技术研究[D]. 陈宇.杭州电子科技大学 2015



本文编号：3282688