An Efficient Map Matching Algorithm And Architecture For Large-scale Vehicle GPS Stream Data

In many intelligent transportation applications, floating vehicles which have been installed GPS generates a lot of data. In the fields of transportation and computer nowadays, it has been a research hotspot to analyze and probe into these data, such as the calculation of traffic state of road network, the detection of traffic abnormality and the analysis of urban dynamics. On account of the existence of GPS positioning error, usually there is no direct links between the GPS tracks and the data of road network. Thus, before the conduct of the research, it is an essential step to match the running tracks with the road network, namely, the map-matching.During the floating vehicle's operation, the GPS equipment will send the related data of latitude and longitude to the server in every about 30 to 60 seconds, thereby the GPS flow data come into being. However, in map-matching algorithm, both the deviation between GPS data and road network data, and the ambiguity resulted from the impact of some sparse GPS points on the recovery of vehicle's track should be taken into consideration. Meanwhile, it is vital significance to meet the calculation requirements of real-time matching. Therefore, we attempt to bring forward the distributed map-matching algorithm in this thesis to deal with the numerous amount of floating traffic data effectively and efficiently.Based on Hidden Markov Model, the following concerns on the deviation between the GPS position data and the road network, the accessibility of destination and the driving speed and etc are all taken into account in map-matching, which is able to improve the matching accuracy and reduce the ambiguity of the trajectories recovery. In addition, in the experiment, Jstorm-based distributed systems is adopted to be the basic framework to design the concurrent map-matching algorithm for the large volume of floating car stream data with high efficiency. The main work in this paper includes:1) The accelerating strategy in map-matching algorithm. In order to cope up with the large-scale floating car data, as well as to improve the real-time calculation performance, the grid index and the shortest path list strategy to accelerate the algorithm are presented in details in the paper, of which the grid index is mainly used to identify the candidate segments, and the shortest path list is applied to test the accessibility;2) The improvement of the original Hidden Markov map-matching algorithm. First, an overview based on the Hidden Markov map-matching algorithm is introduced; besides, the improvement of the algorithm and its implementation for the real-time stream data is elaborated. Finally, we discuss the abnormality during the map matching process and its correspondences.3) The design of the distributed map-matching system. To deal with the vast amount of floating car stream data, it is insufficient to meet the needs of real-time, merely depending on the performance of individual compute node. Under the Jstorm-based system which is presented in this paper, we design the map-matching algorithm based on spout/bolt programming model for the large volume floating car stream data.On the basis of theories that have been illustrated above, two experiments are designed to validate the performance and the accuracy of map-matching algorithm based on the Jstorm framework, among which two sets of data are involved in, especially the one polished by Kubicka et al[1] will be use to validate the accuracy of our algorithm, and the other gathered in the first week of 2015 in Shenzhen will be used to test the performance of the algorithm. The experiments turn out that: F₁-Score of the algorithm is higher than 95.8%, and the efficiency meets the need of large-scale real-time processing.