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

Diploma Thesis , 2001 , 74 Pages , Grade: sehr gut

Mathematics - Applied Mathematics

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

• Vorwort
• 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 In 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
• 5 Zusammenfassung
• A Implementierung
• A.1 asp_basic.
• A.2 asp_weights
• Literaturverzeichnis

Zielsetzung und Themenschwerpunkte

Ziel dieser Diplomarbeit ist die Entwicklung eines Verfahrens, das entscheidet, ob ein Anschlußfahrzeug im öffentlichen Personennahverkehr (ÖPNV) bei Verspätungen warten soll oder nicht. Dabei soll die Gesamtwartezeit aller Fahrgäste minimiert werden.

• Modellierung des Anschlußsicherungsproblems (ASP) in kreisfreien Verkehrsgraphen
• Beweis der totalen Unimodularität der Koeffizientenmatrix des ASP
• Entwicklung von Lösungsansätzen und Heuristiken für allgemeine Netze (mit Kreisen)
• Implementierung und Evaluierung der Algorithmen
• Analyse der Ergebnisse und Ausblick auf zukünftige Forschungsfragen

Zusammenfassung der Kapitel

• Kapitel 1: Stand der Forschung - Dieses Kapitel gibt einen Überblick über bereits bestehende Verfahren zur Fahrplangestaltung und Verspätungsmanagement im ÖPNV. Es werden die wichtigsten Arbeiten vorgestellt, die sich mit dem Problem der Anschlußsicherung befassen.
• Kapitel 2: Modellierung - In diesem Kapitel wird ein neues Modell zum Anschlußsicherungsproblem (ASP) vorgestellt, das in kreisfreien Verkehrsgraphen eine exakte Lösung liefert. Es werden die notwendigen Voraussetzungen, Notationen und die Herleitung der Zielfunktion erläutert. Außerdem werden verschiedene Modellierungsansätze, darunter ein kubisches, ein quadratisches und ein lineares Modell, diskutiert.
• Kapitel 3: Die Berechenbarkeit - Dieses Kapitel befasst sich mit der Berechenbarkeit des ASP. Es wird bewiesen, dass die Koeffizientenmatrix des ASP total unimodular ist, was bedeutet, dass die lineare Relaxation des Problems eine ganzzahlige Lösung liefert. Außerdem wird ein Verfahren zur Erkennung von Kreisen in Verkehrsgraphen vorgestellt.
• Kapitel 4: Lösungsverfahren für allgemeine Netze - In diesem Kapitel werden Lösungsansätze und Heuristiken für das ASP in allgemeinen, nicht kreisfreien Netzen vorgestellt. Es werden verschiedene Ansätze, darunter Branch-and-Bound-Verfahren und die Variation von Gewichtungen, diskutiert. Außerdem wird ein Algorithmus zur schnellen Erkennung von Kreisen präsentiert, der für alle Heuristiken verwendet wird und implementiert wurde.

Schlüsselwörter

Die Arbeit befasst sich mit der Optimierung des öffentlichen Personennahverkehrs (ÖPNV) und der Lösung des Anschlußsicherungsproblems (ASP). Wichtige Schlüsselwörter sind Fahrplangestaltung, Verspätungen, Verkehrsgraphen, total unimodulare Matrizen, lineare Programmierung, Heuristiken, Branch-and-Bound-Verfahren, Kreise in Graphen, Algorithmen.

• College: University of Kaiserslautern
• Grade: sehr gut
• Author: Susanne Scholl (Author)
• Publication Year: 2001
• Pages: 74
• Catalog Number: V38184
• ISBN (eBook): 9783638373364
• Language: German
• Tags: Anschluß-Sicherung, Verspätungen, Personennahverkehr