KIT | KIT-Bibliothek | Impressum | Datenschutz

Time-Dependent Route Planning with Contraction Hierarchies

Batz, Gernot Veit Eberhard

Abstract:
Design and experimental evaluation of route planning algorithms for time-dependent road networks, which model regular effects like congestions. By generalizing contraction hierarchies, we achieve fast and space efficient computation of minimum travel time routes and profiles. We also consider additional constant costs (e.g., to penalize detours and motorway tolls), which makes route planning NP-hard. Then, routes become heuristic, but we get quite near to the optimum as experiments show.

Open Access Logo


Volltext §
DOI: 10.5445/IR/1000047759
Coverbild
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Jahr 2014
Sprache Englisch
Identifikator urn:nbn:de:swb:90-477592
KITopen-ID: 1000047759
Verlag KIT, Karlsruhe
Abschlussart Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdaten 08.07.2014
Referent/Betreuer Prof. P. Sanders
Schlagworte algorithm engineering, earliest arrival problem, road networks, server-based route planning, time-dependent shortest path, travel time profile
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page