Some of the most complex and difficult yet exciting logistical challenges can be found in the airline industry. OSI has experience collaborating with some of the world’s largest airlines on mathematical optimization solutions to address their operational challenges.
Problem statement
Turns
Creating an airline schedule is a long and iterative process. A schedule starts out as a rough and simplified draft. As operation day approaches, the schedule gets passed on from model to model, each adding a little more detail and specificity along the way.
At this point in the planning process, each flight has already been determined, consisting of an origin, destination, departure time, and duration. The next step is to build turns. For every arrival, there are multiple departing flights that a plane could fly next, so a turn is a match between an arriving flight and a later departure flight at the same airport. Once all flights have been linked together through turns, each plane now has a full itinerary.
Ground time
Turns determine how long a plane will stay on the ground. Ground time is an important decision variable as it impacts the buffer time between flights to prevent cascading delays. With inadequate ground time, any delay in the arriving flight gets propagated directly into the next one. On the other hand, excessive buffer time will lead to planes idling on the ground. Hence, optimally allocating ground time between arrivals and departures is crucial for customer satisfaction and airline’s profitability.
Ground time is a precious resource that is useful in preventing delays but tightly capped by the limited fleet size. The schedule cannot create more ground time, however it can still shift ground time to the flights that need it most.
The incumbent approach simply uses a LIFO (last-in-first-out) approach. Although this does result in tight turns making sure the fleet can cover all of the scheduled flights, it does not consider that flights with a higher likelihood of delay may need a longer ground time. Although there are various operational models that add more sophistication to the turns in later stages of the flight planning process, we want the airline to have a more realistic vision of the plane itineraries sooner. This allows network planners to make decisions sooner with more confidence and provides those later operational models a better headstart.
Solution
OSI developed a turn building model which uses the CPLEX solver to build optimal turns. The airline provides the model with information on which flights have the highest likelihood of delay, and the model builds turns that distributes more of the available ground time to those flights while adhering to operational constraints such as maintenance requirements.
The model is able to add five or more minutes of ground time to 13%-19% of the flights that were identified to have a higher likelihood of delay, all within a rapid runtime of 10 seconds, and seamlessly integrates with the rest of the airline’s codebase.
The graph below shows the distribution of ground times for all high delay-likelihood flights in July 2019. Note that the time required to deboard, board, clean, and fuel the plane has been subtracted from all of the ground time values in this blog (making it possible for flights to have “zero” minutes of ground time). The proportion of flights with 5 or less minutes of ground time decreased from 38% to 24%, while the proportion of flights with 10+ minutes of ground time increased from 50% to 63%. The clear shift to the right shows that ground time has successfully been redistributed to these flights that need it most.
JuMP
Our model was implemented using JuMP, a modeling package within Julia. After initial prototyping in python, JuMP proved to be a better choice for our use case by significantly decreasing the run time of our model.
OSI has expertise in a wide variety of optimization software, so our clients can be confident that they are using the best tools to tackle their business challenges. Instead of crutching on safe and established methods, we love to help our customers leave their comfort zone to embrace the latest tools.
You can hear more about our project in Willem’s talk at the JuMP-dev conference in Montreal, Canada, in 2024.
https://youtu.be/KeqCERdQx6o?feature=shared
