KIT | KIT-Bibliothek | Impressum | Datenschutz

Efficient Routing in Road Networks with Turn Costs

Geisberger, Robert; Vetter, Christian

Abstract:
We present an efficient algorithm for shortest path computation in road networks with turn costs. Each junction is modeled as a node, and each road segment as an edge in a weighted graph. Turn costs are stored in tables that are assigned to nodes. By reusing turn cost tables for identical junctions, we improve the space efficiency. Preprocessing based on an augmented node contraction allows fast shortest path queries. Compared to an edge-based graph, we reduce preprocessing time by a factor of 3.4 and space by a factor of 2.4 without change in query time.



Originalveröffentlichung
DOI: 10.1007/978-3-642-20662-7_9
Scopus
Zitationen: 23
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Jahr 2011
Sprache Englisch
Identifikator ISBN: 978-3-642-20662-7
ISSN: 0302-9743, 1611-3349
KITopen-ID: 1000097647
Erschienen in Experimental Algorithms. Ed.: P. M. Pardalos
Verlag Springer, Berlin
Seiten 100–111
Serie Lecture Notes in Computer Science ; 6630
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page