A Large-Scale Neighborhood Search Approach to Airport Slot Allocation

Nuno Antunes Ribeiro (), Alexandre Jacquillat () and António Pais Antunes ()
Additional contact information
Nuno Antunes Ribeiro: CITTA, Department of Civil Engineering, University of Coimbra, 3030-788 Coimbra, Portugal
Alexandre Jacquillat: Heinz College, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
António Pais Antunes: CITTA, Department of Civil Engineering, University of Coimbra, 3030-788 Coimbra, Portugal

Transportation Science, 2019, vol. 53, issue 6, 1772-1797

Abstract: Access at the vast majority of busy airports located outside the United States is subject to schedule coordination. These airports declare a value of capacity and allocate a corresponding number of slots to the airlines. Slot allocation follows rules and priorities established by the International Air Transport Association (IATA), which introduce coupling constraints across the allocation of slots at multiple times of the day and on multiple days of the year. As a result, slot allocation is a highly complex combinatorial problem, which carries enormous weight for airlines, airports, and passengers. Integer programming models have been proposed to support slot allocation by minimizing deviations from the airlines’ requests. Because of the problem’s complexity, these models have been only successfully implemented at small- and medium-sized airports. This paper develops an original algorithm based on large-scale neighborhood search to solve the slot allocation problem at the largest schedule-coordinated airports. The proposed algorithm combines a constructive heuristic , which provides an initial feasible solution in short computational times, and an improvement heuristic , which iteratively reoptimizes slot allocation by subdividing the slot requests into smaller subsets. The algorithm is implemented at Lisbon’s Airport (LIS), one of the top-20 busiest airports in Europe. Results suggest that it can provide optimal or near-optimal solutions in a few hours of computation, while direct implementation of existing optimization models with commercial solvers does not terminate after several days of computation. Ultimately, the proposed approach considerably enhances the capabilities of slot allocation models and algorithms.

Keywords: airport slot allocation; integer programming; large-scale neighborhood search (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1287/trsc.2019.0922 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:53:y:2019:i:6:p:1772-1797

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().