Anschluß-Sicherung bei Verspätungen im öffentlichen Personennahverkehr

Inhaltsverzeichnis

1 Stand der Forschung

1.1 Fahrplangestaltung

1.1.1 Event-Activity-Netze

1.2 Verspätungen

1.3 Fazit

2 Modellierung

2.1 Voraussetzungen

2.2 Notationen

2.2.1 Der Graph

2.2.2 Daten

2.2.3 Herleitung der Zielfunktion

2.3 Das Anschlußsicherungsproblem (ASP)

2.3.1 Kubisches Modell

2.3.2 Quadratisches Modell

2.3.3 Lineares Modell

2.4 Analyse des Modells

2.5 Spezialfälle

2.5.1 n sich später nicht mehr kreuzende Fahrzeuge

2.5.2 Zubringer-Problem

3 Die Berechenbarkeit

3.1 Totale Unimodularität

3.2 Erkennen der Baumstruktur

3.2.1 Erkennen von Dikreisen [Mar59]

3.2.2 Erkennen von Kreisen in ungerichteten Graphen

3.2.3 Rechenaufwand [RCH72]

4 Lösungsverfahren für allgemeine Netze

4.1 Netzanalyse und Voraussetzungen

4.2 Allgemeine Netze

4.2.1 Vermeidung von “Pseudo-Kreisen”

4.2.2 Wege und Gewichte

4.3 Lösungsansätze für allgemeine Graphen

4.3.1 Lösungsansatz bei wenigen, kleinen Kreisen

4.3.2 Branch-and-Bound

4.3.3 Gewichte variieren

4.4 Exakte Formulierung für allgemeine Graphen

4.4.1 Herleitung

4.4.2 Das Modell

4.4.3 Interpretation

A Implementierung

A.1 asp_basic

A.2 asp_weights

Zielsetzung & Themen

Die Diplomarbeit hat zum Ziel, mathematische Modelle und effiziente Algorithmen zur Sicherung von Anschlüssen bei Verspätungen im öffentlichen Personennahverkehr (ÖPNV) zu entwickeln, um die Gesamtwartezeiten der Fahrgäste zu minimieren.

• Modellierung des Anschlußsicherungsproblems (ASP) als Optimierungsproblem
• Einsatz von Event-Activity-Netzen zur Abbildung der Verkehrsabläufe
• Entwicklung von Lösungsverfahren für kreisfreie und allgemeine Netze
• Implementierung in Software zur praktischen Anwendbarkeit und Validierung

Auszug aus dem Buch

Zusammenfassung der Kapitel

1 Stand der Forschung: Überblickskapitel über bestehende Methoden zur Fahrplangestaltung und Einordnung der Relevanz des Anschlußsicherungsproblems (ASP).

2 Modellierung: Mathematische Herleitung und Definition der Zielfunktion des ASP unter Verwendung von zeitexpandierten Graphen sowie Darstellung von kubischen, quadratischen und linearen Modellen.

3 Die Berechenbarkeit: Analyse der Komplexität und mathematischen Eigenschaften des Modells, insbesondere der totalen Unimodularität und Methoden zur Erkennung von Baumstrukturen.

4 Lösungsverfahren für allgemeine Netze: Vorstellung von heuristischen und exakten Lösungsansätzen für den allgemeinen Fall, inklusive Branch-and-Bound-Verfahren und Gewichtsanpassungen.

A Implementierung: Dokumentation der erstellten Computerprogramme und praktischen Umsetzung der Modelle in einer Softwareumgebung.

Schlüsselwörter

ÖPNV, Anschlußsicherung, Verspätungsmanagement, Fahrplangestaltung, Optimierung, Event-Activity-Netze, zeitexpandierter Graph, totale Unimodularität, lineare Programmierung, Gesamtwartezeit, Algorithmus, Branch-and-Bound, genetische Algorithmen, Verkehrssicherheit, Verkehrsplanung

Häufig gestellte Fragen

Worum geht es grundsätzlich in dieser Arbeit?

In der Arbeit geht es um die mathematische Modellierung und Lösung des Problems, Anschlüsse im öffentlichen Nahverkehr (ÖPNV) bei auftretenden Verspätungen so zu steuern, dass die gesamte Wartezeit der Fahrgäste minimiert wird.

Welches sind die zentralen Themenfelder?

Die zentralen Themen umfassen die mathematische Optimierung, Graphentheorie zur Abbildung von Verkehrsnetzen sowie Informatik zur algorithmischen Implementierung von Fahrplananpassungen.

Was ist das primäre Ziel der Arbeit?

Das primäre Ziel ist es, ein mathematisches Verfahren zu entwickeln, das in sehr kurzer Zeit (wenigen Minuten) entscheidet, ob ein Anschlussfahrzeug auf ein verspätetes Fahrzeug warten soll, um die Gesamteffizienz des Netzes zu maximieren.

Welche wissenschaftliche Methode wird verwendet?

Die Autorin nutzt Methoden der ganzzahligen Optimierung und der linearen Relaxation. Es werden Event-Activity-Netze erstellt und die mathematischen Modelle auf Eigenschaften wie die totale Unimodularität untersucht.

Was wird im Hauptteil behandelt?

Der Hauptteil erstreckt sich von der grundlegenden Modellbildung durch Graphen über die mathematische Formulierung (kubisch, quadratisch, linear) bis hin zu Lösungsverfahren wie Branch-and-Bound für allgemeinere, komplexere Netze.

Welche Schlüsselwörter charakterisieren die Arbeit?

Die Arbeit ist durch Begriffe wie ÖPNV, Anschlußsicherung, Verspätungsmanagement, mathematische Optimierung, zeitexpandierte Graphen und Gesamtwartezeit charakterisiert.

Warum lassen sich existierende Methoden für Zugverkehre nicht direkt auf den ÖPNV anwenden?

Existierende Methoden für den Zugverkehr sind oft NP-schwer und benötigen zu hohe Rechenzeiten. Zudem weist der ÖPNV andere Netzstrukturen und höhere Flexibilitätsanforderungen bei Verspätungen auf, weshalb ein neues, spezifischeres Modell nötig war.

Welche Rolle spielen "Pseudo-Kreise" bei der Modellierung?

Pseudo-Kreise entstehen durch parallele Linienführungen. Sie werden in der Arbeit durch spezifische Vereinfachungen umgangen, um die Modellierung und die Berechnung der optimalen Fahrplanreaktion zu erleichtern.

Wie wurde die Arbeit praktisch implementiert?

Es wurden Computerprogramme in C und C++ entwickelt, die als Eingabe die Netzstruktur und Verspätungsdaten nehmen und das Modell für einen Standard-Solver (Visual Xpress) aufbereiten.