Offline map matching using time-expanded graph for low-frequency data. (September 2021)

• Record Type: Journal Article
• Authors: Tanaka, Akira; Tateiwa, Nariaki; Hata, Nozomi; Yoshida, Akihiro; Wakamatsu, Takashi; Osafune, Shota; Fujisawa, Katsuki
• Is Part Of: Transportation research. Volume 130(2021)
• Publication Date: 2021-09
• Subjects: Offline map matching -- Time-expanded graph -- Neighborhood search analysis -- Fractional cascading -- Bottom-up segmentation; Transportation -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.011
• DOI: 10.1016/j.trc.2021.103265
• Languages: English
• ISSNs: 0968-090X

Abstract

Highlights: Parameter-free time-dependent map-matching algorithm for low-frequency data. Map matching based on the area between the predicted path and the vehicle trajectory. Bottom-up segmentation and fractional cascading are applied for speedup. Abstract: 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.