Combined Assignment Models​

$20-50M

Increase in annual profits​

15 mins

Change in flight times allowed before/after takeoff​

Overview

Airlines use several models (generally in a specific sequence) to create their flight schedules. Combining two models into one gives greater opportunity for optimization. We integrated two airline models (Fleet Assignment and Through Assignment) into a single model for United Airlines, which created the opportunity for United to possibly save tens of millions of dollars annually.
airport2-case-study-img

Business Problem

Airline fleet scheduling is a very large-scale decision problem, due to its variability and mathematical complexity. As a result, it’s typically divided into a series of decisions solved by separate mathematical models. However, this results in a sub-optimal solution. By combining several models into a single model, we can create more profitable schedules. United Airlines hired Optym to do this with its Fleet Assignment Model (FAM) and Through Assignment Model (TAM).

Our Approach

We combined FAM and TAM into a single integrated model called ctFAM (Combined Through and Fleet Assignment Model). This model used an improvement approach and changed both the fleet assignment (the plane type assigned to a flight leg) and through assignment (the flight legs to connect in a single plane route) to improve overall profitability. Our approach used the very large-scale neighborhood (VLSN) search technique, a novel technique that identifies and evaluates billions of solutions to find the best solution within minutes.

We developed several extensions of ctFAM with greater degrees of freedom (such as allowing flight times to be changed by plus or minus 15 minutes of scheduled departure times) to create more profitable schedules. Our techniques integrated well with those used by United Airlines at that time and augmented them instead of replacing them.

Key Benefits

  1. We applied this technique to data provided by United Airlines and demonstrated that the schedules generated were implementable.
  2. The algorithms demonstrated the potential for a $25 million to $50 million increase in annual profits.

Results

The computational times of these algorithms varied from a few seconds to a few minutes – proving that these algorithms can be embedded in real-time decision support systems. Results from this research were published in several prestigious journals, demonstrating not only the practical merit of the work, but academic merit as well.