Im Rahmen dieser Arbeit wurde die Optimierung in der Flugplanung untersucht. Es wurden effiziente Algorithmen zur Lösung der zugrunde liegenden Optimierungsprobleme entwickelt und die Leistungsfähigkeit der Verfahren untersucht. Die Ergebnisse der Arbeit kommen in Entscheidungsunterstützungssystemen zum Einsatz, verbessern die Qualität der berechneten Lösungen und leisten auf diese Weise einen Beitrag zur Kostensenkung bei Fluggesellschaften. Wir beschäftigen uns zunächst mit dem Problem des Netzwerkentwurfs. Die Aufgabe besteht darin, ein Flugnetzwerk so aufzubauen, dass die prognostizierte Nachfrage möglichst kostengünstig bedienen werden kann. Das zugrunde liegende lineare ganzzahlige Optimierungsproblem zeichnet sich durch seine hohe Komplexität aus. Zur Lösung dieses Problems entwickeln und implementieren wir den Relax-and-cut- Algorithmus, der auf der Lagrange-Relaxation basiert und zusätzliche gültige Ungleichungen (cuts) zur Steigerung der Effizienz berücksichtigt. Das entstandene Optimierungssystem beinhaltet sowohl exakte als auch heuristische Verfahren zur Lösung des Netzwerkentwurfproblems. Den zweiten Schwerpunkt dieser Arbeit bildet die Planungsaufgabe der Flottenzuweisung. Diesem Planungsschritt kommt eine zentrale Bedeutung innerhalb einer Fluggesellschaft zu, weil hier die wesentlichen Eigenschaften des Flugplans festgelegt werden und dadurch die Betriebskosten und die Erlöse definiert werden. Eine verbesserte Flottenzuweisung erhöht deutlich die Profitabilität eines Flugplans. Die Aufgaben der Marktmodellierung und des Revenue Managements sind stark mit der Flottenzuweisung verzahnt. Wir untersuchten die Abhängigkeiten zwischen diesen Planungsschritten und entwickelten drei Integrationsstrategien, die eine übergreifende Optimierung ermöglichen. Durch die Integration konnte die Qualität der Lösungen deutlich verbessert werden.
In this thesis we investigate the optimization process in the airline scheduling. We develop efficient algorithms for solving the underlying optimization problems and analyze the performance of the algorithms. The results of this work are in use in decision support systems, improve the quality of the solutions, and contribute in this way to cost reduction in airlines. In the first part of the thesis the network design problem is considered. The goal is to design an airline network in the way that the forecasted traffic demand is served as cost-efficient as possible. The underlying mixed-integer linear optimization problem has a very high complexity. To solve the problem we develop and implement the relax-and-cut algorithm. The algorithm is based on the Lagrangian relaxation and uses additional valid inequalities (cuts) for the network design problem to improve the efficiency. The developed optimization system contains several exact and heuristic methods for solving the network design problem. The second part of the thesis investigates the fleet assignment problem. Fleet assignment is one of the most important planning tasks in an airline. Main properties of the airline schedule are defined in this step and determine the operating costs and revenues for the schedule. Better solutions of the fleet assignment problem can improve the overall profitability of the schedule. The tasks of market modeling and revenue management are closely connected with the fleet assignemt problem. We consider the interdependencies between these planning tasks and develop three integration strategies. These strategies lead us to the integrated optimization of the tasks. As a result the quality of the solutions is improved significantly.
Optimierung in der Flugplanung: Netzwerkentwurf und Flottenzuweisung
HNI-Verlagsschriftenreihe, Universität Paderborn ; 173 ; 1-190
2006
190 Seiten, Bilder, Tabellen, Quellen
Hochschulschrift
Deutsch