New Multiobjective Shortest Path Algorithms

Abstract

The main problem studied in this thesis is the Multiobjective Shortest Path (MOSP) problem. We focus on the problem variant with three or more objectives. It is a generalization of the classical Shortest Path problem in which arcs in the input graph are weighted with vectors instead of scalars. The main contribution is the Multiobjective Dijkstra Algorithm (MDA), a label- setting algorithm that achieves state of the art performance in theory and in practice. Motivated by this result, the thesis goes on with the design of variants of the MDA for different variants of the MOSP problem. For the One-to-One MOSP problem the Targeted MDA (T-MDA) has the same asymptotic running time than the MDA but trades in memory for speed in practice. The additional paths stored during the T-MDA are managed in a pseudo-lazy way. This is a novel way to organize explored paths that ensures that the algorithm’s priority queue stores at most one path per node in the input graph simultaneously. The paths that are held back from the queue are organized in lists that are kept sorted by just prepending or appending paths to them, i.e., using constant time insertions. The resulting implementation of the T-MDA solves bigger instances than the MDA and is also faster. We study the generalization of the Time-Dependent Shortest Path problem to the multiobjective case. We provide a detailed analysis of the generalization’s limitations and discuss when the MDA is applicable. For MOSP instances with large sets of optimal paths, good approximation algorithms are important. We combine the MDA with an outcome space partition technique from the literature to obtain a new FPTAS for the MOSP problem. The resulting MD-FPTAS works also for multiobjective instances of the Time-Dependent Shortest Path problem, which is a novelty. Finally, we use the MDA and its biobjective version, the BDA, to solve the Multiobjective Minimum Spanning Tree (MO-MST) problem and the k-Shortest Simple Path (k-SSP) problem, respectively. For the solution of instances of these two problems, the MDA and the BDA are used as subroutines. An MO-MST instance is solved applying the MDA on a so called transition graph. In this graph paths have equivalent costs to trees in the original graph and thus, the optimal solutions computed by the MDA in the transition graph correspond to optimal trees in the original graph. Since the transition graph has an exponential size w.r.t. the size of the original graph, we discuss new pruning techniques to reduce its number of arcs effectively. The solution of the k-SSP, which is a scalar optimization problem, using a biobjective subroutine is surprising but our new algorithm is state of the art in theory and in practice.

In dieser Arbeit beschäftigen wir uns hauptsächlich mit dem Multikriterielle Kürzeste Wege (MOSP) Problem. Es ist eine Verallgemeinerung des klassischen Kürzeste Wege Problems, bei der Kanten im Eingangsgraphen mit d-dimensionalen Vektoren anstelle von Skalaren gewichtet sind. Der Hauptbeitrag der Arbeit ist der Multiobjective Dijkstra Algorithmus (MDA), ein label-setting Algorithmus, der in der Theorie und in der Praxis eine Verbesserung der in der Literatur vorhandenen Ergebnisse darstellt. Motiviert durch dieses Ergebnis entwickeln wir im weiteren Verlauf der Arbeit Varianten des MDAs für verschiedene Varianten des MOSP Problems.

Für das Punkt-zu-Punkt MOSP Problem hat der Targeted MDA (T-MDA) die gleiche asymptotische Laufzeit wie der MDA. Durch einen erhöhten Speicherverbrauch ist er in der Praxis aber deutlich schneller. Die zusätzlich gespeicherten Pfade werden auf eine pseudo-lazy Art verwaltet. Dies ist eine neuartige Methode zur Organisation von explorierten Pfaden, die sicherstellt, dass die Größe der Prioritätswarteschlange des Algorithmus auf höchstens einen Pfad pro Knoten im Graphen beschränkt bleibt. Die Pfade, die aus der Warteschlange zurückgehalten werden, werden in Listen organisiert, die durch Voranstellen oder Anhängen von Pfaden sortiert bleiben. Das heißt, dass nur Konstantzeit-Operationen benötigt werden. Der T-MDA löst größere Instanzen als der MDA und ist auch schneller.

Wir untersuchen die Verallgemeinerung des zeitabhängigen Kürzeste Wege Problems auf den multikriteriellen Fall. Wir bieten eine detaillierte Analyse der Grenzen und Möglichkeiten dieser Verallgemeinerung und diskutieren, wann der MDA hierauf anwendbar ist. Für MOSP Instanzen mit großen Mengen optimaler Pfade sind gute Approximationsalgorithmen wichtig. Wir kombinieren den MDA mit einer Technik zur Partitionierung des Ergebnisraums aus der Literatur, um einen neuen FPTAS für das MOSP Problem zu erhalten. Der resultierende MD-FPTAS funktioniert auch für Instanzen mit verallgemeinert zeitabhängigen Kostenfunktionen, was neuartig ist.

Schließlich verwenden wir den MDA und seine bikriterielle Version als Unterroutinen, um jeweils das Multiobjective Minimum Spanning Tree (MOMST) Problem und das k-Shortest Simple Path (k-SSP) Problem zu lösen. Eine MO-MST Instanz wird gelöst, indem der MDA auf einen sogenannten Übergangsgraphen angewendet wird. In diesem Graphen haben Pfade äquivalente Kosten zu den Bäumen im ursprünglichen Graphen und somit entsprechen die optimalen Lösungen, die vom MDA im Übergangsgraphen berechnet werden, den optimalen Bäumen im ursprünglichen Graphen. Da der Übergangsgraph eine exponentielle Größe im Verhältnis zur Größe des ursprünglichen Graphen hat, diskutieren wir neue Techniken zur Reduzierung seiner Anzahl von Kanten. Die Lösung des k-SSP Problems, ein skalares Optimierungsproblem, unter Verwendung einer bikriteriellen Unterroutine ist überraschend, aber unser neuer Algorithmus ist sowohl in der Theorie als auch in der Praxis auf dem neuesten Stand.