Likelihood-based offline map matching of GPS recordings using global trace information

Abstract

In batch map matching the objective is to derive from a time series of position data the sequence of road segments visited by the traveler for posterior analysis. Taking into account the limited accuracy of both the map and the measurement devices several different movements over network links may have generated the observed measurements. The set of candidate solutions can be reduced by adding assumptions about the traveller’s behavior (e.g. respecting speed limits, using shortest paths, etc.). The set of feasible assumptions however, is constrained by the intended posterior analysis of the link sequences produced by map matching. This paper proposes a method that only uses the spatio-temporal information contained in the input data (GPS recordings) not reduced by any additional assumption.

The method partitions the trace of GPS recordings so that all recordings in a part are chronologically consecutive and match the same set of road segments. Each such trace part leads to a collection of partial routes that can be qualified by their likelihood to have generated the trace part. Since the trace parts are chronologically ordered, an acyclic directed graph can be used to find the best chain of partial routes. It is used to enumerate candidate solutions to the map matching problem.

Qualification based on behavioral assumptions is added in a separate later stage. Separating the stages helps to make the underlying assumptions explicit and adaptable to the purpose of the map matched results. The proposed technique is a multi-hypothesis technique (MHT) that does not discard any hypothesized path until the second stage.

A road network extracted from OpenStreetMap (OSM) is used. In order to validate the method, synthetic realistic GPS traces were generated from randomly generated routes for different combinations of device accuracy and recording period. Comparing the base truth to the map matched link sequences shows that the proposed technique achieves a state of the art accuracy level.