| Bibliography | Ng, Patrick: A hierarchical approach to the bottleneck problem in street networks. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 13 (2024). 51 pages, english.
|
| Abstract | 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.
|
Full text and other links | Volltext
|
| Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
|
| Superviser(s) | Funke, Prof. Stefan; Proissl, Dr. Claudius |
| Entry date | October 15, 2024 |
|---|