Optimierung

ZIB  →  Diskrete Methoden  →  Optimierung  →  Projekte  →  Verkehr und Logistik  →  Airline Crew Scheduling

Airline Crew Scheduling

Personalplanung im Luftverkehr

Im Planungsprozess einer Fluggesellschaft finden Techniken der diskreten Optimierung seit Jahrzehnten zahlreiche Anwendungen. Ein in der Beschreibung einfaches, in der Lösbarkeit jedoch sehr schwieriges und komplexes Problem von enormer ökonomischer Relevanz ist dabei die Personalplanung im Fachjargon auch Airline Crew Scheduling genannt. Die Aufgabe besteht darin, Pairings zu generieren, d.h. zulässige Abfolgen von Arbeitstätigkeiten der Besatzungsmitglieder, so daß alle geplanten Flüge der Fluggesellschaft genau von einer Crew abgedeckt werden und die Kosten des Gesamtplanes minimiert werden.

CS-Icon

Beschreibung

In diesem Projekt entwickeln wir auf Set-Covering/Partitioning-Modellen basierende Column-Generation-Optimierungsverfahren zur Pairing Optimierung. Kern des Verfahrens sind spezielle Lagrange-Pfadsuchtechniken mit denen auch große und komplexe Szenarien mit mehreren Tausend Flügen und Dutzenden von Base Constraints für einen festen Besatzungstyp gelöst werden können.

Langfristiges Ziel dieses Projektes ist es von der sequentiellen Planung der Besatzungsmitglieder , d.h. vereinfacht erst Kapitän, dann Copilot und zuletzt Kabine, hin zu einer alle Freiheitsgrade nutzenden integrierten Pairing Optimierung zu gelangen. Erster Schritte auf den Weg dahin ist die Untersuchung von sogenannten Anpassungsoptimierungen mit Hilfe von Base Constraints.

Die Integration unseres Verfahrens in das Planungssystem NetLine/Crew der Lufthansa Systems Berlin GmbH ist ein weiteres Projektziel.

NetLine/Crew SchedVis
Planungssystem NetLine/Crew Visualisierung des Planungsgraphen mit SchedVis

Die Visualisierung des Planungsgraphen wurde erzeugt mit SchedVis, einem Tool von Fabian Stoeffler basierend auf JavaView.

Kernpunkte

  • Konstruktionsregeln für Pairings
  • Entwicklung eines Spaltenerzeugungsverfahren
  • Lösen von realen Szenarien
  • Integrierte Planung von Flugzeugbesatzungen

Poster

  • Poster (05/2005) [ps.gz]

Publikationen

  • Klingenfuss, Verena. Umlaufplanung von Flugzeugen im Linienflugverkehr. Diplomarbeit, Technische Universität Berlin, 1994.
  • Ralf Borndörfer, Andreas Löbel, Uwe Strubbe, Manfred Völker. Zielorientierte Dienstplanoptimierung. In: Heureka '99: Optimierung in Verkehr und Transport, pp. 171–194, Köln, 1999. ZIB Report 98-41.
  • Müller, Ronald. Rotationsoptimierung mit Wartungsbedingungen im Luftverkehr. Diplomarbeit, Technische Universität Berlin, 2001.
  • Ralf Borndörfer, Marting Grötschel, Andreas Löbel. Duty Scheduling in Public Transit. In: MATHEMATICS –- Key Technology for the Future, Willi Jäger and Hans-Joachim Krebs (Eds.), pp. 653–674, Springer Verlag, Berlin, 2003. ZIB Report 01-02.
  • Ralf Borndörfer, Andreas Löbel, Steffen Weider. Integrierte Umlauf- und Dienstplanung im Öffentlichen Verkehr. In: Heureka '02: Optimierung in Verkehr und Transport, pp. 77–98, Köln, 2002. ZIB Report 02-10.
  • Schlechte, Thomas. Das Resource-Constraint-Shortest-Path-Problem und seine Anwendung in der ÖPNV-Dienstplanung. Diplomarbeit, Technische Universität Berlin, 2003.
  • Ralf Borndörfer, Andreas Löbel, Steffen Weider. A Bundle Method for Integrated Multi-Depot Vehicle and Crew Scheduling in Public Transit. Forschungsbericht 04–14, Zuse-Institut Berlin, 2004.
  • Ralf Borndörfer, Uwe Schelten, Thomas Schlechte, Steffen Weider. A Column Generation Approach to Airline Crew Scheduling. Forschungsbericht 05–37, Zuse-Institut Berlin, 2005. (to appear in the Conference Proceedings of SOR 2005).