基于改进AOE网络的低频浮动车数据地图匹配算法

摘要

由于低频浮动车数据时间间隔较长，现有地图匹配方法难以满足低频浮动车数据地图匹配的要求．综合考虑浮动车数据轨迹点之间的整体特性，在局部和全局地图匹配算法的基础上，提出了一种基于改进AOE网络的低频浮动车数据地图匹配方法．首先，采用相交分析判断GPS点缓冲区和候选路段的关系，以获取候选路段和候选匹配点；其次，基于四叉树空间索引和Dijkstra算法，获取候选匹配点之间的最短路径；第三，设计了一种改进AOE网络，提出了基于改进AOE网络的最短可达路径算法，以获取最终的地图匹配点；最后，对改进AOE网络的地图匹配算法进行评价，并通过实验分析了算法的时间效率和正确率．实验结果表明：基于改进AOE网络的地图匹配算法正确率为95．3％，程序执行总时间为96．8 s．其正确率分别比点到线的局部地图匹配方法和基于弱Fréchet距离的全局地图匹配方法的正确率高13．6％和2．8％．%Due to the long time interval characteristic,the existing map-matching algorithms are not suitable for the low-frequency FCD (floating car data ). By analyzing local map-matching algorithms and global map-matching algorithms,and overall considering the FCD trace,a map-matching algorithm for low-frequency FCD based on improved AOE (activity on edge )network was proposed. Firstly, intersection analysis between a buffer around a GPS point and road segments was carried out to acquire the candidate road segments and candidate map-matching points. Secondly,quadtree spatial index and Dijkstra algorithm were introduced to obtain the shortest path between the adjacent candidate map-matching points. Thirdly,the improved AOE network was built to search the FCD shortest path and the map-matching points were acquired. Lastly,the proposed algorithm was evaluated in terms of time efficiency and accuracy. Results show that the accuracy of the proposed algorithm is 95. 3%,and the total program execution time is 96. 8 s. The accuracy is respectively 13. 6% and 2. 8% higher than that of the local map-matching algorithm and global map-matching algorithm.