技术摘要：
本发明提供了一种基于动态预存储的路网轨迹双向查询方法，应用于轨迹查询优化领域。本发明能够根据动态时间规整、点对聚类分组、基于动态预存储的双向搜索来对基于预存储的传统解决方案进行优化，减少轨迹间最短路径查询时的大量重复计算，显著提高查询效率。本发明技  全部
背景技术：
随着物联网的发展，传感器设备不断优化，车辆轨迹数据的采集也变得越来越方 便。作为物联网重要应用之一的智慧交通，离不开对大量轨迹数据的查询分析。其中分析轨 迹间最短路径的动态变化并找出距离峰值对公交车路线甚至无人自动驾驶车辆的路线规 划有着重要的意义。难点在于给定查询轨迹的时间可能并不完全重合，且一段历史轨迹可 能会跨路网多个路段，移动对象在这些路段上的速度也并不相同，不利于动态最短路径的 计算；并且由于城市路网规模庞大，轨迹间最短路径的计算代价极高，且子轨迹对间存在大 量重复计算，大幅降低了查询的效率。 因此如何减少轨迹间最短路径查询中的重复计算是需要解决的重要问题。传统的 解决方案会采用预存储部分路网顶点间最短路径来加速查询，然而当移动对象并不落在预 存储路径上时，并不能减少子轨迹对之间共同路径的重复计算，所以本发明设计出了一种 基于动态预存储的双向搜索算法，该算法减少了大量子轨迹对之间共同路径的计算，优化 了传统方法，加快了查询。 三、
技术实现要素：
【发明目的】 为了能够在轨迹间动态最短路径查询时减少子轨迹对之间大量共同路径的重复 计算，提高查询效率。 【技术方案】 本发明为轨迹间动态最短路径查询提供了一种优化解决方案，该方案是针对轨迹 动态时间规整后的子轨迹对间最短路径查询中存在大量重复计算的问题，设计一种基于动 态预存储的路网轨迹双向查询方法。主要步骤如下： 首先将待查询的两条轨迹进行动态时间规整，划分为时间单元相对应的子轨迹对 集合，接着将这些子轨迹对所落在路段端点间可能涉及的点对组合进行分组(默认去重)， 分组方法采用聚类方法，针对分组后的每组点对查询集合分别执行基于动态预存储的双向 搜索求得最短路径。得到上述结果后，子轨迹对间查询结果只需加上路段上的一小部分移 动即可。最后集合所有子轨迹对间查询结果即可得到待查询轨迹间的动态最短路径。 【有益效果】 本发明所述的基于动态预存储的路网轨迹双向查询算法，优化了基于预存储的传 统解决方案，可以减少轨迹间最短路径查询时的大量重复计算，显著提高了查询效率。 3 CN 111597210 A 说　明　书 2/5 页 四、附图说明 图1动态时间规整 图2子轨迹对应SD点对情况 图3基于动态预存储的双向搜索 五、