Optimization

ZIB  →  Discrete Methods  →  Optimization  →  Projects  →  Traffic and Logistics  →  Airline Crew Scheduling

Airline Crew Scheduling

Airline Crew Scheduling

For decades techniques of the discrete optimization have found numerous applications in the planning process of an aviatian company. The personnel planning in the specialized jargon also called as airline crew scheduling is thereby a problem of enormous economic relevance, which is simple to describe, but complex and very difficult to solve. The task consists of generating pairings i.e. feasible successions of work activities of the crew members, such that all planned flights of the airline are covered by exactly one crew and the costs of the total plan are minimized.

CS-Icon

Description

In this project we develop a column generation algorithmn based on set covering/partitioning models for pairing optimization. Core of the approach are special Lagrange-path-search-techniques. With those we are able to solve large and complex scenarios with several thousand flights and dozens of base constraints for a fixed type of crew.

A long-term goal of this project is to get away from the sequential planning of the crew members, i.e. first captain, then copilot and at last cabine and to reach an integrated pairing optimization using all degrees of freedom. First steps on the way to this are the investigations of so-called adjustment optimizations by using base constraints.

The integration of our algorithmn into the planning system NetLine/Crew of Lufthansa Systems Berlin GmbH is a further aim of the project.

NetLine/Crew SchedVis
Planning system NetLine/Crew Visualization of the planning graph with SchedVis

Visualization of the planning graph was produced with SchedVis, a tool written by Fabian Stoeffler based on JavaView.

Key Issues

  • Rules of pairing-construction
  • Development of a column generation algorithmn
  • Solving of real world scenarios
  • Integrated planning of airline crews

Poster

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

Related Projects

Publications

  • Klingenfuss, Verena. Umlaufplanung von Flugzeugen im Linienflugverkehr. Master's Thesis, 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. Master's Thesis, Technische Universität Berlin, 2001.
  • 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.
  • 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.
  • Schlechte, Thomas. Das Resource-Constraint-Shortest-Path-Problem und seine Anwendung in der ÖPNV-Dienstplanung. Master's Thesis, 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. Technical Report 04–14, Zuse-Institut Berlin, 2004.
  • Ralf Borndörfer, Uwe Schelten, Thomas Schlechte, Steffen Weider. A Column Generation Approach to Airline Crew Scheduling. Technical Report 05–37, Zuse-Institut Berlin, 2005. (to appear in the Conference Proceedings of SOR 2005).