A column generation approach for large-scale aircrew rostering problems

This article describes a method for solving the crew rostering problem in a ir transportation. This problem consists of constructing personalized sched ules that assign pairings, days off, and other activities to airline crew m embers. A generalized set partitioning model and a method using column gene ration have been used. This method has been adapted in a number of ways to take advantage of the nature of the problem and to accelerate solution. Num erical tests on problems from Air France have demonstrated that this method is capable of solving very large scale problems with thousands of constrai nts and hundreds of subproblems. The tests have also shown that these adapt ations are capable of reducing solution time by a factor of about a thousan d. Finally, results from this method are compared with those obtained with the method currently used at Air France.