Map Matching For GPS Trajectories Based On Trajectory Segmentation And Clustering

The trajectory data generated by GPS and other positioning equipment has the advantages of easy collection and low cost,and has been widely used in many fields.The trajectory data can be used in many scenarios in life such as road network updates,traffic flow prediction.However,due to the presence of noise data in the trajectory data,the original trajectory data does not match well with the road networks.At the same time,the trajectory data has different sampling rates.The high sampling rate trajectories are with more information compared to the ones with low sampling rates.Therefore,for the trajectories of different sampling rates,a specific map matching algorithm is required.In response to the above problems,this thesis conducts the following research:(1)A Hidden Markov Model based on trajectory segmentation,called Segment-based Hidden Markov Model(SHMM),is proposed for map matching of high sampling rate trajectories.The matching algorithm divides the original trajectory into sub-trajectory segments.Then,each sub-trajectory segment is matched to avoid repeated matching of trajectory points,while reducing the impact of noise data on the matching accuracy.Finally,compared with baseline experiments,the SHMM algorithm proposed in this paper improves the matching precision,recall and time by 2%,1% and 5ms.(2)This thesis proposes a low sampling rate trajectory clustering algorithm based on similar paths,which is different from the traditional trajectory data clustering algorithm.This algorithm calculates the similarity between low sampling rate trajectories by using the LCSS-based method to avoid calculating the geometry distance between trajectories.Compared with traditional clustering algorithms using geometric distance to measure the similarity between the trajectories,the clustering algorithm in this paper improve the precision and recall by 4.7% and 8.6%.(3)Map matching algorithm based on similar path clustering for low-sampling-rate GPS trajectories,Trajectory Collaboration based Map Matching(CMM),is proposed.This algorithm uses the low-sampling-rate trajectory clustering algorithm proposed in this paper.The algorithm can complement each other to get higher matching accuracy.The effectiveness of the matching algorithm is proved by experiments.Compared with the baseline experiment,the CMM algorithm has improved,precision,recall and time by 1%,8% and 25.4ms.In summary,the map matching algorithm proposed in this thesis for the high sampling rate trajectory and the clustering and matching algorithm for the low sampling rate trajectory can achieve higher matching accuracy with higher efficiency than the comparative experiment,which solves the existing problem.The shortcomings in the map matching algorithm also prove that the research in this thesis has great practical significance.