Optimising airport slot allocation decisions with stability
considerations
Fotios A. Katsigiannisa,*, Konstantinos G. ZografosaaLancaster University, Lancaster, United Kingdom
f.katsigiannis@lancaster.ac.uk, k.zografos@lancaster.ac.uk*
Presenter

Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island
March 18, 2022
Keywords: airport slot allocation, mixed integer programming, stable matching

1INTRODUCTION

Airport Slot Allocation (ASA) is the main airport demand management mechanism currently beingapplied in 198 airports (as per the 2022 summer season (IATA/ACI/WWACG, 2020)) which
concern more than half of global passenger demand (despite the impact of COVID-19). The ASA
process is defined by the World Airport Scheduling Guidelines (WASG)(IATA/ACI/WWACG,2020). During the ASA process airlines submit requests for airport slots based on their commercialinterests and preferences, while coordinators allocate slots to requests following a set of primary andsecondary criteria stemming from WASG. Existing ASA studies propose formulations that consider
airlines’ preferences for each available time slot (Zografos et al., 2017; Jacquillat and Vaze, 2018;Fairbrother et al., 2019), but they do not explicitly consider the interactions between the two sidesof the coordination process, i.e., the explicit consideration of airlines’ utility by the coordinator when
applying WASG.
In this paper we propose an Integer Programming (IP) formulation and a Deferred Acceptance (DA)algorithm (Gale and Shapley, 1962) that consider the ASA problem as a two-sided matching gameand model each submitted airline request and available airport slot as distinct entities. In doing so,time-dependent functions express the airlines’ utility for each submitted request and the priority
assigned by the coordinators based on WASG. The IP formulation considers the equilibria between
the airline and the coordinators’ side but introduces increased computational complexity. Vis-à-vis
this complication, the proposed DA algorithm generates multiple airport slot schedules within
tractable computational times. The generated schedules guarantee that the utility achieved for eachrequest cannot be improved without compromising the request-to-slot assignment of a more
important request (based on the airlines’ preferences and the WASG-defined prioritisationconsidered by the coordinator), ergo ensuring that airlines and coordinators have no incentives toreject or alter the proposed allocations. Consequently, the request-to-slot assignments proposed by
our approach are said to be stable and achieve improved schedule acceptability.

2

FORMULATION

The paper introduces an IP formulation (expressions 1-5). The notation required for formulating theIP and the DA algorithm is presented in Table 1. The expressions used for the definition of the IPformulations are provided as follows.
𝑥∈̃TRISTAN XI Symposium

≤1𝑚∈𝑀

(1)

Original abstract submittal

F.A. Katsigiannis, K.G. Zografos
𝐻 𝑥∈[∈2≤ 𝐶𝐴𝑃𝑐 ∈ 𝐶, 𝑑 ∈ 𝐷, 𝑘 ∈ 𝐾, 𝑡 ∈ [0, |𝑇 |̃ − 𝑐]+ − ]

(2)
(3)

𝑥∈[+)

𝑥
∈[ −𝑥
∈

|

≤1(𝑚𝑎, 𝑚𝑑) ∈ 𝑀 × 𝑀, 𝜅 ∈ [𝛵𝑇 , |𝑇 |)̃̃|]|𝑡 − 𝑡 | ≤ Ω̃

𝑚𝑖𝑛 𝑍 = 𝛽𝑚∈𝑀

𝑍𝛧
𝛧
𝛧+𝛽+𝛽+𝛽|𝑀 ||𝐷||𝑇 |̃
|𝑀||𝐷||𝑀||𝑇 ||𝐷|
̃(4)
(5)

Table 1 – Notation of the IP formulation)

𝑀:𝑀∪𝑀𝑀 ×𝑀=𝑀

𝐷 (𝐷 )Sets

𝑀(𝐶: {5, 15, 60}
𝑇 :̃ {1,2, … , 𝑛}
𝐾: {𝐴𝑟𝑟, 𝐷𝑒𝑝, 𝑇𝑜𝑡𝑎𝑙}𝑡Parameters

𝑇𝑇𝐶𝐴𝑃𝐻𝛯 (𝑡)𝛹 (𝑡)Decisionvariables andobjectives

𝛽𝑥𝑍𝑍𝑍𝑍Set of request series denoted by 𝑚
Set of arrival (departure) series
Set of paired requests (𝑚𝑑, 𝑚𝑎)
Set of days in scheduling season denoted by𝑑 (of request 𝑚)
Set of capacity time intervals indexed by 𝑐
Set of time intervals per day based oninterval 𝑐 ̃ indexed by 𝑡, 𝑡′
Set of movement types denoted by 𝑘Requested time for slot series 𝑚
Maximum and minimum turnaround timesof paired request 𝑝Capacity for movements 𝑘 for a period[𝑠, 𝑠 + 𝑐] on day 𝑑 based on time interval 𝑐Indicates whether series 𝑚 is requested on
day 𝑑 or not
Preference assigned by request 𝑚 to slot 𝑡
Priority assigned by the coordinator torequest 𝑚 with respect to 𝑡
Relative importance assigned to objective 𝑗
1 if request 𝑚 is allocated to time 𝑡; 0otherwise
Number of rejected requests’
Maximum displacement
Number of displaced requests
Total displacement

Expressions (1) are assignment constraints. Expressions (2) define rolling capacity constraints forarrival/departure and total movements. Expressions (3) are turnaround time constraints. (4) areauxiliary expressions defining the maximum displacement objective. Expression (5) defines thescalar objective function of our model which consists of relative importance weights (𝛽 ) for eachconsidered objective. The model defined by (1)-(5) is complemented by expressions whichguarantee that there will be no request-to-slot assignments where a request may prefer anotheravailable slot, or a slot would rather be matched to another request of higher priority. These arereferred to as stability inequalities consider 𝛹 (𝑡) for determining the requests that will be assigned
to each slot, while 𝛯 (𝑡) is used for considering airlines’ preferences.

TRISTAN XI Symposium

Original abstract submittal

F.A. Katsigiannis, K.G. Zografos

33

SOLUTION METHODOLOGY

The solution of the IP formulation using commercial solvers (airport instance concerning 2491
requests series which translate to 72000 movements) requires days so as to produce a single airport
schedule. In response, in what follows we detail a fast DA algorithm that can generate multiple
airport slot schedules that are Pareto optimal with respect to each submitted request. DA algorithms
were first introduced by Gale and Shapley (1962) and are currently being considered in several
scheduling and resource allocation problems (Abdulkadiroglu and Sönmez, 2013).
In contrast to the MIP defined in section 2, the proposed algorithm considers the rules and priorities
of WASG using 𝛯 and 𝛹 as soft constraints and operates based on the following logic. At thefirst iteration of the algorithm, all requests demand the slot that has the best spot on their preferencelist (step 1 in Algorithm 1). Based on the slot’s capacity, the requests with highest priority areprovisionally matched to the resource (step 2). If the number of applications exceeds the capacity ofthe slot, then the applications with the lowest priority (as per 𝛹 (𝑡)) are rejected. In the case that thecapacity of the slot suffices to accommodate all applicants, then all requests are matched. The
preference lists of the requests are updated (step 3) and the algorithm proceeds to the next iteration.
During the following iterations, each request that was rejected in previous iterations proposes to thebest-remaining and feasible slot (the best option remaining in 𝛯 after the update process describedin step 3) and the requests with the highest priority are matched with the slot. At this point a subsetof requests from among the previously matched requests and the newly proposing requests isselected. This signifies, that if a request proposed to 𝑡, and 𝑡 prefers request 𝑚 to a previously
matched request 𝑚 (𝛯 (𝑡) < 𝛯 (𝑡)), then 𝑚 is unmatched and request 𝑚 takes their place. The
algorithm terminates when either all requests receive a slot, or requests that remain unmatched have
empty preference lists (the request has been rejected by all slots).
Algorithm 1 – A deferred acceptance algorithm for ASA
Input: Set of requests: 𝑀 indexed by 𝑚
Set of slots: 𝑇 indexed by 𝑡
Preference list of each request (𝑚) with respect to each slot (𝑡): 𝛯 = {𝛯 (𝑡)|∀𝑡 ∈ 𝑇 , 𝛯 (𝑡)}Slot-dependent priority of each request (𝑚) by the coordinator: 𝛹 = {𝛹 (𝑡)|∀𝑡 ∈ 𝑇 , 𝛹 (𝑡)}Output: Set of stable request-to-slot assignments
Define the sets of paired requests (𝑃𝑅 ) and the list of request-slot pairs (𝑃 ) to be empty(𝑃𝑅 = { }, 𝑃 = [] )Initialise the list of unmatched requests to be equal to the request set (𝑈𝑅 = 𝑀 )while there are unmatched requests with non-empty preference lists do:(step 1) Each 𝑚 applies for the slot 𝑡 such that argmax 𝛯 (𝑡)∈̃(step 2) ∀ 𝑡 ∈ 𝑇 ,̃ the algorithm determines which requests will be provisionally matched to 𝑡
(step 3) The preference lists of all requests that applied in this iteration are updated by removing 𝛯 (𝑡)from 𝛯(step 4) 𝑈𝑅, 𝑃𝑅 and 𝑃 are updated
return 𝑃4RESULTS

Preliminary results using preference list lengths of alternative sizes, indicate that the DA algorithm
reports objective values that are comparable to the values reported by the IP formulation. In addition,
the sets of schedules generated by Algorithm 1 are not only acceptable and non-dominated withrespect to each submitted request, but also constitute an efficient frontier between the spilled
airline/passenger demand and maximum displacement. The DA and the IP can be used inconjunction so as to produce airport schedules comprising Pareto optimal request-to-slot
assignments in more tractable computational times. This set of observations suggest that the DA

TRISTAN XI Symposium

Original abstract submittal

F.A. Katsigiannis, K.G. Zografos

4algorithm may grasp the specificities of ASA, generate multiple stable schedules, and provide crucial
decision-support to the ASA decision-making process.

5DISCUSSION

The proposed IP and DA algorithm provide request-to-slot assignments that are Pareto optimal perse, meaning that a request cannot receive an improved allocation without compromising theallocation efficiency of a more important request. Hence, the reported schedules are stable based on
the perspectives of both airlines and coordinators. Our computational results to date exhibit that theconcurrent consideration of airlines’ preferences and the priorities assigned by the coordinators
allows the scheduling of additional movements throughout the entire scheduling season. This isachieved by scheduling requests that operate for longer effective periods and serve more passengers.
Despite the computational complexity of the problem, Algorithm 1 may produce a large set ofschedules, albeit requiring a fraction of the computational times required for the solution of the IPformulation.
Our presentation will elaborate on the computational implications of the proposed methodology.
Comparisons among alternative solution approaches and slot allocation regimes/prioritisations will
enable us to discuss the method’s implications for policy and decision-making.

6REFERENCES

Abdulkadiroglu, A. and Sönmez, T., 2013. Matching markets: Theory and practice. Advances inEconomics and Econometrics, 1, pp.3-47.
Fairbrother, J., Zografos, K.G., Glazebrook, K., (2019). A slot scheduling mechanism at congested
airports which incorporates efficiency, fairness and airline preferences. Transportation Science,54 (1) pp. 115-138.
Gale, D., Shapley, L.S., (1962). College Admissions and the Stability of Marriage. The American
Mathematical Monthly 69, 9–15.
IATA/ACI/WWACG, (2020). Worldwide Airport Slot Guidelines [WWW Document]. URL
https://www.iata.org/en/policy/slots/slot-guidelines/ (accessed 9.22.20).
Jacquillat, A., Vaze, V., (2018). Interairline Equity in Airport Scheduling Interventions.
Transportation Science, 52 (4) pp. 941-964.
Zografos, K.G., Androutsopoulos, K.N., Madas, M.A., (2017). Minding the gap: Optimizing airport
schedule displacement and acceptability. Transportation Research Part A: Policy and Practice,
114 pp. 203-221.

ACKNOWLEDGEMENTS
The research reported in this paper has been supported by the UK’s Engineering and PhysicalSciences Research Council (EPSRC) through the Programme Grant EP/M020258/1 “Mathematicalmodels and algorithms for allocating scarce airport resources (OR-MASTER)”. The opinions
expressed in this extended abstract reflect the authors’ views.

TRISTAN XI Symposium

Original abstract submittal