Idioma:

Exact Routing in Large Road Networks Using Contraction Hierarchies

Geisberger, Robert ; Sanders, Peter ; Schultes, Dominik ; Vetter, Christian

Transportation science, 2012-08, Vol.46 (3), p.388-404 [Periódico revisado por pares]

Linthicum, MD: INFORMS

Texto completo disponível

Citações Citado por

Enviar para

Título:
Exact Routing in Large Road Networks Using Contraction Hierarchies
Autor: Geisberger, Robert ; Sanders, Peter ; Schultes, Dominik ; Vetter, Christian
Assuntos: algorithm engineering ; Algorithms ; Applied sciences ; Business orders ; Data models ; Exact sciences and technology ; Graph representations ; Ground, air and sea transportation, marine construction ; Heuristics ; Hierarchy ; Highways ; Methods ; Mobile devices ; Mobile phones ; Multilevel analysis ; Preprocessing ; Queries ; Road network ; Road transportation and traffic ; Roads ; Roads & highways ; Role distance ; Route optimization ; route planning ; Shortest path algorithms ; shortest paths ; Studies ; Traffic congestion ; Transportation ; Transportation planning, management and economics ; Travel time
É parte de: Transportation science, 2012-08, Vol.46 (3), p.388-404
Notas: ObjectType-Article-2
SourceType-Scholarly Journals-1
ObjectType-Feature-1
content type line 23
Descrição: Contraction hierarchies are a simple approach for fast routing in road networks. Our algorithm calculates exact shortest paths and handles road networks of whole continents. During a preprocessing step, we exploit the inherent hierarchical structure of road networks by adding shortcut edges. A subsequent modified bidirectional Dijkstra algorithm can then find a shortest path in a fraction of a millisecond, visiting only a few hundred nodes. This small search space makes it suitable to implement it on a mobile device. We present a mobile implementation that also handles changes in the road network, like traffic jams, and that allows instantaneous routing without noticeable delay for the user. Also, an algorithm to calculate large distance tables is currently the fastest if based on contraction hierarchies.
Editor: Linthicum, MD: INFORMS
Idioma: Inglês

Links

View record in Pascal Francis

Voltar para lista de resultados

Realização: Logos de Redes Sociais:

Exact Routing in Large Road Networks Using Contraction Hierarchies

Geisberger, Robert ; Sanders, Peter ; Schultes, Dominik ; Vetter, Christian

Linthicum, MD: INFORMS

Buscando em bases de dados remotas. Favor aguardar.