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

沈敬伟; 周廷刚; 张弘弢

doi:10.3969/j.issn.0258-2724.2015.03.018

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

doi: 10.3969/j.issn.0258-2724.2015.03.018

基金项目:

国家自然科学基金资助项目(41301417, 41201467)

重庆市基础与前沿计划资助项目(cstc2014jcyjA20017)

四川省应急测绘与防灾减灾工程技术研究中心开放基金资助项目(K2015B015)

详细信息

作者简介:
沈敬伟(1984-),男,副教授,博士,研究方向为浮动车数据分析,E-mail:jingweigis@163.com

计量
- 文章访问数: 1060
- HTML全文浏览量: 55
- PDF下载量: 581
- 被引次数: 0
出版历程
- 收稿日期: 2014-12-03
- 刊出日期: 2015-06-25

A Map-Matching Algorithm Based on Improved AOE Network for Low Frequency Floating Car Data

摘要

摘要: 由于低频浮动车数据时间间隔较长,现有地图匹配方法难以满足低频浮动车数据地图匹配的要求.综合考虑浮动车数据轨迹点之间的整体特性,在局部和全局地图匹配算法的基础上,提出了一种基于改进AOE网络的低频浮动车数据地图匹配方法.首先,采用相交分析判断GPS点缓冲区和候选路段的关系,以获取候选路段和候选匹配点;其次,基于四叉树空间索引和Dijkstra算法,获取候选匹配点之间的最短路径;第三,设计了一种改进AOE网络,提出了基于改进AOE网络的最短可达路径算法,以获取最终的地图匹配点;最后,对改进AOE网络的地图匹配算法进行评价,并通过实验分析了算法的时间效率和正确率.实验结果表明:基于改进AOE网络的地图匹配算法正确率为95.3%,程序执行总时间为96.8 s. 其正确率分别比点到线的局部地图匹配方法和基于弱Frchet距离的全局地图匹配方法的正确率高13.6%和2.8%.
- 浮动车数据 /
- 改进AOE网络 /
- 地图匹配算法 /
- 最短路径
Abstract: 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.
- floating car data /
- improved AOE network /
- map-matching algorithm /
- shortest path

HTML全文

参考文献(38)

GUO Diansheng, ZHU Xi, JIN Hai, et al. Discovering spatial patterns in origin-destination mobility data

LI Jun, QIN Qiming, XIE Chao, et al. Integrated use of spatial and semantic relationships for extracting road networks from floating car data

[J]. Transactions in GIS, 2012, 16(3): 411-429.

CASTRO P S, ZHANG D, LI S. Urban traffic modelling and prediction using large scale taxi GPS traces

[J]. International Journal of Applied Earth Observation and Geoinformation, 2012, 19: 238-247.

LI Qingquan, ZENG Zhe, ZHANG Tong, et al. Path-finding through flexible hierarchical road networks: an experiential approach using taxi trajectory data

BRAKATSOULAS S, PFOSER D, SALAS R, et al. On map-matching vehicle tracking data

WU Dongdong, ZHU Tongyu, LV Weifeng, et al. A heuristic map-matching algorithm by using vector-based recognition

[C]//Proceedings of the 10th International Conference on Pervasive Computing. Berlin: Springer, 2012: 57-72.

MARCHAL F, HACKNEY J, AXHAUSEN K W. Efficient map matching of large global positioning system data sets: tests on speed-monitoring experiment in Zrich

[J]. International Journal of Applied Earth Observation and Geoinformation, 2011, 13: 110-119.

王志建,王力,汪健. 基于拓扑判断的海量GPS数据延时地图匹配算法

李清泉,胡波,乐阳. 一种基于约束的最短路径低频浮动车数据地图匹配算法

王美玲,程林. 浮动车地图匹配算法研究

[C]//Proceedings of the 31st International Conference on Very Large Data Bases. Trondheim: VLDB Endowment, 2005: 853-864.

CHEN Biyu, YUAN Hui, LI Qingquan, et al. Map-matching algorithm for large-scale low-frequency floating car data

ALT H, EFRAT A, ROTE G, et al. Matching planar maps

[C]//Proceedings of the International Multi-Conference on Computing in the Global Information Technology(ICCGI 2007). Washington: IEEE Computer Society, 2007: 18.

唐进君,曹凯. 基于分层模糊控制的地图匹配算法

[J]. Transportation Research Record: Journal of the Transportation Research Board, 2005, 1935: 93-100.

WENK C, SALAS R, PFOSER D. Addressing the need for map-matching speed: localizing global curve-matching algorithms

LOU Yin, ZHANG Chengyang, ZHENG Yu, et al. Map-matching for low-sampling-rate GPS trajectories

[J]. 西南交通大学学报,2012,47(5): 861-866. WANG Zhijian, WANG Li, WANG Jian. Delay map matching algorithm of mass GPS data based on topological judgment

LI Jun, XIE Lianghui, LAI Xinjun. Route reconstruction from floating car data with low sampling rate based on feature matching

[J]. Journal of Southwest Jiaotong University, 2012, 47(5): 861-866.

BIERLAIRE M, CHEN J, NEWMAN J. A probabilistic map matching method for smartphone GPS data

[J]. 武汉大学学报:信息科学版,2013,38(7): 805-809. LI Qingquan, HU Bo, YUE Yang. Flowing car data map-matching based on constrained shortest path algorithm

[J]. Geomatics and Information Science of Wuhan University, 2013, 38(7): 805-809.

[J]. 测绘学报,2012,41(1): 133-138. WANG Meiling, CHENG Lin. Study on map-matching algorithm for floating car

[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(1): 133-138.

[J]. International Journal of Geographical Information Science, 2014, 28(1): 22-38.

[J]. Journal of Algorithms, 2003, 49: 262-283.

[J]. 山东大学学报:工学版,2008,38(4): 42-48. TANG Jinjun, CAO Kai. Hierarchical fuzzy controller based map-matching algorithm

[J]. Journal of Shandon University: Engineering Science, 2008, 38(4): 42-48.

[C]// Proceedings of the 18th International Conference on Scientific and Statistical Database Management (SSDBM'06). Washington: IEEE Computer Society, 2006: 379-388.

[C]//Proceedings of the International Conference on Advances in Geographic Information Systems. New York: Association for Computing Machinery, 2009: 352-361.

[J]. Research Journal of Applied Sciences, Engineering and Technology, 2013, 6(12): 2153-2158.

[J]. Transportation Research Part C: Emerging Technologies, 2013, 26: 78-98.

施引文献

附加材料(0)

访问统计