Journal of Geo-information Science ›› 2015, Vol. 17 ›› Issue (10): 1143-1151.doi: 10.3724/SP.J.1047.2015.01143

• Orginal Article • Previous Articles     Next Articles

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

WANG Xiaomeng1,2(), CHI Tianhe2,*(), LIN Hui1,2, SHAO Jing1,2, YAO Xiaojing1,2, YANG Lina2   

  1. 1. University of Chinese Academy of Sciences, Beijing 100049, China
    2. Institute of Remote Sensing and Digital Earth, CAS, Beijing 100101, China
  • Received:2015-04-15 Revised:2015-05-15 Online:2015-10-10 Published:2015-10-10
  • Contact: CHI Tianhe E-mail:wangxiaomeng1986@163.com;chith@126.com
  • About author:

    *The author: CHEN Nan, E-mail:fjcn99@163.com

Abstract:

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.

Key words: FCD, map matching, HMM, grid, road segment transition matrix