Optimizing Gate and Stand Assignments

Business Situation

Consider the difficulty of finding a parking space for your car in a busy parking lot. Now imagine an environment where not every space can accommodate every car, where the parking lot is usually full yet demand is predicted to increase significantly in the future, and where adding one new space costs

10M USD (30M-50M DDK). If you replace cars with aircraft, that’s the situation that Copenhagen Airport (CPH) faced in 2010. The OR group at CPH was brought in to build a system that could maximize the utilization of each existing aircraft stand (the equivalent of a parking space for a car), and that could also be used to create a plan for increasing future capacity in the most cost-effective way.

Building the Model

Traditionally, strategic assessment of stand and gate capacity at an airport has been done in a high-level, top-down fashion. However, such analysis often ignores crucial operational details that can have a significant impact on the demand for a particular type of stand. For example, in 2010 CPH had seven large stands, which appeared sufficient to meet the expected overall demand from large aircraft. However, on closer inspection, it turned out that only two of these stands could accommodate the Boeing 777-300ER, and likely future schedules had periods when three would be on the ground at the same time

After careful review, the OR team formulated a detailed, bottom-up optimization model for the problem, incorporating virtually all of the operational requirements and restrictions in the model. The model included both hard constraints (e.g., certain aircraft type could only park at certain stands) as well as softer preferences (e.g., some airlines prefer to be located closer together, since they have a high number of passengers transferring between them). The mathematical model was built in two months using the C++ API of Gurobi.

Results

Gurobi was able find solutions for the initial version of this model in roughly five minutes. These solutions provided valuable insights, and also pointed out ways in which the model could be refined to provide even more valuable information. One refinement added additional operational detail to the model. Another extended the solution process to include the ability to solve a simplified version of the model in less than 20 seconds, This allowed for easy what-if analysis around key decision trade-offs. The results from the model allowed the team to recommend a more efficient plan, which served as the basis for a set of new investments in stands and gates whose total cost was over $70M USD (400M DDK).

Process Learnings

A key to the team’s success has been the focus on solving the right high-opportunity problem. Since the team is working in the airport, they are close to the people and the problems. Being at the intersection of operations and development has been critical to their ability to understand the core problem opportunity in the area they are trying to solve.

Role of Gurobi

Gurobi has played several key roles: Gurobi’s easy to use C++ API and interactive shell helps us quickly prototype ideas and see if our gut is right. We do it all ourselves and use Gurobi in the process. When ready, we send out the results, people see the solutions work, and then we work to improve the model. With Gurobi we don’t have to worry about the algorithms. We get the data, build the model, give it to Gurobi, and get the results.

Role of Excel

Since our focus is on rapid prototyping, we use Excel as the front-end of the system, i.e. the place where all the data was captured. The datasheets are then exported to CSV files and transferred to the server where the application is running. The application reads the data, solves the model, saves it as a CSV file, and sends the solution back to Excel. Why Excel? It is easy to work with. While it is a spreadsheet, it can act as a database and since people are used to working in Excel it is intuitive to use.

Copenhagen Airport

• The world’s first private airport (1925)
• Busiest airport in Scandinavia
• Serves over 150 airlines and 23 million passengers a year
• Moved from Government control to public-private partnership in 2005

Team structure

The OR group started in 2009 when analysts from the operational departments were consolidated into a single team.
In 2013 the team includes 7 people, of which 5 have a M.SC. in Operations Research. Outside of the purchase of Gurobi, everything else is done in house. After we see good results, we start looking for providers that can deliver systems to replace our prototypes.