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.


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