Abstract: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.