Exact algorithms for the single airport slot allocation problem

Read full text Summarise with VIRAT
Authors: Paula Fermín Cueto
Cited by: 0

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Airport slot allocation is a demand management mechanism designed to maximise the utilisation of existing infrastructure at congested airports. Aircraft operators submit schedules of regular flights they wish to operate over a five- to seven-month period, and a designated coordinator allocates the available airport slots, which represent the permission to operate regular flights at specific dates and times. From an optimization perspective, this problem is a special class of the Resource Constrained Project Scheduling Problem where the main objective is to minimise the difference between the allocated and requested slot times, subject to airport capacity limits and other operational constraints. Despite widespread recognition of the need for optimization in slot allocation, there is no consensus on how the problem should be modelled. Industry guidelines are often ambiguous, and several aspects of the current practice have been subject to criticism. As a result, much of the academic literature has concentrated on developing integer programming models, either to influence policy or to propose formulations for under-explored elements of the problem. Little attention has been given to the algorithmic aspect of the problem, particularly to exact methods, which have the potential to deliver solutions that achieve better utilisation of existing capacity and higher airline acceptability compared to heuristic approaches. This thesis addresses this gap by introducing two main algorithms that can solve the problem efficiently, primarily through aggressive model size reduction, a key challenge in this and similar scheduling problems. We first propose a preprocessing scheme that identifies significantly more redundant constraints and variables than a commercial solver in a fraction of the time. Building on this, we develop Caracal, an exact solution method that combines a column-and-row generation algorithm for the linear relaxation with a branch-and-cut framework to find optimal integer solutions. These algorithms are developed using a minimal slot allocation formulation. Finally, we test these solution approaches on several practically relevant problem variants, including novel formulations for aircraft upgrade requests, historic overages, and season segmentation. Extensive computational experiments demonstrate that the proposed methods can find optimal or near-optimal solutions on instances derived from real UK airport data, as well as on a set of realistic synthetic instances. These instances, along with the code to generate them, are made publicly available to support future benchmarking of slot allocation algorithms.

Fields of Study & Subjects

Air Traffic Management and Optimization Vehicle Routing Optimization Methods Healthcare Operations and Scheduling Optimization

Publication details

Journal / source
ERA
Publication date
20 March 2026
Language
EN
Document type
Thesis