Abstract

Online Disruption and Delay Management
Sabine Büttner
In many optimization problems in practice, a solver cannot draw on complete information
about the data which specifies the instances. Some portion of the data is unknown at
the beginning and becomes available over time, but requests have to be answered immediately. These problems are in the field of online optimization. The quality of a method
and the corresponding solution can most often only be rated in hindsight, when all data is
known. A common way to compare online algorithms is to use Competitive Analysis: the
cost entailed by an online solution process is compared to the optimal offline cost, i.e. the
minimum cost if all data would have been known in advance. The competitiveness of an
algorithm is defined by the maximum ratio of these to terms over all instances.
This concept is a powerful tool to analyze algorithms from a theoretic viewpoint. Nevertheless, the technique has often been criticized for being too pessimistic, because algorithms
with a poor theoretical performance are useful in practical applications.
This thesis tries to find ways to overcome these drawbacks and go beyond pure competitive
analysis for several problems. On the one hand, the worst-case nature of the analysis and,
on the other hand, the pessimistic assumption, that the algorithms have absolutely no
knowledge about the future data is addressed.
In a first part, the known online Canadian Traveller Problem is extended. In this problem, a
shortest path through a network has to be determined. The graph is given at the beginning,
but some of the edges might in fact be unavailable. This is revealed in an online fashion
only, when one of the endpoints is reached. The Canadian Travelling Salesman Problem as
well as the Canadian Tour Operator Problem adopt this feature. In contrast to finding a
shortest path through the graph, the problems ask for shortest tours – in the first variant,
the tour is required to go through all vertices at least once, while in the second vertices,
can be left unvisited if a given penalty is paid instead. Competitive algorithms for general
graphs as well as for restricted graph-classes and lower bounds on the competitiveness are
given. Furthermore, the model and the objective aim is varied (Resource Augmentation,
latency objective) which yields again competitive algorithms. Besides, algorithms to derive
robust solutions for the second problem are presented.
In a second part, the Online Delay Management Problem on a single train line is investigated. In this problem, the best waiting decision for a train has to be specified, such that
on time passengers and passengers with a source delay are served equally satisfyingly. The
focus is again on going beyond the known results in the competitive analysis framework.
Several existing concepts are deployed to achieve results with more practical relevance.
Among these are Comparative Analysis, Average-case (Competitive) Analysis as well as
Stochastic Programming. Algorithms meeting the various quality aims are described.
Online Disruption and Delay Management
Sabine Büttner
In vielen praktischen Optimierungsproblemen kann zur Lösung anfangs nicht auf alle
Daten, die die Probleminstanz definieren, zurückgegriffen werden. Teile der Informationen werden erst im Laufe der Zeit bekannt, und dennoch müssen Lösungsverfahren schon
Entscheidungen treffen ohne alle Werte zu kennen. Diese Probleme fallen in den Bereich
der Online Optimierung. Die Bewertung von Lösungen und Lösungsverfahren geschieht
meist erst im Nachhinein. In der dazu oftmals angewendeten Kompetitivitätsanalyse werden die Kosten, die eine (online gegebene) Lösung verursacht, in Relation zu den optimalen
Kosten gestellt, wenn alle Informationen von Beginn an verfügbar gewesen wären. Auch
wenn dieses Verfahren ein brauchbares Werkzeug zur theoretischen Bewertung von Onlinealgorithmen darstellt, sieht sie sich doch oftmals gerechtfertigter Kritik gegenüber. Die
theoretische Bewertung eines Verfahrens geschieht in einer ’worst-case’-Analyse, und in
praktischen Auswertungen erweisen sich Verfahren meist als deutlich besser.
In dieser Arbeit wird für bestimmte online Probleme versucht, diese Nachteile zu umgehen. Dabei spielen sowohl die unrealistische Annahme, dass Algorithmen vollkommen ohne
Information über die zukünftigen Daten auskommen müssen, als auch alternative AnalyseMethoden eine Rolle.
Im ersten Teil wird das bekannte Canadian Traveller Problem zum Canadian Travelling
Salesman und dem Candian Tour Operator Problem erweitert. In der klassischen Variante muss ein kürzester Weg durch einen Graphen bestimmt werden, in den zwei neuen
Modellen eine kürzeste Tour. In der letzteren Variante dürfen zusätzlich einzelne Knoten
gegen das Zahlen einer ‘penalty’ ausgelassen werden. Allen Problemen ist dabei die OnlineEigenschaft gemeinsam: Wenn auf dem Pfad oder auf der Tour ein Knoten erreicht wird,
kann entdeckt werden, dass eine davon ausgehende Kante gesperrt und damit unpassierbar
ist. Die Arbeit bietet untere Schranken für die Kompetitivität der Probleme sowie kompetitive Algorithmen für allgemeine, aber auch für eingeschränkte Graphklassen. Außerdem werden die Modelle bzw. die Zielfunktionen variiert (z.B. durch Resource Augmentation, latency-Zielfunktion). Auch für diese Varianten werden kompetitive Algorithmen
beschrieben.
Ein zweiter Teil behandelt das Online Delay Management Problem auf einer einzelnen
Zuglinie wiederum mit dem Ziel, die klassischen Kompetitivitätsergebnisse zu erweitern.
In diesem Problem muss die beste Warteentscheidung für einen Zug getroffen werden, sodass pünktliche und (vorab) verspätete Passagier gleichermaßen zufrieden gestellt werden.
Zum Überwinden des pessimistischen Charakters der Kompetitivitätsanalyse werden verschiedene bestehende Konzepte angewendet und Algorithmen, die das jeweilige Qualitätsmaß berücksichtigen, vorgestellt. Anwendung finden dabei Comparative Analysis, Averagecase (Competitive) Analysis und Stochastic Programming.