Map-Matching Algorithm for GPS Trajectories in Complex Urban Road Networks

Map-matching for GPS trajectories is a key groundwork in mining transportation data. Reliable matching results are significant for monitoring traffic situation, publishing real-time transportation information, vehicle tracking, smart vehicle dispatching, and routing behavior analysis. In real urban road networks, there are numerous complicated road structures such as elevated roads, frontage roads, and interchange bridges. Traditional map-matching algorithms could not match trajectories on these structures accurately. In this paper, we propose a map-matching algorithm based on the topological structure of the road networks and transform the problem of matching GPS trajectories in road map into the problem of finding the shortest path in a weighted road network. We test the algorithm with the real data of GPS trajectories of tens of thousands of taxis in Chengdu. The results show that the presented algorithm can acquire a high success ratio and accuracy ratio in complicated urban road networks.