Identifying dependencies among delays

Abstract

Die Behandlung von Störungen bei Vorliegen von Kapazitätsbeschränkungen im Anschlusssicherungsproblem (auf Englisch ``Delay Management Problem"") wurde theoretisch und numerisch untersucht. Es wurde eine neue Formulierung dieser Nebenbedingungen für das Makromodell des Problems entwickelt. Das Ziel war es, ein lineares ganzzahliges Makromodell des Bahnsystems zu konstruieren, das einen zulässigen Fahrplan findet, der robuster als die Lösung des Modells ohne Kapazitätsbeschränkungen ist, ohne dabei detaillierte Kenntnisse der Infrastruktur zu benutzen. Die Bestimmung der neuen Nebenbedingungen wurde in R implementiert und in der üblichen Weise validiert, insbesondere an den gemessenen Verspätungen der Deutsche Bahn. Die Verspätungsdaten wurden im Rahmen des DisKon Projekts (Disposition und Konfliktlösungsmanagement) der AG-Optimierung (Prof. Dr. A. Schöbel) zur Verfügung gestellt. Das Anschlusssicherungsproblem mit Kapazitätsbeschränkung wurde als gerichteter Graph (der als Event-Activity-Graph bezeichnet wird) modelliert. Es konnte die NP-Schwierigkeit des Problems bewiesen werden, selbst wenn alle warte/nicht-warte Entscheidungen bestimmt sind. Überdies wurden Vergleiche zwischen dieser Formulierung und denen von anderen Arbeitskreisen für ähnliche Problemstellungen durchgeführt, um Ähnlichkeiten, sowie Vor- und Nachteile zu analysieren. Die Verspätungsdateien wurden mit Hilfe einer stochastischen Analyse erforscht. Die gemessenen Ankunft- und Abfahrtsverspätungen der Züge wurden als Beobachtungen der entsprechenden Zufallsvariablen betrachtet, auf die verschiedene stochastische Verfahren (insbesondere drei graphische Modelle) angewendet wurden, um die Abhängigkeiten zwischen den Störungen zu bestimmen. Die drei Modelle wurden zum ersten Mal für Eisenbahnverspätungsanalyse eingesetzt: zwei von diesen (Full Conditional Independence Graph und Covariance Graph) sind klassische Modelle, während das dritte (das Tri-graph Verfahren) erst 2004 von Prof. Dr. Bühlmann (ETH Zürich) eingeführt wurde. Es hat in dieser Arbeit eine seiner ersten Anwendungen außer dem genetischen Gebiet. Die Ergebnisse der Methoden wurden verglichen. Die identifizierten Abhängigkeiten von dem Tri-graph Verfahren wurden als Zeitbeschränkungen zwischen den Variablen hinzugefügt und ersetzen damit die Kapazitätsbeschränkungen des Anschlusssicherungsproblems. Dazu wurden mehrere lineare Regressionen (mit verschiedene Steigungen) untersucht. Das Ziel bestand darin, die Approximationsfehlern zu minimieren. Dabei wurden die Verteilungsinformationen aus der statistischen Analyse zur approximativen Bestimmung der funktionalen Zusammenhänge genutzt. Zur Bestätigung der Ergebnisse wurde ein weiteres Experiment durchführt. Daten von simulierten Verspätungsszenarios wurden generiert und mit Hilfe des Tri-graph Verfahren analysiert. Die Ergebnisse wurden als Zeitnebenbedingungen in das entsprechende Makromodell geschrieben. Die Lösungen der Makromodelle (mit und ohne Kapazitätsbeschränkungen) wurden verglichen, um die Robustheit der Lösung zu testen.