Research On Map Matching Algorithm For Large Scale Probe Vehicle Data

Traffic jam has been a bottleneck for city development. Most developedcountries are developing Intelligent Transport System (ITS) to improveservice level of urban transportation. Probe Vehicle System (PVS) is anadvanced approach which provide raw data for ITS. One of the key techniquesfor PVS is Map Matching, which is the theme of this research.Compared with real-time data, historic probe vehicle data has longer timeinterval and distance interval. In this paper, map matching problem isregarded as a shortest path problem, and an integer programming model hasbeen developed. Then, this paper proposes a global map-matching algorithm,which consists of three phrases: data preprocessing, link matching and pointmatching. In data preprocessing, digital map is divided into two kinds of grid,and links associated with each gird are extracted and stored. In link matching,candidate link network is obtained by simply computing gird index from GPScoordinates for each trip. Then, Dijkstra algorithm has been used to search theshortest path. In point matching, the location of vehicle is found throughvertical projection, and link travel time has been calculated.This paper develops a Mapbasic program based on MapInfo to check theresults of map matching. To make up the shortcomings of traditionalmeasurement, the correct matching route has been strictly defined. Inexperiments for1000trips, the type of map matching result has been definedand indentified. Based on manual counting, three parameters have beenproperly determined. What’s more, the algorithm has been further improved.Finally, in large scale probe vehicle data practice, this research displaysexcellent performance in both accuracy and efficiency. Evidences show thatthis paper has not only theoretical significance but also practical value.