KIT | KIT-Bibliothek | Impressum | Datenschutz

Engineering Algorithms for Dynamic and Time-Dependent Route Planning

Zeitz, Tim 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract:

Efficiently computing shortest paths is an essential building block of many mobility applications, most prominently route planning/navigation devices and applications. In this thesis, we apply the algorithm engineering methodology to design algorithms for route planning in dynamic (for example, considering real-time traffic) and time-dependent (for example, considering traffic predictions) problem settings. We build on and extend the popular Contraction Hierarchies (CH) speedup technique. With a few minutes of preprocessing, CH can optimally answer shortest path queries on continental-sized road networks with tens of millions of vertices and edges in less than a millisecond, i.e. around four orders of magnitude faster than Dijkstra’s algorithm. CH already has been extended to dynamic and time-dependent problem settings. However, these adaptations suffer from limitations. For example, the time-dependent variant of CH exhibits prohibitive memory consumption on large road networks with detailed traffic predictions.

This thesis contains the following key contributions: First, we introduce CH-Potentials, an A*-based routing framework. CH-Potentials computes optimal distance estimates for A* using CH with a lower bound weight function derived at preprocessing time. ... mehr


Volltext §
DOI: 10.5445/IR/1000154045
Veröffentlicht am 22.12.2022
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Publikationsdatum 22.12.2022
Sprache Englisch
Identifikator KITopen-ID: 1000154045
Verlag Karlsruher Institut für Technologie (KIT)
Umfang IX, 243 S.
Art der Arbeit Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdatum 09.12.2022
Referent/Betreuer Wagner, Dorothea
Müller-Hannemann, Matthias
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page