Wer saß nicht schon einmal in einem verspäteten Bus und mußte dann rennen, nur um seinen Zug gerade noch wegfahren zu sehen? Wäre es nicht schön, wenn er warten würde? Diese Situation tritt täglich im öffentlichen Personennahverkehrs (ÖPNV) auf. Fahrgäste verpassen ihren Anschluß, es sei denn, das Anschluß-Fahrzeug wartet. Dann pflanzt sich die Verspätung jedoch auf das wartende Fahrzeug fort und an den folgenden Haltestellen kann der Anschluß möglicherweise nicht gehalten werden. Ziel der Arbeit ist es, ein Verfahren zu entwickeln, das entscheidet, ob ein Anschluß-Fahrzeug warten soll oder nicht, so daß die Gesamtwartezeit aller Fahrgäste minimal ist.
Kapitel 1 gibt einen allgemeinen Überblick über bereits bestehende Verfahren und stellt die wichtigsten Arbeiten vor. Kapitel 2 stellt ein neu entwickeltes Modell zum Anschlußsicherungsproblem (ASP) vor, das in kreisfreien Verkehrsgraphen eine exakte Lösung liefert. In Kapitel 3 wird bewiesen, daß die Koeffizientenmatrix des (ASP) total unimodular ist, die lineare Relaxation des Problems also eine ganzzahlige Lösung liefert. Ferner wird ein Verfahren zur Erkennung von Kreisen vorgestellt. Kapitel 4 stellt sowohl Lösungsansätze und Heuristiken zur Lösung des (ASP) in allgemeinen, nicht kreisfreien Netzen vor, als auch einen Algorithmus zur schnellen Erkennung von Kreisen, der Grundlage für alle Heuristiken ist und implemetiert wurde. Kapitel 5 faßt alle Ergebnisse noch einmal kurz zusammen und gibt einen Ausblick über noch offene Fragen.
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
1.1 Fahrplangestaltung
Die Reaktion auf unerwartet eintretende Verspätungen, sogenannte Quellverspätungen (source delays), entspricht der Erstellung eines neuen Fahrplans, der möglichst nahe am alten ist, die Quellverspätung jedoch mit einbezieht. Im Idealfall sollte die Berechnung möglichst wenig Zeit benötigen (wenigen Sekunden). Was liegt also näher, als ein bereits bestehendes Verfahren zur allgemeinen Fahrplangestaltung anzuwenden? Hierbei entstehen jedoch folgende Probleme:
In [Nac96] und [Nac97] wird gezeigt, daß das Problem, einen periodischen Taktfahrplan, wie er in jeder größeren Stadt bereits existiert, der fahrplanmäßige Gesamtwartezeit aller Fahrgäste zu minimieren versucht, zu erstellen, NP-schwer ist. Selbst die von Nachtigall verwendeten genetischen Algorithmen ([Nac95], [Nac98], [NV96], [NV97], [Nac93]) rechnen einige Minuten, andere sogar mehrere Stunden oder Tage. Bei reiner Fahrplangestaltung stellen diese langen Rechenzeiten kein Problem dar, da für die Erstellung eines neuen Fahrplans in der Regel genügend Zeit zur Verfügung steht, für das Anschlußsicherungsproblem sind sie jedoch inakzeptabel.
Fast alle Verfahren sind für den Zugverkehr entworfen worden. Einen allgemeinen Überblick über die Vielfalt der Fahrplangestaltung und Verkehrsplanung gibt J.-F. Cordeau in [Cor98]. Schienenverkehr bringt allein durch seine Linienführung und die dadurch resultierende Inflexibilität große Probleme mit sich.
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.
- Quote paper
- Susanne Scholl (Author), 2001, Anschluß-Sicherung bei Verspätungen im öffentlichen Personennahverkehr, Munich, GRIN Verlag, https://www.grin.com/document/38184
