Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Parallel Computation of Best Connections in Public Transportation Networks

Daniel Delling, Bastian Katz, and Thomas Pajor

Abstract

Exploiting parallelism in route planning algorithms is a challenging algorithmic problem with obvious applications in mobile navigation and timetable information systems. In this work, we present a novel algorithm for the one-to-all profile-search problem in public transportation networks. It answers the question for all fastest connections between a given station S and any other station at any time of the day in a single query. This algorithm allows for a very natural parallelization, yielding excellent speed-ups on standard multi-core servers. Our approach exploits the facts that first, time-dependent travel-time functions in such networks can be represented as a special class of piecewise linear functions, and that second, only few connections from S are useful to travel far away. Introducing the connection-setting property, we are able to extend Dijkstra's algorithm in a sound manner. Furthermore, we also accelerate station-to-station queries by preprocessing important connections within the public transportation network. As a result, we are able to compute all relevant connections between two random stations in a complete public transportation network of a big city (New York) on a standard multi-core server in real time.

Details

Publication typeArticle
Published inJournal of Experimental Algorithmics
URLhttp://dl.acm.org/citation.cfm?id=2345678
Pages4.1–4.26
Volume17
Number4
PublisherACM
> Publications > Parallel Computation of Best Connections in Public Transportation Networks