Offline map matching using time-expanded graph for low-frequency data

Akira Tanaka, Nariaki Tateiwa, Nozomi Hata, Akihiro Yoshida, Takashi Wakamatsu, Shota Osafune, Katsuki Fujisawa

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


Map matching is an essential preprocessing step for most trajectory-based intelligent transport system services. Due to device capability constraints and the lack of a high-performance model, map matching for low-sampling-rate trajectories is of particular interest. Therefore, we developed a time-expanded graph matching (TEG-matching) that has three advantages (1) high speed and accuracy, as it is robust for spatial measurement error and a pause such as at traffic lights; (2) being parameter-free, that is, our algorithm has no predetermined hyperparameters; and (3) only requiring ordered locations for map matching. Given a set of low-frequency GPS data, we construct a time-expanded graph (TEG) whose path from source to sink represents a candidate route. We find the shortest path on TEG to obtain the matching route with a small area between the vehicle trajectory. Additionally, we introduce two general speedup techniques (most map matching methods can apply) bottom-up segmentation and fractional cascading. Numerical experiments with worldwide vehicle trajectories in a public dataset show that TEG-matching outperforms state-of-the-art algorithms in terms of accuracy and speed, and we verify the effectiveness of the two general speedup techniques.

Original languageEnglish
Article number103265
JournalTransportation Research Part C: Emerging Technologies
Publication statusPublished - Sept 2021

All Science Journal Classification (ASJC) codes

  • Transportation
  • Automotive Engineering
  • Civil and Structural Engineering
  • Management Science and Operations Research


Dive into the research topics of 'Offline map matching using time-expanded graph for low-frequency data'. Together they form a unique fingerprint.

Cite this