The operational airline crew scheduling problem

This paper describes the operational airline crew scheduling problem and represents a first published attempt to solve it. The problem consists of modifying, as necessary, personalized planned monthly assignments of airline crew members during day-to-day operations. It requires covering, at minimal cost, 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 for the problem in which the flight schedule is fixed and represents input data. 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, from the point of view of both solution times and achieved objectives, have been obtained on generated test problems. Because 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.