Home | english | Impressum | Sitemap | KIT


Fast and Exact Route Planning

Research Project

News

  • 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
G. Veit Batz
Moritz Kobitzsch
Dennis Schieferdecker

Research Students

Alumni
Dr. Dennis Luxen

Dr. Robert Geisberger
Dr. Dominik Schultes
Christian Vetter

   

europe


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

 

Documents

Overview Documents

Book Chapters
Titel Autor Quelle

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
Titel Tagung Datum Autoren

6th Workshop on Experimental Algorithms (WEA)

June 2007

P. Sanders, D. Schultes



Reports
Titel Autor Quelle

Robert Geisberger

Dissertation, Fakultät für Informatik, Karlsruher Institut für Technologie, Germany, February 2011.

Dominik Schultes

PhD Thesis, Fakultät für Informatik, Universität Karlsruhe (TH), Germany, Final version, February 2008.



Talks
Titel Referent Datum

Peter Sanders

March 23, 2009


 
 

Time Dependent Routing

Journal Articles
Titel Autor Quelle

G.V. Batz, R. Geisberger, P. Sanders, and C. Vetter

Journal of Experimental Algorithmics (JEA), Volume 18, Article No. 1.4, 2013.



Conferences / Symposia
Titel Tagung Datum Autoren

European Symposium on Algorithms (ESA 2012)

September 2012

G.V. Batz and P. Sanders

European Symposium on Algorithms (ESA 2010)

September 2010

H. Bast, E. Carlsson, A. Eigenwillig, R. Geisberger, C. Harrelson, V. Raychev, F. Viger

International Symposium on Experimental Algorithms (SEA 2010)

May 2010

R. Geisberger

International Symposium on Experimental Algorithms (SEA 2010)

May 2010

G.V. Batz, R. Geisberger, S. Neubauer, P. Sanders

International Symposium on Experimental Algorithms (SEA 2010)

May 2010

T. Kieritz, D. Luxen, P. Sanders, C. Vetter

Workshop on Algorithm Engineering and Experiments (ALENEX 2009)

January 2009

G.V. Batz, D. Delling, P. Sanders, and C. Vetter



Reports
Titel Autor Quelle

Robert Geisberger

Technical Report, October 6, 2010, Fakultät für Informatik, Karlsruher Institut für Technologie, arXiv:1010.0809v1

Marc Schmitzer

Diploma Thesis, Karlsruhe Institute of Technology, supervised by G.V. Batz, P. Sanders, and J. Speck, 2010

R. Geisberger

Technical Report, August 11, 2009, Fakultät für Informatik, Universität Karlsruhe

Christian Vetter

Student research project, Universität Karlsruhe (TH), supervised by G.V. Batz and P. Sanders, 2009.

Sabine Neubauer

Student research project, Universität Karlsruhe (TH), supervised by G.V. Batz and P. Sanders, 2009.

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

R. Geisberger, M.N. Rice, P. Sanders, V.J. Tsotras

Journal of Experimental Algorithmics (JEA), Volume 17, Issue 1, Article No. 1.2, 2012.

R. Geisberger, P. Sanders, D. Schultes, C. Vetter

Transportation Science, April 2012



Conferences / Symposia
Titel Tagung Datum Autoren

International Symposium on Experimental Algorithms (SEA 2011)

May 2011

R. Geisberger, C. Vetter

Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE 2010)

October 2010

R. Geisberger, N. Sturtevant

Symposium on Combinatorial Search (SoCS 2010)

Juli 2010

Robert Geisberger, Dennis Schieferdecker

Workshop on Algorithm Engineering and Experiments (ALENEX 2010)

January 2010

R. Geisberger, M. Kobitzsch, P. Sanders

16th European Symposium on Algorithms (ESA 2008)

September 2008

P. Sanders, D. Schultes, C. Vetter

7th Workshop on Experimental Algorithms (WEA 2008)

May/June 2008

R. Geisberger, P. Sanders, D. Schultes, D. Delling

6th Workshop on Experimental Algorithms (WEA 2007)

June 2007

P. Sanders, D. Schultes



Reports
Titel Autor Quelle

R. Geisberger

Technical Report, February 4, 2010, Fakultät für Informatik, Karlsruhe Institute of Technology

Robert Geisberger

Diploma Thesis, Universität Karlsruhe (TH), supervised by P. Sanders and D. Schultes, 2008

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
Titel Tagung Datum Autoren

Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2010)

September 2010

R. Geisberger, P. Sanders

Workshop on Algorithm Engineering and Experiments (ALENEX 2007)

January 2007

S. Knopp, P. Sanders, D. Schultes, F. Schulz, D. Wagner



Reports
Titel Autor Quelle

S. Knopp, P. Sanders, D. Schultes, F. Schulz, D. Wagner

Technical Report, July 2006. (outdated version)



 
 

Transit-Node Routing

Journal Articles
Titel Autor Quelle

H. Bast, S. Funke, P. Sanders, D. Schultes

Science 316 (5824): S. 566, 2007



Conferences / Symposia
Titel Tagung Datum Autoren

12th International Symposium on Experimental Algorithms (SEA 2013)

June 2013

Julian Arz, Dennis Luxen, Peter Sanders

9th DIMACS Challenge on Shortest Paths

P. Sanders, D. Schultes

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

P. Sanders, D. Schultes

Journal of Experimental Algorithmics (JEA), Volume 17, Issue 1, Article No 1.6, 2012.



Conferences / Symposia
Titel Tagung Datum Autoren

14th European Symposium on Algorithms (ESA 2006)

September 2006

P. Sanders, D. Schultes

ESA 2005 October 2005 P. Sanders, D. Schultes


Reports
Titel Autor Quelle

Dominik Schultes

Master's thesis, Department of Computer Science, Universität des Saarlandes, July 2005.

P. Sanders, D. Schultes

Full paper, submitted for publication, preliminary version, September 2007.



 
 

Combinations

Journal Articles
Titel Autor Quelle

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
Titel Tagung Datum Autoren

7th Workshop on Experimental Algorithms (WEA 2008)

R. Bauer, D. Delling, P. Sanders, D. Schieferdecker, D. Schultes, D. Wagner

9th DIMACS Challenge on Shortest Paths

November 2006

D. Delling, P. Sanders, D. Schultes, D. Wagner



 
 

Applications

This section focuses on applications and realisitic scenarios.

Conferences / Symposia
Titel Tagung Datum Autoren

1st ACM SIGSPATIAL Workshop on MapInteraction (MapInteract 2013)

Nov, 5th 2013

Dennis Luxen

6th Annual Symposium on Combinatorial Search (SoCS 2013)

July 2013

Florian Drews, Dennis Luxen

6th Annual Symposium on Combinatorial Search (SoCS 2013)

July 2013

Dennis Luxen, Dennis Schieferdecker

Mediterranean Conference on Algorithms (MedAlg 2012)

December 2012

G.V. Batz, R. Geisberger, D. Luxen, P. Sanders, and R. Zubkov

11th International Symposium on Experimental Algorithms (SEA'12)

Jun 7-9, 2012

Dennis Luxen, Dennis Schieferdecker

Workshop on Algorithm Engineering and Experiments (ALENEX 2012)

January 2012

D. Delling, M. Kobitzsch, D. Luxen, R. Werneck

19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2011)

November 2011

Dennis Luxen, Christian Vetter

International Symposium on Experimental Algorithms (SEA 2011)

May 2011

D. Luxen, P. Sanders

International ICST Conference on Theory and Practice of Algorithms
in Computer Systems (TAPAS 2011)

April 2011

R. Bader, J. Dees, R. Geisberger, P. Sanders

Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2010)

September 2010

R. Geisberger, D. Luxen, P. Sanders, S. Neubauer, L. Volker



Reports
Titel Autor Quelle

G.V. Batz, R. Geisberger, D. Luxen, P. Sanders

Technical Report, November 22, 2010, Fakultät für Informatik, Karlsruher Institut für Technologie, arXiv:1011.4465v1

Chrisitian Vetter

Diploma Thesis, Karlsruhe Institute of Technology, supervised by Peter Sanders, 2010

J. Dees, R. Geisberger, P. Sanders, R. Bader

Technical Report, February 23, 2010, Fakultät für Informatik, Karlsruher Institut für Technologie

R. Geisberger, D. Luxen, S. Neubauer,

P. Sanders, L. Volker

Technical Report, July 30, 2009, Fakultät für Informatik, Universität Karlsruhe

Lars Volker

Student research project, Universität Karlsruhe (TH), supervised by P. Sanders and D. Schultes, 2008.