Abstract:

For it’s difficult to guarantee the accuracy and time efficiency of online map matching simultaneously, an improved online map matching algorithm based on the HMM model is proposed. Different from other global or local algorithms, the algorithm introduces reliable point to divide the trajectory, thus reducing the calculation of transition probability and the output delay of matching results. Also, the method of calculating the transmitting probability by combining distance factor and directional factor is proposed. The algorithm is verified using floating car trajectory data in Seattle. Experimental results show that the proposed algorithm outperforms the traditional HMM map matching algorithm both in accuray and time efficiency, which can meet the requirement of online map matching.

Key words: map matching, HMM, reliable point, transition probability, transmitting

摘要：

针对轨迹数据在线地图匹配中难以同时保障算法的准确率和时间效率的问题, 提出一种基于隐马尔科夫模型(HMM)改进的在线地图匹配算法, 并提出综合距离因素和方向因素计算发射概率的方法。与其他全局或者局部算法的不同之处在于, 改进的在线地图匹配算法引入可靠点进行轨迹分割, 减少了转移概率的计算和匹配结果的输出延时。用西雅图市浮动车的轨迹数据进行算法的实验验证, 结果表明, 与传统的HMM地图匹配算法相比, 改进的算法在准确率和时间效率上更优, 能够满足在线地图匹配的需求。

关键词: 地图匹配, 隐马尔科夫模型(HMM), 可靠点, 转移概率, 发射概率