Shortest path and vehicle trajectory aided map-matching for low frequency GPS data

Quddus, Mohammed and Washington, Simon (2015) Shortest path and vehicle trajectory aided map-matching for low frequency GPS data. Transportation Research Part C: Emerging Technologies, 55 328-339. doi:10.1016/j.trc.2015.02.017


Author Quddus, Mohammed
Washington, Simon
Title Shortest path and vehicle trajectory aided map-matching for low frequency GPS data
Journal name Transportation Research Part C: Emerging Technologies   Check publisher's open access policy
ISSN 0968-090X
1879-2359
Publication date 2015-06-01
Sub-type Article (original research)
DOI 10.1016/j.trc.2015.02.017
Open Access Status Not yet assessed
Volume 55
Start page 328
End page 339
Total pages 12
Place of publication Kidlington, Oxford United Kingdom
Publisher Pergamon Press
Language eng
Formatted abstract
Map-matching algorithms that utilise road segment connectivity along with other data (i.e. position, speed and heading) in the process of map-matching are normally suitable for high frequency (1 Hz or higher) positioning data from GPS. While applying such map-matching algorithms to low frequency data (such as data from a fleet of private cars, buses or light duty vehicles or smartphones), the performance of these algorithms reduces to in the region of 70% in terms of correct link identification, especially in urban and sub-urban road networks. This level of performance may be insufficient for some real-time Intelligent Transport System (ITS) applications and services such as estimating link travel time and speed from low frequency GPS data. Therefore, this paper develops a new weight-based shortest path and vehicle trajectory aided map-matching (stMM) algorithm that enhances the map-matching of low frequency positioning data on a road map. The well-known A∗ search algorithm is employed to derive the shortest path between two points while taking into account both link connectivity and turn restrictions at junctions. In the developed stMM algorithm, two additional weights related to the shortest path and vehicle trajectory are considered: one shortest path-based weight is related to the distance along the shortest path and the distance along the vehicle trajectory, while the other is associated with the heading difference of the vehicle trajectory.

The developed stMM algorithm is tested using a series of real-world datasets of varying frequencies (i.e. 1 s, 5 s, 30 s, 60 s sampling intervals). A high-accuracy integrated navigation system (a high-grade inertial navigation system and a carrier-phase GPS receiver) is used to measure the accuracy of the developed algorithm. The results suggest that the algorithm identifies 98.9% of the links correctly for every 30 s GPS data. Omitting the information from the shortest path and vehicle trajectory, the accuracy of the algorithm reduces to about 73% in terms of correct link identification. The algorithm can process on average 50 positioning fixes per second making it suitable for real-time ITS applications and services.
Keyword GPS
Digital map
Map-matching algorithm
Vehicle trajectory
A* search algorithm
Genetic algorithm
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Non-UQ

Document type: Journal Article
Sub-type: Article (original research)
Collection: School of Civil Engineering Publications
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 31 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 35 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Fri, 03 Mar 2017, 17:39:07 EST by Jeannette Watson on behalf of School of Civil Engineering