KIT | KIT-Bibliothek | Impressum | Datenschutz

Engineering and Augmenting Route Planning Algorithms

Delling, Daniel

In this work, we introduce the first efficient, provably correct, algorithms for route planning in time-dependent and multi-criteria scenarios. Therefore, we follow the concept of algorithm engineering by designing, analyzing, implementing, and evaluating speed-up techniques for Dijkstra's algorithm. As a result, we are able to compute best connections in continental-sized time-dependent transportatios networks (both of roads and railways) in the matter of a few milliseconds.

Open Access Logo

Volltext §
DOI: 10.5445/IR/1000011046
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Publikationsjahr 2009
Sprache Englisch
Identifikator urn:nbn:de:swb:90-110465
KITopen-ID: 1000011046
Verlag Universität Karlsruhe (TH)
Art der Arbeit Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdaten 10.02.2009
Referent/Betreuer Prof. D. Wagner
Schlagwörter algorithm engineering, shortest paths, time-dependency, graph algorithms
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page