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