Groupe d’études et de recherche en analyse des décisions


The Operational Flight and Multi-Crew Scheduling Problem


This paper introduces a new kind of operational crew scheduling problem which consists in simultaneously modifying, as necessary, the existing flight departure times and planned individual work days (duties) for the set of crew members, while respecting predefined aircraft itineraries. It requires the covering of all flights from a day of operation while minimizing changes in both the flight schedule and the next-day planned duties for the considered crew members. Each flight must be covered by a crew of a fixed size. The maximum allowed duration of a personalized duty, which differs from one crew member to another, must be respected. Fixed aircraft itineraries are respected by imposing a set of flight precedence constraints, introduced for the first time by Stojkovic and Soumis (2000). In addition, a new type of same flight departure time constraints is introduced. They ensure that a flight which must appear in several personalized duties (the number of personalized duties is equal to the number of crew members required to cover this flight) will have the same departure time in each of these duties. The problem is mathematically formulated as an integer nonlinear multi-commodity network flow model with time windows and supplementary constraints. The optimal solution approach is based on Dantzig-Wolfe decomposition/column generation embedded into a branch-and-bound scheme. The resulting computational times on commercial-size problems are very good. Our new simultaneous approach produces solutions whose quality is far better than that of the traditional sequential approach where the flight schedule has been changed first and then input as a fixed data to the crew scheduling problem.

, 26 pages

Ce cahier a été révisé en novembre 2001