Online map matching algorithm based on the gated recurrent unit model

doi:10.3969/j.issn.1000-5641.201921022

Abstract

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

CLC Number:

TP392

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.

References

[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