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

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

作　　者：王晓蒙[1,2] 池天河[2] 林晖[1,2] 邵静[1,2] 姚晓婧[1,2] 杨丽娜[2] 

机构地区：[1]中国科学院大学,北京100049 [2]中国科学院遥感与数字地球研究所,北京100101

出　　处：《地球信息科学学报》2015年第10期1143-1151,共9页Journal of Geo-information Science

基　　金：国家科技支撑计划项目(2015BAJ02B00);国家科技部政策引导类项目(2011FU125Z24)

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

关 键 词：浮动车 地图匹配 隐马尔可夫模型 网格 路段转移矩阵 

分 类 号：U491.1[交通运输工程—交通运输规划与管理] TP274.2[交通运输工程—道路与铁道工程]