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.