Aufgabe der Fahrplanauskunft ist es, Fahrgästen eine Auswahl von Verbindungen zwischen Start- und Zielort zur Auswahl zu stellen. Fahrplanauskunftssysteme bestimmen mögliche Verbindungen anhand unterschiedlicher Kriterien, wie zum Beispiel der (fahrplanmäßigen) Reisezeit, der Anzahl der Umstiege oder der Kosten der Verbindung. Kaum beachtet werden dabei bisher die möglichen Auswirkungen von Verspätungen auf die Verbindungen. Erstens führen Verspätungen in der Regel zu einer Verlängerung der Reisezeit. Zweitens kann es sein, dass Anschlüsse verpasst werden, wenn ein Anschlusszug nicht wartet, und die Verbindung also gar nicht mehr wie geplant gefahren werden kann. Ziel der robusten Fahrplanauskunft ist es, Verbindungen zu bestimmen, die möglichst unempfindlich gegenüber Verspätungen sind. In diesem Artikel stellen wir drei unterschiedliche Robustheitskonzepte vor und erklären ihre Anwendung auf die Fahrplanauskunft. Wir beschreiben algorithmische Ansätze zur Bestimmung robuster Verbindungen und diskutieren Vor- und Nachteile der unterschiedlichen Konzepte.

Der Fachvortrag zur Veranstaltung ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.

1 Einleitung

Ziel der Fahrplanauskunft ist es, im öffentlichen Verkehr basierend auf einem Fahrplan Reiseverbindungen für Fahrgäste zu bestimmen. Der Fahrgast gibt Start- und Zielort und die gewünschte Abfahrtszeit (oder Ankunftszeit) an, spezifiziert eventuell noch weitere Kriterien wie den Fahrzeugtyp oder eine Maximalanzahl an Umsteigevorgängen und erhält darauf basierend eine Verbindung oder eine Menge von Verbindungen. Fahrplanauskunftssysteme finden sich auf der Website fast jedes größeren Verkehrsbetriebs, beispielsweise der Website der Deutschen Bahn1 .

Die Auswahl der angezeigten Verbindungen erfolgt nach verschiedenen Gütekriterien, wie der Reisezeit, der Anzahl der Umsteigevorgänge und den Kosten einer Verbindung. Unterschiedliche Modelle und Algorithmen werden benutzt, um Fahrplanauskunft als mathematisches Problem zu modellieren und zu lösen. Einen Überblick über den Stand der Technik, grundlegende Modelle und algorithmische Ansätze zum exakten Lösen dieser Optimierungsprobleme geben Müller-Hannemann et al. [17] und Bast et al. [20]. Zu den wichtigsten exakten Verfahren, die in den letzten Jahren entwickelt wurden, gehören [9-11, 13]. Diese Verfahren basieren in der Regel auf dem Sollfahrplan.

Leider kommt es im öffentlichen Verkehr immer wieder zu Verspätungen, so dass sich der tatsächlich gefahrene Fahrplan vom Sollfahrplan unterscheidet. Das kann für die Fahrgäste nicht nur zu höheren Reisezeiten auf den ursprünglich geplanten Verbindungen führen, sondern auch dazu, dass Anschlüsse verpasst werden und Reiserouten angepasst werden müssen. Wenn man bereits unterwegs ist, hätte man daher gerne eine Fahrplanauskunft, die die aktuelle Verspätungslage berücksichtigt. Solche Echtzeit-Auskunftsverfahren sind aus algorithmischer Sicht eigentlich gut realisierbar, wie z.B. Müller-Hannemann und Schnee [19] nachgewiesen haben, jedoch werden derzeit in der Praxis, wenn eine Echtzeit-Auskunft überhaupt angeboten wird, häufig nur suboptimale Heuristiken eingesetzt. In diesem Artikel gehen wir einen Schritt zurück und interessieren uns in erster Linie für die Planungsphase, bei der wir schon vor Fahrtbeginn möglichst robuste Verbindungen finden möchten.

Intuitiv bezeichnet man Verbindungen als „robust'', wenn Verspätungen wenig Auswirkungen auf ihre Durchführbarkeit haben, oder wenn es im Falle von Verspätungen problemlos möglich ist, auf Alternativverbindungen umzusteigen. In der Literatur gibt es unterschiedliche Ansätze, um Auswirkungen von Verspätungen zu minimieren. Eine ganz simple, häufig in Auskunftsportalen angebotene Variante ist das Vorgeben von Mindestzeiten für zulässige Anschlüsse, die der Kunde pauschal nach seinem Sicherheitsbedürfnis wählt. Alternativ kann man für jeden potenziellen Anschluss ein Zuverlässigkeitsmaß einführen (z.B. die Größe des Umstiegspuffers) und dann daraus ein Gesamtmaß für die Zuverlässigkeit einer Verbindung bilden, welches man optimiert [12]. Dibbelt et al. [11] greifen diese Grundidee auf und minimieren die erwartete Ankunftszeit einer Verbindung unter der Annahme, dass die Wahrscheinlichkeiten für gebrochene Umstiege voneinander unabhängig sind und sich direkt aus dem Umstiegspuffer ergeben. Anstelle von Verbindungen werden Entscheidungsgraphen berechnet, die dem Nutzer an jeder Stelle seiner Reise Instruktionen geben, wie am besten weiter zum Ziel gereist werden soll. Ein wesentlicher Nachteil der genannten Verfahren ist, dass sie kein (oder wenigstens kein realistisches) Modell besitzen, welche Verspätungen auftreten können. Bei Verfahren der robusten Optimierung hingegen modelliert man die Unsicherheit, indem man Mengen von Szenarien angibt, die die Verspätungsmuster beschreiben, gegen die man sich absichern möchte.

Mit diesem Artikel möchten wir erläutern, wie Konzepte der robusten Optimierung für die Fahrplanauskunft eingesetzt werden können. Dabei stellen wir die Ergebnisse unserer Arbeiten [6, 14, 15] vor. Diese Arbeiten fassen erstmalig den vorher nur intuitiven Begriff der Robust­ heit einer Verbindung formal und erlauben es, ihn als (weiteres) Optimierungskriterium bei der Verbindungssuche zu einzusetzen.

Wir nutzen als zugrunde liegendes Netzwerkmodell sogenannte Ereignis-Aktivitäts-Netzwerke (EAN). Diese besitzen den Vorteil, dass Verbindungssuche und Verspätungsausbreitung auf der gleichen Netzwerkstruktur modelliert werden können. Während Verbindungen als Wege dargestellt werden, führen Verspätungen zu einer Änderung der Netzwerkstruktur. Wird durch solche Änderungen ein Weg zerstört, ist die zugehörige Verbindung aufgrund der Verspätung nicht mehr durchführbar.

In diesem Artikel stellen wir deswegen zunächst in Abschnitt 2 Ereignis-Aktivitäts-Netzwerke und die Modellierung von Fahrplanauskunftsproblemen und in Abschnitt 3 die Verspätungsausbreitung in EANs vor. Es folgt eine kurze Einführung in die robuste Optimierung in Abschnitt 4. Drei unterschiedliche Konzepte zur robusten Fahrplanauskunft werden dann in den Abschnitten 5.1-5.3 vorgestellt und in Abschnitt 6 verglichen.

2 Ereignis-Aktivitätsnetzwerke und Fahrplanauskunft

2.1 Ereignis-Aktivitätsnetzwerke

Das Konzept der Ereignis-Aktivitätsnetzwerke (EANs) stammt ursprünglich aus der Projektplanung. In der Verkehrsplanung wird es benutzt, um zeitliche Abhängigkeiten zwischen Abfahrten und Ankünften von Zügen an Bahnhöfen darzustellen, etwa um zulässige Fahrpläne zu erstellen oder Verspätungsausbreitung zu modellieren.

Start- und Zielort eines Fahrgastes, sowie Abfahrten und Ankünfte von Fahrzeugen an Haltestellen werden im EAN N = (E,A) über Knoten, sogenannte Ereignisse dargestellt. Genauer ist die Knotenmenge E gegeben als Vereinigung von Abfahrts- und Ankunftsereignissen Eab und Ean , sowie jeweils einem weiteren Knoten um Start- und Zielort des Fahrgasts zu modellieren. Die Abfahrt eines Fahrzeugs an einer Haltestelle wird mit der Ankunft an der nachfolgenden Haltestelle durch eine Fahrkante a E Afahr verbunden. Weiterhin wird die Ankunft an einer Haltestelle, die nicht Endhaltestelle eines Fahrzeugs ist, mit der darauf folgenden Abfahrt des Fahrzeugs durch eine Wartkante a E Awarte verbunden. Mögliche Umstiege zwischen Fahrzeugen werden durch Umstiegsaktivitäten a E Aumstieg zwischen der Ankunft des zu verlassenden Fahrzeugs und der Abfahrt des zu betretenden Fahrzeugs dargestellt.

Wir gehen im Felgenden davon aus, dass der Fahrgast eine Abfahrtszeit und keine Ankunftszeit angegeben hat. (Ist die Ankunftszeit angegeben, funktionieren alle weiteren Überlegungen ganz analog.) Im Falle einer festgelegten Abfahrtszeit wird der Startknoten estart durch Startkanten A,tart mit allen Abfahrten am Startort ab der gewählten Startzeit verbunden, der Zielknoten eziel durch Zielkanten A.ieI mit allen Ankünften am Zielort. Ein Beispiel für ein EAN ist in Abbildung 1 dargestellt.

Zu sehen sind hier zwei Fahrzeuge f1und f2 f1 fährt von Haltestelle h1  über h3  nach h4 , f2 fährt von h2 über h3 nach h4. Die fahrplanmäßigen Zeiten für Ankunfts- und Abfahrtsereignisse sind in den jeweiligen Knoten angegeben. Fahr-, Warte-, und Umstiegszeiten ergeben sich aus der Differenz der in den Knoten angegebenen Zeiten. Beispielsweise beträgt die Fahrzeit mit f1 von h1 nach h3 21 Minuten. Start- und Zielaktivitäten geben an, in welches Fahrzeug der Fahrgast einsteigen kann, bzw. in welchem Fahrzeug er das Ziel erreichen könnte.

Ein Fahrgast möchte um 15:00 Uhr von h1 nach h4 fahren. Da nur Fahrzeug fi in h1 abfährt, muss er dort einsteigen.  In h3 kann er auswählen, ob er in Fahrzeug f2 umsteigt, oder in f1 sitzenbleibt. Steigt er um, ergibt sich eine Reisezeit von 33 Minuten (oder 35 Minuten ab der gewünschten Abfahrtszeit). Entscheidet er sich, in f1 zu bleiben, beträgt die Reisezeit 38 Minuten (oder 40 Minuten ab der gewünschten Abfahrtszeit).

Abb. 1: Beispiel für ein EAN

2.2 Fahrplanauskunft als Kürzeste-Wege-Problem im EAN

Wie in Abbildung 1 leicht zu erkennen ist, werden die möglichen Verbindungen vom Start- zum Zielbahnhof durch die Wege im Netzwerk vom Start- zum Zielknoten dargestellt. Um einen Weg mit kürzester Reisezeit zu finden, kann jetzt ein Standard kürzeste-Wege-Verfahren, beispielsweise Dijkstras Algorithmus [4] verwendet werden, indem man als Kantenlängen im Netzwerk die Fahr-, Warte- und Umsteigezeiten setzt. Nutzt man aus, dass solche Netzwerke stets azyklisch sind, kann man einen kürzesten Weg in Linearzeit (bezüglich der Kantenanzahl im Graphen) bestimmen. Jüngste Studien zeigen, dass diese sehr einfache Grundidee auch praktisch sehr effizient umgesetzt werden kann, wenn man den Graphen nicht explizit, sondern äußerst kompakt mit Hilfe von Arrays implizit abspeichert [11].

Auch die Suche nach Wegen mit einer möglichst geringen Anzahl an Umstiegen lässt sich als Kürzeste-Wege-Problem im EAN formulieren. Anstelle Fahr-, Warte- und Umstiegszeiten als Kantenlängen anzunehmen, gewichtet man Fahr- und Wartekanten mit o und Umstiegsaktivitäten mit 1. Die „Länge" eines Weges gibt dann die Anzahl der Umstiege an, ein ,,kürzester Weg" minimiert die Anzahl der Umstiege. Um Lösungen zu finden, die gut bezüglich mehrerer Kriterien sind, also z.B. eine kurze Reisezeit und eine geringe Anzahl an Umstiegen bieten, können Algorithmen für multikriterielle kürzeste Wege benutzt werden. Auch hier gibt es speziell an die Verbindungssuche im ÖV angepasste Algorithmen, auf EAN-Modellen basiert etwa [18]. Einschränkungen auf eine bestimmte Fahrzeugklasse (zum Beispiel: nur Nahverkehr), die Ankunft vor einem bestimmten Zeitraum oder die Beschränkung auf Strecken in einem bestimmten Gebiet lassen sich ebenfalls modellieren, indem vor der Wegesuche alle Knoten und Kanten aus dem EAN gelöscht werden, die wegen zeitlicher oder räumlicher Einschränkungen oder Einschränkungen der benutzbaren Fahrzeuge nicht in einem Weg vorkommen sollen.

3 Verspätungsausbreitung im EAN

Im Folgenden beschreiben wir ein EAN-basiertes Modell zur Verspätungsausbreitung, wie es beispielsweise auch in der Anschlusssicherung benutzt wird [2, 7].
Sei ,r = (1r;)iEE der ursprüngliche Fahrplan, d. h. für jedes Abfahrts- oder Ankunftsereignis I bezeichne 1r; die fahrplanmäßige Zeit, zu der das Ereignis stattfindet. Sei d = (da)aEA,..,uAw.«. ein Vektor von Quellverspätungen, d. h. Verspätungen während Fahr- oder Warteaktivitäten, die nicht durch vorhergehende Verspätungen verursacht werden. Quellverspätungen können beispielsweise durch Wettereinflüsse oder Baustellen entstehen.

Abhängig von den Quellverspätungen d wird der Sollfahrplan ,r zu einem Dispositionsfahrplan 1r(d) aktualisiert. Dabei ist zunächst zu beachten, dass wenn eine Fahraktivität länger dauert als geplant, sich die darauf folgende Ankunft zeitlich nach hinten verschiebt. Gleiches gilt für die darauf folgende Abfahrt des Zuges, falls die Verspätung nicht durch Zeitpuffer im Sollfahrplan aufgefangen werden kann. Es bezeichne l;j die Mindestdauer einer Aktivität (i, j). Bei Fahraktivitäten ergibt sich diese aus der mindestens benötigten Zeit, um die entsprechende Strecke zurückzulegen, für Warte- und Umstiegsaktivitäten ist es die Zeit, die benötigt wird, damit alle Fahrgäste aus- oder umsteigen können. Für Start- und Zielaktivitäten setzen wir lij := 0. Für den Dispositionsfahrplan 1r(d) gilt für jede Fahr- und Warteaktivität d. h. (im Falle einer Fahraktivität), dass das Fahrzeug frühestens lij Minuten nach Abfahrtser­ eignis i an der nächsten Haltestelle ankommen kann.

Weiterhin nehmen wir an, dass d. h. kein Ereignis darf früher stattfinden, als ursprünglich geplant.

Formel (1) siehe PDF.

Formel (2) siehe PDF.

Verspätungen pflanzen sich auch fort, wenn Fahrzeuge auf verspätete Fahrzeuge warten, um Umstiegsmöglichkeiten zu erhalten. Wir gehen hier von einem regelbasierten Ansatz aus: Für jede Umsteigeaktivität (i, j) E Aumstieg ist eine Maximalwartezeit W;j festgelegt, die das Fahrzeug, in das umgestiegen wird, im Falle einer Verspätung des Fahrzeugs, aus dem umgestiegen wird, warten würde. Auch die Deutsche Bahn nutzt im Wesentlichen solche regelbasierten Ansätze. Diese Regel lässt sich für Umstiegsaktivität (i,j) E Aumstieg schreiben als Falls dagegen gilt, so wird nicht aktiv versucht, den Anschluss zu halten, und die Bedingung (3) fällt weg.

Formel (3) siehe PDF.

Wir erhalten folgende Rechenvorschrift für die Erstellung des Dispositionsfahrplans die wir auf alle Knoten i E Eab u e.,,, in der durch die fahrplanmäßigen Zeiten 1r; vorgegebenen Reihenfolge anwenden. Dabei setzen wir aus technischen Gründen d;i = o für alle Umstiegs­ aktivitäten a E Aumstieg und w;j = oo für alle Fahr- und Warteaktivitäten.

Formel (4) siehe PDF.

Formel (5) siehe PDF.

Gilt für eine Umstiegsaktivität (i, j) E Aumstieg so sagen wir, dass Umstieg (i, j) gehalten wird. Fahrgäste können zwischen den entsprechenden Fahrzeugen umsteigen. Umstiege können aus zwei Gründen gehalten werden: Erstens, weil die Wartezeitregel (3) erfüllt ist (das heißt der ankommende Zug ist gar nicht, oder nicht zu sehr verspätet), oder zweitens, weil auch der abfahrende Zug verspätet ist. Im Falle findet die Abfahrt j statt, bevor Fahrgäste, die in i angekommen sind umsteigen konnten. Die Verbindung wird also nicht gehalten. Wir bezeichnen mit N( d) das Netzwerk N, aus dem alle nicht gehaltenen Umstiege entfernt wurden mit dem zugehörigen Dispositionsplan 1r( d) und den sich daraus ergebenden Kantenlängen.

Formel (6) siehe PDF.

Dieses Modell berücksichtigt noch keine Verspätungsfortpflanzung durch Konflikte in der Nutzung der Infrastruktur, etwa bei der Gleisbelegung im Bahnverkehr. Diese können leicht durch Einführung zusätzlicher Kanten im EAN modelliert werden, entlang derer sich Verspätungen dann ebenfalls fortpflanzen (siehe etwa (7]). Zur besseren Berechenbarkeit unserer Algorith­ men zur robusten Fahrplanauskunft betrachten wir hier aber nur das oben beschriebene ver­ einfachte Modell.

4 Kurze Einführung in die robuste Optimierung

In diesem Artikel werden Ansätze und Methoden beschrieben, um gezielt nach robusten Ver­ bindungen zu suchen. Die zu Grunde liegenden Konzepte stammen aus dem Gebiet der ro­ busten Optimierung [1], das sich in den letzten Jahren zu einem lebendigen Forschungsgebiet im Bereich der mathematischen Optimierung entwickelt hat.
Allgemein lassen sich Optimierungsprobleme (P) in der Form schreiben. Dabei beschreibt X die Menge aller möglichen Lösungen, in unserem Fall also die Menge aller Verbindungen für einen Fahrgast. Aus dieser Menge soll eine Lösung x ausgewählt werden, die eine Zielfunktion z, beispielsweise die Reisezeit, minimiert.

Formel siehe PDF.

Sowohl die Menge der zulässigen Lösungen X als auch die Zielfunktion z sind in manchen Anwendungen unsicher, das heißt sie hängen von Parametern s ab, die nicht im Voraus bekannt sind. In unserer Anwendung stellt s die Verspätungen dar. Diese beinflussen einerseits die Reisezeit auf einer Verbindung x, andererseits bestimmen sie aber auch, welche Verbindungen überhaupt zulässig sind, da durch Verspätungen Anschlüsse wegfallen und somit Verbindungen, die auf diesen Anschlüssen beruhen, wegfallen können. Diese Abhängigkeit eines Optimierungsproblems von einem sogenannten Szenario s lässt sich schreiben als

Formel siehe PDF.

Dabei wird (P(s)) als unsicheres Problem bezeichnet.
In der robusten Optimierung wird angenommen, dass zwar nicht das konkrete Szenario s, wohl aber die Menge U aller möglichen (oder: aller wahrscheinlichen) Szenarien bekannt ist. Die UnsicherheitsmengeU kann dabei explizit gegeben sein als Ue := { s1 , s2, ... , sn}, oder implizit charakterisiert sein, etwa: es gibt auf höchstens 15 Streckenabschnitten Quellverspätungen von bis zu 20% der Reisezeit, auf allen anderen Abschnitten beträgt die Quellverspätung höchstens 5%.
Die robuste Optimierung sucht nun nach einer Lösung x, die gleichzeitig für alle Optimierungsprobleme (P(s)) mit s EU gut ist. Um ,,gleichzeitig für alle guf' zu formalisieren, wurden Robustheitskonzepte entwickelt, die zu teilweise sehr unterschiedlichen Lösungen führen können. Welches Robustheitskonzept sinnvoll ist, ist abhängig von der jeweiligen Anwendung. Das erste und vielleicht älteste Robustheitskonzept ist die strenge Robustheit [3, 8]. Es wird eine Lösung gesucht, die unter jedem Szenario zulässig ist und unter den Lösungen, die das erfüllen, den kleinsten Zielfunktionswert im schlimmsten Fall hat:

Formel siehe PDF.

Weitere Robustheitskonzepte werden im weiteren Verlauf des Artikels vorgestellt werden.

5 Robuste Fahrplanauskunft

Ziel der robusten Fahrplanauskunft ist es, basierend auf dem ursprünglichen Fahrplan, einer Fahrgastanfrage (Startzeit, Startort und Zielort) und einer Unsicherheitsmenge möglicher Verspätungsszenarien U eine Verbindung vom Start- zum Zielort zu finden, die im Falle von Verpätungen aus U noch möglichst gut ist.

Was möglichst gut bedeutet, hängt wie oben erwähnt, vom gewählten Robustheitskonzept ab. Drei unterschiedliche Ansätze werden in den Abschnitten 5.1-5.3 beschrieben. Welche Routen als robust gegenüber Verspätungen bezeichnet werden, hängt aber auch wesentlich von der Wahl der Unsicherheitsmenge U ab, also der Menge der Verspätungen, die als möglich, oder wahrscheinlich, angesehen werden. Per se sind die gefundenen Verbindungen erst einmal nur robust gegenüber Verspätungen aus U (auch wenn man davon ausgehen kann, dass viele ähnlich geartete Verspätungsszenarien auch mit abgedeckt werden). Die Wahl der Unsicherheitsmenge U ist also ein wesentlicher Faktor für den Erfolg der robusten Fahrplanauskunft in der Praxis.

Wir gehen zunächst von Unsicherheitsmengen aus, die wie folgt definiert sind: jede kann bis zu einem (kleinen) Wert quellverspätet sein. Zusätzlich kann es K Aktivitäten mit größeren Quellverspätungen geben, für jede Aktivität ist dafür eine obere Schranke von festgelegt. Unsere Unsicherheitsmenge enthält immer auch das sogenannte nominale Szenario, in dem keine Verspätungen auftreten.

5.1 Streng robuste Fahrplanauskunft

Das Konzept der streng robusten Optimierung wurde bereits in Abschnitt 4 beschrieben als: Finde eine Lösung, die

1.    unter jedem Szenario zulässig ist und

2.    unter den Lösungen, die das erfüllen, den kleinsten Zielfunktionswert im schlimmsten Fall hat.

Übertragen auf die robuste Fahrplanauskunft bedeutet (1.): die Verbindung muss unter jedem möglichen Verspätungsszenario d E U noch befahrbar sein. Das heißt: jede Umstiegsaktivität auf dem entsprechenden Weg P im EAN muss unter jedem Verpätungsszenario d E U gehalten werden. Solche Umstiegsaktivitäten bezeichen wir im folgenden als robust, alle anderen als unsicher.

Um eine streng robuste Verbindung zu finden, müssen also zunächst alle streng robusten Umstiegsaktivitäten identifiziert werden. Unglücklicherweise ist es für die oben beschriebene Unsicherheitsmenge im Allgemeinen sehr schwer zu entscheiden, ob eine Umstiegsaktivität streng robust ist. In [6] haben wir bewiesen, dass dieses Problem NP-schwer ist. Im Folgenden soll eine anschauliche Begründung gegeben werden, warum es so schwer ist zu entscheiden, ob eine Umstiegsaktivität streng robust ist.

Wir betrachten die in Abbildung 2(a) dargestellte Situation. Zu sehen sind Abfahrts- und Ankunftsereignisse von drei Zügen, zwischen denen an einigen Bahnhöfen umgestiegen werden kann, was durch die gestrichelten Linien dargestellt ist. Der Sollfahrplan und die Mindestfahrzeiten sind der Einfachheit halber nicht angegeben, wohl aber die fahrplanmäßigen Pufferzeiten Pa auf jeder Aktivität a E Afahr U Awarte U Aumstieg, die sich als berechnen.

Formel siehe PDF.

Mit Hilfe dieser Pufferzeiten kann man die Rechenvorschrift zur Erstellung eines Dispositions­ fahrplans (4) äquivalent umschreiben zu einer Vorschrift, die die jeweilige Verspätung D;(d) in einem Knoten i angibt:

Formel siehe PDF.

An den Umstiegsaktivitäten sind die Wartezeiten angegeben, das heißt die Zeit, die der Zug in den umgestiegen wird über seine fahrplanmäßige Abfahrtszeit hinaus auf die verspätete Ankunft des ankommenden Zugs warten würde.

Weiterhin sind die maximalen Verspätungen auf den Aktivitäten angegeben. Ist nichts angegeben, beträgt die maximale Verspätung 0. In diesem Beispiel ist K = 4, das heißt es können vier große Verspätungen auftreten. Der Einfachheit halber ist ea = 0, es können also keine zusätzlichen kleinen Verspätungen auftreten.

Wir interessieren uns in diesem Beispiel für die fett markierte Umstiegsaktivität: Ist diese streng robust - oder gibt es ein Verspätungsszenario, in dem sie wegfällt?

In Abbildung 2(b) sehen wir, dass bei kleinen Verspätungen die Wartezeit auf der Umstiegsaktivität ausreicht, um den Anschluss zu halten. Weiterhin sehen wir in Abbildung 2(c), dass der Anschluss in diesem Beispiel auch gehalten wird, wenn die Verspätungen auf jeder Aktivität maximal sind. Das liegt daran, dass sich die Verspätungen auch auf den Zug, in den umgestiegen wird, übertragen. Die Umstiegsaktivität ist aber trotzdem nicht streng robust: Ein Verspätungsszenario, in dem der Anschluss nicht gehalten wird, ist in Abbildung 2(d) dargestellt.

Um herauszufinden, ob eine Umstiegsaktivität streng robust ist, müssen im schlimmsten Fall also tatsächlich alle möglichen Verspätungsszenarien getestet werden.
Für viele Umstiegsaktivitäten lässt sich über dynamische Programmierung allerdings in polynomieller Zeit entweder beweisen, dass sie streng robust sind oder ein Verspätungsszenario generieren, das dazu führt, dass sie nicht gehalten werden. Diese Methode ist in [6, 15] beschrieben.

Nun kann man sich entweder damit zufrieden geben, eine Untermenge .,4rob der streng robusten Umstiegsaktivitäten Arob gefunden zu haben, oder für die verbleibenden Anschlüsse aufwändigere Methoden, beispielsweise ganzzahlige Programmierung, heranziehen, um herauszufinden, ob sie streng robust sind.

Hat man die Menge der streng robusten Verbindungen Arob, oder eine Untermenge _,4rob bestimmt, ergibt sich (1.), also die Menge der Wege, die in jedem Szenario zulässig sind, einfach als die Menge aller Wege von Start- zum Zielknoten im EAN mit Kanten Arahr u Awarte u Arob u Astart U Aziel (bzw. Arahr U Awarte U .,4rob U Astart U As;.1), also nach Entfernung der nicht robusten Umstiegsaktivitäten.

Unter allen in jedem Szenario zulässigen Verbindungen lässt sich nun sehr leicht die bestimmen, die im nominalen Szenario, das heißt im Fall, dass es keine Verspätungen gibt, die kürzeste Reisezeit bietet. Diesen Fall haben wir in [6, 15] untersucht. Möchte man (wie in (2.)) tatsächlich die Verbindung mit der im schlimmsten Verspätungsfall kürzesten Reisezeit bestimmen, dann muss man für alle Ankünfte am Zielort noch die frühestmögliche Ankunftszeit bestimmen. Dazu kann binäre Suche mit dem oben erwähnten Algorithmus zur Erzeugung von Verspätungsszenarien kombiniert werden.

In beiden Fällen zeigt sich aber der große Nachteil des Konzepts der strengen Robustheit für die Fahrplanauskunft: es können nur Anschlüsse genutzt werden, für die die eingeplante Zeit so lang ist, dass sie alle vorausgehenden Verspätungen auffangen können.

Abb. 2: Beispiel für die Auswirkungen von Verspätungen auf den fett markierten Umstieg.

5.2 Leicht robuste Fahrplanauskunft

Streng robuste Verbindungen vermeiden unsichere Anschlüsse vollständig und führen dementsprechend in vielen Fällen zu inakzeptabel hohen geplanten Reisezeiten.
Hingegen ist die Idee der leichten Robustheit (light robustness) [5], die nominale Qualität der betrachteten Lösungen festzulegen und unter diesen nominal akzeptablen Lösungen eine “robusteste” Lösung zu wählen.

Auf die Fahrplanauskunft lässt sich dieses Konzept übertragen, indem nur Verbindungen betrachtet werden, deren nominale Reisezeit unter einem vorher festgelegten Maximalwert R liegt. Dieser kann im Fahrplanauskunftssystem definiert sein (beispielsweise als 120% der Min­ destreisezeit) oder vom Fahrgast festgelegt werden. Wählt man als Maß für die Robustheit einer Lösung die Anzahl der enthaltenen unsicheren Verbindungen, so lässt sich nun, basierend auf der in Abschnitt 5.1 beschriebenen Unterteilung der Verbindungen in  „robuste" und „unsichere" Verbindungen, eine leicht robuste Verbindung mit Hilfe eines Kürzeste-Wege-Algorithmus im EAN bestimmen. Ereignisse, die zeitlich zu weit von der geplanten Abfartszeit entfernt liegen, um eine Reisezeit von höchstens R zu ermöglichen, werden zuvor aus dem EAN gelöscht.

5.3 Reparierbar robuste Fahrplanauskuntt

5.3.1 Was ist reparierbar robuste Fahrplanauskuntt?

Anders als strenge und leichte Robustheit zielt reparierbare Robustheit (recoverable robustness) [16] nicht darauf ab, eine Lösung zu finden, die in jedem Szenario unverändert umsetz­ bar ist, sondern erlaubt es, die gefundene Lösung noch zu „reparieren", nachdem ein Szenario eingetreten ist. ,,Reparierbar" ist im Fall der Fahrplanauskunft so zu verstehen, dass falls ein Anschluss verpasst wird, eine alternative Verbindung vom aktuellen Standort des Fahrgasts unter Berücksichtigung aller Verspätungen (und ihrer Auswirkungen auf Anschlüsse etc) angegeben werden kann. Zur Bewertung einer solchen reparierbar robusten Verbindung können dann wieder einerseits die Reisezeit im nominalen Fall (ohne Verspätungen), als auch im schlimmstmöglichen Szenario (aus der Unsicherheitsmenge U) herangezogen werden.

5.3.2 Annahmen an die Information der Fahrgäste

Um eine algorithmische Suche nach einer solchen reparierbar robusten Verbindung durchzuführen, müssen neben den in Abschnitt 3 beschriebenen Annahmen zur Verspätungsausbreitung auch Annahmen über die dem Fahrgast verfügbare Information getroffen werden. Wir gehen im Folgenden vereinfachend davon aus, dass es für jedes Verspätungsszenario einen Aufdeckzeitpunkt gibt, an dem es vollständig enthüllt wird und dass dieser Zeitpunkt zeitlich vor dem Eintreten der ersten Verspätung liegt. Die Unsicherheitsmenge U besteht also aus Paaren von Verspätungsvektoren

Diese Annahme spiegelt natürlich nicht vollständig das Auftreten von Verspätungen im realen Betrieb wieder: Erstens nehmen wir an, dass alle (für die entsprechende Verbindung relevanten) Verspätungen schlagartig bekannt werden, während in Wirklichkeit Verspätungen unterschiedlicher Quelle erst nach und nach bekannt werden. Zweitens gehen wir davon aus, dass wir Ort, Zeitpunkt und Höhe der Verspätungen schon dann kennen, bevor sie tatsächlich im System beobachtet werden können. Sie bietet jedoch die Möglichkeit, Algorithmen zum Finden reparierbar robuster Verbindungen unter einfachen Bedingungen zu erproben. In Abschnitt 5.3.4 werden wir diskutieren, inwiefern diese Annahmen in Hinsicht auf tatsächliche Störungsszenarien verallgemeinert werden können.

5.3.3 Wie kann man reparierbar robuste Verbindungen berechnen?

In [14] haben wir einen ersten Ansatz vorgestellt, um eine reparierbar robuste Fahrplanauskunft zu geben. Wir gehen dabei bikriteriell vor, das heißt, es werden beide Zielfunktionen (nominale Reisezeit und Reisezeit im schlimmsten Fall) beachtet. Zunächst wird für jedes Szenario s die Menge von Aktivitäten. bestimmt, die zum Zeitpunkt stattfinden, d. h. Aus technischen Gründen fügen wir dieser Menge noch alle Zielaktivitäten hinzu und erhalten. Für jede Aktivität wird die Reisezeit einer Verbindung über (i, j) im nominalen Fall bestimmt. Diese ergibt sich als die Länge eines kürzesten Weges im von estart nach eziel, der (i, j) enthält. Falls es keinen solchen Weg gibt, setzen wir Lnom(i,j). Für jede andere Aktivität (i,j) können wir Lnom(i,j) auf O setzen.

Für jedes Szenario s und jede Aktivität wird weiterhin die minimale Reisezeit Ls(i,j) über (i,j) im Falle des Verspätungsszenarios s bestimmt. Diese ergibt sich als die Länge eines kürzesten Weges im Netzwerk von estart nach €ziel, der (i,j) enthält. Für jede  andere  Aktivität (i,j)  können  wir  wieder  L8 (i , j ): = 0 setzen. Wir setzen  Lwc(i,j): = max,w L.(i,j), das heißt, dass eine Aktivität, wenn sie in mehr als einer Menge enthalten ist, die (über alle Szenarien) längstmögliche Reisezeit zugewiesen bekommt.
Für jede Verbindung, repräsentiert durch einen Weg P im EAN N, ergibt sich dann die nominale Reisezeit als max(i,j)EP Lnom(i,j) und die längstmögliche Reisezeit als max(i,j)EP Lwc(i, j).

Setzt man für eine der beiden Zielfunktionen, beispielsweise für die nominale Reisezeit, eine Qualitätsschranke rwc fest, kann man alle Kanten mit Lnom(i,j) rnom aus dem Netzwerk löschen, da diese zu Wegen mit höherer nominaler Reisezeit gehören. Nun bestimmt man in dem verbleibenden Netzwerk einen Weg P, der max(i,j)EP Lwc(i,j) minimiert; das kann ganz analog zu einem Kürzeste-Wege-Verfahren gemacht werden. Jede dieser Lösungen ist Paretooptimal für das bikriterielle Problem, das heißt keine andere Verbindung ist bezüglich einer der Zielfunktionen echt besser und bezüglich der anderen genauso gut. Führt man dieses Verfahren für alle unterschiedlichen Reisezeiten Lnom(i,j) aus, so erhält man eine (bezüglich der Zielfunktionswerte) vollständige Auswahl an Pareto-Lösungen des bikriteriellen Problems. Hierbei lassen sich die Rollen der Zielfunktionen natürlich auch vertauschen.

5.3.4 Mögliche Erweiterungen der Annahmen

Die in diesem Artikel getroffenen Annahmen betreffen den Aufbau der Unsicherheitsmenge, die Verspätungsausbreitung und die Information der Fahrgäste. In diesem Abschnitt werden wir kurz diskutieren, welche dieser Annahmen essentiell für das in Abschnitt 5.3.3 beschriebene Verfahren zur Bestimmung reparierbar robuster Verbindungen sind, und welche verallgemeinert werden können.

Das in Abschnitt 5.3.3 beschriebene Verfahren berechnet zunächst für jedes Szenario einen Menge und für jede in dieser Menge enthaltenen Aktivität a ein Label L.(a). Für diesen Schritt ist es also wesentlich, eine endliche, nicht zu große Menge an Szenarien zu haben. In der Realität gibt es aber natürlich eine unendliche (oder zumindest sehr große) Menge an möglichen Szenarien. In unseren Experimenten in [14] haben wir uns bisher damit beholfen, zufällig eine Menge von Szenarien auszuwählen. Wünschenswert wäre es, die „wesentlichen" Szenarien zu bestimmen und im Rahmen des beschriebenen Verfahrens zu nutzen.

Modell und Algorithmus zur reparierbar robusten Fahrplanauskunft benötigen als Eingabe die Dispositionsfahrpläne für die betrachteten Verspätungsszenarien. Wie diese Dispositionsfahrpläne erstellt wurden, ist dabei irrelevant. Das Verfahren funktioniert also unabhängig von der Wahl des Verspätungsausbreitungsmodells und kann sogar ohne Ausbreitungsmodell auf Ba­ sis von beobachteten Verspätungen durchgeführt werden.

Das in [14) benutzte Modell zur Fahrgastinformation ist etwas allgemeiner als das hier beschriebene. Es wird gefordert, dass die Ereignisse durch einen Schnitt im EAN in Ereignisse ohne Verspätungsinformation und Ereignisse mit voller Verspätungsinformation geteilt werden. Der in Abschnitt 5.3.2 beschriebene Aufdeckzeitpunkt stellt einen Spezialfall davon dar: alle Ereignisse haben keine Verspätungsinformation, während in i mit vollständige Information besteht. Eine Verallgemeinerung des Verfahrens auf mehrere Aufdeckzeitpunkte pro Szenario, um das schrittweise Bekanntwerden von Verspätungen berücksichtigen zu können, wird momentan untersucht. Das hier vorgestellte Verfahren beruht allerdings wesentlich auf den Annahmen, dass die Höhe der Verspätung eines Ereignisses spätestens zur Zeitpunkt des Ereignisses bekannt wird und dass der Informationsstand in einem Ereignis unabhängig von der gewählten Verbindung vom Startort zum Ereignis ist.

6 Vergleich der Konzepte

In diesem Artikel haben wir drei Konzepte zur robusten Fahrplanauskunft vorgestellt. Das Konzept der strengen Robustheit führt zu Verbindungen, die unter allen Verspätungsszenarien (aus der vorher definierten Unsicherheitsmenge) wie geplant durchführbar sind. Im Gegensatz dazu können bei der Wahl einer leicht robusten oder einer reparierbar robusten Verbindung Anschlüsse wegfallen. Während die leicht robuste Optimierung darauf abzielt, eine Verbindung auszugeben, die möglichst wenige potenziell gefährdete Anschlüsse enthält, wählt reparierbar robuste Fahrplanauskunft Verbindungen, in denen der Wegfall eines Umstiegs sich leicht durch Wahl einer Alternatiwerbindung kompensieren lässt.

Die hohe „Sicherheit' einer streng robusten Verbindung geht leider einher mit einer sehr hohen nominalen Reisezeit, denn eine Ausfallsicherheit der Anschlüsse wird meist nur durch das Einplanen sehr langer Umstiegszeiten erreicht. In (6, 15) haben wir die Konzepte der strengen und der leichten Robustheit für unterschiedliche, auf dem Fahrplan der Deutschen Bahn von 2011 basierende Instanzen und unterschiedliche Unsicherheitsmengen uf, verglichen. Nehmen wir an, dass sich jede Fahr- und Warteaktivität um maximal e  = 10% der geplanen Zeitverspäten kann und K = 3 Aktivitäten sich bis zu A = 20 Minuten verspäten können, ergibt sich in der streng robusten Lösung ein durchschnittlicher Zuwachs in der nominalen Reisezeit von fast 50% gegenüber einer bezüglich der Reisezeit optimierten Route. In den in [6, 15] durchgeführten Experimenten zeigt sich aber auch deutlich, dass dieser Reisezeitzuwachs im hohen Maße abhängig vom geforderten Grad der Sicherheit ist. Sichert man sich beispielsweise nur gegen kleine Verspätungen ab (K = O) beträgt der durchschnittliche Zuwachs der nominalen Reisezeit nur noch etwa 15%. Je breiter man sich also gegen Verspätungen absichert, desto mehr Zuwachs in der nominalen Reisezeit muss man in Kauf nehmen. Diesen Effekt bezeichnen wir als Preis der Robustheit.

Leichte Robustheit erlaubt es dagegen, den akzeptablen Reisezeitzuwachs explizit festzulegen. Unter allen Verbindungen, deren Reisezeit unter einer vorher festgelegten Maximalreisezeit liegt, wird eine Verbindung gewählt, die möglichst wenig unsichere Anschlüsse enthält. Ist es möglich, das Ziel im vorgegebenen Zeitraum auf einer streng robusten Verbindung zu errei­ chen, so wird diese auch als leicht robuste Verbindung ausgegeben. In unseren Experimenten haben wir einen Reisezeitanstieg um 60 bzw. 120 Minuten erlaubt, was einem durchschnitt­ lichen Anstieg von etwa 15% (bzw. 30%) entsprach. Die unter Erlaubnis dieses Reisezeitzu­ wachses gefundenen Verbindungen waren um ein Vielfaches öfter streng robust als nominal optimale Verbindungen. Gleichzeitig stieg die minimale eingeplante Umstiegszeit, was ebenfalls als Indikator für eine höhere Ausfallsicherheit gewertet werden kann.

Während sich der Preis der Robustheit als trade-off zwischen nominaler Reisezeit und Robustheit im Falle der streng robusten Farplanauskunft nur indirekt über die Wahl der Unsicherheitsmenge steuern lässt, erlaubt es das Konzept der leichten Robustheit, die akzeptierte Reisezeit direkt festzulegen.

Beide Konzepte sichern sich gegen Verspätungen durch Vermeiden unsicherer Anschlüsse ab. Das kann zu Verbindungsauskünften führen, in denen einem Fahrgast aus Sicherheitsgründen schon jetzt geraten wird, nicht den regulären Anschlusszug zu nehmen, sondern eine Periode auf den nächsten Anschlusszug zu warten. Eine solche Lösung ist natürlich in der Praxis sinnlos: der Fahrgast sollte auf jeden Fall versuchen, den ersten Anschlusszug zu bekommen, nur falls er ihn verpasst, ist es sinnvoll mit einem späteren Anschlusszug zu fahren.

Das Konzept der reparierbaren Robustheit zieht Fahrgastreaktionen auf Verspätungen und kurzfristige Fahrplanänderungen bei der Bestimmung einer robusten Verbindung in Betracht. Eine reparierbar robuste Umsteigeaktivität kann viele unsichere Anschlüsse enthalten - sofern im Falle eines Wegfallens eines Anschlusses gute Alternatiwerbindungen vorhanden sind. Das oben beschriebene Problem der unnötig langen Umsteigeaktivitäten in der strengen und leichten Robustheit kann hier also nicht auftreten.

In einem in [14] durchgeführten Experiment wurden nominal optimale Verbindungen und reparierbar robuste Verbindungen unter der Annahme verglichen, dass Fahrgäste ihre Verbindungen beim Bekanntwerden von Verspätungen ändern können. Es ergab sich, dass die dort berechneten reparierbar robusten Verbindungen im Vergleich mit nominal optimalen Verbindungen bei einem Zuwachs der nominalen Reisezeit von nur 9 Minuten die Reisezeit im schlimmsten Fall um durchschnittlich 29 Minuten verbessern, die maximal erzielte Verbesserung lag sogar bei 220 Minuten. Im Vergleich mit streng robusten Lösungen ergab sich, dass schon die durchschnittliche Reisezeit auf einer streng robusten Verbindung im nominalen Fall nicht besser als die durchschnittliche Reisezeit auf einer reparierbar robusten Verbindung im schlimmsten Fall. Reparierbare Robustheit erweist sich also in dieser Hinsicht als deutlich überlegen.

Bei diesem Vergleich ist allerdings zu beachten, dass die niedrige Reisezeit der mit unserem Konzept berechneten reparierbar robusten Verbindungen daher rührt, dass Informationen über Verspätungen zum Verbindungs-Update genutzt werden können. Diese sind in der Praxis zumindest nicht in dem Umfang und zu so einem frühen Zeitpunkt verfügbar, wie in unserem in Abschnitt 5.3.2 beschriebenen Modell angenommen. Es bleibt also zu überprüfen, ob sich das Konzept der reparierbaren Robustheit auch für realitätsnähere Informationsmodelle als überlegen erweist. Es ist allerdings zu erwarten, dass das Einbeziehen von möglichen Verbindungs-Updates, wie es in der reparierbaren Robustheit möglich ist, unabhängig vom Informationsmodell von großem Wert ist.

Während sich streng und leicht robuste Wege sowohl für endliche Unsicherheitsmengen, als auch für Unsicherheitsmengen der Form wie oben beschrieben berechnen (oder zumindest approximieren) lassen, funktioniert der vorgestellte Algorithmus zunächst nur für endliche Szenarienmengen. Unendliche Szenarienmengen müssen bisher durch Samplen angenähert werden, über die Qualität dieser Annäherung ist bisher noch nichts bekannt.

Eine detaillierte Beschreibung der durchgeführten Experimente findet sich in [6, 14, 15].

7 Fazit

Robustheit ist ein wesentliches Gütekriterium bei der Beurteilung einer Verbindung und sollte deswegen in die Verbindungssuche einbezogen werden. Eine formale Definition des intuitiv leicht verständlichen Begriffs der „Robustheit'', der den Anforderungen der Verbindungssuche gerecht wird, ist dabei keinegswegs trivial. In dieser Arbeit haben wir die Konzepte ,,strenge Robustheit'', ,,leichte Robustheit" und ,,reparierbare Robustheit'' auf die Fahrplanauskunft übertragen. Das Konzept der strengen Robustheit führt zwar zu Lösungen, die auch im schlimmsten Fall noch befahrbar sind, produziert aber deswegen inakzeptabel lange Umstiegszeiten und erweist sich damit als zu unflexibel für eine realistische Verbindungssuche. Die leichte Robustheit erlaubt es, innerhalb der akzeptierten Reisezeitspanne nach der Verbindung zu suchen, die die wenigsten unsicheren Anschlüsse enthält und somit in gewissem Sinne „am robustesten" ist. Wie schnell ein Fahrgast sein Ziel durch Wechseln auf andere Verbindungen noch erreichen kann, falls einer der in einer Verbindung enthaltenen Anschlüsse wegfällt, wird aber erst in der reparierbaren Robustheit in die Verbindungssuche einbezogen.

Ein erstes, leicht anwendbares Konzept zur reparierbaren robusten Fahrplanung haben wir in diesem Artikel vorgestellt. Erste experimentelle Vergleiche, einerseits zu Reisezeitminimalen, andererseits zu streng robusten Verbindungen waren vielversprechend. Es bleibt aber noch viel Forschungspotential, sowohl in Bezug auf eine realitätsnähere Modellierung des schrittweisen Bekanntwerdens von Verspätungsszenarien und der Reaktionsmöglichkeiten der Fahrgäste, als auch bezüglich einer für die Anwendung im Rahmen eines Fahrplanauskunftssystems angemessenen Rechenkomplexität.

8 Literatur

8.1 Bücher

[1] A. Ben-Tal, L. EI Ghaoui, and A. Nemirovski. Robust Optimization. Princeton University Press, Princeton and Oxford, 2009.

[2] A. Schöbe!. Optimization in public transportation. Stop location, delay management and tariff planning from a customer-oriented point of view. Optimization and lts Applications. Springer, New York, 2006.

8.2 Zeitschrittenartikel

[3] A. Ben-Tal and A. Nemirovski. Robust convex optimization. Mathematics of Operations Research, 23(4):769-805, 1998.

[4] E.W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269-271, 1959.

[5] M. Fischetti and M. Monaci. Light robustness. In R. K. Ahuja, R.H. Möhring, and C.D. Zaroliagis, editors, Robust and online large-scale optimization, volume 5868 of LNCS, pages 61-84. Springer, Heidelberg, 2009.

[6] M. Goerigk, M. Schmidt, A. Schöbe!, M. Knoth, and M. Müller-Hannemann. The price of strict and light robustness in timetable information. Transportation Science,  2013. Vor der Druckveröffentlichung online erhältlich unter http://transci. j ournal.informs. org/content/early/2013/07/30/trsc.2013.0470.full.pdf+html.

[7] M. Schachtebeck and A. Schöbe. To wait or not to wait and who goes first? Delay management with priority decisions. Transportation Science, 44(3):307-321, 2010.

[8] A.L. Soyster. Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations Research, 21:1154-1157, 1973.

8.3 Beiträge aus Tagungsbänden

[9] H. Bast, E. Carlsson, A. Eigenwillig, R. Geisberger, C. Harrelson, V. Raychev, and F. Viger. Fast routing in very !arge public transportation networks using transfer patterns. In Proceedings of the 18th Annual European Symposium an Algorithms (ESA'10), volume 6346 of Lecture Notes in Computer Science, pages 29Q-301. Springer, 2010.

[10] D. Oelling, T. Pajor, and R.F. Werneck. Round-based public transit routing. In Proceedings of the 14th Meeting an Algorithm Engineering and Experiments (ALENEX'12), pages 130-140. SIAM, 2012.

[11] J. Dibbelt, T. Pajor, B. Strasser, and D. Wagner. lntriguingly simple and fast transit routing. In Proceedings of the 12th International Symposium an Experimental Atgorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science, pages 43-54. Springer, 2013.

[12] V. Disser, M. Müller-Hannemann, and M. Schnee. Multi-criteria shortest paths in timedependent train networks. In C.C. McGeoch, editor, Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08), volume 5038 of Lecture Notes in Computer Science, pages 347-361. Springer, June 2008.

[13] R. Geisberger. Contraction of timetable networks with realistic transfers. In P. Festa, editor, Proceedings of the 9th International Symposium on Experimental A/gorithms (SEA'10), volume 6049 of Lecture Notes in Computer Science, pages 71-82. Springer, May 2010.

[14] M. Goerigk, S. Heße, M. Müller-Hannemann, M. Schmidt, and A. Schöbet. Recoverable robust timetable information. In D. Frigioni and S. Stiller, editors, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS), volume 33 of OpenAccess Series in lnformatics (OAS/cs), pages 1-14. Schloss Dagstuhl­ Leibniz-Zentrum fuer Informatik, 2013.

[15] M. Goerigk, M. Knoth, M. Müller-Hannemann, M. Schmidt, and A. Schöbet. The price of robustness in timetable information. In A. Caprara and S. Kontogiannis, editors, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS), volume 20 of OpenAccess Series in lnformatics (OAS/cs), pages 76-87, Dag­ stuhl, Germany, 2011. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[16] C. Liebchen, M. Lübbecke, R. H. Möhring, and S. Stiller. The concept of recoverable robustness, linear programming recovery, and railway applications. In R. K. Ahuja, R.H. Möhring, and C.D. Zaroliagis, editors, Robust and online large-scale optimization, volume 5868 of Lecture Note on Computer Science, pages 1-27. Springer, 2009.

[17] M. Müller-Hannemann, F. Schulz, D. Wagner, and C. Zaroliagis. Timetable information: Models and algorithms. In Algorithmic Methods for Railway Optimization, volume 4359 of Lecture Notes in Computer Science, pages 67-90. Springer, 2007.

[18] M. Müller-Hannemann and M. Schnee. Finding all attractive train connections by multicriteria Pareto search. In F. Geraets, L Kroon, A. Schoebel, D. Wagner, and C. Zaroliagis, editors, Proceedings of the 4th Dagstuhl conterence on algorithmic approaches for trans­ portation modeling, optimization, and systems (ATMOS), volume 4359 of Lecture Notes in Computer Science, pages 246-263. Springer Verlag, 2007.

[19] M. Müller-Hannemann and M. Schnee. Eflicient timetable information in the presence of delays. In R. Ahuja, R.-H. Möhring, and C. Zaroliagis, editors, Robust and Online Large­Sca/e Optimization, volume 5868 of Lecture Notes in Computer Science, pages 249-272. Springer, 2009.

8.4 Schrittenreihen

[20] H. Bast, D. Oelling, A. V. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner, and R. F. Werneck. Route planning in transportation networks. Technical Report MSR­TR-2014-4, Microsoft Research, 2014.