We show how to route on very large public transportation networks (up to half a billion arcs) with average query times of a few milliseconds. We take into account many realistic features like: traffic days, walking between stations, queries between geographic locations instead of a source and a target station, and multi-criteria cost functions. Our algorithm is based on two key observations: (1) many shortest paths share the same transfer pattern, i.e., the sequence of stations where a change of vehicle occurs; (2) direct connections without change of vehicle can be looked up quickly. We precompute the respective data; in practice, this can be done in time linear in the network size, at the expense of a small fraction of non-optimal results. We have accelerated public transportation routing on Google Maps with a system based on our ideas. We report experimental results for three data sets of various kinds and sizes. © 2010 Springer-Verlag.
https://doi.org/10.1007/978-3-642-15775-2_25Cite as:
@incollection{Bast_2010,
doi = {10.1007/978-3-642-15775-2_25},
url = {https://doi.org/10.1007%2F978-3-642-15775-2_25},
year = 2010,
publisher = {Springer Berlin Heidelberg},
pages = {290--301},
author = {Hannah Bast and Erik Carlsson and Arno Eigenwillig and Robert Geisberger and Chris Harrelson and Veselin Raychev and Fabien Viger},
title = {Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns},
booktitle = {Algorithms {textendash} {ESA} 2010}
}