Efficient Routing in Road Networks with Turn Costs
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.
| 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 | Dimensions Scopus |
| Globale Ziele für nachhaltige Entwicklung |