Development of a map-matching algorithm for dynamic sampling rate GPS signals to determine vehicle routes on a MATSim network

Abstract

The rapid development and proliferation of GPS-enabled systems and devices has led to a significant increase in the availability of transport data, more specifically GPS trajectories, that can be used in researching vehicle activities. In order to save data storage- and handling costs many vehicle tracking systems only store low-frequency trajectories for vehicles. We analyzed a number of existing methods used to map GPS trajectories to a digital road network and implemented such an algorithm in MATSim, an open source collaborative simulation package for Java. The map-matching algorithm was tested on a simple grid network and a real and extensive network of the city of Cape Town, South Africa. Experimentation showed the network size has the biggest influence on algorithm execution time and that a network must be reduced to include only the links that the vehicle most likely traversed. The algorithm is not suited for trajectories with sampling rates less than 5s as it can result in unrealistic paths chosen, but it manages to obtain accuracies of around 80% up until sampling sizes of around 50s whereafter the accuracy decreases. Further experimentation also revealed optimal algorithm parameters for matching trajectories on the Cape Town network. The use case for the implementation was to infer basic vehicle travel information, such as route travelled and speed of travel, for municipal waste collection vehicles in the city of Cape Town, South Africa.