A force-directed approach for offline GPS trajectory map matching

Rappos, Efstratios (School of Management and Engineering Vaud, HES-SO // University of Applied Sciences Western Switzerland) ; Robert, Stephan (School of Management and Engineering Vaud, HES-SO // University of Applied Sciences Western Switzerland) ; Cudré-Mauroux, Philippe (eXascale Infolab, University of Fribourg, Fribourg, Switzerland)

We present a novel algorithm to match GPS trajectories onto maps offline (in batch mode) using techniques borrowed from the field of force-directed graph drawing. We consider a simulated physical system where each GPS trajectory is attracted or repelled by the underlying road network via electrical-like forces. We let the system evolve under the action of these physical forces such that individual trajectories are attracted towards candidate roads to obtain a map matching path. Our approach has several advantages compared to traditional, routing-based, algorithms for map matching, including the ability to account for noise and to avoid large detours due to outliers in the data whilst taking into account the underlying topological restrictions (such as one-way roads). Our empirical evaluation using real GPS traces shows that our method produces better map matching results compared to alternative offline map matching algorithms on average, especially for routes in dense, urban areas.


Keywords:
Conference Type:
full paper
Faculty:
Ingénierie et Architecture
School:
HEIG-VD
Institute:
IICT - Institut des Technologies de l'Information et de la Communication
Subject(s):
Ingénierie
Publisher:
Seattle, Washington, USA, 6-9 November 2018
Date:
2018-11
Seattle, Washington, USA
6-9 November 2018
Pagination:
10 p.
Published in:
Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 6-9 November 2018, Seattle, Washington, USA
DOI:
ISBN:
9781450358897
External resources:
Appears in Collection:

Note: The status of this file is: restricted


 Record created 2019-04-02, last modified 2019-04-30

Fulltext:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)