Fast algorithms for minimum error map-matchings

GPS data of vehicles travelling on road networks can be used to estimate travel times. This requires the identification of the corresponding paths in the network. We developed algorithms identifying a path minimizing a special distance with a GPS trajectory even in presence of cycles. Mild assumptions over the GPS precision and the use of heuristic steps allow fast map matchings. We compared these algorithms over 30000 real and generated GPS samples on a grid graph and two real life networks. We show that on average, our algorithm and the heuristic return in minutes paths that have respectively 92.5% and 89% of the trajectory in a corridor of one meter around them