Abstract
Map matching (MM) aims to align GPS trajectory with the actual roads on a map that vehicles pass through, essential for applications like trajectory search and route planning. The Hidden Markov Model (HMM) is commonly employed for online MM due to its interpretability and suitability for low GPS sampling rates. However, in complex urban areas with notable GPS drift, existing HMM methods face efficiency and accuracy challenges due to the use of a uniform road search radius and imprecise real-time road condition understanding. This paper proposes an improved HMM method using multiple trajectory types based on the following key ideas: Vehicle trajectories can be divided into two types: fixed trajectories (e.g., bus) and free trajectories (taxis, private cars). The relatively accurate information of fixed trajectories can help us more accurately measure the error distribution, as well as accurate road conditions. The novelty of our approach lies in the following aspects: i) Using fixed bus trajectories to estimate region-specific GPS error distribution, optimizing observation probabilities and reducing candidate road search costs. ii) Utilizing real-time fixed trajectories for accurate, real-time road state estimation, enhancing dynamic state transition probabilities in HMM. Empirical analysis, based on real bus and taxi trajectories in Shenzhen over half a year, demonstrate that our method outperforms existing methods in terms of map matching efficiency and accuracy.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
An, Q., Feng, Z., Chen, S., Huang, K.: A green self-adaptive approach for online map matching. IEEE Access 6, 51456–51469 (2018)
Chao, P., Xu, Y., Hua, W., Zhou, X.: A survey on map-matching algorithms. In: Borovica-Gajic, R., Qi, J., Wang, W. (eds.) ADC 2020. LNCS, vol. 12008, pp. 121–133. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-39469-1_10
Chen, R., Yuan, S., Ma, C., Zhao, H., Feng, Z.: Tailored hidden Markov model: a tailored hidden Markov model optimized for cellular-based map matching. IEEE Trans. Industr. Electron. 69(12), 13818–13827 (2021)
Guo, D., Wang, H.: Automatic region building for spatial analysis. Trans. GIS 15, 29–45 (2011)
Hu, G., Shao, J., Liu, F., Wang, Y., Shen, H.T.: If-matching: towards accurate map-matching with information fusion. IEEE Trans. Knowl. Data Eng. 29(1), 114–127 (2016)
Knapen, L., Bellemans, T., Janssens, D., Wets, G.: Likelihood-based offline map matching of GPS recordings using global trace information. Transp. Res. Part C Emerg. Technol. 93, 13–35 (2018)
Lou, Y., Zhang, C., Zheng, Y., Xie, X., Wang, W., Huang, Y.: Map-matching for low-sampling-rate GPS trajectories. In: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 352–361 (2009)
Mohamed, R., Aly, H., Youssef, M.: Accurate real-time map matching for challenging environments. IEEE Trans. Intell. Transp. Syst. 18(4), 847–857 (2016)
Newson, P., Krumm, J.: Hidden Markov map matching through noise and sparseness. In: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 336–343 (2009)
Ozdemir, E., Topcu, A.E., Ozdemir, M.K.: A hybrid hmm model for travel path inference with sparse GPS samples. Transportation 45, 233–246 (2018)
Taguchi, S., Koide, S., Yoshimura, T.: Online map matching with route prediction. IEEE Trans. Intell. Transp. Syst. 20(1), 338–347 (2018)
Xu, M., Du, Y., Wu, J., Zhou, Y., et al.: Map matching based on conditional random fields and route preference mining for uncertain trajectories. Math. Probl. Eng. 2015 (2015)
Yuan, J., Zheng, Y., Zhang, C., Xie, X., Sun, G.Z.: An interactive-voting based map matching algorithm. In: 2010 Eleventh International Conference on Mobile Data Management, pp. 43–52. IEEE (2010)
Zhang, D., Dong, Y., Guo, Z.: A turning point-based offline map matching algorithm for urban road networks. Inf. Sci. 565, 32–45 (2021)
Zhang, D., Guo, Z., Guo, F., Dong, Y.: An offline map matching algorithm based on shortest paths. Int. J. Geogr. Inf. Sci. 35(11), 2238–2261 (2021)
Zhang, Y., He, Y.: An advanced interactive-voting based map matching algorithm for low-sampling-rate GPS data. In: 2018 IEEE 15th International Conference on Networking, Sensing and Control (ICNSC), pp. 1–7. IEEE (2018)
Zhao, K., et al.: Deepmm: deep learning based map matching with data augmentation. In: Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 452–455 (2019)
Acknowledgement
This study was funded by the National Natural Science Foundation of China (No. 62372443, No. 62376263), Shenzhen Industrial Application Projects of undertaking the National key R & D Program of China (No. CJGJZD20210408091600002).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Song, Y., Zhao, J., Gao, X., Zhang, F., Ye, K. (2024). Enhanced HMM Map Matching Model Based on Multiple Type Trajectories. In: Yang, DN., Xie, X., Tseng, V.S., Pei, J., Huang, JW., Lin, J.CW. (eds) Advances in Knowledge Discovery and Data Mining. PAKDD 2024. Lecture Notes in Computer Science(), vol 14649. Springer, Singapore. https://doi.org/10.1007/978-981-97-2262-4_28
Download citation
DOI: https://doi.org/10.1007/978-981-97-2262-4_28
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-2264-8
Online ISBN: 978-981-97-2262-4
eBook Packages: Computer ScienceComputer Science (R0)