Increasing airport capacity utilisation through optimum slot scheduling: review of current developments and identification of future needs

The slot scheduling problem aims to optimally assign (few months before operations) requested movements (requests for landing or take-off) at an airport to coordination time intervals within a given scheduling period. Typical constraints for the slot scheduling problem emerge from the declared airport capacity, the priorities arising from the existing slot allocation framework (e.g., historical slot holdings), the operational requirements of airlines and airports (e.g., turnaround time, ground handling, flight connectivity), ATFM constraints (e.g., airspace sectors’ capacity), as well as the criteria used for scheduling slot requests. In existing literature, the slot scheduling problem has been studied in the context of either a single airport (Koesters 2007b; Zografos et al. 2012) or a network of airports (Castelli et al. 2011, 2012; Corolli et al. 2014). Airport capacity is modelled either as a deterministic (Zografos et al. 2012) or a stochastic parameter (Corolli et al. 2014).

A primary criterion of the slot scheduling problem (Koesters 2007b; Zografos et al. 2012; Castelli et al. 2011, 2012; Corolli et al. 2014) is the minimisation of a delay-based cost function. This can be expressed either in the form of typical operational delay or the “schedule delay” concept (Swaroop et al. 2012). Operational delay is usually expressed in terms of the expected arrival/departure delays and total passenger delays. “Schedule delay” is a distance-based measure expressing the difference between requested and allocated slot times and is used as a proxy of the value assigned to a given time interval (slot time) by the airlines. Koesters (2007b) developed a deterministic approach to model the initial slot allocation process and calculated schedule delays for various declared capacity and demand levels.

On top of allocation efficiency considerations (usually expressed by delay measures), fairness and equity, access and competition, as well as environmental objectives have been also proposed by researchers (Cohen and Odoni 1985; Andreatta and Lulli 2009; Ranieri et al. 2013). Such objectives aim to allocate capacity among several classes of users of congested airports by maximising some type of a social welfare function taking into account policy or social considerations (e.g., user’s ability-to-pay principle, non-discriminatory allocation practices, access to small communities). In order to maximise social benefits, “socially desirable” criteria are proposed: (i) number of passengers served by the resulting schedule in order to ensure sufficient utilisation of resources, (ii) number of airports or cities served to safeguard connectivity to small communities, (iii) number of slots (including grandfathered) reserved for established airlines to avoid drastic changes at the expense of schedule feasibility and viability, (iv) number of slots allocated to new entrants to ensure equity and a level playing field for all competing airlines and (v) total or average noise exposure or emissions at an airport.

Depending on the geographical scope of the slot scheduling problem, two basic model categories are encountered: (i) single-airport models and (ii) airport network models in which slots are simultaneously allocated at a network of airports.

A slot request issued by an airline usually involves a specific coordination interval for a series of days ranging throughout the scheduling period (e.g., 08:00 AM, every Monday). The single-airport slot scheduling problem aims to allocate series of airport slots (in specific priority classes) to coordination time intervals within a given scheduling period under airport capacity and airports’/airlines’ operational constraints. It belongs to the category of resource-constrained scheduling problems where the arrival/departure slot requests constitute the jobs to be processed by a single constrained resource type, i.e., the airport, over the entire planning horizon. The airport capacity represents the available resource units. For a unified notation and classification scheme of resource-constrained project scheduling problems, the reader can also refer to Brucker et al. (1999).

Based on the formulation of the general resource-constrained scheduling problem of Pritsker et al. (1969), Zografos et al. (2012) formulated the single-airport slot scheduling problem as an integer linear, deterministic scheduling model. The problem is defined for a set of coordination time intervals \(T=\left\{ {0,\ldots ,n-1} \right\} \) defined per day \(\delta \in D\) (the set of calendar days for the scheduling period) and the set of requested (series of) movements M. Each movement \(m\in M\) is associated with a series of slots over the entire planning horizon, modelled through parameters \(a_{m}^{\delta }\), which take value one if movement m operates on day \(\delta \in D\), and zero otherwise. A capacity constraint \(c\in C\) is defined by the airport capacity values \(u_{c}^{\delta t} \) defined for a time period of fixed duration (e.g., 15 min) starting at time interval t and day \(\delta \). Thus, for a specified start time s, \(T_{c}^{s} =\left\{ {t\in T|s\le t<s+t_{c} } \right\} \) defines the set of consecutive coordination time intervals over which the constraint is active. Stated otherwise, the constraint ensures that the total number of movements allocated to time intervals in \(T_{c}^{s} \) should not exceed \(u_{c}^{\delta s} \) for any s such that \(0\le s\le n-t_c \). Moreover, capacity constraints may be modelled separately for arrivals and departures through parameters (\(b_{mc} )\), being equal to one if the movement is an arrival/departure and the constraint applies to arrivals/departures only, and zero otherwise. In addition to the capacity constraints, the model proposed by Zografos et al. (2012) incorporates the precedence constraint imposed through minimum turnaround time \(t_{ad} \ge 0\) for each pair of movements \((m_a ,m_d )\), \(m_a ,m_d \in M\), such that \(m_{a} \) is the arrival that corresponds to departure \(m_{d} \). The cost of allocating movement \(m\in M\) to coordination time interval \(t\in T\) is \(f_{m}^{t} \ge 0\). The latter is modelled as \(\left| {t-t_{m} } \right| \), with \(t_{m} \) expressing the time interval originally requested for m. An indicative formulation (Zografos et al. 2012) of the single-airport slot allocation problem is given by (1)–(4), where the allocation of movements (m) to time intervals (t) is specified through binary decision variables \(\left( {x_m^t } \right) \), which take value one if movement m is allocated to interval t, and zero otherwise. The objective function (1) minimises the total absolute difference between the requested and allocated time interval (i.e., “schedule delay”). Expression (2) ensures that every movement is allocated to a single time interval, while (3) specifies that the allocation of movement to a certain time interval must satisfy the corresponding capacity constraints. The turnaround time constraints (4) resemble those proposed by Christofides et al. (1987) in the context of project scheduling and apply to requests for which both an arrival and a departure slot time have been requested. These constraints enforce the obvious restriction that an arrival must be separated from a departure by at least a specified number of coordination time intervals, expressing the aircraft turnaround time. The number of time intervals usually depends on the aircraft type, accounting for the fact that larger aircraft require larger turnaround (service) times. Although constraint (4) involves a large number of inequalities, the emerging formulation leads to strong linear relaxations.

The single-airport slot allocation problem falls into the category of scheduling problems with time-dependent resource constraints, a generalised version of the resource-constrained project scheduling problem (Brucker et al. 1999) known to be NP-hard (Garey and Johnson 1979). Consequently, it is rather unlikely to find a solution algorithm with polynomial complexity. Zografos et al. (2012) proposed a heuristic algorithm for the scheduling problem at hand, in which slots are allocated hierarchically for each priority class. This approach is aligned with IATA’s fundamental requirement giving the ultimate priority to the satisfaction of slot requests of airlines having “grandfathered rights”. After solving the proposed model for slot requests pertaining to a given priority class, capacity constraints are updated accordingly, and the model is solved for slot requests of the subsequent priority class. The linear relaxation of a restricted version of the problem is solved with capacity constraints added iteratively only as needed. If the optimal solution is fractional, then reduce-and-split cuts (Andersen et al. 2005) are generated and included in the model. If the solution remains fractional, then variable fixing is performed by identifying the variable with the highest fractional value and fixing its value to one. Subsequently, the linear relaxation is solved again, and the process iterates until an integer solution is found. The proposed slot allocation model was applied at three international airports in Greece. The largest problem instance involved 1087 slot requests (on a daily basis) for a planning horizon of 197 scheduling days, characterised as a medium-sized problem. For problem instances in which the corresponding linear relaxation of the proposed formulation was strong, the solution time ranged from a few seconds up to 3 min. For instances in which additional cutting planes constraints were used to solve the integer program, the solution time ranged up to four and a half hours, which is, however, clearly compatible with the strategic planning context (i.e., few months before operation) of the respective slot allocation problem.

Jacquillat and Odoni (2015) proposed an integrated approach that jointly optimises the flight scheduling at the strategic level and the utilisation of airport capacity at the tactical level subject to capacity and delay reduction constraints. The proposed single-airport scheduling model reflects mostly the US scheduling practice, and it is based on the strategic network-based scheduling model of Pyrgiotis and Odoni (2015)) discussed in the subsequent section. It considers a two-stage lexicographic objective that aims to determine a schedule minimising maximum displacement while simultaneously keeping total (aggregate) displacement at the lowest possible levels. The authors demonstrated the model at John F. Kennedy International (JFK) airport and showed that a moderate rescheduling (no more than 15–30 min per flight) of 75–90 % of the flights can drastically reduce congestion at busy U.S. airports.

A strong criticism of the existing slot allocation practice is that it does not explicitly consider the strong complementarity of slots assigned to a single flight at origin and destination airports. This inefficiency of the existing slot allocation practice has been identified and explored by various studies, which implicitly or explicitly address the allocation of slots at a network of interconnected airports simultaneously taking into account slot interdependencies at departure and arrival airports. The simultaneous allocation of slots at different interconnected airports gives rise to a slot scheduling problem at a network of airports, where in addition to constraints applying to the single airport scheduling problem, any allotment of a pair of slots to a flight should be compatible with the associated flight time.

Castelli et al. (2012) proposed a mathematical model for the slot scheduling problem at network level, which aims to minimise the airlines’ shift costs (an alternative notion to schedule delay) due to the deviation of allocated slots from the commercially and operationally ideal pair of departure/arrival slots (called ideal slots) for every flight. Apart from assigning departure and arrival slots to each flight, the proposed model aims at determining the corresponding flight route. The proposed model is based on the mathematical formulation proposed in Bertsimas et al. (2011) for the ATFM problem and aims to allocate a departure and an arrival slot for each flight, while simultaneously determining the corresponding route between departure and arrival airports. Each route involves a sequence of neighbouring airspace sectors connecting the origin and destination airports. By incorporating the route selection problem into the slot scheduling problem, an estimate for the flight time is made (which is set equal to the travel time of the selected route). This enables the assessment of compatibility between departure and arrival slots allocated for each flight. Any deviation from ideal slots implies cost (“shift cost”) for the airlines associated to the operation of the corresponding flight. Moreover, when the route that a flight must follow from an origin to a destination airport is longer than the desired one, additional shift costs are involved. The following notation is pertinent: A is the set of airlines, F is the set of flights, \(F_a \subseteq F\) is the set of flights of airline \(\alpha \), and T is the set of time periods. S denotes the set of (en route) sectors, \(S^{f}\subseteq S\cup K\) denotes the set of sectors that can be traversed by flight f, including the origin and destination airports, \(L_i^{f} \) the set of sector i’s subsequent sectors \((i\in S^{f})\) and \(P_i^{f} \) the set of sector i’s preceding sectors \((i\in S^{f})\) for flight f. Moreover, let K denote the set of airports, \(K_{k,t} \) the capacity of airport k at time t and \(G_{j,t}^{a} \) the number of slots on which airline a has Grandfather Rights (GFR) at airport j at time t. Each flight (f) is associated to a pair of origin and destination airports \((\hbox {orig}_{f}, \mathrm{dest}_{f} )\) and the corresponding ideal departure and arrival slots \((d_{f}, a_{f} )\) specified by the relevant airline. Moreover, it is assumed that each flight is associated to a time interval of acceptable departure times for the origin airport and a relevant time interval of acceptable arrival times at the destination airport denoted by \(T_{\mathrm{orig}_{f} }^f =[T_{-\mathrm{orig}_f }^f,\bar{T}_{\mathrm{orig}_f}^f]\) and \(T_{\mathrm{dest}_f }^f =[T_{-\mathrm{dest}_f }^f,\bar{T}_{\mathrm{dest}_f}^f]\), respectively. In this work, a flight route is defined by a sequence of adjacent airspace sectors. The number of time units that flight f needs to traverse sector j before entering sector \(j{'}\) is denoted by \(l_{fjj'} \) and constitutes a major input for the associated routing problem. In any case, the total duration of a flight (f) should not exceed a threshold value denoted by \(end_f \). Finally, deviating \(\hat{t}\) time units from the ideal arrival slot of flight f involves a cost \((c^{f}(\hat{t}))\), while the cost associated with an additional flight duration of \(\hat{d} \) time units as compared to the ideal one for flight f is denoted by \((c_\mathrm{dur}^f (\hat{d}))\).

A key feature in the proposed mathematical formulation is related to the decision variables used for keeping track of the presence of each flight within airspace sectors over time. A set of variables \((w_{j,t}^f )\) are defined by (5):If variable \((w_{j,t}^f )\) takes value 1, then the following cases may apply: (i) if j is an airspace sector, then flight (f) has already entered it (however, it does not mean that the flight is still in this sector at time (t)), (ii) if j is the destination airport, then the flight has already arrived at that airport by time (t), and (iii) if j is the origin airport, then the flight has already departed from that airport. Thus, a flight (f) enters an airspace sector (j) at time (t) when the \((w_{j,t}^f -w_{j,t-1}^f )\) is equal to one. The proposed mathematical model is given by (6)–(17) below (Castelli et al. 2012). where The objective function (6) consists of the sum of two parts: (i) the total cost of arrival schedule delay at the destination airports and (ii) the cost of flight time deviation from the ideal flight time. Note that \(\mathop \sum \nolimits _{t\in T_{\mathrm{dest}_f }^f } t\left( {w_{\mathrm{dest}_f ,t}^f -w_{\mathrm{dest}_f ,t-1}^f } \right) \) in objective function (18) expresses the arrival time of flight (f) at destination airport, while \(\mathop \sum \nolimits _{t\in T_{\mathrm{orig}_f }^f } t\left( {w_{\mathrm{orig}_f ,t}^f -w_{\mathrm{orig}_f ,t-1}^f } \right) \) expresses the corresponding departure time from the origin airport. Thus, the second part of the objective function subtracts from the estimated flight duration (arrival minus departure time) the corresponding ideal flight duration (ideal arrival minus ideal departure time). Constraint (7) implies that each flight must leave the origin airport and arrive at destination airport. Constraint (8) states that any flight (f) cannot depart from the origin airport before the maximum acceptable time \(T_{-\mathrm{orig}_f }^f\). Constraint (9) requires that the number of flights that arrive at or depart from an airport (k) at time interval (t) should not exceed the capacity of the airport \((K_{k,t} )\) for the specific time interval. Constraint (10) imposes the relevant Grandfather Rights (GFR) constraint. Constraints (11)–(15) define the route selection problem for each flight. Constraint (11) states that any flight entering a sector (j) should traverse the sector and enter a neighbouring one (i) after at least \(l_{fji} \) time units. Constraint (12) implies that any flight entering a sector (j) should have crossed a preceding sector (i) within at least \(l_{fij} \) time units. Constraint (13) states that any transition between sectors or between sectors and airports must have been completed by the latest arrival time of the flight. Constraint (14) implies that a route for each flight (f) may traverse a sector (j) at most once. Constraint (15) states that the total duration of a flight should not exceed a maximum value \((end_f )\). Finally, constraint (16) implies that if a flight has arrived at a sector (j) by time t \((w_{j,t}^f =1)\), then \(w_{j,{t'}}^{f}=1 \hbox {for any} \;{t'}>t\).

The model is further enhanced with a set of valid inequalities proposed in Bertsimas et al. (2011) in order to strengthen its linear relaxation. The proposed slot scheduling model belongs to the category of resource-constrained scheduling problems, and thus, it is rather unlikely to find a solution algorithm with polynomial computational complexity. Using an IP solver, it was proven feasible to solve at a reasonable amount of time (30 min of CPU time) only randomly generated instances with 2200 flights at a network of 60 airports over a time horizon of up to 5 h. Given that the time horizon of the real-life slot scheduling problem for a network of airports spans over a time horizon of several months, the proposed model would lead to huge integer programming problems that cannot be treated by an IP solver. In a subsequent research work, the authors proposed an ant colony optimisation algorithm able to handle real-life instances of the problem (Castelli et al. 2011). A line of criticism in the model described above is that it can be applied for scheduling a set of flights only for a given day. It does not take into account explicitly the allocation of slots for a given flight over the entire scheduling season (e.g., around six months). In order to apply the proposed model in line with the current slot allocation framework, it is necessary to formulate and solve the model for the entire time horizon of the real-life problem. However, the proposed model does not account for series of slots, and therefore, slots allocated to the same movement over the time horizon may differ from day to day. Moreover, this model includes capacity constraints for the total number of movements per time unit without accounting for capacity constraints associated to arrivals or departures only. Finally, the model does not address the rolling capacity constraints applied at schedule coordinated airports.

Corolli et al. (2014) enriched the slot scheduling problem at network level by considering explicitly the inherent uncertainty of airport capacity. They argued that incorporating the uncertainty of actual airport capacity in the slot allocation model throughout the planning horizon may lead to substantial benefits on the basis of operational delays. In particular, Corolli et al. (2014) extended the single-airport model proposed by Zografos et al. (2012) for a network of interconnected airports, treating airport capacity as time-dependent and stochastic. A two-stage stochastic programming formulation with recourse was developed with the aim to minimise the sum of schedule delays and expected operational delays, taking into account airport capacity, flight connectivity and turnaround time constraints. In this model, the flight time between any pair of interconnected airports is assumed fixed and known in advance. By allocating a slot at the origin/destination airport, the corresponding slot at the associated destination/origin airport is fixed accordingly.

At the first stage of the proposed stochastic model, flights are scheduled by allocating slots to origin and destination airports. Given an assignment of slots to the associated requested movements, the second stage of the model aims to estimate the corresponding expected operational delay over all possible airport capacity realisations. For each possible realisation of airport capacity (modelled as random variable), Corolli et al. (2014) approximate operational delays by the total number of delayed movements (i.e., movements whose actual landing or take-off time deviates from scheduled). In particular, two alternative ways for approximating operational delays are proposed. In the first approach, the delayed movements per coordination time interval for a given airport are calculated as the difference between the number of movements requesting a slot in that interval and the corresponding airport capacity. However, delayed movements in one time interval are summed up to the allocated movements for the subsequent time interval. In order to incorporate the downstream effects of delays, the second (more accurate) approach updates the demand of the next time period with the number of flights not served due to capacity constraints in the current time period. The solution of the proposed stochastic model was achieved through the sample average approximation method. The model was applied at different interconnected airport networks including 5–10 airports. Slot requests for four different days were considered resulting to problem instances ranging from 6520 up to 9267 flights. The solution time ranged from 1.7 to almost 40 h. Although the resulting computational times seem viable within the relevant strategic decision-making framework, solving the slot scheduling problems for a larger airport network and real-world time horizon (i.e., scheduling season) requires further investigation.

Complementing the previous work on slot scheduling models at network level, the work of Pyrgiotis and Odoni (2015)) introduces a new criterion on the slot scheduling problem that expresses the maximum displacement associated to a schedule (i.e., schedule delay). Pyrgiotis and Odoni (2015) demonstrated a demand smoothing (or flight rescheduling) model integrated with a network queuing model to estimate both local and system-wide effects of introducing scheduling limits (e.g., capacity caps) at busy airports. The demand smoothing model, formulated as an integer program, starts from a given (initial) schedule based on airlines’ preferences and produces a feasible modified schedule complying with the scheduling limits applied at an airport without cancelling any flights, while simultaneously respecting all aircraft and passenger connections (i.e., all aircraft and passengers should be able to fly their original routes/itineraries). The proposed model generates a new schedule for a single day of network operations that lexicographically minimises the maximum and total displacement from the initial schedule. Unlike the model proposed by Castelli et al. (2012), the proposed model does not take into account explicitly the flight time feasibility. Instead, the model assumes that the initial flight schedule announced by airlines is feasible with respect to flight time. Based on this assumption and forcing the displacement for a departure to be equal to the displacement for the corresponding arrival, the flight time feasibility is only implicitly imposed. Although this assumption alleviates the flight time feasibility constraint from the network-based slot allocation problem, it unnecessarily excludes solutions (schedules) that might be feasible in terms of flight time, albeit with uneven departure and arrival displacement. Another limitation of the model is that it addresses the airport scheduling problem only for a single day, and hence, it cannot be directly applied for allocating slots throughout the scheduling season. The model was applied for assessing the impact of the proposed flight rescheduling on queuing delays for one of the busiest days in 2007 of Newark Liberty International airport (1910 movements). Results of the relevant computational tests demonstrated substantial reduction in queuing delays.

All models discussed above aim at supporting the coherent initial allocation of slots to airlines accommodating their flights within a network of interconnected airports. Therefore, their applicability in the existing slot allocation framework is limited to the initial allocation of slots to airlines without accounting for the possibility of slot exchanges between airlines at a post-allocation stage. Along these lines, Pellegrini et al. (2012) introduced a hybrid model based on the model previously proposed by Castelli et al. (2012). The model proposed by Pellegrini et al. (2012) aims to: (i) support the exchange of slots initially allocated to airlines and (ii) allocate slots to new requests issued by airlines at the secondary phase of the slot allocation process. The work presented in Pellegrini et al. (2012) is based on the assumption that the existing bilateral slot exchange framework is replaced by a market framework operating as a combinatorial exchange mechanism (Sandholm et al. 2002). The implementation of the proposed market framework is facilitated by a deterministic slot scheduling model. The proposed model is formulated as a linear integer program aiming to allocate slots at both origin and destination airports of each flight by minimising shift costs (another term for schedule delay used in literature) on the basis of initial allocation of slots to flight requests.

The model is defined on a network of interconnected airports (K) operating a set of flights (F) of a set of airlines (A) through airspace partitioned to a set of sectors (S). The notion of slot is extended for the airspace sectors, expressing a time interval in which a sector can be entered by a flight. Instead of allocating departure, arrival and airspace sector slots to flight requests, as in the model proposed for the initial slot allocation phase, the model for the secondary phase assigns a bundle of slots defining a flight route to each flight request. In this context, any feasible solution to the model involves a bundle of slots assigned to the departure and arrival airports along with the airspace sectors defining a feasible route between the given pair of airports. The objective of the proposed model is to assign a feasible route to each of the flights so that the total shift cost for the airlines is minimised subject to: (i) grandfather rights constraints, (ii) capacity constraints for airports and airspace sectors, (iii) neutrality of the revenue scheme (i.e., total amount paid or received by airlines equals zero) and (iv) airline-specific maximum acceptable value of total cost for airlines (i.e., total shift cost plus the payment made by the airline on the basis of the trading mechanism). The model was tested on a small-size problem instance of 20 airlines with approximately 3000 slots at a network of 40 airports and 200 airspace sectors for a 5-h time horizon. The test problems were solved to optimality by an IP solver. The authors argue that the application of the proposed model at the secondary stage of slot allocation may lead to the reduction in airlines cost as compared to the current practice.