The Research On Dynamic Parallel Map Matching Algorithm For Complicated Urban Road Network

Vehicle navigation is an important component of the urban intelligent transportation system.The intelligent transportation system is greatly influenced by navigation positioning's accuracy and real-time response.However,the positioning device itself in the vehicle navigation system and external factors,the data collected may not be accurate in positioning.At the same time,along with the complexity and diversification of urban roads,the rapid increase in the number of motor vehicles and other factors,the accuracy and real-time nature of vehicle trajectory data map matching has been severely challenged.Accroding to the characteristics of GIS road network data and GPS vehicle trajectory data of the complicated urban road network in the intelligent traffic system,this paper proposes dynamic parallel algorithms of map matching to revise the raw and inaccurate trajectory data.These algorithms base on the "point-to-line" geometric map matching theory,and they are propsed to achieve the candidate road segments and determine weighting values.By using these algorithms,the large trajectory data has achieved efficiently accurate map matching result.These map matching algorithms cost less and are easy to be realized,so it can be widely deployed in the vehicle navigation system.The main works of this paper are as follows:(1)Based on the characteristics of GPS trajectory data and GIS road network data,the corresponding data preprocessing method was proposed.A cleaning algorithm was proposed to eliminate abnormal GPS trajectory data.Format transformation and key information extraction were proposed to obtain GIS road network data easily and quickly.The road network data was modeled and a grid coordinate map was designed.(2)A dynamic geometric weight-based map matching algorithm was proposed for complicated urban road networks.The algorithm selected a road segment by establishing a dynamic area.The weighting summation values were established dynamically based on various factors including vehicle speed,running distance and road density,which effectively improved the accuracy of map matching process.(3)Based on the theory of parallel computing,a dynamic parallel algorithm of map matching algorithm for large scale GPS trajectory data was proposed.The large-scale trajectory data was partitioned to achieve data parallel computing.In order to reduce the burden cost of traversing and loading the global map,a tree-like grid index structure was designed to improve the search speed of the target candidate segment set.According to this structure,the large scale trajectory data effectively regulated and matched on the map.The results showed that the data preprocessing method improved the efficiency and accuracy of the map matching data source,and the proposed map matching algorithm had improved matching performance compared to other algorithms.Therefore,these algorithms proposed in this paper were suitable for trajectory data matching and correction in complex urban road networks.