Map-Matching Algorithm Based on Hidden Markov and Constraint Value Pruning

Abstract

Map matching is the process of matching global positioning system (GPS) trajectory data with map data. Its purpose is to determine the actual route of the moving object. Because of factors such as positioning devices and the environment, the GPS trajectory data obtained may not be accurate. In location-based services, map matching can be used to address the accuracy and reliability issues of GPS location data. There are currently many map-matching algorithms, for example, spatio-temporal-based (STD) matching algorithm, improved interactive voting-based map-matching (IIVMM) algorithm, and turning-point-based (TPB) offline map-matching algorithm, but existing algorithms have some shortcomings, such as low matching accuracy on complex roads or low sampling rates, and routing calculation time bottlenecks. Therefore, this paper proposes a fast matching algorithm based on constrained value pruning that is suitable for complex roads. The algorithm considers the multi-directional features within the road and uses secondary calculations to determine candidate points, improving the accuracy of candidate point selection. Additionally, two pruning strategies based on constrained values are introduced to reduce the majority of the routing calculation process and improve the matching efficiency. Finally, comparative experiments are conducted on a real trajectory dataset. The results show that, compared with STD, IIVMM, and TPB algorithms, the algorithm accuracy is improved by about 2% to 4%, and the running time is reduced by about 30%.