Research on vehicle trajectory matching method based on improved HMM

Abstract

Aiming at the problem that traditional vehicle trajectory matching algorithms based on hidden Markov model(HMM) cannot have both accuracy and time efficiency in complex and special road sections, a vehicle trajectory matching method based on improved HMM modeling was proposed. In the determination of candidate road sections, grid index was generated to improve the overall retrieval efficiency. The improved HMM model integrated heading angle factors in the calculation of launch probability, considered the deviation effect caused by vehicle speed on heading angle, and set empirical factors for adjustment. At the same time, considering the factors such as the excessive error of the observation value before and after and the curve section, the actual travel distance of the vehicle within the unit sampling interval was used instead of the observation distance value to ensure the accuracy of the calculation of the transfer probability. Finally, the measured data was used to conduct experiments to verify the performance of the improved algorithm. The experimental results indicated that the matching accuracy of this method was about 94.0%, which was 2.8% higher than that of the traditional HMM trajectory matching method. It also had certain advantages in improving time efficiency and matching accuracy of complex road sections. The single-point matching time was reduced by about 0.9 ms, suitable for matching under complex road conditions such as intersections, overpasses, and parallel sections.

Keywords

vehicle trajectory / map-matching / hidden Markov model (HMM) / road network

References

[1] GAO W C, LI GUO L, TA N . Overview of road network matching algorithms. Journal of Software, 2018, 29(2): 225-250.

[2] FAN J C, FU C, STEWART K, et al. Using big GPS trajectory data analytics for vehicle Miles traveled estimation. Transportation Research Part C: Emerging Technologies, 2019, 103: 298-307.

[3] YU J, YANG Q, LU J F, et al. Advanced map matching algorithms: a survey and trend. Acta Electronica Sinica, 2021, 49(9): 1818-1829.

[4] WHITE C E, BERNSTEIN D, KORNHAUSER A L. Some map matching algorithms for personal navigation assistants. Transportation Research Part C: Emerging Technologies, 2000, 8(1-6): 91-108.

[5] BI J, ZHU Y, CHENG Y. A comprehensive map matching algorithm based on curve fitting and network topology. Journal of Transport Information and Safety, 2014, 32(6): 127-131.

[6] TENG Z J, ZHANG Y, LI H T. Improved D-S evidence theory map matching algorithm under the background of intersecting roads. Journal of Chinese Inertial Technology, 2020, 28(3): 380-385.

[7] TENG Z J, ZHANG Y, LI H T, et al. Adaptive D-S evidence theory map matching algorithm for complex road networks. Journal of Jilin University (Engineering and Technology Edition), 2021, 51(2): 524-530.

[8] SU H B, WANG G Z, WANG J D. Map matching algorithm based on fuzzy neural network. Journal of University of Science and Technology Beijing, 2012, 34(1): 43-47.

[9] LU J P, LUO Y T, HUANG Z S, et al. An information fusion map matching method based on ranking learning. Journal of Zhejiang University (Science Edition), 2020, 47(1): 27-35.

[10] MOHAMED R, ALY H, YOUSSEF M. Accurate real-time map matching for challenging environments. IEEE Transactions on Intelligent Transportation Systems, 2017, 18(4): 847-857.

[11] ZHOU C, YUAN J Z, LIU H Z, et al. Survey of map matching algorithm for intelligent transport system. Computer Science, 2015, 42(10): 1-6.

[12] NEWSON P, KRUMM J. Hidden Markov map matching through noise and sparseness//The 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, November 4-6, 2009, Seattle Washington, US. New York: ACM. 2009: 336-343.

[13] LUO A, CHEN S H, XU B. Enhanced map-matching algorithm with a hidden Markov model for mobile phone positioning. ISPRS International Journal of Geo-Information, 2017, 6(11): 327.

[14] HSUEH Y, CHEN H, HUANG W. A hidden Markov model-based map-matching approach for low-sampling-rate GPS trajectories//2017 IEEE 7th International Symposium on Cloud and Service Computing(SC2), November 22-25, 2017, Kanazawa, Japan, New York: IEEE, 2017: 271-274.

[15] YUAN J, ZHENG Y, ZHANG C, et al. An interactive-voting based map matching algorithm//2010 Eleventh International Conference on Mobile Data Managemen, May 23-26, Kansas City, MO, USA, New York: IEEE, 2010: 43-52.

[16] SONG C B, YAN X F, STEPHEN N, et al. Hidden Markov model and driver path preference for floating car trajectory map matching. IET Intelligent Transport Systems, 2018, 12(10): 1433-1441.

[17] WU G, QIU Y J, WANG G R. Map matching algorithm based on hidden Markov model and genetic algorithm. Journal of Northeastern University (Natural Science), 2017, 38(4): 472-475.

[18] CHE M L, WANG Y L, ZHANG C, et al. An enhanced hidden Markov map matching model for floating car data. Sensors, 2018, 18(6): 1758.

[19] GOH C Y, DAUWELS J, MITROVIC N, et al. Online map-matching based on hidden Markov model for real-time traffic sensing applications//International IEEE Conference on Intelligent Transportation Systems, September 16-19, 2012, Anchorage, AK, USA. New York: IEEE, 2012: 776-781.

[20] JAGADEESH G R, SRIKANTHAN T. Online map-matching of noisy and sparse location data with hidden Markov and route choice models. IEEE Transactions on Intelligent Transportation Systems, 2017, 18(9): 2423-2434.

[21] TAGUCHI S, KOIDE S, YOSHIMURA T. Online map matching with route prediction. IEEE Transactions on Intelligent Transportation Systems, 2019, 20(1): 338-347.

[22] YIN J C, WU F, LI A P, et al. Trajectory matching method considering speed and heading information. Geomatics and Information Science of Wuhan University, 2021, 46(11): 1774-1781.

[23] KONG X F, YANG J W. A scenario-based map-matching algorithm for complex urban road network. Journal of Intelligent Transportation Systems, 2019, 23(6): 617-631.

[24] MAAREF M, KASSAS Z M. Ground vehicle navigation in GNSS-Challenged environments using signals of opportunity and a closed-loop map-matching approach. IEEE Transactions on Intelligent Transportation Systems, 2020, 21(7): 2723-2738.