基于门控循环单元模型的在线路网匹配算法

doi:10.3969/j.issn.1000-5641.201921022

华东师范大学学报（自然科学版） ›› 2020, Vol. 2020 ›› Issue (6): 63-71.doi: 10.3969/j.issn.1000-5641.201921022

基于门控循环单元模型的在线路网匹配算法

陈良健, 许建秋

南京航空航天大学计算机科学与技术学院, 南京 211106

收稿日期:2019-06-10 发布日期:2020-12-01
通讯作者: 许建秋, 男, 副教授, 硕士生导师, 研究方向为移动对象数据库. E-mail: jianqiu@nuaa.edu.cn E-mail:jianqiu@nuaa.edu.cn
基金资助:
国家自然科学基金(61972198)；江苏省自然科学基金(BK20191273)

Online map matching algorithm based on the gated recurrent unit model

CHEN Liangjian, XU Jianqiu

College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China

Received:2019-06-10 Published:2020-12-01

摘要/Abstract

摘要： 路网匹配是道路网轨迹数据分析领域的一项关键技术, 一个快速且准确的路网匹配算法能够为上层应用提供良好的技术支持. 随着轨迹数据的爆炸式增长, 现有的在线路网匹配算法存在延时的现象, 尤其是在低频轨迹数据的环境下, 无法快速地对轨迹数据进行路网匹配. 神经网络和深度学习的发展为解决这些问题提供了新的方法. 提出了一种利用门控循环单元(Gated Recurrent Unit, GRU)模型快速定位轨迹采样点的候选路段、从而加速在线路网匹配计算的方法, 并将此方法和最新的在线路网匹配算法进行了实验比较. 结果表明, 基于GRU模型的在线路网匹配算法能够有效地加快匹配过程, 提高匹配效率.

关键词: 在线路网匹配, 移动对象, 门控循环单元模型

Abstract: Map matching is a key technology in the field of road network trajectory data analysis. A fast and accurate map matching algorithm can provide good technical support for upper-layer applications. With the explosive growth of trajectory data, existing online map matching algorithms experience a delay phenomenon; in particular, in the context of low-frequency trajectory data, it is impossible to quickly perform map matching on trajectory data. The development of neural networks and deep learning provide new methods for solving these problems. This paper uses the gated recurrent unit(GRU) model to quickly locate candidate segments of trajectory sampling points, thus accelerating the calculation process for online map matching. The proposed method is experimentally compared to the latest online map matching algorithm; the results show that the GRU-based online map matching algorithm can effectively speed-up the matching process and improve matching efficiency.

Key words: online map matching, moving object, gated recurrent unit (GRU) model

中图分类号:

TP392

陈良健, 许建秋. 基于门控循环单元模型的在线路网匹配算法[J]. 华东师范大学学报（自然科学版）, 2020, 2020(6): 63-71.

CHEN Liangjian, XU Jianqiu. Online map matching algorithm based on the gated recurrent unit model[J]. Journal of East China Normal University(Natural Science), 2020, 2020(6): 63-71.

参考文献

[1] QUDDUS M A, OCHIENG W Y, NOLAND R B. Current map-matching algorithms for transport applications: State-of-the art and future research directions [J]. Transportation Research Part C: Emerging Technologies, 2007, 15(5): 312-328
[2] TAGUCHI S, KOIDE S, YOSHIMURA T. Online map matching with route prediction [J]. IEEE Transactions on Intelligent Transportation Systems, 2018, 20(1): 338-347
[3] WHITE C E, BERNSTEIN D, KORNHAUSER A L. Some map matching algorithms for personal navigation assistants [J]. Transportation Research Part C: Emerging Technologies, 2000(8): 91-108
[4] QUDDUS M, OCHIENG W Y, ZHAO L, et al. A general map matching algorithm for transport telematics applications [J]. GPS Solutions, 2003, 7(3): 157-167
[5] BRAKATSOULAS S, PFOSER D, SALAS R, et al. On map-matching vehicle tracking data [C]//Proceedings of the 31st International Conference on Very Large Data Bases. VLDB Endowment, 2005: 853-864.
[6] SCHÜSSLER N, AXHAUSEN K W. Map matching of GPS traces on high-resolution navigation networks using the multiple hypothesis technique(MHT), Working Paper 568 [R]. Zurich: Institute for Transport Planning and System (IVT), 2009.
[7] KIM W, JEE G I, LEE J G. Efficient use of digital road map in various positioning for ITS [C]// Position Location and Navigation Symposium. IEEE, 2000: 170-176. DOI: 10.1109/PLANS.2000.838299
[8] YIN Y F, SHAH R R, ZIMMERMANN R. A general feature-based map matching framework with trajectory simplification [C]// Proceedings of the 7th ACM SIGSPATIAL International Workshop on GeoStreaming. ACM, 2016: Article number 7. DOI: 10.1145/3003421.3003426.
[9] 高文超, 李国良, 塔娜. 路网匹配算法综述 [J]. 软件学报, 2018, 29(2): 225-250
[10] TA N, WANG J Q, LI G L. Map Matching Algorithms: An Experimental Evaluation [C]// Web and Big Data, APWeb-WAIM 2018, Lecture Notes in Computer Science, vol 10988. Cham: Springer, 2018: 182-198.
[11] NEWSON P, KRUMM J. Hidden Markov map matching through noise and sparseness [C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM. 2009: 336-343.
[12] VITERBI A J. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm [G]//IISc Centenary Lecture Series, The Foundations of the Digital Wireless World. Singapore: World Scientific Publishing Co. Pte. Ltd., 2009: 41-50.
[13] WANG G F, ZIMMERMANN R. Eddy: An error-bounded delay-bounded real-time map matching algorithm using HMM and online Viterbi decoder [C]// 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems(ACM SIGSPATIAL 2014). ACM, 2014: 33-42. DOI: 10.1145/2666310.2666383.
[14] MOHAMED R, ALY H, YOUSSEF M. Accurate real-time map matching for challenging environments [J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 18(4): 847-857
[15] HOU X T, LUO L B, CAI W T, et al. Fast online map matching for recovering travelling routes from low-sampling GPS data [C]//2018 IEEE SmartWorld, Ubiquitous Intelligence and Computing, Advanced and Trusted Computing, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People and Smart City Innovation. IEEE, 2018: 917-924. DOI: 10.1109/SmartWorld.2018.00165.
[16] GOH C Y, DAUWELS J, MITROVIC N, et al. Online map-matching based on hidden Markov model for real-time traffic sensing applications [C]//2012 15th International IEEE Conference on Intelligent Transportation Systems. IEEE, 2012: 776-781. DOI: 10.1109/ITSC.2012.6338627.
[17] HUNTER T, ABBEEL P, BAYEN A. The path inference filter: Model-based low-latency map matching of probe vehicle data [J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 15(2): 507-529
[18] SALVADOR M M, BUDKA M, QUAY T. Automatic transport network matching uisng deep learning [J]. Transportation Research Procedia, 2018, 31: 67-73. DOI: 10.1016/j.trpro.2018.09.053.
[19] HAYKIN S. Neural Networks and Learning Machines [M]. 3rd ed. Beijing: China Machine Press, 2009.
[20] CHO K, VAN MERRIENBOER B, GULCEHRE C, et al. Learning phrase representations using RNN encoder-decoder for statistical machine translation [EB/OL]. (2014-09-03)[2019-05-02]. https://arxiv.org/abs/1406.1078.
[21] CHUNG J Y, GULCEHRE C, CHO K H, et al. Empirical evaluation of gated recurrent neural networks on sequence modeling [EB/OL]. (2014-12-11)[2019-05-02]. https://arxiv.org/abs/1412.3555.
[22] YUAN J Y, WANG H J, LIN C J, et al. A novel GRU-RNN network model for dynamic path planning of mobile robot [J]. IEEE Access, 2019(7): 15140-15151

基于门控循环单元模型的在线路网匹配算法

Online map matching algorithm based on the gated recurrent unit model

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价