KIT | KIT-Bibliothek | Impressum

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.

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Jahr 2014
Sprache Englisch
Identifikator URN: urn:nbn:de:swb:90-477592
KITopen ID: 1000047759
Verlag 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