Optimizing flight crew schedules

Because of restrictive work rules and interacting cost components, building flight crew schedules is a complex process. However, operations research techniques have been successful in reducing crew costs. The optimization is modeled as a set-partitioning problem, where the rows represent flights to be covered and the columns represent candidate crew trips. The work rules dictate whether or not a particular crew trip is valid, while the major cost components affect its desirability. Solving many sets of small subproblems has been more successful than attempting to find a global solution to a single large problem because of combinatorial problems and non-integer solutions. At American Airlines, the savings of the integer linear programming (ILP) approach relative to the enumeration methods previously used is estimated at $18 million per year. Intuitive evidence suggests that a global optimum is being achieved for small fleets (200 flights per day or less), but that additional savings are possible in the larger fleets.