Donà, C. (2017). Mixed integer programming to optimize Vienna’s Airport rolling processes [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2017.48580
E105 - Institut für Stochastik und Wirtschaftsmathematik
-
Date (published):
2017
-
Number of Pages:
60
-
Keywords:
Gemischt-ganzzahlige Programmierung; Optimierung; Flughafen Wien Schwechat; Rollprozess
de
Mixed Integer Programming; Optimization; Vienna International Airport; Rolling Process
en
Abstract:
Prozessplanungsprobleme haben in den letzten Jahren des vorigen Jahrhunderts einen grossen Bedeutungsgewinn als Anwendungsfeld der gemischt-ganzzahligen linearen Optimierung (MILP) erfahren, was dem Aufkommen effizienter L oesungsmethoden auch f uer mittlere und gr oessere Probleminstanzen geschuldet ist. In dieser Arbeit wird ein Modell formuliert, das folgerichtig aus dem Bereich des job scheduling kommt, um die Rollprozesse f uer landende und abfliegende Flugzeuge zu beschreiben. Der Anspruch dieser Thesis ist zweifacher Natur: Einerseits wird die Wahl des Modells zun aechst durch eine detaillierte Beschreibung der airside Operationen eines Flugzeugs im Flughafenbereich motiviert. Das Ziel der Optimierung ist jenes, die Gesamtrollzeit f uer einen gegebenen Flugplan zu minimieren, um die Effizienz dieser Operation zu steigern und damit die negativen oekonomischen wie oekologischen Auswirkungen eines zu lang laufenden Prozesses zu reduzieren. Das Modell wird mit Daten des Flughafens Wien-Schwechat (VIE) kalibriert, sodass eine Absch aetzung ueber die potentielle Verbesserung des Rollprozesses ebendort gegeben werden kann. Der zweite Schwerpunkt dieser Diplomarbeit liegt auf der Theorie der gemischtganzzahligen Optimierung. Dabei wird zun aechst dargelegt, wie Probleme ueber Polyedern formuliert werden k oennen und wie daraus verschiedene Arten von Relaxierungen und die m aechtige Methode der cutting planes als Versuche der Ann aeherung an eine ideale Formulierung verstanden werden k oennen. Die pr aesentierten Methoden m uenden schliesslich im Branch-and-Cut-Verfahren, welches das Beste der beiden Welten vereint, sodass der Abschluss des theoretischen Teils gleichzeitig eine Beschreibung eines der heute meist verwendeten L oesungsverfahren darstellt.
de
Process scheduling problems have become a considerable field of application for mixed integer linear programs (MILPs) with the raise of powerful methods to solve medium-large-scale models in a satisfying amount of time in the last decade of the previous century. In this work we propose a model that is inspired from the area of job scheduling to depict the rolling process for landing and departing aircrafts. Therefore, the claim of this thesis is twofold: On the one hand, it is aimed to motivate carefully the choice of the model by describing the airside operations of an aircraft in the airport perimeter. The objective of the optimization is to reduce the overall rolling time for a given flight schedule in order to improve efficiency and reduce the negative economic and environmental consequences of an unnecessarily extended process. The model is fitted with data from the Vienna International Airport (VIE) and does provide an estimate on the potential margin of improvement in the rolling process. On the other hand, the second focus of this thesis is on the theory of MILPs that lie in the class of NP-hard problems. It will be presented how problems can be formulated using polyhedra, motivating the introduction of different kinds of relaxations and the powerful cutting plane toolbox as attempts to approach the ideal formulation. The outlined methods culminate in the Branch-and-Cut algorithm combining the best of the two worlds, so that the conclusion of the theoretical part represents also a description of one of nowadays most used MILP solution procedures.
en
Additional information:
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers