Intriguingly Simple and Fast Transit Routing

Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner

Abstract

This paper studies the problem of computing optimal journeys in dynamic public transit networks. We introduce a novel algorithmic framework, called Connection Scan Algorithm (CSA), to compute journeys. It organizes data as a single array of connections, which it scans once per query. Despite its simplicity, our algorithm is very versatile. We use it to solve earliest arrival and multi-criteria profile queries. Moreover, we extend it to handle the minimum expected arrival time (MEAT) problem, which incorporates stochastic delays on the vehicles and asks for a set of (alternative) journeys that in its entirety minimizes the user's expected arrival time at the destination. Our experiments on the dense metropolitan network of London show that CSA computes MEAT queries, our most complex scenario, in 272 ms on average.

Details

Publication typeInproceedings
Published inProceedings of the 12th International Symposium on Experimental Algorithms (SEA'13)
URLhttp://rd.springer.com/chapter/10.1007/978-3-642-38527-8_6
Pages43–54
Volume7933
SeriesLecture Notes in Computer Science
PublisherSpringer
> Publications > Intriguingly Simple and Fast Transit Routing