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.
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.
The 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.
 |  |
| 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 (05/2005) [ps.gz]
