Akira Tanaka, Nariaki Tateiwa, Nozomi Hata, Akihiro Yoshida, Takashi Wakamatsu, Shota Osafune, Katsuki Fujisawa,
Offline map matching using time-expanded graph for low-frequency data,
To appear in Transportation Research Part C: Emerging Tech- nologies, Elsevier, 2021.
Map matching is an essential preprocessing step for most trajectory-based intelligent transport system services. Dueto device capability constraints and the lack of a high-performance model, map matching for low-sampling-rate tra-jectories is of particular interest. Therefore, we developed a time-expanded graph matching (TEG-matching) thathas three advantages (1) high speed and accuracy, as it is robust for spatial measurement error and a pause such asat traffic lights; (2) being parameter-free, that is, our algorithm has no predetermined hyperparameters; and (3) onlyrequiring ordered locations for map matching. Given a set of low-frequency GPS data, we construct a time-expandedgraph (TEG) whose path from source to sink represents a candidate route. We find the shortest path on TEG to obtainthe matching route with a small area between the vehicle trajectory. Additionally, we introduce two general speeduptechniques (most map-matching methods can apply) bottom-up segmentation and fractional cascading. Numerical ex-periments with worldwide vehicle trajectories in a public dataset show that TEG-matching outperforms state-of-the-artalgorithms in terms of accuracy and speed, and we verify the effectiveness of the two general speedup techniques.
Keywords:Offline map matching, Time-expanded graph, Neighborhood search analysis, Fractional cascading,Bottom-up segmentation
Offline map matching using time-expanded graph for low-frequency data,
To appear in Transportation Research Part C: Emerging Tech- nologies, Elsevier, 2021.
Map matching is an essential preprocessing step for most trajectory-based intelligent transport system services. Dueto device capability constraints and the lack of a high-performance model, map matching for low-sampling-rate tra-jectories is of particular interest. Therefore, we developed a time-expanded graph matching (TEG-matching) thathas three advantages (1) high speed and accuracy, as it is robust for spatial measurement error and a pause such asat traffic lights; (2) being parameter-free, that is, our algorithm has no predetermined hyperparameters; and (3) onlyrequiring ordered locations for map matching. Given a set of low-frequency GPS data, we construct a time-expandedgraph (TEG) whose path from source to sink represents a candidate route. We find the shortest path on TEG to obtainthe matching route with a small area between the vehicle trajectory. Additionally, we introduce two general speeduptechniques (most map-matching methods can apply) bottom-up segmentation and fractional cascading. Numerical ex-periments with worldwide vehicle trajectories in a public dataset show that TEG-matching outperforms state-of-the-artalgorithms in terms of accuracy and speed, and we verify the effectiveness of the two general speedup techniques.
Keywords:Offline map matching, Time-expanded graph, Neighborhood search analysis, Fractional cascading,Bottom-up segmentation
アクセス
トータル
