KIT | KIT-Bibliothek | Impressum | Datenschutz

Efficient Routing in Road Networks with Turn Costs

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

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: 36
Dimensions
Zitationen: 27
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 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 Verlag
Seiten 100–111
Serie Lecture Notes in Computer Science ; 6630
Nachgewiesen in Scopus
Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page