Using iterated local alignment to aggregate GPS trajectories into a traffic flow map

Desire line maps are widely deployed for traffic flow analysis by virtue of their ease of interpretation and computation. They can be considered to be simplified traffic flow maps, whereas the computational challenges in aggregating small scale traffic flows prevent the wider dissemination of high resolution flow maps. GPS trajectories are a promising data source to solve this challenging problem. The solution begins with the alignment (or map matching) of the GPS trajectories to the road network. However even the state-of-the-art map matching APIs produce sub-optimal results with small misalignments. While these misalignments are negligible for large scale flow aggregation in desire line maps, they pose substantial obstacles for small scale flow aggregation in high resolution maps. To remove these remaining misalignments, we introduce innovative local alignment algorithms, where we infer road segments to serve as local reference segments, and proceed to align nearby road segments to them. With each local alignment iteration, the misalignments of the GPS trajectories with each other and with the road network are reduced, and so converge closer to a minimal flow map. By analysing a set of empirical GPS trajectories collected in Hannover, Germany, we confirm that our minimal flow map has high levels of spatial resolution, accuracy and coverage.