Heuristic search for allocation of slots at network level

This paper considers the allocation of slots for a network of coordinated (congested) airports, where the term “slot” refers to a time on a specific day when a carrier is given permission to use the full range of airport infrastructure for the purpose of landing and take-off at a slot-controlled airport. We take into account the existing IATA rules and guidelines: priorities of requests for slots, the capacity limitations at each airport, the minimal turnaround time between arrival and subsequent departure of the same aircraft, and allocation to series of slots rather than to individual slots. Given the complexity of the problem, we propose an approach that consists of (i) a constructive heuristic procedure to generate a feasible and coherent allocation of slots for each airport from the network, and (ii) an iterative heuristic to improve the quality of an initial feasible solution in terms of the schedule delay (time difference between allocated time slots and airline requests). To evaluate whether the approach would be practical in real operation, we perform tests on a set of generated benchmark instances that span an entire scheduling season. The instances differ by the number of airports in the network and by the distribution of requests among airports from a given network - the largest number of airports forming a network is 100, while the maximum total number of aircraft movements considered on a half-yearly basis exceeds 4.6·106. We provide computational comparisons with solutions obtained when each airport from a network is considered independently (the en-route constraint is ignored). These results reveal that the consideration of the en-route constraint, which ensures a coherent allocation of slots at origin and destination airports, introduces only a minor degradation in the schedule delay and in the number of unaccommodated requests. Furthermore, we investigate the heuristic performance for reduced-capacity scenarios.