KIT | KIT-Bibliothek | Impressum | Datenschutz

Contraction of Timetable Networks with Realistic Transfers

Geisberger, Robert 1
1 Karlsruher Institut für Technologie (KIT)

Abstract:

We contribute a fast routing algorithm for timetable networks with realistic transfer times. In this setting, our algorithm is the first one that successfully applies precomputation based on node contraction: gradually removing nodes from the graph and adding shortcuts to preserve shortest paths. This reduces query times to 0.5 ms with preprocessing times below 4 minutes on all tested instances, even on continental networks with 30 000 stations. We achieve this by an improved contraction algorithm and by using a station graph model. Every node in our graph has a one-to-one correspondence to a station and every edge has an assigned collection of connections. Also, our graph model does not require parallel edges.


Originalveröffentlichung
DOI: 10.1007/978-3-642-13193-6_7
Scopus
Zitationen: 29
Dimensions
Zitationen: 21
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2010
Sprache Englisch
Identifikator ISBN: 978-3-642-13193-6
ISSN: 0302-9743, 1611-3349
KITopen-ID: 1000097653
Erschienen in Experimental Algorithms. Ed.: P. Festa
Verlag Springer Verlag
Seiten 71-82
Serie Lecture Notes in Computer Science ; 6049
Nachgewiesen in Scopus
Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page