Bachelorarbeit BCLR-2024-13

Bibliograph.
Daten
Ng, Patrick: A hierarchical approach to the bottleneck problem in street networks.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 13 (2024).
51 Seiten, englisch.
Kurzfassung

Hierarchical speed-up techniques have proven to be very effective in solving pathfinding problems in street networks, especially the shortest path problem. One of the most prominent hierarchical approaches is the Contraction Hierarchies algorithm. Another important pathfinding problem is the bottleneck problem, which has the goal of finding the path with the largest minimum capacity. The goal of this thesis is to explore how the Contraction Hierarchies algorithm can be adapted to solve the bottleneck problem in street networks. It also investigates how to use workarounds to overcome any shortcomings that may arise due to the different nature of the two problems. These workarounds prove to lead to a big query time improvement compared to the native approach while still keeping preprocessing times low. The algorithms are tested on real street networks varying in size between one million and 25 million vertices. Finally, it is tested if an adapted Contraction Hierarchies approach can be used to efficiently solve the minimum capacity shortest path problem.

Volltext und
andere Links
Volltext
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Algorithmik
BetreuerFunke, Prof. Stefan; Proissl, Dr. Claudius
Eingabedatum15. Oktober 2024
   Publ. Institut   Publ. Informatik