Map Matching with Travel Time Constraints

Map matching determines which road a vehicle is on based on inaccurate measured locations, such as GPS points. Simple algorithms, such as nearest road matching, fail often. We introduce a new algorithm that finds a sequence of road segments which simultaneously match the measured locations and which are traversable in the time intervals associated with the measurements. The time constraint, implemented with a hidden Markov model, greatly reduces the errors made by nearest road matching. We trained and tested the new algorithm on data taken from a large pool of real drivers.