How do you operate an airport during peak traffic under extreme uncertainties, continuous exceptions, restricted resources and unpredictable weather? By calculating a plan for optimizing the airport and its resources. Sounds simple, but requires some serious mathematics to work.
When Christmas arrives, Lapland changes.
At Kittilä Airport, the number of passengers grew by 12% in 2018. This growth puts heavy pressure on infrastructure and resources in the region.
Even though Kittilä is a small airport with twelve parking spots, 58 flights arrive and depart on the busiest days. The number of possible parking alternatives at the airport quickly becomes impossible for a human to calculate.
58 flights can be parked 10^31 different ways – a tough nut to crack even for a supercomputer. With 70-80% of those flights landing within a four-hour time frame, calling peaks busy would be an understatement.
Parking spots aren’t the only limited resource. The airport is constantly struggling to provide enough buses, staff and check-in counters to cater to the increase in air traffic. Simply adding more resources is ineffective, since outside the busiest season the airport only receives one or two flights a day. How do you operate an airport with limited resources?
In co-operation with the parking experts and the management of Kittilä airport, we created an optimization model that generates optimal parking plans.
Previously, daily parking plans at Kittilä were created manually the night before, on pen and paper. As Kittilä’s challenges are related to schedule changes and lack of resources, the criteria behind the perfect parking plan were defined as:
- The plan’s ability to withstand schedule changes (robustness)
- Bus resources required to execute the plan
In creating the perfect plan, the model allows the user to adjust the criteria freely.
With the criteria set, the optimization model then uses flight data to build a mathematically perfect parking plan based on all the data available. The plan takes into consideration all rules (e.g. not all airplane types are allowed at all parking spots) and preferences (e.g. Non-Schengen flights parked near passport control) regarding the parking. The solution also uses machine learning to predict arrival times and passenger numbers, which are then incorporated into the optimization process.
Together with Finavia and Reaktor, we created a planning solution running on AWS with the optimization model at its heart. Instead of dabbling with pen and paper on top of a spreadsheet, the airport parking operators can now build a parking plan in and reserve the busses they need from the same simple user interface. If situations change during the day, a new optimal plan can be created in seconds.
Imagine that. A mathematically perfect parking plan with the click of a button.
The solution is used daily in building the parking plan and in optimizing the bus routes and resources. It’s also used to update the plan if delays occur and enables long-term resource planning (which previously was unheard of).
How does the optimization work?
Brute-forcing a solution by generating parking plans and checking if they fill requirements is far too time-consuming to be feasible. Instead, we frame the problem as a linear mixed-integer optimisation problem, aiming to maximise robustness whilst adding business, legal and logistical requirements as linear constraints. This narrows the feasible region in which to find a solution. Dantzig’s Simplex algorithm is then used to find the solution, using an iterative process of elimination. For constraints for which no hard data is available, we estimate their values using a Gaussian Process prediction model.
From 3 hours to 30 seconds.
The solution was deployed in December 2018, but the results are already hugely impressive.
Comparing December 2018 with December 2017:
- The number of flights increased by 12 %
- The share of airport-related flight delays decreased by 61 %
- Duration of average airport-related flight delay decreased by 66 %
- The decrease in delays resulted in an estimated 500 000 € cost savings
- The airport’s NPS score increased by 20 points
More robust against schedule changes
The new parking plan created by the model is optimal in the sense that the idle time between successive flights at the same stand is as long as possible. Therefore, when delays or exceptions inevitably occur, it is less likely that the delays will impact other flights. As the plan is more robust, delays do not snowball to other flights.
Using the new system, it’s now possible to instantly get a helicopter view of the entire airport. Parking spots, planes and busses are now shown on a single screen, which makes it easy to understand what is happening at the airport. And a single click creates a new plan, if problems appear on the horizon.
Operating an airport is a collective affair. As the parking plan is now easily presentable and familiar to everyone at the airport, collaboration and coordination between different parties at the airport is simplified.
Less CO2 emissions
The likelihood that a plane has to circle around Kittilä before a parking space becomes available has been reduced. As a result, tons of fuel is saved.
After we got our hands on this stand allocation software, our work has been much easier and we can better coordinate not only the parking plans but also the fueling of planes, pushback operations and apron buses. There's no way going back, planning the operations is a complete mess without this tool.