 | ||
Map matching is the problem of how to match recorded geographic coordinates to a logical model of the real world, typically using some form of Geographic Information System. The most common approach is to take recorded, serial location points (eg. from GPS) and relate them to edges in an existing street graph (network), usually in a sorted list representing the travel of a user or vehicle. Matching observations to a logical model in this way has applications in satellite navigation, GPS tracking of freight, and transportation engineering.
Contents
Map matching algorithms can be divided in real-time and offline algorithms. Real-time algorithms associate the position during the recording process to the road network. Offline algorithms are used after the data is recorded and are then matched to the road network. Real-time applications can only calculate based upon the points prior to a given time (as opposed to those of a whole journey), but are intended to be used in 'live' environments. This brings a compromise of performance over accuracy. Offline applications can consider all points and so can tolerate slower performance in favour of accuracy.
Examples and use cases
Uses for map-matching algorithms range from the immediate and practical, such as applications designed for guiding travellers, to the analytical, such as generating detailed inputs for traffic analysis models and the like.
Probably the most common use of map-matching is where a traveller has some mobile computer giving him or her directions across a street network. In order to give accurate directions, the device must know exactly where in the street network the user is. A GPS location has positional error though, so picking the nearest street segment and routing from there will likely not work. Instead, the history of locations reported by the GPS can be used to guess a plausible route and infer the current location more accurately.
Other uses, more analytical in nature, include:
There are other examples and this subject is still undergoing active research and development.
Implementation
Map matching is implemented in a variety of programs, including the open source GraphHopper routing engine. It is also included in a variety of proprietary programs and mapping/routing applications.