Improving profitability through schedule optimization

Southwest Airlines

5%

Reduction in Crew Duties by Produced Flight Schedules

Overview

The most profitable airline schedules adapt to passenger demand as it varies month to month. Southwest Airlines, the largest airline in the United States in terms of domestic passengers boarded, operates more than 4,000 flights each day, using over 700 aircraft to serve about 100 destinations in 11 countries. We partnered with Southwest Airlines to develop SkyMAX – a new-generation flight schedule optimization system that builds better flight schedules from scratch to improve annual network profitability.
Transmaldavian-case-study

Business Problem

Network planners at Southwest update flight schedules several times per year to match seat capacity with passenger demand. These schedules specify what markets (origin-destination pairs) to fly, flight frequency for each market, when to fly and fleet types for each flight leg. It’s a daunting optimization problem to generate schedules for thousands of flights, while taking into account both profitability and operational constraints, with an almost infinite number of possible solutions. Southwest wanted to solve this problem by using the latest technology to build new flight schedules from scratch, but it was unable to find a suitable commercial software solution. After Southwest engaged in an international search to find the right company to solve this problem, it selected Optym as its partner.

Our Approach

We developed proprietary algorithms by combining in novel ways several operations research techniques, such as mixed integer programming, heuristics, very large-scale neighborhood search and parallel computing, and we demonstrated that clean-sheet flight scheduling was mathematically possible. We then modified our algorithms to enable incremental optimization of existing flight schedules.

We also combined flight scheduling with crew scheduling and optimized the problem holistically, and the system produced flight schedules that reduced crew costs significantly. We combined our optimization algorithms with an advanced decision support system, where users could define constraints, prepare scenarios, run different optimization modes and view schedules using advanced visualization tools. We hosted SkyMAX in the cloud to enable high performance, reliability and scalability.

Key Benefits

  1. Maximized profitability: The system balances network profitability and operational constraints to find the best times (for both nonstop and connecting passengers) and allocates the right aircraft to each flight leg in the schedule.
  2. Improved aircraft utilization: Planners can develop more effective schedules that increase aircraft utilization by simultaneously adding a combination of fleeting and timing changes to the schedule.
  3. Faster schedule generation: Because the system rigorously builds flight schedules that satisfy all operational constraints, manual efforts are minimized.

Results

When Southwest started to use SkyMAX in 2015, it was an immediate success. Planners were able to create new flight schedules that were both highly operable and highly profitable. Using SkyMAX, Southwest generates schedules that improve network profitability by tens of millions of dollars annually. It was considered impossible to generate optimal clean-sheet flight schedules for an airline the size of Southwest, due to the size of the mathematical problem. But with SkyMAX, Southwest’s network planning became innovative by creating clean-sheet schedules to maximize profitability, instead of incrementally modifying an existing schedule. Using SkyMAX, Southwest significantly reduced the time it takes network planners to create new schedules. Multiple users can now collaborate to create and analyze more what-if scenarios, create more base schedules and perform strategic planning studies.