KIT | KIT-Bibliothek | Impressum | Datenschutz

Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns

Bast, Hannah; Carlsson, Erik; Eigenwillig, Arno; Geisberger, Robert 1; Harrelson, Chris; Raychev, Veselin; Viger, Fabien
1 Karlsruher Institut für Technologie (KIT)


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.

DOI: 10.1007/978-3-642-15775-2_25
Zitationen: 99
Zitationen: 61
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2010
Sprache Englisch
Identifikator ISBN: 978-3-642-15775-2
ISSN: 0302-9743, 1611-3349
KITopen-ID: 1000097652
Erschienen in Algorithms - ESA 2010. Ed.: M. de Berg
Verlag Springer Verlag
Seiten 290–301
Serie Lecture Notes in Computer Science ; 6346
Nachgewiesen in Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page