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

Fachbereich Mathematik
Universität Kaiserslautern

Anschluß-Sicherung bei Verspätungen im OPNV

Diplomarbeit

eingereicht von

Susanne Scholl

Juni 2001

Inhaltsverzeichnis

Vorwort ... 4

1 Stand der Forschung ... 5
1.1 Fahrplangestaltung ... 5
1.1.1 Event- Activity-Netze ... 6
1.2 Verspätungen ... 11
1.3 Fazit ... 15

2 Modellierung ... 16
2.1 Voraussetzungen ... 16
2.2 Notationen ... 18
2.2.1 Der Graph ... 18
2.2.2 Daten ... 19
2.2.3 Herleitung der Zielfunktion ... 20
2.3 Das Anschlußsicherungsproblem (ASP) ... 23
2.3.1 Kubisches Modell ... 23
2.3.2 Quadratisches Modell ... 25
2.3.3 Lineares Modell ... 29
2.4 Analyse des Modells ... 31
2.5 Spezialfälle ... 32
2.5.1 n sich später nicht mehr kreuzende Fahrzeuge ... 33
2.5.2 Zubringer-Problem ... 33

3 Die Berechenbarkeit ... 34
3.1 Totale Unimodularität ... 34
3.2 Erkennen der Baumstruktur ... 35
3.2.1 Erkennen von Dikreisen [Mar59] ... 36
3.2.2 Erkennen von Kreisen in ungerichteten Graphen ... 40
3.2.3 Rechenaufwand [RCH72] ... 42

4 Lösungsverfahren für allgemeine Netze ... 43
4.1 Netzanalyse und Voraussetzungen ... 43
4.2 Allgemeine Netze ... 45
4.2.1 Vermeidung von "Pseudo-Kreisen" ... 45
4.2.2 Wege und Gewichte ... 46
4.3 Lösungsansätze für allgemeine Graphen ... 47
4.3.1 Lösungsansatz bei wenigen, kleinen Kreisen ... 48
4.3.2 Branch-and-Bound ... 53
4.3.3 Gewichte variieren ... 55
4.4 Exakte Formulierung für allgemeine Graphen ... 56
4.4.1 Herleitung ... 56
4.4.2 Das Modell ... 57
4.4.3 Interpretation ... 58

Zusammenfassung ... 59

A Implementierung ... 60
A.l asp-basic ... 61
A.2 asp-weights ... 67

Literaturverzeichnis ... 74

Vorwort
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.

[...]

Kapitel 1
Stand der Forschung
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 die 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 starre Linienführung und die dadurch resultierende Inflexibilität große Probleme mit sich.

- So befassen sich viele Arbeiten allein mit dem Problem der Fahrplangestaltung auf eingleisigen Strecken ([CH90], [XC94], [HKF96], [HK98], [BLNN98]) auf denen es leicht geschehen kann, daß ein langsamer Zug einen schnellen ausbremst und es so zu regelmäßigen Verspätungen kommt.

- Allein die Planung des Verkehrsflusses an einer einzigen Haltestelle nicht trivial. So zum Beispiel die richtige Ein- und Abfahrtsfolge in Bahnhöfen, um regelmäßige Verspätungen durch das Ausbremsen schneller Züge durch langsamere an den angrenzenden Strecken zu verhinden([Car94], [Kro97]), sowie die Minimierung der Wartezeit an einer Haltestelle. Dies wird mit Hilfe von Polyedern gelöst, die die gewünschte Taktzeit repräsentieren (ein Quadrat für einen 15-Minuten-Takt, eine Strecke für 30 Minuten und ein Dreieck für 20 Minuten...), die so auf Kreisen (die dann eine Stunde repräsentieren) plaziert werden, daß die Strecke zwischen ihren Ecken (also die Wartezeit) minimal wird ([SU89], [Wei83]).

- Das Schienennetz wird auch vom Güterverkehr genutzt, der schwer zu kalkulieren ist, da ein Güterzug je nach Fracht verschiedene Höchstgeschwindigkeiten erreichen kann und so ganze Streckenzüge blockieren kann. ([Cedg 11, [D J911)

Wie man sieht, entstehen die Hauptprobleme im Schienenverkehr durch unterschiedliche Geschwindigkeiten der Fahrzeuge und mangelnde Überholmöglichkeiten.

Dies ist im öffentlichen Personen-Nahverkehr (ÖPNV) nicht der Fall, da in der Stadt alle Verkehrsteilnehmer mit etwa der gleichen Geschwindigkeit fahren und sich ansonsten problemlos überholen können.

Deshalb kann man sich im ÖPNV dem durchaus nicht leicht zu lösenden Problem der Anschlußsicherung widmen.

1.1.1 Event-Activity-Netze
Nachfolgend wird das von K. Nachtigall ([Nac95], [Nac98], [NV96], [NV97], [Nac93]) entwickelte Verfahren näher erläutert, da es unter den vorhandenen Verfahren zur Fahrplangestaltung mit der geringsten Rechenzeit auskommt.

1. Der Verkehrsgraph:
Nachtigall verwendet ein Event-Activity-Netz (Ereignis-Aktivitäten-Netz).

[...]