Automatic optimization of subproblems in scheduling airline crews

Scheduling crews is critical to operating an airline. We developed a selection process for selecting subproblems that reduces the size of the problems solved and improves the quality of the solutions. By focusing on solving the weekly and fully dated crew-scheduling problems, we developed a natural methodology for solving subproblems that calculates all the possible connections of one day while fixing the connections of all the other days. Results with large fleets of many carriers show that this process produces superior solutions to the weekly and fully dated problems even if the daily solution of the crew-scheduling problem is not available. Improving the weekly and fully dated problems provides significant benefit and flexibility to the crew-scheduling process. Most important, our method allows for the continuous maintenance and support of the solution close to the actual day of operation. Traditionally, airlines have fully optimized the daily solution, while optimizing the weekly solution manually. The method is in use at Lufthansa, SAS, Alitalia, and KLM and is producing excellent results for the weekly and fully dated crew-scheduling problems.