A weight-based map-matching algorithm for vehicle navigation in complex urban networks

A map-matching algorithm is an integral part of every navigation system and reconciles raw and inaccurate positional data (usually from a global positioning system GPS]) with digital road network data. Since both performance (speed) and accuracy are equally important in real-time map-matching, an accurate and efficient map-matching algorithm is presented in this article. The proposed algorithm has three steps: initialization, same-segment, and next-segment. Distance between the GPS point and road segments, difference between the heading of the GPS point and direction of road segments, and difference between the direction of consecutive GPS points and direction of road segments are used to identify the best segment among candidates near intersections. In contrast to constant weights applied in existing algorithms, the weight of each criterion in this algorithm is dynamic. The weights of criteria are calculated for each GPS point based on its: (a) positional accuracy, (b) speed, and (c) traveled distance from previous GPS point. The algorithm considers a confidence level on the assigned segment to each GPS point, which is calculated based on the density and complexity of roads around the GPS point. The evaluation results indicate 95.34% correct segment identification and 92.19% correct segment assignment. The most important feature of our algorithm is that the high correct segment identification percentage achieved in urban areas is through a simple and efficient weight-based method that does not depend on any additional data or positioning sensors other than digital road network and GPS.