Exact Routing in Large Road Networks Using Contraction Hierarchies

Robert Geisberger (), Peter Sanders (), Dominik Schultes () and Christian Vetter ()
Additional contact information
Robert Geisberger: Karlsruhe Institute of Technology, Department of Informatics, 76128 Karlsruhe, Germany
Peter Sanders: Karlsruhe Institute of Technology, Department of Informatics, 76128 Karlsruhe, Germany
Dominik Schultes: Karlsruhe Institute of Technology, Department of Informatics, 76128 Karlsruhe, Germany
Christian Vetter: Karlsruhe Institute of Technology, Department of Informatics, 76128 Karlsruhe, Germany

Transportation Science, 2012, vol. 46, issue 3, 388-404

Abstract: 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.

Keywords: route planning; shortest paths; algorithm engineering (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1110.0401 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:46:y:2012:i:3:p:388-404

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().