News

The source code of KaTCH, an implementaion of time-dependent contraction hierarchies, has been released under the terms of GNU AGPL (Affero General Public License) version 3 and can be downloaded from here or from GitHub.
The source code of our implementation of contraction hierarchies (CHs) can now be downloaded from here under the terms of the AGPL (GNU affero general public license, click here for more information).
Project OSRM, a fast routing engine for OpenStreetMap data, written in C++ is available under the (simplified) 2-clause BSD license.
In his diploma thesis Christian Vetter has developed the full functioning mobile routing application MoNav based on Contraction Hierarchies using the freely available OpenStreetMap data set.
Dr. Dominik Schultes wins the Klaus Tschira Award for Understandable Science. Read the special supplement to Bild der Wissenschaft (in German, pp 28-31).
Prof. Dr. Peter Sanders held a Google TechTalk about our research activities in route planning. It is available on YouTube.
The old homepage, that has been maintained by Dominik Schultes, will be updated no more (though everything is still available, click here).

People involved in the Project

Researchers
Prof. Dr. Peter Sanders
Moritz Kobitzsch

Research Students

Alumni
Dr. G. Veit Batz
Dr. Robert Geisberger
Dr. Dennis Luxen
Dr. Dennis Schieferdecker
Dr. Dominik Schultes
Christian Vetter

Also, see the website of the group of Prof. Dr. Dorothea Wagner of this project.

Documents

Overview Documents

Book Chapters
Title	Author(s)	Source
Engineering Route Planning Algorithms	D. Delling, P. Sanders, D. Schultes, D. Wagner	2009, Algorithmics of Large and Complex Networks, Springer-Verlag, ISBN 978-3-642-02093-3, 117-139

Conferences / Symposia
Title	Conference	Date	Author(s)
Engineering Fast Route Planning Algorithms	6th Workshop on Experimental Algorithms (WEA)	June 2007	P. Sanders, D. Schultes

Reports
Title	Author(s)	Source
Route Planning in Transportation Networks	H. Bast, D. Delling, A. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner, R. Werneck	Technical Report 2014, Microsoft Research
Building Blocks for Mapping Services	Dennis Luxen	Doctoral thesis, Fakultät für Informatik, Karlsruher Institut für Technologie, Germany, 2013.
Advanced Route Planning in Transportation Networks	Robert Geisberger	Doctoral thesis, Fakultät für Informatik, Karlsruher Institut für Technologie, Germany, February 2011.
Route Planning in Road Networks	Dominik Schultes	Doctoral thesis, Fakultät für Informatik, Universität Karlsruhe (TH), Germany, final version, February 2008.

Talks
Title	Speaker	Date
Google TechTalk: Fast Route Planning	Peter Sanders	March 23, 2009

Time Dependent Routing

Journal Articles
Title	Author(s)	Source
Minimum Time-Dependent Travel Times with Contraction Hierarchies	G.V. Batz, R. Geisberger, P. Sanders, and C. Vetter	Journal of Experimental Algorithmics (JEA), Volume 18, Article No. 1.4, 2013.

Conferences / Symposia
Title	Conference	Date	Author(s)
Time-Dependent Route Planning with Generalized Objective Functions	European Symposium on Algorithms (ESA 2012)	September 2012	G.V. Batz and P. Sanders
Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns	European Symposium on Algorithms (ESA 2010)	September 2010	H. Bast, E. Carlsson, A. Eigenwillig, R. Geisberger, C. Harrelson, V. Raychev, F. Viger
Contraction of Timetable Networks with Realistic Transfers	International Symposium on Experimental Algorithms (SEA 2010)	May 2010	R. Geisberger
Time-Dependent Contraction Hierarchies and Approximation	International Symposium on Experimental Algorithms (SEA 2010)	May 2010	G.V. Batz, R. Geisberger, S. Neubauer, P. Sanders
Distributed Time-Dependent Contraction Hierarchies	International Symposium on Experimental Algorithms (SEA 2010)	May 2010	T. Kieritz, D. Luxen, P. Sanders, C. Vetter
Time-Dependent Contraction Hierarchies	Workshop on Algorithm Engineering and Experiments (ALENEX 2009)	January 2009	G.V. Batz, D. Delling, P. Sanders, and C. Vetter

Reports
Title	Author(s)	Source
Time-Dependent Route Planning with Contraction Hierarchies	Gernot Veit Batz	Doctoral thesis, Fakultät für Informatik, Karlsruher Institut für Technologie, Germany, 2014.
Towards Mobile Time-Dependent Route Planning	Harris Kaufmann	Bachelor thesis, Karlsruhe Institute of Technology, advised by G.V. Batz and J. Speck, March 2013.
Engineering Time-dependent One-To-All Computation	Robert Geisberger	Technical Report, October 6, 2010, Fakultät für Informatik, Karlsruher Institut für Technologie, arXiv:1010.0809v1
PCA-Based Compression of Travel Time Functions	Marc Schmitzer	Diploma Thesis, Karlsruhe Institute of Technology, supervised by G.V. Batz, P. Sanders, and J. Speck, 2010
Contraction of Timetable Networks with Realistic Transfers	R. Geisberger	Technical Report, August 11, 2009, Fakultät für Informatik, Universität Karlsruhe
Parallel Timede-Dependent Contraction Hierarchies	Christian Vetter	Student research project, Universität Karlsruhe (TH), supervised by G.V. Batz and P. Sanders, 2009.
Space Efficient Approximation of Piecewise Linear Functions	Sabine Neubauer	Student research project, Universität Karlsruhe (TH), supervised by G.V. Batz and P. Sanders, 2009.
Time Dependent Contraction Hierarchies - Basic Algorithmic Ideas	G.V. Batz, R. Geisberger, P. Sanders	Technical Report, April 24, 2008, Fakultät für Informatik, Universität Karlsruhe

Contraction Hierarchies / Highway-Node Routing

The source code of our implementation of contraction hierarchies (CHs) is available under the terms of the AGPL (GNU affero general public license, click here for more information). Click here to download the source code.

Journal Articles
Titel	Autor	Quelle
Route Planning with Flexible Edge Restrictions	R. Geisberger, M.N. Rice, P. Sanders, V.J. Tsotras	Journal of Experimental Algorithmics (JEA), Volume 17, Issue 1, Article No. 1.2, 2012.
Exact Routing in Large Road Networks Using Contraction Hierarchies	R. Geisberger, P. Sanders, D. Schultes, C. Vetter	Transportation Science, April 2012

Conferences / Symposia
Title	Conference	Date	Author(s)
Efficient Routing in Road Networks with Turn Costs	International Symposium on Experimental Algorithms (SEA 2011)	May 2011	R. Geisberger, C. Vetter
A Comparison of High-Level Approaches for Speeding up Pathfinding	Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE 2010)	October 2010	R. Geisberger, N. Sturtevant
Heuristic Contraction Hierarchies with Approximation Guarantee	Symposium on Combinatorial Search (SoCS 2010)	July 2010	Robert Geisberger, Dennis Schieferdecker
Mobile Route Planning	16th European Symposium on Algorithms (ESA 2008)	September 2008	P. Sanders, D. Schultes, C. Vetter
Dynamic Highway-Node Routing	6th Workshop on Experimental Algorithms (WEA)	June 2007	P. Sanders, D. Schultes
Route Planning with Flexible Objective Functions	Workshop on Algorithm Engineering and Experiments (ALENEX 2010)	Januar 2010	R. Geisberger, M. Kobitzsch, P. Sanders
Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks	7th Workshop on Experimental Algorithms (WEA)	May/June 2008	R. Geisberger, P. Sanders, D. Schultes, D. Delling

Reports
Title	Author(s)	Source
Heuristic Contraction Hierarchies with Approximation Guarantee	R. Geisberger	Technical Report, February 4, 2010, Fakultät für Informatik, Karlsruhe Institute of Technology
Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks	Robert Geisberger	Diploma Thesis, Universität Karlsruhe (TH), supervised by P. Sanders and D. Schultes, 2008
Parallel Highway-Node Routing	Manuel Holtgrewe	Student research project, Universität Karlsruhe (TH), supervised by P. Sanders, D. Schultes, J. Singler, 2008.

Many-to-Many Shortest Path

Conferences / Symposia
Title	Conference	Date	Author(s)
Engineering Time-Dependent Many-to-Many Shortest Paths Computation	Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2010)	September 2010	R. Geisberger, P. Sanders
Computing Many-to-Many Shortest Paths Using Highway Hierarchies	Workshop on Algorithm Engineering and Experiments (ALENEX 2007)	January 2007	S. Knopp, P. Sanders, D. Schultes, F. Schulz, D. Wagner

Reports
Title	Author(s)	Source
Fast Computation of Distance Tables using Highway Hierarchies	S. Knopp, P. Sanders, D. Schultes, F. Schulz, D. Wagner	Technical Report, July 2006. (outdated version)

Transit-Node Routing

Journal Articles
Title	Author(s)	Source
Fast routing in road networks with transit nodes	H. Bast, S. Funke, P. Sanders, D. Schultes	Science 316 (5824): S. 566, 2007

Conferences / Symposia
Title	Conference	Date	Author(s)
Transit Node Routing Reconsidered	12th International Symposium on Experimental Algorithms (SEA 2013)	June 2013	Julian Arz, Dennis Luxen, Peter Sanders
Almost Constant Time Shortest-Path Queries in Road Networks	9th DIMACS Challenge on Shortest Paths		P. Sanders, D. Schultes
In Transit to Constant Shortest-Path Queries in Road Networks	Workshop on Algorithm Engineering and Experiments (ALENEX 2007)	January 2007	H. Bast, S. Funke, D. Matijevic, P. Sanders, D. Schultes

Highway Hierarchies

Journal Articles
Titel	Autor	Quelle
Engineering highway hierarchies	P. Sanders, D. Schultes	Journal of Experimental Algorithmics (JEA), Volume 17, Issue 1, Article No 1.6, 2012.

Conferences / Symposia
Title	Conference	Date	Author(s)
Engineering Highway Hierarchies	14th European Symposium on Algorithms (ESA)	September 2006	P. Sanders, D. Schultes
Highway Hierarchies Hasten Exact Shortest Path Queries	ESA 2005	October 2005	P. Sanders, D. Schultes

Reports
Title	Author(s)	Source
Fast and Exact Shortest Path Queries Using Highway Hierarchies	Dominik Schultes	Master's thesis, Department of Computer Science, Universität des Saarlandes, July 2005.
Engineering Highway Hierarchies	P. Sanders, D. Schultes	Full paper, submitted for publication, preliminary version, September 2007.

Combinations

Journal Articles
Titel	Autor	Quelle
Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra's Algorithm	R. Bauer, D. Delling, P. Sanders, D. Schieferdecker, D. Schultes, and D. Wagner	ACM Journal of Experimental Algorithmics, Volume 15, Article 2.3, pp 2.1-2.31

Conferences / Symposia
Title	Conference	Date	Author(s)
Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstras Algorithm	7th Workshop on Experimental Algorithms (WEA 2008)		R. Bauer, D. Delling, P. Sanders, D. Schieferdecker, D. Schultes, D. Wagner
Highway Hierarchies Star	9th DIMACS Challenge on Shortest Paths	November 2006	D. Delling, P. Sanders, D. Schultes, D. Wagner

Applications

This section focuses on real life problems as well as more realisitic scenarios.

Conferences / Symposia
Title	Conference	Author(s)	Speaker
Flexible Route Guidance Through Turn Instruction Graphs	1st ACM SIGSPATIAL Workshop on MapInteraction	Dennis Luxen	Dennis Luxen
Multi-Hop Ride Sharing	6th Annual Symposium on Combinatorial Search (SoCS 2013)	Florian Drews, Dennis Luxen
Candidate Sets for Alternative Routes in Road Networks - Extended Abstract	6th Annual Symposium on Combinatorial Search (SoCS 2013)	Dennis Luxen, Dennis Schieferdecker	Dennis Schieferdecker
Efficient Route Compression for Hybrid Route Planning	Mediterranean Conference on Algorithms (MedAlg 2012)	G.V. Batz, R. Geisberger, D. Luxen, P. Sanders, and R. Zubkov
Candidate Sets for Alternative Routes in Road Networks	11th International Symposium on Experimental Algorithms (SEA'12)	Dennis Luxen, Dennis Schieferdecker
Robust Mobile Route Planning with Limited Connectivity	Workshop on Algorithm Engineering and Experiments (ALENEX 2012)	D. Delling, M. Kobitzsch, D. Luxen, R. Werneck	M. Kobitzsch
Real-Time Routing with OpenStreetMap data	19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2011)	Dennis Luxen, Christian Vetter
Hierarchy Decomposition and Faster User Equilibria on Road Networks	International Symposium on Experimental Algorithms (SEA 2011)	D. Luxen, P. Sanders	D. Luxen
Alternative Route Graphs in Road Networks	International ICST Conference on Theory and Practice of Algorithms in Computer Systems (TAPAS 2011)	R. Bader, J. Dees, R. Geisberger, P. Sanders
Fast Detour Computation for Ride Sharing	ATMOS 2010	R. Geisberger, D. Luxen, P. Sanders, S. Neubauer, L. Volker

Reports
Title	Source	Author(s)
Compressed Transmission of Route Descriptions	Technical Report, November 22, 2010, Fakultät für Informatik, Karlsruher Institut für Technologie, arXiv:1011.4465v1	G.V. Batz, R. Geisberger, D. Luxen, P. Sanders
Fast and Exact Mobile Navigation with OpenStreetMap Data	Diploma Thesis, Karlsruhe Institute of Technology, supervised by Peter Sanders, 2010	Chrisitian Vetter
Defining and Computing Alternative Routes in Road Networks	Technical Report, February 23, 2010, Fakultät für Informatik, Karlsruher Institut für Technologie	J. Dees, R. Geisberger, P. Sanders, R. Bader
Fast Detour Computation for Ride Sharing	Technical Report, July 30, 2009, Fakultät für Informatik, Universität Karlsruhe	R. Geisberger, D. Luxen, S. Neubauer, P. Sanders, L. Volker
Route Planning in Road Networks with Turn Costs	Student research project, Universität Karlsruhe (TH), supervised by P. Sanders and D. Schultes, 2008.	Lars Volker