Research On Map Matching Algorithm Based On Low-Sampling-Rate Floating Car Data

Traffic congestion has become a serious problem that restricts the development of many cities. In order to improve the traffic, today the major countries in the world start to develop the intelligent transport system(ITS). Floating car technology is a new way for ITS to collect traffic information. Due to the existence of the positioning error, the data collected by float car is not so accurate. Map matching algorithm is used to modify the positioning error.Map matching is the process of aligning a sequence of observed user positions with the road network on a digital map. Unfortunately, most current map matching approaches only deal with high-sampling-rate(typically one point every 1-30s) GPS data, and become less effective for low-sampling- rate points as the uncertainty in data increases. Based on the analysis of existing algorithms, we propose a global map- matching algorithm for low-sampling- rate GPS trajectories. Firstly, we make a preprocessing for GPS trajectories and the road network. Secondly, the candidate set of GPS point is filtered by using error region and angle constraints. Then, the algorithm considers the spatial geometric and topological structures of the road network and the temporal/speed constraints of the trajectories. Based on spatio-temporal analysis, a candidate graph is constructed from which the critical path is the best matching path. At last, we localize the candidate graph to accelerate the calculation process and the localization strategy doesn't decrease the matching accuracy.The experiments are performed on real dataset. The results show that our algorithm outperforms Weak-Fréchet-Distance(WFD) in terms of matching accuracy and running time for low-sampling trajectories. Meanwhile, when compared with fuzzy matching algorithm based on blocks, our algorithm also improves accuracy.