THE OPERATIONAL AIRLINE CREW SCHEDULING PROBLEM

This paper describes the operational airline crew scheduling problem a nd represents a first published attempt to solve it. The problem consi sts of modifying, as necessary, personalized planned monthly assignmen ts of airline crew members during day-to-day operations. It requires c overing, 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 cl assical crew pairing problem and the problem of constructing personali zed monthly assignments must be treated simultaneously. An. optimizati on approach is proposed for the problem in which the flight schedule i s fixed and represents input data. The problem is mathematically formu lated as a Set Partitioning type problem, and a column generation meth od 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 t he best in the given situation.