Route Planning in Road Networks Dominik Schultes <mail@dominik-schultes.de> Algorithmik II (Group of Prof. Sanders) Institut für Theoretische Informatik Schwerpunkt Nr. 1126

SciAm 50 (Scientific American 50 Award) Winner list of all winners (see page 2, 43.) article on route planning press release (in German)

Documents

PhD Thesis

• Final version. February 2008.
  
  

Overview

• Abstract. March 2007.
  
  
• P. Sanders and D. Schultes. Engineering Fast Route Planning Algorithms.
  In 6th Workshop on Experimental Algorithms (WEA), LNCS 4525, pp. 23-36. © Springer, 2007.
  
  

Highway Hierarchies

• Master's thesis, Department of Computer Science, Universität des Saarlandes, July 2005.
  • optimised for printing (gzipped postscript, 9.4 MB, note that colour printing is recommended)
  • optimised for viewing (pdf, 2.1 MB)
  • without Appendix B "Examples" (pdf, 0.9 MB)
    
    
• P. Sanders and D. Schultes. Highway Hierarchies Hasten Exact Shortest Path Queries.
  In 13th European Symposium on Algorithms (ESA), LNCS 3669, pp. 568-579. © Springer, 2005.
  
  
• P. Sanders and D. Schultes. Engineering Highway Hierarchies.
  In 14th European Symposium on Algorithms (ESA), LNCS 4168, pp. 804-816. © Springer, 2006.
  
  
• P. Sanders and D. Schultes. Engineering Highway Hierarchies.
  full paper, submitted for publication, preliminary version, September 2007.
  
  
• for the general audience:
  • K. Rümmele. Der Weg ist das Ziel.
    UniKaTH 1/2006. (short article on our work, in German)
  • S. Fuchs, P. Sanders, D. Schultes. Karlsruher Informatiker arbeiten an Navigationssystemen der 2. Generation.
    Radio Regenbogen, 2006. (radio broadcast, in German)
    
    

Many-to-Many Shortest Paths

• S. Knopp, P. Sanders, D. Schultes, F. Schulz, D. Wagner. Fast Computation of Distance Tables using Highway Hierarchies.
  Technical Report, July 2006. (outdated version)
  
  
• S. Knopp, P. Sanders, D. Schultes, F. Schulz, D. Wagner. Computing Many-to-Many Shortest Paths Using Highway Hierarchies.
  In Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 36-45, 2007.
  
  

Combinations

• D. Delling, P. Sanders, D. Schultes, D. Wagner. Highway Hierarchies Star.
  In 9th DIMACS Challenge on Shortest Paths, 2007.
  • workshop version (Nov 2006)
  • proceedings version (Feb 2007, preliminary version)
    
    
• R. Bauer, D. Delling, P. Sanders, D. Schieferdecker, D. Schultes, D. Wagner. Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra's Algorithm.
  In 7th Workshop on Experimental Algorithms (WEA), LNCS 5038, pp. 303-318. © Springer, 2008.
  
  

Transit-Node Routing

• Press Releases / Reports.
  
  
• H. Bast, S. Funke, P. Sanders, D. Schultes. Fast Routing in Road Networks with Transit Nodes.
  Science, Vol. 316. no. 5824, p. 566, 27. April 2007.
  
  
• P. Sanders and D. Schultes. Robust, Almost Constant Time Shortest-Path Queries in Road Networks.
  In 9th DIMACS Challenge on Shortest Paths, 2007.
  • workshop version (Nov 2006)
  • proceedings version (Feb 2007, preliminary version)
    
    
• H. Bast, S. Funke, D. Matijevic, P. Sanders, D. Schultes. In Transit to Constant Shortest-Path Queries in Road Networks.
  In Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 46-59, 2007.
  
  

Highway-Node Routing / Contraction Hierarchies

• D. Schultes and P. Sanders. Dynamic Highway-Node Routing.
  In 6th Workshop on Experimental Algorithms (WEA), LNCS 4525, pp. 66-79. © Springer, 2007.
  
  
• R. Geisberger, P. Sanders, D. Schultes, D. Delling. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks.
  In 7th Workshop on Experimental Algorithms (WEA), LNCS 5038, pp. 319-333. © Springer, 2008.
  
  
• P. Sanders, D. Schultes, C. Vetter. Mobile Route Planning.
  • Outdated version, January 2008.
  • Submitted for publication, preliminary version, April 2008.
    
    
• M. Holtgrewe. Parallel Highway-Node Routing.
  Student research project, Universität Karlsruhe (TH), supervised by P. Sanders, D. Schultes, J. Singler, 2008.
  
  

Betweenness Approximation

• R. Geisberger, P. Sanders, D. Schultes. Better Approximation of Betweenness Centrality.
  In Workshop on Algorithm Engineering and Experiments (ALENEX), 2008.
  
  
• R. Geisberger. Better Approximation of Betweenness Centrality.
  Student research project, Universität Karlsruhe (TH), supervised by P. Sanders and D. Schultes, 2008.
  
  

Demo / Visualisation

• We provide an interactive demo of highway hierarchies and some background information on our visualisation tool.

Talks