A critical review and crucial comparison of state-of-the-art map-matching algorithms

Abstract

GPS-equipped-devices are widely used in our daily life, which enables to collect a huge amount of GPS trajectories data. More and more applications, such as urban computing, vehicle navigation and route recommendation have begin to use GPS trajectory information to achieve better quality of services. However, due to the limitation of GPS device, the GPS data is not always accurate. Map-matching algorithms integrate a sequence of noisy GPS trajectories data with digital road network to align the location of a vehicle on a link so as to identify the correct trace on which a vehicle is traveling. It is an crucial and primary step for many GPS-based applications. Fortunately, several map-matching algorithms have been developed in the few years. The existing works have developed the quality of map-matching. However, each algorithm has its own shortcoming. For example, local and incremental map-matching algorithms are fast while they are sensitive. Global map-matching algorithm is more accurate than the other map-matching algorithm. Nevertheless, global map-matching algorithm cost a lot of time for computing. So far, there have been no comparison for the existing algorithms. It is necessary to evaluate the performance of each map-matching algorithm. In the thesis, we present a critical review of map-matching algorithms and evaluate five state-of-the-art map-matching algorithms using a dataset of GPS trajectories collected from Beijing, China. Our experiment indicates that ant colony-based map-matching approach perform both accuracy and efficiency.

Date of Award	2015
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology