一种面向海量浮动车数据的地图匹配方法

浮动车数据已广泛应用于交通监管、智能出行、城市规划等领域,地图匹配是浮动车数据关键技术之一,保障匹配算法精度的同时提高匹配效率,是面向海量浮动车数据地图匹配方法的难点。本文提出一种基于HMM（Hidden Markov Model）的地图匹配模型,相对传统模型尝试了多个方面的改进：在发射概率计算中引入航向角变量,并探讨了该变量对模型精度的影响;以格网对路网进行划分,构建哈希索引,实现候选路段快速查找;采用路径无权距离替代路径实际距离,并对路网进行预处理,根据浮动车有限时间内的活动范围构建路段转移矩阵,实现路段转移概率快速计算,以减小路径匹配算法时间复杂度。将模型应用于北京出租车轨迹数据匹配结果表明,对于采样时间间隔在1~120 s的浮动车数据模型切实可行。在满足匹配精度应用需求的前提下,模型效率有了较大幅度提升,能有效应用于海量浮动车数据地图匹配。

A Research of Map-Matching Method for Massive Floating Car Data

Floating Car Data (FCD) has been widely applied into traffic supervision, smart travelling, urban planning and so forth. Map-matching is one of the key technologies of FCD, for current map-matching algorithms, it is difficult to improve their map-matching efficiency considerably with a guaranteed accuracy. To solve this problem, our research proposes a map-matching model based on Hidden Markov Model (HMM), and makes a variety of improvements compared with the traditional model: (1) in addition to the position information, it introduces the heading angle variable to emission probability calculation, and discusses its influences on model accuracy and how to set a reasonable weight; (2) it divides road network according to a square grid, constructs candidate road segments searching algorithm based on hash index, and then discusses the optimization approach of the candidate road segment collection; (3) the numbers of segments in the path is used as the measurement for transition probability computation instead of the practical length, which simplifies the calculation procedure; (4) by preprocessing the road net, it constructs a road segment transition matrix according to the characteristic that floating cars have a limited scope of space activities in a given time, which realizes the fast calculation of road segment transition probability and reduces the time complexity of road matching calculation to a significant extent. We have applied this map-matching model in analyzing Beijing taxis’ trajectory data, in which the sampling time interval varies from 1 s to 120 s. The result demonstrates that this model is practicable, the required road segment transition matrix can be constructed in affordable space cost, and its efficiency is improved significantly with the condition that the accuracy meets the application requirements, which makes the model more applicable for massive FCD map-matching. As a conclusion, the proposed model has a high application value for multiple cases.