Online map-matching of noisy and sparse location data with hidden Markov and route choice models

• Main Authors: Jagadeesh, George Rosario, Srikanthan, Thambipillai
• Other Authors: School of Computer Science and Engineering
• Format: Article
• Language: English
• Published: 2020
• Subjects: Engineering::Computer science and engineering; Intelligent Transportation Systems; Hidden Markov Models
• Online Access: https://hdl.handle.net/10356/145629
• Institution: Nanyang Technological University

With the growing use of crowdsourced location data from smartphones for transportation applications, the task of map-matching raw location sequence data to travel paths in the road network becomes more important. High-frequency sampling of smartphone locations using accurate but power-hungry positioning technologies is not practically feasible as it consumes an undue amount of the smartphone’s bandwidth and battery power. Hence, there exists a need to develop robust algorithms for map matching inaccurate and sparse location data in an accurate and timely manner. This paper addresses the above need by presenting a novel map matching solution that combines the widely-used approach based on a Hidden Markov Model (HMM) with the concept of drivers’ route choice. Our algorithm uses a HMM tailored for noisy and sparse data to generate partial map-matched paths in an online manner. We use a route choice model, estimated from real drive data, to reassess each HMM-generated partial path along with a set of feasible alternative paths. We evaluated the proposed algorithm with real-world as well as synthetic location data under varying levels of measurement noise and temporal sparsity. The results show that the map-matching accuracy of our algorithm is significantly higher than that of the state of the art, especially at high levels of noise.