A Modelling Framework for Solving the Network-Wide Airport Slot
Allocation Problem
M. Keskina,*, K.G. ZografosaaCentre for Transport and Logistics (CENTRAL), Department of Management Science, Lancaster
University Management School, Lancaster University, Lancaster, United Kingdom
m.keskin@sheffield.ac.uk, k.zografos@lancaster.ac.uk* Corresponding author

Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

April 4, 2022
Keywords: Network-level airport slot allocation, airport network connectivity, bi-objective
optimization1INTRODUCTION

Many airports around the world are overly congested. These airports are classed as coordinatedairports and access to these airports is controlled through the International Air Transport Association
Worldwide Airport Slot Guidelines (IATA WASG) (IATA, 2021). The capacity of coordinatedairports is expressed in slots. A slot is defined as a time interval during which airlines can haveaccess to the airport infrastructure to operate their flights. Therefore, airlines submit slot requests foreach scheduling season. An independent coordinator allocates slots to requests using a set of rules
described in IATA WASG aiming to satisfy the submitted requests as close as possible to theirrequested time by minimizing slot displacement, i.e., the difference between the requested andallocated time. A similar process is followed for the facilitated airports, for which there is a potential
for congestion only during some periods of the day, week, or season, and the necessary adjustments
are made by the facilitators, similar to the coordinators at coordinated airports (IATA, 2021).
The slot allocation problem has been studied for single airports and at network level. Singleairport models (Zografos et al., 2012; Ribeiro et al., 2018) allocate slots independently at each airport
without taking into account network level interactions. Network level models, on the other hand,allocate slots simultaneously to all airports to capture the inherent flight connectivity interactions
throughout the network (Pellegrini et al., 2017; Benlic, 2018). Existing network level slot allocation
models use as input the requests made by the airlines at each individual airport and extend the single
airport models by introducing flight connectivity constraints to ensure network-wide flight schedulecompatibility. Owing to the complexity of the network level problem, the proposed network level
formulations use simplified approaches, e.g., consider only primary slot allocation criteria, do notcapture the interaction between airport airside and terminal capacity constraints, and do not capture
peculiarities of the slot allocation process emerging from the local interpretation of the IATA
WASG.
In this paper, we are introducing a novel approach in modeling network level slot allocation. In
contrast with existing models, our modeling approach is using as input the initial schedules that havebeen generated at each individual airport and optimally adjusts them to ensure network-wide flightconnectivity. Thus, the proposed approach mirrors better the current network-wide practice. Itensures the autonomy of the slot allocation process at each individual airport and affords theTRISTAN XI Symposium

Original abstract submittal

M. Keskin, K. G. Zografos

2

generation of context specific individual airport schedules, while guaranteeing the network-wide
flight connectivity. Another important feature of the proposed approach is the incorporation of theconnectivity importance of each airport in optimizing the adjustment of the schedules of theindividual airports. This modeling feature can assist decision makers to allocate the cost of thenetwork-wide schedule adjustment (total schedule displacement) among the airports by ensuring thatthe schedules of key airports will not be overly disturbed.

2

NETWORK WIDE SLOT ALLOCATION MODELLINGAND SOLUTION FRAMEWORKWe propose a framework where the slot allocation at each individual coordinated airport isperformed first (as it also happens in practice) by considering the IATA WASG and the complexities
and peculiarities associated with the allocation of slots at each airport. The schedules of theindividual coordinated airports are then used to allocate the slots at network level, such that capacity
limits of each airport, turnaround times for the aircraft, and flight times are respected. The allocationof slots at network level is achieved by ensuring network-wide flight connectivity while optimizing
objective(s) expressing the network-wide slot allocation performance. In this paper we are
introducing two bi-objective optimization models. Model 1 considers the minimization of the: i)total displacement encountered by all flights throughout the network (network-wide scheduleefficiency), and ii) maximum displacement, i.e., interflight-equity. Model 2 considers theoptimization of the network-wide schedule efficiency as in the case of the first model, while thesecond objective optimizes the inter-airline fairness by allocating the total network-wide
displacement to all airlines proportionally to the number of their requested slots at all coordinatedairports. For both models we are introducing variants that: i) do not consider the importance of the
airports in ensuring the network connectivity, ii) incorporate the connectivity importance of the
airports through the consideration of alternative connectivity indices.

2.1

Incorporating Airport Importance

Although there are several indices to quantify the importance of an airport in the air transport
network, we focus on two measures. The first is the betweenness centrality measure (Guimera et al.,2005), which is defined as the ratio of number of shortest paths connecting any two airports thatinvolve a transfer at the airport in consideration to the number of all shortest paths connecting them.
Each arc connecting two airports in the network represents a direct flight between these airports andcan be assigned a weight to illustrate the characteristics of the airports’ relationship. We use thenumber of flights throughout the season as the weight of an arc, and define its distance as the reverseof its weight. The shortest paths between two airports are calculated using these distances.
Betweenness centrality is a measure showing the potential of an airport to funnel the flow of theflights in the network, and is calculated for airport 𝑖 as follows:𝑔 (𝑖)𝑐𝑖 = ∑𝑗,𝑘∈𝐴|𝑗,𝑘∉𝐴 𝑔𝑗𝑘𝑗𝑘(1)

where 𝐴 is the set of airports, and 𝑔𝑗𝑘 and 𝑔𝑗𝑘 (𝑖) stand for the number of shortest paths between
airports 𝑗 and 𝑘, and among them, the number of those that include a stop at airport 𝑖, respectively(Guimera et al., 2005).
The second measure we use is the connectivity index proposed by IATA (2020). It is a measure ofthe degree of integration of an airport into the network in terms of number of passengers travelling.
It is mathematically expressed for airport 𝑖 as follows:
𝐶𝐼𝑖 = ∑𝑗∈𝐷𝑖 𝑠𝑖𝑗 𝑤𝑗

TRISTAN XI Symposium(2)

Original abstract submittal

M. Keskin, K. G. Zografos

3

where 𝐷𝑖 is the set of airports to which there is a direct flight from airport 𝑖, and 𝑠𝑖𝑗 and 𝑤𝑗 stand forthe total number of seats belonging to the flights from airport 𝑖 to 𝑗 and the size of airport 𝑗 in termsof number of passengers handled, respectively.

2.2

Proposed Solution Approach

To solve the proposed bi-objective models and generate the associated efficient frontiers, we use the𝜀 −constraint method (Ehrgott, 2005). The algorithmic framework for Model 1 is presented in
Algorithm 1. A similar approach is followed for Model 2 with different objective functions.
Algorithm 1: Description of the proposed solution framework
Input: Mathematical model for the bi-objective problem, airport schedules obtained from the single
airport slot allocation models, airport importance measures
1. Solve the model using a single objective to minimize the total displacement
2. Let ∆𝑠𝑖𝑛𝑔𝑙𝑒 be the optimal total displacement
3. Solve the model using a single objective to minimize the maximum displacement
4. Let 𝑧𝑠𝑖𝑛𝑔𝑙𝑒 be the optimal maximum displacement
5. Initialize 𝜀: 𝜀 ← 𝑧𝑠𝑖𝑛𝑔𝑙𝑒
6. Solve the model using a single objective to minimize the total displacement with an additional
constraint 𝑧 ≤ 𝜀, where 𝑧 is the maximum displacement
7. Let ∆ be the optimal total displacement
8. Store the total and maximum displacement information of this solution
9. Update 𝜀 with a step size 𝛿: 𝜀 ← 𝜀 + 𝛿
10. Repeat Step 6 until ∆ = ∆𝑠𝑖𝑛𝑔𝑙𝑒
11. Construct the efficient frontier with the stored solutions obtained in Step 8
Output: Network-wide schedules to be evaluated and selected using the key performance indicators

3RESULTS AND DISCUSSION

We present the results from the application of Model 1, which seeks to minimize the totaldisplacement and the maximum displacement received by any flight, to an instance that includes 56
airports, 16 of which are either coordinated or facilitated airports and the network has 479,307 flights
in total. We use the default settings of CPLEX 12.10 solver on a workstation with Intel Xeon E5
2.60 GHz processor and 32 GB RAM. We perform two sets of experiments by weighting thedisplacement by the betweenness centrality measures (case 1) and without weighting thedisplacement (case 2). Figure 1 shows the trade-off between maximum displacement and total
displacement, where the displacements are reported in 5-minute time intervals, for the two cases
under consideration. For both cases, we observe that there is not a strong trade-off between the
maximum and total displacements, i.e., increasing the maximum displacement does not pay off
regardless of whether the airport importance coefficients are used or not. Specifically, when thedisplacements are weighted by the betweenness centrality measures, a 66.7% increase in the
maximum displacement results in an improvement of 5% in total weighted displacement, while thenumber of displaced flights is decreased from 137,082 to 136,021. Similarly, when thedisplacements are not weighted, the improvement in total displacement is only 0.05% when themaximum displacement is increased by 20%, from 15 to 18 intervals, corresponding to 15 minutes,
while the number of displaced flights decreased from 139,689 to 139,321. Furthermore, we observethat the resulting total displacement values are similar between the two analyzed cases. However,
the airports are affected differently depending on their importance profiles. For instance, in theschedules with maximum displacement of 15 intervals, which is equivalent to 75 minutes, when thedisplacements are weighted by the betweenness centrality measures, the airport with the highest
centrality value receives only 6% of the total actual displacement, whereas when the displacements
are not weighted, this airport is allocated 32% of the total actual displacement. These results shedlights on the decision making process regarding the adjustments to the initial slot allocations. If theTRISTAN XI Symposium

Original abstract submittal

M. Keskin, K. G. Zografos

4decision makers would like to prioritize some of the airports, then using airport importancecoefficients makes sure that “important” airports receive less displacement.
435,000

442000Total Weighted Displacement

7.E+07

Total Unweighted Displacement441950

7.E+07441850

7.E+07
7.E+07441800

7.E+07441750

7.E+07441700Total Unweighted Displacement

Total Weighted Displacement

441900
7.E+07

Total Unweighted Displacement

8.E+07434,950434,900
434,850434,800
434,750434,700
434,650

7.E+07441650

7.E+07
7.E+0744160015161718192021222324434,600
15161718

Maximum Displacement

25

Maximum Displacementa. Using betweenness centrality measures

b. Not using the centrality coefficients

Figure 1 – Trade-offs between maximum and total displacements
Work under way includes i) incorporating airport importance using the IATA connectivity indicesand analyzing the trade-off between total and maximum displacements through Model 1, and ii)
analyzing the trade-off between slot allocation efficiency and fairness both at airport and airline level
through solution of Model 2 using both importance measures proposed.

AcknowledgementsThis work has been supported by the Engineering and Physical Sciences Research Council (EPSRC)
through the Programme Grant EP/M020258/1. The opinions expressed in this article reflect theauthors’ views.

References
Benlic, U. 2018. Heuristic search for allocation of slots at network level. Transportation ResearchPart C: Emerging Technologies, 86, pp. 488-509.
Ehrgott, M., 2005. Multicriteria optimization (Vol. 491) Springer Science & Business Media.
Guimera, R., Mossa, S., Turtschi, A., & Amaral, L.N., 2005. The worldwide air transportation
network: Anomalous centrality, community structure, and cities’ global roles. Proceedings of theNational Academy of Sciences, 102 (22) pp. 7794-7799.
International Air Transport Association (IATA), 2021. Worldwide Airport Slot Guidelines (WASG).
https://www.iata.org/en/policy/slots/slot-guidelines, accessed 7 December 2021.
International Air Transport Association (IATA), 2020. Measuring the connections that drive
economicgrowth.
https://www.iata.org/en/iata-repository/publications/economic-reports/airconnectivity-measuring-the-connections-that-drive-economic-growth/, accessed 7 December 2021.
Pellegrini, P., Bolić, T., Castelli, L., & Pesenti, R. 2017. SOSTA: An effective model for theSimultaneous Optimisation of airport SloT Allocation. Transportation Research Part E: Logistics
and Transportation Review, 99, pp. 34-53.
Ribeiro, N. A., Jacquillat, A., Antunes, A. P., Odoni, A. R., & Pita, J. P., 2018. An optimization
approach for airport slot allocation under IATA guidelines. Transportation Research Part B:Methodological, 112, pp. 132-156.
Zografos, K.G., Salouras, Y. & Madas, M.A., 2012. Dealing with the efficient allocation of scarce
resources at congested airports. Transportation Research Part C: Emerging Technologies, 21 (1)pp. 244-256.

TRISTAN XI Symposium

Original abstract submittal