Current map-matching algorithms for transport applications: State-of-the art and future research directions

Map-matching algorithms integrate positioning data with spatial road network data (roadway centrelines) to identify the correct link on which a vehicle is travelling and to determine the location of a vehicle on a link. A map-matching algorithm could be used as a key component to improve the performance of systems that support the navigation function of intelligent transport systems (ITS). The required horizontal positioning accuracy of such ITS applications is in the range of 1 m to 40 m (95%) with relatively stringent requirements placed on integrity (quality), continuity and system availability. A number of map-matching algorithms have been developed by researchers around the world using different techniques such as topological analysis of spatial road network data, probabilistic theory, Kalman filter, fuzzy logic, and belief theory. The performances of these algorithms have improved over the years due to the application of advanced techniques in the map matching processes and improvements in the quality of both positioning and spatial road network data. However, these algorithms are not always capable of supporting ITS applications with high required navigation performance, especially in difficult and complex environments such as dense urban areas. This suggests that research should be directed at identifying any constraints and limitations of existing map matching algorithms as a prerequisite for the formulation of algorithm improvements. The objectives of this paper are thus to uncover the constraints and limitations by an in-depth literature review and to recommend ideas to address them. This paper also highlights the potential impacts of the forthcoming European Galileo system and the European Geostationary Overlay Service (EGNOS) on the performance of map matching algorithms. Although not addressed in detail, the paper also presents some ideas for monitoring the integrity of map-matching algorithms. The map-matching algorithms considered in this paper are generic and do not assume knowledge of 'future' information (i.e. based on either cost or time). Clearly, such data would result in relatively simple map-matching algorithms. (C) 2007 Elsevier Ltd. All rights reserved.