The encyclopedia · Engineering & Operations · Operational decision · 1988–1993
United Airlines uses a generator+optimizer loop to schedule crews, saving $16M a year.
United Airlines built a crew-scheduling system that generates candidate pairings then picks the cheapest set covering every flight, saving $16 million a year.
United Airlines
the move
United Airlines must schedule crews for up to 1,700 flights a day, and the schedule changes frequently, so the old approach was slow and costly.
The obvious approach is to solve the whole scheduling problem at once, but that is intractable at this size. United split it into two cooperating pieces.
A generator builds candidate crew pairings, and an optimizer solves an elastic embedded set-partitioning integer program to pick the cheapest set that covers every segment exactly once. When a feasible set is found, the system cycles between generator and optimizer to improve it.
The result let United respond quickly to schedule changes and cut crew scheduling costs by $16 million annually.
why it works
- Separating generation from optimisation makes the intractable problem tractable
- Elastic set partitioning handles the 'cover every flight once' rule cleanly
- Cycling between generator and optimizer improves the solution repeatedly
- Fast response to schedule changes is itself worth money in aviation
what transfers
For huge integer programs, alternate between generating good candidate solutions and optimising over them instead of trying to solve the whole problem in one pass.
what came after
The system was designed to handle both medium and very large problems, was adopted for United's daily scheduling, and cut crew scheduling costs by $16 million a year. It became a landmark paper in airline crew optimization (Management Science, 1993).
references
spotted an error? The archive wants to know.