The network level airport slot allocation problem: A new formulation and matheuristic solution approach

Efficiently allocating resources to enable flights to land and take-off at an airport is a heavily constrained problem. Airlines request to use slots, where permission is granted to use airport infrastructure, which are allocated within the limits of the capacity of an airport. As demand for slots often significantly exceeds supply, this can lead to airlines being allocated undesirable slots that do not align with their intended operations. This issue is exacerbated when schedules are created independently at different airports across a network, as undesirable allocations may result in infeasible airline operations. This paper introduces a novel integer linear program (ILP) formulation for the network slot allocation problem, incorporating rejected requests, flight time flexibility and seasonality. We investigate solving the network-level slot allocation problem simultaneously across a network, compared to allocating slots at each airport independently. Our results show that scheduling over the network simultaneously ensures the feasibility of operational constraints that are not met when each airport is scheduled independently. Additionally, a matheuristic destroy-and-repair approach is developed to schedule flights over a network of ten of the largest airports across Europe. The flight request data used is derived from the real-world operations at each airport. The proposed matheuristic approach leads to comparable solutions to an exact solver within significantly shorter run times, contributing new tools that can be deployed by schedulers for real-world scenarios within a reasonable computational time.