Deutsch

In dieser Arbeit behandeln wir die gleichzeitige Planung von Flugzeugrouten und Personal unter Berücksichtigung von Störungen. Beide Planungsschritte werden normalerweise mehrere Monate vor der eigentlichen Ausführung der Pläne durchgeführt. Verspätungen während der Ausführung der Pläne können aufgrund von Beschränkungen bei Wartungsintervalen und Arbeitszeiten die Pläne ungültig werden lassen. In solchen Fällen können die Pläne oftmals nur unter Einsatz zusätzlicher Ressourcen und weiteren Verspätungen durchgeführt werden. Beide Planungsprobleme sind eng miteinander verzahnt, da aus Effizienzgründen die Besatzungen häufig die Flugzeuge wechseln, solche Wechsel von Flugzeugen aber auch zu zusätzlichen Verspätungen führen können. Wir präsentieren ein integriertes stochastisches Modell für die Erstellung von Flugzeugrouten und Plänen für die Besatzung mit dem Ziel sowohl die geplanten Kosten zu minimieren als auch die Pünktlichkeit zu maximieren. Wir lösen das integrierte Modell heuristisch, indem wir die beiden Probleme für Flugzeugrouten und Besatzungen in einem iterativen Vorgehen jeweils einzeln lösen. Wir entwickeln ein Branch-and-Price-and-Cut Verfahren für die stochastischen Planungsprobleme für Flugzeugrouten und Personaleinsatz. Die Generierung von Spalten ist als ein ressourcenbeschränktes Kürzestewege-Problem abgebildet. Der Algorithmus zur Generierung von Spalten basiert auf dynamischer Programmierung mit neuen heuristischen Elementen, die entscheidend für die gute Laufzeit der Methode sind. Mit diesem Verfahren können wir das stochastische Planungsproblem mit mehr als 250 Flügen in weniger als 4 Stunden lösen. Die wichtigste Eigenschaft des entwickelten stochastischen Modells ist, dass die Verspätungsszenarien nur bei der Generierung von Spalten berücksichtigt werden müssen. Die zusätzlichen Restriktionen können einfach in die bestehende Modellirung eingebetet und mit den vorhandenen Methoden berücksichtigt werden. Wir präsentieren ein Simulationsmodell und ein Vorgehen zum Vergleich verschiedener Ansätze für robuste Planung. Mit diesem Vorgehen vergleichen wir die Ergebnisse des stochastischen Modells mit einem deterministischen Ansatz ohne Verspätungsszenarien. Beim deterministischen Ansatz werden Wechsel von Flugzeugen durch Personal bestraft, wenn nicht ausreichend Puffer während dieser Wechsel existiert. Das deterministische Modell kann in deutlich kürzerer Zeit gelöst werden, da keine Verspätungsszenarien berücksichtigt werden. Durch Simulation der erstellten Pläne können wir die Pünktlichkeit und den Grad der Verletzung von Arbeitszeitregelungen bestimmen und mit den bei der Planung vorhergesagten Werten vergleichen. Das stochastische Modell hat sowohl eine hohe Vorhersagekraft der Pünktlichkeit als auch ein sehr gutes Verhältnis zwischen Kosten und Verbesserung der Robustheit. Die deterministischen Modelle können ähnliche Ergebnisse erreichen, müssen dafür aber aufwändig kalibriert werden. Zusätzlich stellen wir ein Verfahren zur Reparatur von gestörten Plänen vor. Dieses Verfahren integriert die Anpassung der Pläne mit gezielten Verspätungen von Flügen zur Auflösung von Konflikten. Die Probleme zur Reparatur von Flugzeugrouten und Einsatzplänen der Besatzungen werden dabei durch ein iteratives Vorgehen, das auf den entwickelten Optimierungskomponenten basiert, heuristisch gelöst. Die Lösungszeit kann dabei im Vergleich zu exakten Verfahren drastisch reduziert werden.