基于路网复杂度分区的轨迹分段地图匹配方法

doi:10.3778/j.issn.1002-8331.2306-0271

摘要/Abstract

摘要： 针对现有大多数地图匹配方法在城市复杂环境下难以有效平衡匹配速度和精度的问题，提出了一种基于路网复杂度分区的轨迹分段地图匹配方法。该方法包括路网分区和轨迹分段匹配两个部分。通过构建的路网复杂度分区模型将路网划分为复杂区域和非复杂区域；对复杂区域内的轨迹段采用改进的隐马尔可夫模型进行匹配，非复杂区域内的轨迹段采用基于几何拓扑的快速匹配模型进行匹配；将不同区域内匹配的轨迹段进行拼接，得到完整轨迹的匹配结果。为得到路网复杂度分区模型的最优参数，进行了11组不同参数设置的对比实验，并将最终结果与ST-matching和传统隐马尔可夫模型两种地图匹配方法匹配的结果进行对比。结果表明，在三个数据集的匹配准确率均在96%以上，比其他两种对比算法匹配时间减少了60%，在保证匹配准确率的前提下有效提升了匹配效率。

关键词: 地图匹配, 路网分区, 轨迹分段, 隐马尔可夫模型, 几何拓扑

Abstract: In order to solve the problem that most of the existing map matching methods are difficult to effectively balance the matching speed and accuracy in the complex urban environment, a trajectory segmentation map matching method based on the complexity partition of the road network is proposed. The method includes two parts：road network partition and trajectory segment matching. The road network is divided into complex areas and non-complex areas through the constructed road network complexity partition model. Then, the trajectory segments in the complex areas are matched using the improved hidden Markov model, and the trajectory segments in the non-complex areas are matched based on the fast matching model of geometric topology is used for matching. Finally, the matched trajectory segments in different regions are spliced to obtain the matching result of the complete trajectory. In order to obtain the optimal parameters of the road network complexity partition model, 11 sets of comparative experiments with different parameter settings are carried out, and the final results are compared with the matching results of the ST-matching algorithm and the traditional hidden Markov model. The results show that the matching accuracy of the method in this paper is above 96% in the three data sets, and the matching time is reduced by 60% compared with the other two comparison algorithms, which effectively improves the matching efficiency under the premise of ensuring the matching accuracy.

Key words: map matching, road network partition, trajectory segmentation, hidden Markov model, geometric topology

王庆庆, 郭杜杜, 王洋, 周飞, 秦音. 基于路网复杂度分区的轨迹分段地图匹配方法[J]. 计算机工程与应用, 2024, 60(15): 261-269.

WANG Qingqing, GUO Dudu, WANG Yang, ZHOU Fei, QIN Yin. Trajectory Segment Map Matching Method Based on Road Network Complexity Partition[J]. Computer Engineering and Applications, 2024, 60(15): 261-269.

参考文献

[1] 高文超, 李国良, 塔娜. 路网匹配算法综述[J]. 软件学报, 2018, 29(2): 225-250.
GAO W C, LI G L, TA N. Survey of map matching algorithms[J]. Journal of Software, 2018, 29(2): 225-250.
[2] ZHANG C, ZHU F, WANG X, et al. Taxi demand prediction using parallel multi-task learning model[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(2): 794-803.
[3] ZHONG Z, LUO Y, LIANG W. STGM: vehicle trajectory prediction based on generative model for spatial-temporal features[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(10): 18785-18793.
[4] ZHENG H, LI X, LI Y, et al. GCN-GAN: integrating graph convolutional network and generative adversarial network for traffic flow prediction[J]. IEEE Access, 2022, 10: 94051-94062.
[5] CUI G, BIAN W, WANG X. Hidden Markov map matching based on trajectory segmentation with heading homogeneity[J]. GeoInformatica, 2021, 25: 179-206.
[6] 于娟, 杨琼, 鲁剑锋, 等. 高级地图匹配算法: 研究现状和趋势[J]. 电子学报, 2021, 49(9): 1818-1829.
YU J, YANG Q, LU J F, et al. Advanced map matching algorithms: a survey and trends[J]. Acta Electronica Sinica, 2021, 49(9): 1818-1829.
[7] 陈菲, 邹涛, 王伦. 改进的基于投影的地图匹配算法[J]. 计算机工程与应用, 2011, 47(31): 242-244.
CHEN F, ZOU T, WANG L. Improved projection-based map matching algorithm[J]. Computer Engineering and Applications, 2011, 47(31): 242-244.
[8] 汪小寒, 何增宇, 胡王悟, 等. 复杂路段的角度差和后续点地图匹配方法[J]. 计算机应用研究, 2022, 39(2): 379-384.
WANG X H, HE Z Y, HU W W, et al. Map matching method for complex road sections via difference and subsequent points[J]. Application Research of Computers, 2022, 39(2): 379-384.
[9] HASHEMI M, KARIMI H A. A weight-based map-matching algorithm for vehicle navigation in complex urban networks[J]. Journal of Intelligent Transportation Systems, 2016, 20(6): 573-590.
[10] 宋縯蛟, 周佳悦, 王龙浩, 等. 采用R树和轨迹分段的HMM高效地图匹配方法[J]. 系统仿真学报, 2023, 35(2): 339-349.
SONG Y J, ZHOU J Y, WANG L H, et al. The efficient HMM map matching using R-tree and trajectory segmentation[J]. Journal of System Simulation, 2023, 35(2): 339-349.
[11] DOGRAMADZI M, KHAN A. Accelerated map matching for GPS trajectories[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 23(5): 4593-4602.
[12] XIONG Z, LI B, LIU D. Map-matching using hidden Markov model and path choice preferences under sparse trajectory[J]. Sustainability, 2021, 13(22): 12820.
[13] 滕志军, 曲兆强, 何义昌, 等. 基于初始位置的高速公路快速地图匹配算法[J]. 中国惯性技术学报, 2017, 25(4): 461-465.
TENG Z J, QU Z Q, HE Y C, et al. Fast map-matching algorithm for highway based on initial position[J]. Journal of Chinese Inertial Technology, 2017, 25(4): 461-465.
[14] 盛彩英, 席唱白, 钱天陆, 等. 浮动车轨迹点地图匹配及插值算法[J]. 测绘科学, 2019, 44(8): 106-112.
SHENG C Y, XI C B, QIAN T L, et al. Study of map-matching and interpolation algorithm of floating car data[J]. Science of Surveying and Mapping, 2019, 44(8): 106-112.
[15] LIU M, ZHANG L, GE J, et al. Map matching for urban high-sampling-frequency GPS trajectories[J]. International Journal of Geo-Information, 2020, 9(1): 31.
[16] 刘纪平, 张用川, 徐胜华, 等. 一种顾及道路复杂度的增量路网构建方法[J]. 测绘学报, 2019, 48(4): 480-488.
LIU J P, ZHANG Y C, XU S H, et al. An incremental construction method of road network considering road complexity[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(4): 480-488.
[17] 陆建, 王炜. 城市道路网规划指标体系[J]. 交通运输工程学报, 2004, 4(4): 62-67.
LU J, WANG W. Planning indices system of urban road network[J]. Journal of Traffic and Transportation Engineering, 2004, 4(4): 62-67.
[18] YUAN L, LI D, HU S. A map-matching algorithm with low-frequency floating car data based on matching path[J]. EURASIP Journal on Wireless Communications and Networking, 2018, 2018: 1-14.
[19] ZAIDI A S, SUDDLE M R. Global navigation satellite systems: a survey[C]//2006 International Conference on Advances in Space Technologies, 2006: 84-87.
[20] NEWSON P, KRUMM J. Hidden Markov map matching through noise and sparseness[C]//17th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems. New York: ACM, 2009: 336-343.
[21] SONG C, YAN X, STEPHEN N, et al. Hidden Markov model and driver path preference for floating car trajectory map matching[J]. IET Intelligent Transport Systems, 2018, 12(10): 1433-1441.
[22] HU Y, LU B. A hidden Markov model-based map matching algorithm for low sampling rate trajectory data[J]. IEEE Access, 2019, 7: 178235-178245.
[23] HUMMEL B. Map matching for vehicle guidance[M]//Dynamic and mobile GIS. [S.l.]: CRC Press, 2006: 211-222.
[24] KRIMM J, HORVITZ E, LECHNER J. Map matching with travel time constraints[R]. SAE Technical Paper, 2007.
[25] QI H, DI X, LI J. Map-matching algorithm based on the junction decision domain and the hidden Markov model[J]. PloS One, 2019, 14(5): e0216476.
[26] LOU Y, ZHANG C, ZHENG Y, et al. Map-matching for low-sampling-rate GPS trajectories[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2009: 352-361.
[27] 卢家品, 罗月童, 黄兆嵩, 等. 基于排名学习和多源信息的地图匹配方法[J]. 浙江大学学报 (理学版), 2020, 47(1): 27-35.
LU J P, LUO Y T, HUANG Z S, et al. An information fusion map matching method based on ranking learning[J]. Journal of Zhejiang University (Science Edition), 2020, 47(1): 27-35.