Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-4185
Main Title: Robust tail assignment
Translated Title: Robuste Flugzeugumlauf-Planung
Author(s): Dovica, Ivan
Referee(s): Borndörfer, Ralf
Grötschel, Martin
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Der erste Teil dieser Arbeit behandelt das allgemeine stochastische "Kürzeste- Wege-Problem". Gesucht ist der kürzeste Weg in einem Graphen, in dem die Bogenlängen ungewiss und als kontinuierliche Zufallsvariablen definiert sind. Dieses Problem steht im Zentrum verschiedener Anwendungen, vor allem in der robusten Verkehrsplanung, bei der die jeweiligen Wege den Flugzeug-, Zug- oder Busumläufen oder den Dienstplänen der Mitarbeiter entsprechen. Wir schlagen eine neue Lösungsmethode vor, die auf der Diskretisierung von kontinuierlichen Zufallsvariablen basiert. Die Methode ist anwendbar auf jede Klasse von kontinuierlichen Zufallsvariablen. Wir liefern Abschätzungen für den Approximationsfehler der diskretisierten Weglängen im Vergleich mit den kontinuierlichen Weglängen. Des Weiteren präsentieren wir theoretische Ergebnisse zum asymptotischen Laufzeitverhalten der Methode. Im zweiten Abschnitt wenden wir diese Methode für ein reales Praxisproblem im Flugverkehr an: auf das sogenannte "Tail-Assignment-Problem". Das Ziel des "Tail-Assignment-Problems" ist es, die Flugzeugumläufe, d.h. die Routen, bestehend aus Flugsegmenten, für eine Menge von individuellen Flugzeugen so zu erzeugen, dass eine Menge von gegebenen Flügen unter Berücksichtigung der Betriebsbedingungen von jedem einzelnen Flugzeug und unter Beachtung der kurz- bis langfristigen individuellen Wartungserfordernisse überdeckt werden. Wir stellen eine stochastische Formulierung dieses Problems vor und zeigen, wie unsere Methode dieses Problem innerhalb eines Spaltenerzeugungs-Frameworks effizient löst. Wir zeigen den Vorteil unseres stochastischen Ansatzes gegenüber dem KPI-Ansatz durch den Vergleich der Propagation der Verspätungen. Es zeigt sich, dass unser Ansatz zu weniger Betriebskosten ohne Erhöhung der Berechnungskomplexität führt. Eine Kernidee unserer Vorgehensweise zur Lösung des Problems der Robusten Optimierung ist das Anpassen des zugrundeliegenden stochastischen Modells auf komplexe Problemstellungen aus der Realität. Wir schlagen ein Modell von Verspätungspropagation vor, das realistisch und gleichzeitig einfach anwendbar, und deswegen ideal für Vorhersagen einsetzbar ist. Wir bewerten unsere Ergebnisse durch umfassende Simulationen. Wir zeigen eine erhebliche Verringerung von Ankunftsverspätungen und damit auch von Kosten für den Durchschnittsfall sowie für eine Vielzahl der Szenarien. Wir evaluieren diese Verbesserung in anderen realistischen Benchmarks durch Simulation unter Einbeziehung von Gegenmaßnahmen (Rettungsmaßnahmen) und in Szenarien, basierend auf historischen Verspätungsdaten anstelle des stochastischen Modells.
The first part of this thesis is devoted to the general problem of stochastic shortest path problem. It is about searching for the shortest path in a graph in which arc lengths are uncertain and specified by continuous random variables. This problem is at the core of various applications, especially in robust transportation planning where paths correspond to aircraft, train, or bus rotations, crew duties or rosters, etc. We propose a novel solution method based on a discretisation of random variables which is applicable to any class of continuous random variables. We also give bounds on the approximation error of the discretised path lengths compared to the continuous path lengths. In addition, we provide theoretical results for the computational complexity of this method. In the second part we apply this method to a real world airline transportation problem: the so-called tail assignment problem. The goal of the tail assignment problem is to construct aircraft rotations, routes consisting of flight segments, for a set of individual aircraft in order to cover a set of flight segments (legs) while considering operational constraints of each individual aircraft as well as short- to long-term individual maintenance requirements. We state a stochastic programming formulation of this problem and we show how to solve it efficiently by using our method within a column generation framework. We show the gain of our stochastic approach in comparison to standard KPI in terms of less propagated delay and thus less operational costs without growth of computational complexity. A key point of our complex approach to robust optimisation problem is the fit of the underlying stochastic model with reality. We propose a delay propagation model that is realistic, not overfitted, and can therefore be used for forecasting purposes. We benchmark our results using extensive simulation. We show a significant decrease of arrival delays and thus monetary savings on average as well as in the majority of our disruption scenarios. We confirm these benefits in even more life-like benchmarks as simulation where recovery actions are taken and in scenarios which use historical delays directly instead of the stochastic model.
URI: urn:nbn:de:kobv:83-opus4-56640
http://depositonce.tu-berlin.de/handle/11303/4482
http://dx.doi.org/10.14279/depositonce-4185
Exam Date: 28-Jul-2014
Issue Date: 2-Oct-2014
Date Available: 2-Oct-2014
DDC Class: 510 Mathematik
Subject(s): Flugzeug-Umlaufplanung
Spaltenerzeugung
Verspätungspropagation
Column generation
Delay propagation
Stochastic shortest path problem
Tail assignment
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
dovica_ivan.pdf2.75 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.