Solving Airline Crew Scheduling Problems by Branch-and-Cut

TLDR

The crew scheduling problem has been studied for four decades, yet existing methods only approximate optimal solutions; today, personnel costs exceed $1.3 billion annually, so even modest savings are significant, and contractual labor constraints have not been explicitly modeled, preventing assessment of optimality gaps. This work introduces a branch‑and‑cut algorithm that provably solves large set‑partitioning problems in airline crew scheduling to optimality. The solver constructs cutting planes from the convex hull of feasible integer points and embeds them in a tree‑search framework that uses automatic reformulation, heuristics, and linear‑programming techniques to handle both pure set‑partitioning and set‑partitioning with side constraints. Experiments on 68 real‑world problems show the method yields lower‑cost schedules, and crews report higher satisfaction because they spend more duty time flying rather than waiting.

Abstract

The crew scheduling problem is one that has been studied almost continually for the past 40 years but all prior approaches have always approximated the problem of finding an optimal schedule for even the smallest of an airline's fleets. The problem is especially important today since costs for flying personnel of major U.S. carriers have grown and now often exceed $1.3 billion a year and are the second largest item (next to fuel cost) of the total operating cost of major U.S. carriers. Thus even small percentage savings amount to substantial dollar amounts. We present a branch-and-cut approach to solving to proven optimality large set partitioning problems arising within the airline industry. We first provide some background related to this important application and then describe the approach for solving representative problems in this problem class. The branch-and-cut solver generates cutting planes based on the underlying structure of the polytope defined by the convex hull of the feasible integer points and incorporates these cuts into a tree-search algorithm that uses automatic reformulation procedures, heuristics and linear programming technology to assist in the solution. Numerical experiments are reported for a sample of 68 large-scale real-world crew scheduling problems. These problems include both pure set partitioning problems and set partitioning problems with side constraints. These “base constraints” represent contractual labor requirements and have heretofore not been represented explicitly in the construction of crew schedules thus making it impossible to provide any measure of how far the obtained solution was from optimality. An interesting result of obtaining less costly schedules is that the crews themselves are happier with the schedules because they spend more of their duty time flying than waiting on the ground.