Shortest path speed up techniques : lower bounds and applications

Abstract

The widespread proliferation of portable hand held computing devices in the form of mobile phones, rivaling 6 year old desktop computers in raw computational power and outclassing them in terms of communication interfaces and interoperability, gave rise to a plethora of new geospatial applications and services. One of the many roles a modern mobile phone can provide, is the complete substitution of printed maps with added functionality as navigation aid, for self localization, or - with more semantic back-end information - complex routing queries all around the world. With the computer-based compilation of the majority of the worlds' road networks, which are freely available to everyone in the form of OpenStreetMap, vast geospatial databases are to our disposal today. One of the most fundamental questions in such a network is to compute a shortest (or quickest) path between two designated points. This problem was solved by Dijkstra in 1959 in a provably optimal way, but his algorithm, although very elegant and simple in design, does not scale well on continent sized road graphs. Therefore a multitude of alternative approaches for the single-source-single-target shortest path problem and more complicated flavors were devised in the last decade. The motivation for highly efficient algorithms in this field is twofold. On the one hand they enable a real time user experience on a mobile phone, even for complex tasks, on the other hand these approaches scale well when a server back-end is employed, whose task is to server a large number of mobile agents. If used in combination these techniques enable us to compute different shortest path related problems in the order of ten milliseconds on the complete road network of Europe. This constitutes a speedup of more than three magnitudes compared to Dijkstra's approach. This work consists of three main parts, each addressing an exemplary problem in the field of geospatial application which are outlined in the following sections.

- Transit Node Constructions Revisited

In the first part we reconsider the concept of transit nodes as introduced by Bast et al. Transit nodes are an offline speed up technique which enables very fast point to point shortest path distance computations and are based on a precomputed point to point distance table of a small subsets of nodes - the transit nodes. For the first time we construct instance based lower bounds on the size of transit node sets by interpreting a LP formulation of the problem and its dual and, as a side product, we achieve considerably smaller access node sets which directly improve the query time for non-local queries. We devise an algorithm to construct transit node sets for this theoretic framework and verify their properties with a practical implementation. This result was also published as ''Transit Nodes - Lower Bounds and Refined Construction'' at the 14th Meeting on Algorithm Engineering and Experiments (ALENEX) in 2012.

- Applications of speedup Techniques: Path Prediction

In the second chapter of this work we work on the path prediction problem - given the path a mobile user has moved along in a road network up to the current moment, predict where the user will move along in the near future. In contrast to known solutions to this problem we will compute our prediction not only based on the geometry of the known path (using extrapolation) or directional information implied by the underlying road network but make explicit use of the structure of the space of shortest paths in the network. Our proposed path prediction algorithm is equally simple but yields extremely accurate predictions at a very low computational cost. This work was published as path of the paper ''Algorithms for Matching and Predicting Trajectories'' in the 13th Meeting on Algorithm Engineering and Experiments (ALENEX) at 2011.

- Applications of speedup Techniques: Sequenced Route Queries

The third and final chapter considers the problem of a sequenced route query - the problem of planning an optimal route (quickest or shortest) that visits facilities of the respective type (for example a gas station or a super market) on the way home. The proposed solution, based on the combination of a distance sensitive doubling technique and contraction hierarchies, is orders of magnitudes faster than either a naive approach or previous results. In addition it produces the answers in an instant for realistic queries without compromising guaranteed optimality. With such fast query times, this type of route query becomes feasible even on mobile devices or for high-throughput web-based route planners. This work is published as ''Sequenced Route Queries: Getting Things Done on the Way Back Home'' in the Proceedings of the 20th International Conference on Advances in Geographic Information Systems (SIGSPATIAL) in 2012.

In dieser Arbeit bearbeiten wir drei Problemstellungen aus dem Bereich der Routenplanung und deren Anwendung auf großen Straßennetzwerken.

Im ersten Kapitel haben wie eine Methode vorgestellt Transitknotenmengen auf eine bestimmte Art und Weise zu berechnen, die es uns ermöglicht instanzbasiert Aussagen über die Approximationsgüte dieser Mengen zu treffen. Wir haben dafür eine Definition von ''langen'' kürzesten Wegen gewählt, welche entweder direkt auf deren Länge oder aber dem Dijkstrarank ihrer Knoten basiert, und einen Algorithmus entwickelt, der Präfixe aller dieser Pfade effizient berechnet. Mit diesen Präfixen haben wir ein Mengenüberdeckungsproblem und das duale Mengenpackungsproblem definiert, mit denen wir aus den Resultaten der ganzzahligen linearen Optimierung eine untere Schranke für die optimale Größe einer optimalen Transitknotenmenge herleiten können. Wir haben diesen Ansatz mit anderen Konstruktionsverfahren verglichen, um zu erfahren ob diese bei gleicher Definition von ''lang'' nicht wesentlich kleiner gewählt werden könnten. Dies ist nicht der Fall. Allerdings konnten wir zeigen, dass die mit unserer Methode generierten Transitknotenmengen in wesentlich weniger Transitknoten per Knoten im Graph resultieren und damit direkt schnellere kürzeste Pfad Anfragen erlauben.

Im zweiten Kapitel ging es um Pfadvorhersage als Anwendung von schnellen Routenplanungsalgorithmen. Da Straßengraphen eine stark ausgeprägte hierarchische Struktur aufweisen, konnten wir dies nutzen um gefahrene kürzeste Wege ab einer gewissen Länge mit sehr hoher Präzision vorherzusagen. Wir haben dafür die ''Reach'' Metrik von Kanten benutzt, die für jede Kante die Länge des längsten küzesten Pfades angibt, welcher durch diese Kante geht. Zusammen mit anderen komplexen Metriken wie der Anzahl an kürzesten Wegen welche in einem Knoten starten, haben wir mehrere komplett auf Vorberechnung basierende Vorhersagestrategien entwickelt. Diese haben gegenüber ihren online Gegenstücken nicht nur den Vorteil bei der eigentlichen Anfrage weniger Rechenschritte zu benötigen, als auch wesentlich weniger Vorhersagefehler zu erzeugen. Wir haben mehrere online sowie offline Strategien praktisch verglichen und eine optimale Kombination vorgestellt, welche die Anzahl von Vorhersagefehlern minimiert.

Das letzte Kapitel ist eine Anwendung von ''Contraction Hierarchies''. CHs ermöglichen sehr schnell kürzeste Wege zu berechnen. Dies nutzen wir um eine Modifizierte Variante des Problems des Handlungsreisenden zu lösen, bei der zwar die Reihenfolge der Städte fixiert ist aber für jede Stadt sehr viele Alternativen zur Verfügung stehen. Wir haben dafür einen Suchalgorithmus entwickelt, der für je zwei aufeinander folgende Zielmengen einen Suchraum bildet und sich dann iterativ in größer werdenden Abständen vom Startpunkt durch diese Suchräume arbeitet. Dies erlaubt uns Optimalität bei der Länge des Weges beizubehalten und nie mehr als einen konstanten Faktor an möglichen Stadtknoten zu viel zu explorieren. Wir zeigen, dass unsere Implementierung schnell genug ist, um jede realistische Anfrage in wenigen Millisekunden optimal zu beantworten.