Map matching algorithms integrate positioning data with spatial road network data to support the navigation modules of intelligent transport systems requiring location and navigation data. Research on the development of map matching algorithms has significantly advanced over the last few years. This article looks at different methods that have been adopted in map matching algorithms and highlights future trends in map matching and navigation research.
Methodologies Used In Map Matching Algorithms
The general purpose of a map matching algorithm is to identify the correct road segment on which the vehicle is travelling and to determine the vehicle location on that segment. The parameters used to select a precise road segment are mainly based on the proximity between the position fix and the road, the degree of correlation between the vehicle trajectory derived from the position fixes and the road centreline, and the topology of the road network. Orthogonal projection of the position fix onto the selected road segment is normally used to calculate the vehicle location on the segment. Figure 1 shows a general map matching process (see Quddus, 2006 for details) which takes inputs from an integrated GPS/DR such as easting (E), northing (N), speed (v), and heading (θ) and the error variances associated with them. The map matching process also takes inputs from a spatial digital road network database. The outputs of the algorithm are the correct link on which the vehicle is travelling and the location of the vehicle () and the error variances associated with them.
Key Terms in this Chapter
Intelligent Transportation Systems (ITS): ITS can be defined as the integrated application of advanced sensors, computers, electronics, navigation, and communication technologies to vehicles and roadways that increase safety, reduce congestion, enhance mobility, minimize environmental impact, increase energy efficiency, and promote economic productivity for a healthier economy.
Map Matching (MM): MM is a process to match the positioning data (i.e., longitude and latitude or Easting and Northing) onto the digital road map data.
Accuracy: Accuracy is defined as the nearness of a measurement to the standard or true value i.e., a highly accurate navigation system will provide measurements very close to the standard, true or known values. A rigorous statement of accuracy includes statistical measures of uncertainty and variation. Accuracy is generally represented by standard deviation of errors (difference between measurements on the map and the true value).
Topology: Topology is the relationship between entities (points, lines, and polygons). The relationship can be defined as adjacency (in the case of polygons), connectivity (in the case of lines), or containment (in the case of points in polygons).
Dead-Reckoning (DR): DR is the process of estimating the position of a vehicle (or a moving object) with respect to a known position using information on heading, speed, time, and distance travelled by the vehicle.
Global Positioning System (GPS): GPS is a satellite-based radio-navigation, positioning, and time-transfer system. It is designed, financed, and deployed by the US Department of Defense (US DoD) and operated jointly by the US DoD and the Department of Transportation (US DoT).
Fuzzy Logic: Fuzzy logic is a superset of conventional (Boolean) logic that has been extended to handle the concept of partial truth i.e., truth values between “completely true” and “completely false”. It was introduced in the 1960’s by Zadeh (1965). It is suitable to deal with problems involving knowledge expressed in vague, and linguistic terms.