Parallel computation of best connections in public transportation networks

Authors: 
Daniel Delling, Bastian Katz, and Thomas Pajor
Publication Date: 
July, 2012
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 <it>S</it> 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 multicore 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, second, only few connections from <it>S</it> 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.

Work Packages: 
Bibtex Entry: 
@article{Delling:2012:PCB:2133803.2345678, author = {Delling, Daniel and Katz, Bastian and Pajor, Thomas}, title = {Parallel computation of best connections in public transportation networks}, journal = {J. Exp. Algorithmics}, issue_date = {July 2012}, volume = {17}, number = {1}, month = oct, year = {2012}, issn = {1084-6654}, pages = {4.4:4.1--4.4:4.26}, articleno = {4.4}, numpages = {1.16}, url = {http://doi.acm.org/10.1145/2133803.2345678}, doi = {10.1145/2133803.2345678}, acmid = {2345678}, publisher = {ACM}, address = {New York, NY, USA}, keywords = {Shortest paths, profile queries, public transportation, route planning}, }
Publication Details: 
Journal of Experimental Algorithmics (JEA)