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. A plan that considers all rules and regulations, flight schedule and passenger predictions as well robustness for change.
Sounds simple, but requires some serious mathematics to work.
At the Kittilä airport, the number of passengers grew by 12% in 2018 compared to 2017 (which itself was 28% busier than 2016). This puts heavy pressure on the infrastructure and resources of the region, especially its airports.
The struggle for resources
Even though Kittilä is a small airport (12 parking spots), with 58 flights arriving and departing on the busiest days (most of them within the few busy hours), the number of parking alternatives at the airport quickly becomes impossible for a human to calculate.
That’s right, 58 flights can be placed in 10^31 different combinations on the parking plan. A tough nut to crack even for a supercomputer. With 70-80% of those flights landing within a four-hour time frame, atmosphere at the airport is far from holiday spirit.
Parking spots aren’t the only limited resource. The airport is constantly struggling to provide enough busses, staff and check-in counters to cater to the booming air traffic.
Simply adding more resources is ineffective, since outside the busiest season the airport only receives one or two flights a day. The question thus is, how do we optimally operate the airport with the resources we have?
The parking plan dictates the operations of the airport
The entire operations of an airport are built around a parking plan. As it’s name suggest, the parking plan determines where each airplane will be parked.
Previously, the parking plan was created manually on the night before using basically pen and paper. It took three hours to complete and was essentially the best possible guess that an expert could make. This plan was then used as a foundation for reserving the resources (staff, busses etc.) needed to operate the airport throughout the day.
Up-to-date and correct data is the cornerstone of good decision-making, making the daily airport operations more efficient and was also one of the key enablers for this project to succeed.
Head of Data
This project was not about optimizing banners for a website, this was about optimizing the logistics of planes and the experience of hundreds of thousands of people. Thanks to the tight collaboration between the development team, Finavia IT and Kittilä Airport end users, we were able to solve complex and end user problems by utilizing modern technologies and airport data to create something new in a very pragmatic way. Great success.
THE SNOWBALL REACTION
Even though the parking plans were created by experts using their years of experience, they could not withstand the number of exceptions that always occur in winter conditions. Nor were the experts able to predict flight times or the number of passengers on a given flight – which is often not known beforehand.
Incidentally, when one flight is delayed, the situation can snowball into a chaos. Delays cause further delays as another plane cannot land before it has a parking space available. Check-ins are completed at the wrong time forcing passengers to wait for hours before their flight departs. Luggage is delayed. There are too few buses around causing further delays or too many buses leading to inefficiencies elsewhere. And it only tends to get worse as the day progresses.
As such, there was plenty of room to improve on the parking plans – and the operation of the entire airport.
The solution: an optimization model
We created an optimization model in co-operation with the parking experts and the management of the Kittilä airport. As said before, the parking plan is crucial to the running of the entire airport, so that’s where the optimization model focuses.
As Kittilä’s challenges are related to schedule changes (delays after delays) and lack of resources, the criteria behind the perfect parking plan was defined as:
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 perfect 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 model also uses predictions of the arrival times and passenger numbers of the flights to optimize the plan.
Machine learning instead of historical data
Machine learning helps the optimization understand what happens next. It is used to create predictions on arrival times, passenger numbers etc. which are then fed and refed to the optimization model to produce the perfect plan.
Historical data (previous plans) were of little or no use in creating the optimal plans. While the plans used before were created by experts, they were simply not the best possible plans.
Putting the model into practice
Together with Finavia and Reaktor, we created an ERP system for the airport 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).
This Christmas we had a new passenger record but we still made the grade with the help of this great software that not only optimizes the parking plans but also helps us to coordinate work and solve unexpected challenges. We managed to run our operations more smoothly, cut down delays and – most importantly – managed to improve customer experience, which would not have been possible without this visualized optimization tool.
Airport manager /
In recent years a new digitalization track has emerged alongside digital passenger services: how to optimize the core airport operative processes using the possibilities of modern technology and user centric design & development. The potential is huge, and this very successful project has shown that when done in the right way, the payoff is there. Extremely encouraging for us to continue driving this kind of development to provide the best possible performance and experience for passengers and airlines.
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 is no way going back, planning the operations completely sucks without this tool!
If possible (stand, bus or check-in) assignments could be explicitly formed based on the flight and airport data, the optimization problem could in principle be solved by a brute-force calculation.
However, the enormous dimensions of the problem make this approach unfeasible. In practice, it would take the fastest supercomputer in the world billions of years to calculate a solution.
The problem thus needs to be formulated as a linear mixed-integer optimization problem that is solved iteratively by considering a master and a slave problem in a successive manner.
The master problem is defined as a linear continuous optimization problem that only considers a small portion of the data space and can be solved efficiently by using an iterative Simplex algorithm.
The portion of the data space to be considered, on the other hand, is determined by solving the slave problem.
This is based on utilizing the dual solutions related to the optimization constraints, which allows us to find the data space points that have the greatest potential of improving the master solution from the previous iteration.
This is the computationally expensive phase of the solution. It turns out to be beneficial to present the data as a mathematical graph in order to eliminate the time dimension and to present the problem as a shortest path puzzle.
When better assignments can no longer be found, the problem has converged, and the optimal solution can be computed using a branch-and-bound algorithm.
The solution was deployed in December 2018, but the results are already hugely impressive.
When 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.
Not only is the new model by definition the best possible model, it’s also significantly faster than the old way of working. Instead of spending three hours to create a parking plan, it now takes just 30 seconds to produce one.
The solution also optimizes the number of busses required to transport the passengers from the planes to the terminals and vice versa, as well as the number of staff required.
Better passenger experience
Passengers spend less time waiting for their check-in and less time waiting for their plane to land. A total of 300 000 passengers already impacted by the solution.
Less CO2 emissions
The likelihood that a plan has to circle around Kittilä before a parking space becomes available has been reduced. As a result, tons of fuel is saved.
Only the beginning
The model can and will be used at other Finavia airports in the future with Ivalo and Rovaniemi next in line.
Tommi Vihervaara, Head of Data
Henri Lehtonen, Development manager
Heikki Koski, CDO
Riku Lukkari, Maintenance Manager
Kimmo Liukkonen, Airport manager for Kittilä Airport
Data & AI: Fourkind
Maria Pusa, Data Science Consultant
Henri Poikonen, Solution Architecture Consultant
Jarno Kartela, Machine Learning Partner
User interface: Reaktor
Juuso Haaksivuori, Business Development
Aki Kaivola, Software Developer
Juha Karemo, Software Developer
Timi Koponen, UX Designer
Aapo Kojo, UX Designer
Evan Miller, Software Developer