基于浮动网格的路段检索方法

Road Section Retrieval Method Based on Floating Grid

地图匹配是将车辆原始的GPS轨迹数据映射到实际道路网络上的过程,其中为GPS轨迹点检索候选路段是地图匹配的首要环节,然而不同的候选路段检索方式会直接影响地图匹配的准确性和效率.本文针对城市路网环境下的低频采样GPS轨迹数据,提出了一种基于浮动网格的路段检索方法.该方法利用GeoHash网格编码,采用浮动GeoHash网格的方式,为轨迹点检索候选路段.其次为了验证方法的可行性,本文通过隐马尔可夫模型,结合道路网络的拓扑结构以及轨迹的时空约束条件,采用增量的方式,利用维特比算法计算得到局部最优解.最后使用贪心策略,从已经得到的局部最优解中依次延伸得到全局最佳匹配路径.

Map matching is the process of mapping the original global positioning system(GPS)trajectory data of vehicles into the actual road network,and retrieving candidate road sections for GPS trajectory points is the primary link of this process.However,retrieval methods directly affect the accuracy and efficiency of map matching.In this study,a road section retrieval method based on the floating grid is proposed for GPS trajectory data sampled at a low frequency in an urban road network environment.This method resorts to GeoHash grid encoding and floating GeoHash grid to retrieve candidate road sections for trajectory points.Then,to verify the feasibility of the method,this study applies the hidden Markov model,the incremental method,and the Viterbi algorithm to calculate the local optimal solution,with due consideration of the topological structure of the road network and the time-space constraints on the trajectory.Finally,the greedy strategy is employed to obtain the global optimal matching path from the local optimal solution through successive extension.