Research On Map Matching Algorithm Based On GPS Trajectory

Map matching,also known as road network matching or trajectory matching,is the process of matching GPS trajectory data with map data to determine the actual path taken by a moving object.In recent years,with the development of the Internet of Things and internet technology,location-based services(LBS)based on geographic location information have become a popular service.However,the acquisition of GPS trajectory data is not accurate due to factors such as positioning equipment and environment.Map matching can be used to address the accuracy and reliability issues of GPS position data in LBS applications.Currently,there are many map matching algorithms,but existing algorithms have some shortcomings,such as low matching accuracy in complex road situations and routing calculation time bottlenecks.Therefore,this thesis proposes a GPS trajectory-based map matching method that proposes a quadratic calculation to extract candidate points strategy,considers the multi-directional characteristics within the road,improves the accuracy of candidate point selection,and proposes a fast matching algorithm based on limited value pruning to reduce unnecessary routing calculation processes and improve matching efficiency.Finally,comparative experiments were conducted on a real trajectory dataset,and the results demonstrate that the map matching algorithm proposed in this thesis is efficient and accurate,and improves matching efficiency by 29.6% and accuracy by 2.2% compared to the comparative algorithm.The contributions of this thesis are summarized as follows:(1)For candidate point extraction in complex roads,this thesis proposes a strategy of determining candidate points through secondary calculations,considering distance and direction similarity,and adding a pre-selection point extraction process to improve matching accuracy.(2)To address the route calculation time bottleneck problem,this thesis proposes a fast matching algorithm based on a threshold pruning strategy(PFMM),introduces two pruning strategies,and uses an improved Dijkstra routing algorithm to reduce some route calculations that do not affect the matching results,thus improving matching efficiency.In addition,outlier filtering and stop point detection methods are used to process the initial trajectory,filter out error trajectory points,cluster dense trajectory points,and reduce the number of GPS points in the trajectory input to reduce computational costs.(3)To improve algorithm applicability,a real-time PFMM algorithm is implemented using a variable sliding window method to receive trajectory flow input for real-time matching and output local matching results,suitable for real-time applications such as vehicle navigation.