Airline schedules are built weeks in advance, but they have to survive the day of operation. OSI has experience working with some of the world's largest airlines on mathematical optimization, and this post looks at one of their hardest day-of problems: recovering the schedule when an aircraft breaks down.
Every flight in a schedule is assigned to a specific aircraft, and each aircraft flies a chain of flights through the day. When an aircraft is grounded unexpectedly, for a mechanical fault for example, the rest of its chain has nothing to fly it. Airlines call this an irregular operation, or IROP.
The operations team must then re-plan the rest of the day within minutes. They can move a flight to another aircraft, delay it, or cancel it. Every choice affects other flights, because the aircraft that steps in has its own flights to fly later.
Recovery is usually worked out by hand, under time pressure. The safe choice is to keep each flight on its original aircraft and wait for the repair, which passes the whole delay on to passengers. A better plan often exists, but finding it means checking many combinations that a person does not have time to check.
OSI developed a recovery model which uses the CPLEX solver to re-plan the schedule the moment an aircraft is grounded. The model decides which aircraft flies each remaining flight and when it departs. It weighs swaps, delays and cancellations together and returns the plan with the least total disruption, in about a second.
Every plan respects the rules an operations team checks by hand: aircraft type, minimum turn times, and each aircraft being at the right airport for its next flight. The team gets a plan it can act on straight away, with time left to test alternatives.
A disruption does not end at midnight. Where each aircraft finishes today decides whether tomorrow's first flights leave on time, and whether each aircraft reaches its overnight maintenance check. A plan that only fixes today can quietly break tomorrow.
This is where our model stands out. It plans today and tomorrow together, across every city in the network, with each aircraft's maintenance check built in.
Take one of our demonstration scenarios. Aircraft A2 is grounded for four hours in the morning, with flights F203 and F204 still to fly.
The single-day plan moves F203 and F204 to aircraft A3, and in return gives A3’s flight F303 to A2. Today looks fine: 195 minutes of delay and nothing cancelled. But A2 and A3 now end the day in each other’s cities, so neither is where its first flight tomorrow departs from. Tomorrow’s schedule is broken before it begins.
Our two-day model sees this coming. It still moves F203 and F204 to A3, but keeps F303 on A3 and accepts a longer delay on it today. A3 finishes the day in the city where its maintenance check is due, and A2 stays where tomorrow needs it. Tomorrow absorbs the rest in a controlled way: F311 leaves after A3’s check, and F312 moves to A2. Every flight on both days operates, with no cancellations.
On paper, the single-day plan looks cheaper. In reality it is only hiding tomorrow’s damage, because it stops counting at midnight. Our model counts every consequence, today and tomorrow, and then makes the call.
This is what sets our model apart. In about a second, it searches every possible combination of swaps, delays and cancellations and returns the optimal plan. Every aircraft is in the right place, every turn time is respected and every maintenance check is protected, making the model feasible in the long run. When the schedule breaks, the airline gets a plan it can fly with confidence, today and tomorrow.
Technology
The model is a mixed-integer program written in Python with IBM DOcplex and solved with CPLEX. Every plan is independently checked for feasibility before it is shown to the user.
You can see the model in action in the short video below.
