A hierarchical approach to the bottleneck problem in street networks

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. Hierarchische Beschleunigungsverfahren haben sich bei der Lösung von Wegfindungsproblemen in Straßennetzen als sehr effektiv erwiesen, insbesondere beim Problem des kürzesten Weges. Einer der bekanntesten hierarchischen Ansätze ist der Algorithmus „Contraction Hierarchies“. Ein weiteres wichtiges Wegfindungsproblem ist das Engstellenproblem, das darauf abzielt, den Weg mit der größten Mindestkapazität zu finden. Ziel dieser Arbeit ist es, zu untersuchen, wie der Contraction Hierarchies Algorithmus angepasst werden kann, um das Engstellenproblem in Straßennetzen zu lösen. Es wird auch untersucht, wie man Optimierungstechniken verwenden kann, um etwaige Probleme zu überwinden, die aufgrund der unterschiedlichen Natur der beiden Probleme auftreten können. Es zeigt sich, dass diese Optimierungstechniken zu einer großen Verbesserung der Abfragezeit im Vergleich zum nativen Ansatz führen und gleichzeitig die Vorverarbeitungszeiten niedrig halten. Die Algorithmen werden auf realen Straßennetzen mit einer Größe zwischen einer Million und 25 Millionen Knoten getestet. Schließlich wird getestet, ob ein angepasster Contraction Hierarchies-Ansatz verwendet werden kann, um das Problem des kürzesten Weges mit einer Mindestkapazität effizient zu lösen.