Delay Management in Public Transportation: Capacities, Robustness, and Integration

Abstract

In dieser Arbeit beschäftigen wir uns hauptsächlich mit dem Anschlusssicherungsproblem mit Kapazitätsrestriktionen, einem wichtigen Aspekt im operativen Betrieb öffentlicher Verkehrsunternehmen. Im Gegensatz zum meist in der Literatur untersuchten Anschlusssicherungsproblem ohne Kapazitätsrestriktionen berücksichtigen wir dabei explizit die begrenzte Kapazität der Gleissysteme sowie die Sicherheitsabstände, die Züge, die die gleiche Infrastruktur nutzen, zueinander einhalten müssen.Wir stellen eine auf dem Konzept der Ereignis-Aktivitäts-Netzwerke basierende graphentheoretische Modellierung des Anschlusssicherungsproblems mit Kapazitätsrestriktionen vor, leiten daraus ein ganzzahliges lineares Programm (ILP) ab und beweisen wichtige Eigenschaften des Modells und des ILP. Diese Eigenschaften erlauben es uns unter anderem, bekannte Ergebnisse für das Anschlusssicherungsproblem ohne Kapazitätsrestriktionen auf das Problem mit Kapazitätsrestriktionen zu übertragen. Darüber hinaus nutzen wir diese Eigenschaften zur Herleitung von Reduktionsverfahren, die die Größe einer Probleminstanz deutlich reduzieren können. Um auch in der Lage zu sein, sehr große, in der Praxis auftretende Probleminstanzen in akzeptabler Zeit zu lösen, schlagen wir unterschiedliche heuristische Lösungsverfahren vor. Für diese Verfahren beweisen wir verschiedene Fehlerabschätzungen und vergleichen sie numerisch anhand eines praxisnahen Datensatzes. Weiterhin zeigen wir, wie Fahrzeugumläufe in das Anschlusssicherungsproblem integriert werden können, und übertragen Ergebnisse, die wir für das Anschlusssicherungsproblem mit Kapazitätsrestriktionen hergeleitet haben, auf dieses integrierte Problem. Wir zeigen, dass das integrierte Problem bereits in einfachen Spezialfällen NP-schwer ist, identifizieren einen in polynomieller Zeit lösbaren Spezialfall und stellen ein generisches Lösungsverfahren vor.Neben dem Anschlusssicherungsproblem betrachten wir in dieser Arbeit auch Robustheitsaspekte. Wir fassen Ergebnisse einer Fallstudie zur Erstellung robuster Fahrpläne zusammen, stellen das Konzept der "recoverable robustness" vor, erweitern es zum Konzept der "multi-stage recoverable robustness" und zeigen, wie beide Konzepte auf spezielle Fahrplangestaltungsprobleme angewendet werden können, um verspätungsresistente Fahrpläne zu berechnen. Zum Abschluss stellen wir eine modular erweiterbare Programmsammlung vor, mit der die Auswirkungen von Planungsschritten im öffentlichen Verkehr auf nachfolgende Planungsschritte und auf den operativen Betrieb untersucht werden können; Beispiele hierfür sind die Untersuchung der Robustheit eines Linien- oder eines Fahrplans unter Verspätungen.