Research On Map Matching Algorithm Based On GPS Position Sequence

Wide deployment of GPS sensors has enabled the collection of a large amount of moving object position sequence,namely GPS trajectory,which is of great value and significance for building intelligent transportation system and solving serious urban problems such as traffic congestion and environmental pollution.However,due to the limitations of GPS positioning accuracy and data transmission,GPS trajectories are noisy,discrete and incomplete observations of moving objects' movements.Therefore,map matching is a requisite procedure of GPS trajectories analysis in intelligent transportation applications,which is a process of inferring the real movement paths of moving objects on a road network from GPS trajectories.The research on map matching problem originates from navigation applications.So far,dozens of map matching algorithms have been proposed.However,there are still shortcomings in these algorithms.This paper first reviews the main challenges of map matching,and then investigates the state-of-the-art map matching algorithms.Through the analysis and summary of existing algorithms,we found that they have the following problems: 1)most map matching algorithms fail to balance the matching efficiency and matching accuracy effectively;2)the performance of existing algorithms to process trajectory data with low sampling rate is still to be improved;3)most existing algorithms are very sensitive to noise data.To solve the above problems,this paper makes the following contributions.(1)A fast algorithm based on hidden Markov model is proposed for mapmatching high sampling rate GPS trajectories.The main idea of the proposed algorithm is as follows.Firstly,a trajectory simplification method based on sliding window is proposed to filter redundant and parts of noise points in the raw trajectories.Then,an adaptive candidate segment search strategy is proposed to compute the candidate set for each GPS point.Finally,the HMM is used to find the optimal path.In the experiment,two sets of real high sampling rate trajectory datasets are used to verify the performance of the algorithm.The experimental results show that the running time of the algorithm is 4?5 times faster than that of the traditional HMM-based algorithm while achieving similar levels of matching accuracy.(2)An improved map matching algorithm based on interactive voting is proposed for low sampling rate GPS trajectories.The main idea of the proposed algorithm is as follows.Firstly,the proposed algorithm takes into account not only the spatial distances between sampling points,road topology and road segment speed limits,but also the reliable and real-time moving direction and speed of each GPS point to improve the matching accuracy.Secondly,three constraint conditions are introduced to improve the matching accuracy and efficiency via cutting off some candidate roads and transition paths.Two sets of real data sets are used in the experiment to compare the proposed algorithm with the existing IVMM and AIVMM algorithms.Experimental results show that the proposed algorithm outperforms the two comparative algorithms in terms of matching accuracy and efficiency.