Fast Map Matching Between Floating Car Data And Road Network And Its Application In Road Update

Nowadays,with the rapid development of positioning and navigation technology,the demand for the currency and accuracy of road network data is gradually increasing.Due to the frequent updating of road network data,it is necessary to select reasonable and efficient means to update it.Floating car data contains numerous road network information,which is suitable for real-time updating of road network data.How to extract and update road network information using massive track data is very important.Based on the analysis of the current situation and progress of the related research at home and abroad,considering the shortcomings of the existing research,we propose a fast map matching algorithm between the floating car trajectory and the road network and the road network data update algorithm.Our research content and innovation are as follows:(1)The preprocessing method of trajectory data is studied.The quality of the original trajectory data is uneven,and there is a lot of noise.First of all,noise reduction,track segmentation and other processing are carried out,and the road network data are divided based on intersection points,topological relations are reconstructed,and the spatial index is established.(2)The trajectory data thinning algorithm considering road intersection is proposed and Dijkstra algorithm is optimized.In the process of HMM matching between trajectory data and road network data,it is necessary to obtain candidate road segments for each trajectory point,and then the observation probability,transition probability,joint probability are calculated and Viterbi algorithm is carried out to obtain the best matching path.In order to improve the efficiency of the algorithm,consider the topological characteristics of the road network,and avoid the removal of the track data which carries important road network information,a trajectory data thinning algorithm considering road intersections is proposed.The calculation of transition probability involves a lot of calculation of the shortest path distance,which is the main reason for the low efficiency of the algorithm.We introduce the idea of heap optimization,and optimize the Dijkstra algorithm based on the rectangular restricted search area,so as to improve the overall matching efficiency.(3)Similar trajectory data recognition and fusion algorithm is studied.For the trajectory points that have not been successfully matched,they will be connected into traces and the similar traces are identified one by one.A similar matching pair recognition algorithm is proposed.For the similar matching pairs,Delaunay Triangles based on line constraints are constructed to extract the new roads and incrementally update the existing road network data.The credibility of the new roads can be obtained from the weight of their vertices.(4)The algorithm is implemented by C# programming language and experiments are carried out.The experimental results show that the algorithm can quickly match the trajectory data and road network data and extract the new road network data.