http://join2-wiki.gsi.de/foswiki/pub/Main/Artwork/join2_logo100x88.png

Qualität von Heuristiken in der Disposition des Eisenbahnbetriebs = Quality of heuristics in train dispatching

Weymann, Frédéric Herbert Georges

2011

Verantwortlichkeitsangabevorgelegt von Frédéric Herbert Georges Weymann

ImpressumAachen : Publikationsserver der RWTH Aachen University 2011

Umfang221 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2011

Genehmigende Fakultät
Fak03

Hauptberichter/Gutachter
Wendler, Ekkehard (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2011-03-11

Online
URN: urn:nbn:de:hbz:82-opus-36020
URL: https://publications.rwth-aachen.de/record/64151/files/3602.pdf

Einrichtungen

1. Lehrstuhl für Schienenbahnwesen und Verkehrswirtschaft und Verkehrswissenschaftliches Institut (313110)

Inhaltliche Beschreibung (Schlagwörter)
Schienenverkehr (Genormte SW) ; Optimierung (Genormte SW) ; Disposition (Genormte SW) ; Heuristik (Genormte SW) ; Ingenieurwissenschaften (frei) ; rail traffic (frei) ; optimization (frei) ; dispatching (frei) ; heuristic (frei)

Thematische Einordnung (Klassifikation)
DDC: 620

Kurzfassung
Der reibungslose Auflauf des Bahnbetriebs ist ein entscheidender Faktor für den Erfolg des Systems Bahn. Als offenes System ist die Bahn allerdings sehr empfindlich gegenüber externen Störungen, welche zu unvermeidbaren Verspätungen bei den Zugfahrten führen. Umso wichtiger ist eine schnelle Reaktion durch eine vorausschauende und weiträumige Disposition, welche soweit wie möglich verhindert, dass verspätete Zugfahrten andere Fahrten behindern und dadurch Folgeverspätungen hervorrufen. Um den Disponenten bei seiner Arbeit zu unterstützen, wurden in den letzten Jahren zahlreiche rechnergestützte Verfahren zur Lösung von Belegungskonflikten entwickelt, allerdings nur oberflächlich evaluiert. Ein großes Problem bei der Bewertung der Verfahren ist das Fehlen eines Goldstandards, welcher für eine gegebene Betriebssituation eine optimale Lösung vorgibt. Ohne diesen Standard kann nur gezeigt werden, dass ein Verfahren akzeptable und plausible Ergebnisse liefert, es kann aber nicht abgeschätzt werden, wie viel Potential tatsächlich ausgenutzt wird. Im Rahmen dieser Arbeit wird daher ein optimales Lösungsverfahren entwickelt, welches den Ansatz der gemischt-ganzzahlig linearen Programmierung (MIP) verfolgt und auf einer weichenscharfer Darstellung der Infrastruktur, einer detaillierten Berechnung von Beschleunigungs- und Bremsvorgängen und einer Abbildung des Sicherungssystems mit Hilfe der Sperrzeitentheorie aufsetzt. Nach einer Optimierung des Laufzeitverhaltens ist es dem MIP-Löser Gurobi auf einem modernen Rechnersystem trotz der detaillierten Modellierung möglich, innerhalb kurzer Zeit – für die meisten Situationen nur wenige Minuten – eine optimale Dispositionsentscheidung zu ermitteln. Im Rahmen dieser Arbeit wird somit gezeigt, dass die Rechnerhardware und die MIP-Software inzwischen einen Stand erreicht haben, welcher eine realitätsnahe Optimierung der Bahndisposition erlaubt. Mit Hilfe des optimalen Lösungsverfahrens wird anschließend die Güte verschiedener heuristischen Dispositionsverfahren bestimmt. Dabei wird besonderer Wert auf eine möglichst breite Streuung bei den eingesetzten Datenmodellen und Lösungsansätzen gelegt. Um die Stärken und Schwächen der verschiedenen Verfahren genauer analysieren zu können, kommen beim Vergleich sechs Dispositionsbereiche mit unterschiedlichen Eigenschaften sowie verschiedene Arten von Störungssituationen zum Einsatz. Die verschiedenen Dispositionsverfahren werden nicht nur hinsichtlich der Güte der gefundenen Lösungen verglichen, vielmehr wird auch die benötigte Laufzeit auf Echtzeittauglichkeit untersucht. Kurze Laufzeiten sind notwendig, da eine signifikante Reduktion von Folgeverspätungen nur erreicht werden kann, wenn der Dispositionsvorgang mit ausreichendem Abstand zum Konfliktbeginn abgeschlossen ist. Aus den Ergebnissen werden zuletzt Empfehlungen abgeleitet, welche Heuristiken aus Gründen der Lösungsgüte und der Rechenzeit für den Einsatz in bestimmten Situationen empfehlenswert sind.

A smooth operation is a crucial factor for the success of the railway system. However, the railway is an open system and therefore very sensitive towards external disturbances which unavoidably lead to delays. Consequently, it is very important that a dispatcher is able to prevent late train from impeding other rides which would cause even more delays. To assist the dispatchers with their work, numerous computational methods for solving allocation conflicts have been developed in recent years. However, the methods were only evaluated superficially so far. A major problem in the evaluation is the lack of a gold standard which specifies an optimal solution for a given situation. Without this optimal solution one can only show that a method computes acceptable and plausible results, but it cannot be estimated how much potential is actually being utilized. In this thesis, an optimal solution method is developed using the approach of the mixed-integer linear programming (MIP). The method is based on a very detailed model of the railway infrastructure and of the train movements. Resource allocation is modelled by using the blocking time theory. After an optimization of the runtime behaviour, the MIP-solver Gurobi is able to determine an optimum scheduling decision within short time. For most situations, the computation only takes a few minutes. This thesis therefore shows that the computer hardware and the MIP solvers have reached a level which allows a realistic optimization of train dispatching. Using the optimal scheduling method, the quality of various heuristic scheduling methods is determined. Special emphasis is placed on analyzing a wide array of different models and approaches. In order to analyze the strengths and weaknesses of the various methods more accurately, six dispatching regions with different properties and different types of fault situations are considered. The various scheduling methods are compared with respect to the quality of the found solutions and their real-time capability. Short runtimes are necessary because a significant reduction of delays can only be achieved if the computation is complete long before the allocation conflict begins. The results are finally used to draw conclusions which heuristic is recommendable in which situation.

Fulltext:
PDF

Dokumenttyp
Dissertation / PhD Thesis

Format
online, print

Sprache
German

Interne Identnummern
RWTH-CONV-125495
Datensatz-ID: 64151

Beteiligte Länder
Germany