Unambiguous, Real-Time and Accurate Map Matching for Multiple Sensing Sources

This article presents a fast and unambiguous map-matching algorithm to reconstruct routes from sparse GPS traces. Unlike probabilistic methods, it identifies only the road segments that were certainly used, thus avoiding any ambiguity in route estimation. The algorithm efficiently processes low-sampling-rate traces and has been tested on real and simulated GPS data from London, Paris, and Luxembourg, achieving over 85% accuracy for a sampling period of up to 50 seconds. It is suitable for real-time applications and offers robust performance despite GPS measurement errors. Future work will focus on refining the algorithm by dynamically adjusting the sampling rate based on local topography to optimize energy consumption in crowd-sensing applications.

Smart Cities need real-time information to improve the efficiency of their transportation systems. In particular, crowd sensing may help to identify the current speed in each street, the congested areas, etc. In this context, map matching techniques are required to map a sequence of GPS waypoints into a set of streets on a common map. Unfortunately, most map matching approaches are probabilistic. We propose rather an unambiguous algorithm, able to identify all the possible paths that match a given sequence of waypoints. We need an unambiguous identification for each waypoint set. For instance, the actual speed should be assigned to the correct set of streets, without error. To identify all the possible streets, we construct the set of candidates iteratively. We identify all the edge candidates around each waypoint, and reconstruct all the possible sub-routes that connect them. We then verify a set of constraints, to eliminate impossible routes. The road segments common to all computed routes form an unambiguous match. We evaluate the matching ratio of our technique on real city maps (London, Paris and Luxembourg). We also validate our approach with a real GPS trace in Seattle.