SOSTA: An effective model for the Simultaneous Optimisation of airport SloT Allocation

https://doi.org/10.1016/j.tre.2016.12.006Get rights and content

Highlights

  • We propose SOSTA: Simultaneous Optimisation of the airport SloT Allocation.

  • It is an integer programming model that optimally allocates slots at several airports.

  • SOSTA applies all the regulations and best practices currently in use in Europe.

  • SOSTA links flights’ departure and arrival slots and considers aircraft rotations.

  • We validate SOSTA on the real slot requests in the busiest day of 2013.

Abstract

In this paper, we propose SOSTA, an integer linear programming model for optimisation of the airport slot allocation process on the European scale. The main contribution of SOSTA is the simultaneous allocation of slots at all Europan airports, while applying the existing regulation and practices. Additionally, SOSTA considers aircraft rotations through the turnaround time constraints, which is another novel contribution. In an experimental analysis based on real data, we show the benefits of the simultaneous allocation, and the flexibility and capabilities of SOSTA, along with the extremely good computational performance.

Introduction

The continuous growth of air traffic combined with the constrained airport capacity increase generates imbalances between traffic demand and available capacity, leading to significant delays and associated costs. For instance, in Europe in 2014 the traffic has increased by 2.5% in terms of flight hours controlled with respect to 2013, but the estimated cost of en-route and airport Air Traffic Flow Management delay has increased by 7.6% (EUROCONTROL. PRR 2014, 2015). Since airports often represent bottlenecks in the air transport network, initiatives to increase their capacity are always sought. Infrastructural interventions (such as building new runways) are rarely possible, mainly for economic and environmental concerns. Currently, each major airport may consider the following options to mitigate its congestion: either managing the demand at the strategic level or adjusting the allocation of airport resources to flights at the tactical level. The rationale of the former choice is to smooth peaks of traffic demand by moving arrival and/or departure requests to times of the day with a lower demand for the use of the airport infrastructure. Demand management is usually achieved either through the enforcement of administrative measures or through the use of economic instruments such as congestion pricing or auction mechanisms (see, e.g., Perret, 2015). The rationale of the latter choice is to adapt the use of the infrastructure to improve the utilisation of the airport capacity. For example, dynamic change of runway configurations or the selection of the arrival and departure service rates can be used to that end (Jacquillat and Odoni, 2015). This paper focuses on the administrative-based demand management procedure at the strategic level. It proposes Simultaneous Optimisation of the airport SloT Allocation (SOSTA), a decision support tool capable of optimally coordinating the airports’ capacity management at the European level.

Nowadays the capacity of many airports worldwide is managed though airport slots, in accordance with IATA’s (International Air Transport Association) Worldwide Slot Guidelines (IATA, 2015). A slot is defined as “a permission given by a coordinator for a planned operation to use the full range of airport infrastructure necessary to arrive or depart at a Level 3 airport on a specific date and time”. A Level 3 (or coordinated) airport is an airport “where capacity providers have not developed sufficient infrastructure, or where governments have imposed conditions that make it impossible to meet demand. A coordinator is appointed to allocate slots to airspace users and other aircraft operators using or planning to use the airport as a means of managing the declared capacity.” In addition to Level 3 airports, flight schedules are facilitated at Level 2 (or facilitated) airports, which are those “where there is potential for congestion during some periods of the day, week, or season which can be resolved by schedule adjustments mutually agreed between the airspace users and facilitators. A facilitator is appointed to facilitate the planned operations of airlines using or planning to use the airport” (IATA, 2015). In Europe, there is one coordinator per country, meaning that a unique national authority manages the primary slot allocation of each Level 3, and schedule facilitation at Level 2 airports of this country (see, http://www.euaca.org). The allocation and schedule facilitation is always performed on an airport by airport basis, though. In Europe there are as many as 107 airports designated as Level 3 and another 79 as Level 2, representing 60% and 61% of all Level 3 and Level 2 airports in the world, respectively (see the Appendix 11.2 of IATA (2015)).

In the European Union, the IATA’s Worldwide Slot Guidelines are implemented by Council Regulation (EEC) No 95/93 “on common rules for the allocation of slots at Community airport” and its subsequent amendments: EC Regulations No 894/2002, No 1554/2003, No 793/2004, and No 545/2009. The slot allocation process in Europe consists of two main steps: primary slot allocation, and slot exchanges and transfers. The primary slot allocation begins about five months before the start of the season (the winter season starts on the last Sunday of October, the summer season on the last Sunday of March), when the airspace users (e.g., airlines) submit formal requests for slots (and schedule facilitation) to airport coordinators. The requests are submitted in a standardised format, the Standard Schedule Information Manual (SSIM) format (IATA, 2015), containing the flight number, time period of operations (from-to within a season), day of the week, route and arrival or departure time. Airspace users can also indicate the acceptable displacement around the requested slot time. However, “Airport slots are not route, aircraft or flight number specific and may be changed by an airline from one route or type of service to another. Such changes are subject to final confirmation by the coordinator” (IATA, 2015).

At Level 2 airports, when mismatches between capacity and demand exist, an airspace user might be asked to move the scheduled time of an operation, for the minimum necessary amount of time, on a voluntary basis. At the Level 3 airports, the coordinators endeavour to satisfy the requests, under the existing capacity constraints, respecting historical precedence, the so-called grandfather rights. An airspace user obtains the grandfather right on a slot, if it operated the corresponding slot at least 80% of the times in the preceding equivalent season. In such a case we refer to this airspace user as an incumbent. In addition, the incumbent is allowed to slightly modify the time (w.r.t. the preceding equivalent season) of any of its grandfather slots.

Once all grandfather rights from incumbent airspace users are granted, fifty percent of the remaining slots are allocated to new entrant airspace users, and the rest to other airspace users. A new entrant is defined as: “an airline requesting a series of slots1 at an airport on any day where, if the airline’s request were accepted it would hold fewer than five slots at the airport on that day” (IATA, 2015). IATA slot conference takes place after the primary allocations are established, to facilitate negotiations of slot exchanges between airspace users. The aim of the conference is to diminish as much as possible, through negotiations, the difference between the requested and assigned slot times, which is referred to as schedule displacement (see, e.g., Pyrgiotis and Odoni, 2014). For example, from the conversations with a coordinator of one of the congested airports, at the beginning of the process, about 40% of requests could be granted as requested, while other requests had an average of 25 min of difference. The subsequent IATA conference negotiations brought the satisfied requests to about 85% with six minutes of average difference for non-satisfied requests. By the start of the season, 97% of requests were satisfied. This shows how the definition of airspace users’ schedules is a non-trivial exercise at global level. In fact, the slots an airspace user receives are the outcome of several local allocations and may include different schedule displacements. As such, the received slots may be impracticable with respect to, say, the fleet rotation constraints, or undesirable in terms of departing/arriving times for business purposes. Decisions on which schedule displacements to accept, and their magnitude, may not be straightforward as airspace users may have to deal with many coordinators at the same time, and this may require a significant effort especially from airspace users that fly to/from many Level 3 airports.

The European Commission has financed several studies in the last years to assess the implementation of EC Regulation 95/93 and its amendments (Coopers and Lybrand, 1995, NERA, 2004, Mott MacDonald, 2006, SDG, 2011). These studies acknowledge the inefficient use of capacity at some airports, highlight difficulties that new entrants face to obtain slots, and identify significant differences in coordinators’ operations. In this context, Madas and Zografos (2013) propose possible changes in the slot allocation process, including the introduction of economic instruments (e.g., congestion pricing, secondary trading, and auctioning). The design of economic instruments to enhance the efficiency of the slot allocation process has been under investigation for decades as in Rassenti et al. (1982) who proposed to allocate airport slots through a sealed-bid combinatorial auction. Several other auction-based models have been designed and evaluated as in Maldom, 2003, Li et al., 2007, Ball et al., 2007. Recently, ascending-bid multi unit auctions to allocate slots at multiple airports (Sheng et al., 2015) was published. Slot trading has also been extensively studied as, e.g., in Verhoef (2010), or in Pellegrini et al., 2012b, Fukui, 2014 for the European context, and in Kleit and Kobayashi, 1996, Fukui, 2010 who analyse the impacts of slot trading in terms of competitiveness and market entry possibilities in the US. Finally, congestion pricing as a tool to manage airport demand has been proposed by several authors such as Brueckner, 2009, Basso and Zhang, 2010, Czerny, 2010, Czerny and Zhang, 2011.

Airport slots also play a pivotal role in shaping airline competition and social welfare. In fact, the possibility for airlines to operate in specific markets may be limited by the availability of slots. These limitations may prevent airlines to expand their international and intercontinental markets and therefore restrict competition, also in liberalised air transportation markets (Li et al., 2010, Adler et al., 2014). Hence, the economic and social impact of airport slot allocation is twofold. On the one hand, the attractiveness of an airport is driven by the portfolio of its destinations, and this affects airport revenues as well as income, employment and tourism effects for the local economy (see, e.g., Gillen and Hinsch, 2001). On the other hand, slot availability affects airlines scheduling decisions, which in turn promote economic growth by enhancing the connectivity of a region with other parts of the world, typically in deregulated markets where carriers develop hub-and-spoke networks (Adler, 2001, Adler, 2005) or minimise social costs in subsided markets to protect remote communities (see, e.g., Pita et al., 2014 for the case of Norway).

This large body of work has contributed to major insights on the economic performance of demand management alternatives. However, the previous research typically considers simplified operational settings and does not capture the complexity and variability of airport operations and of the networks of flights that airspace users operate. Furthermore, major European legacy airspace users strongly oppose any relaxation of the grandfather rights’ rule since they claim that it is this very same rule that makes their business sustainable, as it protects their most profitable slots at their main home hubs, and provides stability so that airspace users can make long-term investments. In fact, for airspace users offering a hub-and-spoke network to their passengers, the elimination of grandfather rights could be affordable only in case of monetary compensations (see, e.g., Castelli et al., 2012).

This motivates the need to enhance the current administrative framework and to make it more efficient. As already pointed out by Zografos et al. (2012), the current slot allocation process is highly inefficient because the management of its complexity (the allocation needs to comply with numerous criteria and rules) is still empirical. Similar conclusions were also provided by Koesters (2007) who analysed the relationship between demand for slots and displacement. To mitigate these inefficiencies, Zografos et al. (2012) formulate an optimisation model that implements EU regulations (and IATA guidelines) and solves the slot allocation for a single airport by minimising the total displacement. Their model is applied on real data from three different Greek airports, and the results show that the schedule displacement can be reduced in a range from 14% to 95%.

In this paper, we introduce SOSTA, a model that optimally and simultaneously allocates the airport slots/requests at all Level 2 and Level 3 airports in Europe. SOSTA draws upon the integer programming model by Zografos et al. (2012), but extends it from one airport to the network of airports. The model takes into account different types of airport capacity constraints and minimises the cost of deviations between what is requested (by the user) and what is allocated (by the coordinator/facilitator). A further novel contribution of the network perspective implemented in SOSTA lies in explicitly linking departure and arrival slots (when both are needed) of each flight and considering aircraft rotations through the introduction of turnaround time constraints. SOSTA can handle all European airport slots/facilitation requests during a busy day, achieving the optimality of the final allocation in reasonable time.

As recently highlighted in the review paper by Zografos et al. (2016), the slot allocation problem was studied in the context of a network of airports by Castelli et al., 2012, Pellegrini et al., 2012a, Corolli et al., 2014. In particular, Castelli et al. (2012) introduce a much simpler yet more computationally cumbersome model than the one presented in this paper. On the one hand, the problem modelling is too simplified as they do not, for instance, distinguish between interval and hourly capacity constraints (see Section 2.2) or consider turnarounds (Section 2.6). On the other hand, sector capacities are taken into account, which is perhaps a level of detail not needed at the strategic level. In addition, as they adapt the Bertsimas et al. (2011) formulation, which is tailored for the air traffic flow management problem and is unable to deal with very large air traffic samples, the size of the instances that can be solved effectively is significantly smaller than in the current paper (2,200 vs 32,000 requests, see Section 4). Larger instances are solved through a meta-heuristic approach in Pellegrini et al. (2012a), which, however, cannot prove the optimality of the solutions returned. A simultaneous slot allocation is also proposed by Corolli et al. (2014) who extend the Zografos et al. (2012) model by introducing a stochastic programming approach to take into consideration the uncertainty on the capacity availability. However, their model does not capture all the important subtleties of the European allocation process in terms of, for instance, capacity constraints (see again Section 2.2) or presence of grandfather rights, which are ignored. Nevertheless, a relevant feature of their model is the opportunity to perform the slot allocation (a strategic decision) by already encompassing the effects (in terms of estimated delay) of possible capacity reductions that arise at the tactical level only, i.e., on the day of operations. This is achieved through a two-stage stochastic optimisation, the computational burden of which limits the size of manageable instances up to just 9,000 requests.

SOSTA overcomes some limitations of these papers for the benefit of both airport coordinators and airspace users. In fact, SOSTA could ideally be used as a tool to partially replace and shorten the current (lengthy) slot allocation process where users need to interact several times with coordinators and often other airspace users to build and re-build their schedules, based on the accepted and rejected slot requests. Similarly, it should mitigate the use of the secondary slot exchange when, following the primary allocation, airspace users negotiate and exchange among them the allocated slots, subject to coordinators’ approval, to fine-tune their schedules.

Following the introduction of the main assumptions of the problem under investigation (Section 2) and its mathematical formulation (Section 3), we apply SOSTA on the busiest day of 2013. After presenting an overview of the available data (Section 4.1), we show that SOSTA is a valid model that enforces the rules characterising the current system: we apply it to a set of requests for which the final allocation is known and SOSTA returns the same final allocation with only a few exceptions (Section 4.2). Next, we quantify the potential improvement brought by SOSTA’s simultaneous slot allocation at all airports. In order to do so, we compare the results and behaviour of SOSTA with the results of current allocation process in the cases in which the ratio between slot requests and slot availability is greater than the current one. This situation is simulated through the reduction of the airports capacities (all airports, uniformly), to avoid adding fictitious slot requests (Section 4.3). Moreover, we assess the sensitivity of SOSTA when the maximum schedule displacement or the maximum additional block time varies (Section 4.4). Then we analyse the effects of moving from linear to quadratic cost functions (Section 4.5) and of loosening grandafther rights (Section 4.6). Finally, we propose two variants of SOSTA to take into account fairness considerations (Section 4.7). We conclude the paper in Section 5.

Section snippets

SOSTA’s key assumptions

A slot is the right to use the airport infrastructure “on a specific date and time”. As an example, the airport coordinator allocates to an airspace user a slot at 10:00 of a given day. To make the use of the infrastructure viable, the slot has a duration associated to it, for instance 10 min. This means that the airspace user has the permission to arrive (or depart) from 10:00 to 10:10. At large airports, where simultaneous operations can be performed, more than one slot can be associated to

SOSTA formulation

In this section, we formulate SOSTA as an integer linear programming model.

Computational experiments

A non trivial issue that always arises when dealing with problems concerning air traffic over the European skies is the collection of real data. Works present in the literature usually either consider just a small number of airports/sectors (e.g., Zografos et al., 2012) or generate artificial data (e.g., Bertsimas et al., 2011, Castelli et al., 2012, Corolli et al., 2014). In this section, we focus on the computational experiments carried out with the real data that were accessible to us. To

Conclusions

The current airport slot allocation process is a complex process in which optimisation is not really used. In the literature, the need for introducing an optimisation-based decision-aid tool is unanimously recognised, but an agreement on the characteristics of this tool is not reached yet.

In this paper, we propose SOSTA, an integer linear programming model to simulate the slot allocation process currently performed in Europe. Its main original features consist of capturing most of the

Acknowledgments

Contributions from Tatjana Bolić and Lorenzo Castelli to this work are part of the ACCESS project and as such are co-financed by EUROCONTROL acting on behalf of the SESAR Joint Undertaking (SJU) and the European Union as part of the SESAR Exploratory Research programme. Opinions expressed in this work reflect the authors views only. EUROCONTROL and/or the SJU shall not be considered liable for them or for any use that may be made of the information contained herein.

References (42)

  • A.N. Kleit et al.

    Market failure or market efficiency? Evidence on airport slot usage

    Res. Transp. Econ.

    (1996)
  • Z.-H. Li et al.

    Optimal route allocation in a liberalizing airline market

    Transp. Res. Part B: Methodol.

    (2010)
  • P. Pellegrini et al.

    Secondary trading of airport slots as a combinatorial exchange

    Transp. Res. Part E – Logistics Transp. Rev.

    (2012)
  • J. Pita et al.

    Socially-oriented flight scheduling and fleet assignment model with an application to Norway

    Transp. Res. Part B: Methodol.

    (2014)
  • D. Sheng et al.

    Slot auction in an airport network with demand uncertainty

    Transp. Res. Part E – Logistics Transp. Rev.

    (2015)
  • H. Van Landeghem et al.

    Reducing passenger boarding time in airplanes: a simulation based approach

    Eur. J. Oper. Res.

    (2002)
  • E.T. Verhoef

    Congestion pricing, slot sales and slot trading in aviation

    Transp. Res. Part B – Methodol.

    (2010)
  • K.G. Zografos et al.

    Dealing with the efficient allocation of scarce resources at congested airports

    Transp. Res. Part C – Emerg. Technol.

    (2012)
  • N. Adler

    Hub-spoke network choice under competition with an application to western Europe

    Transp. Sci.

    (2005)
  • Airbus Aircraft Characteristics Airport and Maintenance Planning, 2016....
  • M.O. Ball et al.

    Market-based alternatives for managing congestion at New York’s La Guardia Airport

  • Cited by (65)

    • Bi-objective airport slot scheduling considering scheduling efficiency and noise abatement

      2023, Transportation Research Part D: Transport and Environment
    • Algorithmic mechanism design for egalitarian and congestion-aware airport slot allocation

      2023, Transportation Research Part E: Logistics and Transportation Review
    View all citing articles on Scopus
    View full text