Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns
Venue
Algorithms - ESA 2010, 18th Annual European Symposium. Proceedings, Part I, Springer, pp. 290-301
Publication Year
2010
Authors
Hannah Bast, Erik Carlsson, Arno Eigenwillig, Robert Geisberger, Chris Harrelson, Veselin Raychev, Fabien Viger
BibTeX
Abstract
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.
