This paper describes the operational airline crew scheduling problem and represents a first published attempt to solve it. This problem consists of modifying, as necessary, personalized planned monthly assignments of airline crew members during day-to-day operations. It requires the covering at minimal cost of all flight segments from a given time period with available crew while minimizing the disturbances of crew members. To generate modified pairings for selected crew members, both the classical crew pairing problem and the problem of constructing personalized monthly assignments must be treated simultaneously. An optimization approach is proposed. The problem is mathematically formulated as a Set Partitioning type problem and a column generation method embedded in a branch-and-bound search tree has been implemented to solve it. Good results, form the point of view of both solution times and achieved objectives, have been obtained on generated test problems. Since the solution time is reasonable, several different scenarios of the same problem may be solved. A final decision can then be made by considering all scenarios and choosing the one whose solution is the best in the given situation.
Paru en mars 1997 , 29 pages