1 Introduction

Currently, the Ministry of Land, Infrastructure, and Transportation of the Republic of Korea is developing an integrated departure and arrival management system to improve the traffic conditions at the nation’s busiest airports [1]. Several scheduling algorithms are being studied to be used for this departure and arrival management system. The generalized dynamic programming method was proposed to determine the optimal solution for the runway scheduling problems [2]. Mixed Integer Linear Programming (MILP) and Receding Horizon approaches were applied to solve problems for airport surface scheduling [3, 4]. MILP was also applied to examine multiple taxi route scheduling and deterministic departure scheduling problems at runways [5, 6]. A time prediction approach using pre-departure event data at parking gates was proposed to increase airport departure demand [7]. MILP-based scheduling algorithm was used for Spot and Runway Departure Advisor (SARDA) a decision support tool for efficient departure management developed at NASA [8,9,10].

This paper describes an Extended First-Come First-Served (EFCFS) scheduling algorithm that may not find the globally optimum scheduling solutions, but has significantly lower computational costs compared with optimization-based approaches. EFCFS can solve scheduling problems that can be formulated into a node-link structure. Initially, the algorithm was developed to solve an arrival metering problem [11], which imposed node constraints at metering points. Later, link constraints were added to solve traffic flow management problems with arrival and departure rate constraints at airports as well as sector capacity constraints [12, 13]. The capability to handle link directionality was added to apply the algorithm to surface movement scheduling problems [14] by introducing the concept of positive and negative aircraft count. To investigate dynamic taxi routing, route assignment capability that evaluates multiple routes including the minimum distance route for each flight was added [15].

In this paper, the handling of runway constraints is improved to reflect the separation requirements defined by aircraft weight classes. Instead of blocking a time window that is an inverse of the given departure or arrival rate constraints for each scheduled departure or arrival time, the available time slots are dynamically calculated based on the weight class of the aircraft that are being scheduled and the weight classes of the aircraft that are already scheduled. In addition, a new prioritization strategy, called the partial arrival priority, is introduced. The original schedule is divided into a fixed time window, and arrival flights have a higher priority than departure flights within the same time window.

The scheduler is tested with data from three days of historic flight records at Incheon International Airport, which serves approximately 800 flights daily.

Following this introduction, Sect. 2 describes the scheduling algorithm with detailed description of the runway separation constraints. Section 3 shows the scheduling results using historic flight data at Incheon International Airport. Section 4 concludes this paper.

2 Extending First-Come First-Served Approach

Flight progression can be represented as a sequence of airspaces such as departure airport, departure terminal area, enroute sectors, arrival terminal area, and arrival airport, which can be simplified in a node–link structure as shown in Fig. 1. In this path, departure and arrival airports and airspace boundaries become nodes, and the transit paths in sectors or terminal areas become links. A characteristic of nodes is that flights transit them instantly. Rate constraint such as Aircraft Departure Rate (ADR) or Aircraft Arrival Rate (AAR) can be imposed. Links are characterized by having finite transit times, so the link constraint is the maximum number of aircraft that can be accommodated by one link. For the application to airport surface, ramp area, taxiways, and runways are naturally represented in a node–link structure.

Fig. 1
figure 1

Typical flight path and node–link structure for enroute operation [15]

Full size image

If a scheduling problem is formulated into a node–link structure, and the scheduling priority is given, the EFCFS scheduler can determine the earliest arrival and departure time of each flight [13,14,15].

Figure 2 shows the EFCFS scheduling process. The initial forward propagation step computes the earliest arrival time that satisfies all the constraints at the nodes and links that the flight passes through. After the earliest arrival time is determined through the forward propagation, the earliest departure time is computed using backward propagation. The scheduler also determines the actual transit time at each link for minimum delay. Once the given flight is scheduled, all nodes and links that are part of the flight path are updated, and the scheduler repeats the process with the next flight in the priority order. Detailed step-by-step processes are described in [14].

2.1 Airport Surface Movement

The EFCFS scheduler considers two characteristics of airport node–link structure [13]. The first characteristic is the directionality of links representing airport taxiway segments. The EFCFS scheduler uses positive and negative aircraft count, so link availability can be determined by the current count, the maximum capacity, and the direction of the aircraft that is being scheduled [15]. The other characteristic is that only one aircraft can occupy the nodes that represent actual taxiway junctions. By dividing the sum of junction width and the aircraft length by taxiing speed, the junction occupancy time is calculated. The EFCFS applies rate constraints converted from this occupancy time to the junction nodes so that conflict free scheduling is possible.

2.2 Separation Minima

The previous EFCFS scheduler applied predetermined ADR or AAR at nodes that represent runway thresholds. Node constraints are applied as blocked time intervals for each aircraft that is using a given node. Blocking time interval, \(\varDelta t\), is the inverse of ADR or AAR constraint at the given time as shown in Fig. 3.

Fig. 2
figure 2

Solution process of a EFCFS departure scheduler [15]

Full size image

However, the actual \(\varDelta t\) should be determined by the weight classes of the leading and trailing aircraft. Figure 4 describes this process in detail. If a large class aircraft is being scheduled, and another aircraft that has already been scheduled is heavy, the blocking time should be \(\varDelta t_\mathrm{LH} \) if the large aircraft is to arrive before the heavy aircraft and \(\varDelta t_\mathrm{HL} \) if the large aircraft is to arrive after the heavy aircraft as shown in Fig. 4a. The earliest arrival time can be found by comparing the total blocked time slot denoted with gray color and the feasible arrival slot denoted with hatching. The triangle in Fig. 4a indicates the earliest possible arrival time that satisfy the constraints. Figure 4b shows a more complicated example that involves three aircraft in which a medium class aircraft is being scheduled. Four time slots are blocked before and after the scheduled arrival times of the heavy and large class aircraft. It can be observed that the triangle marks the earliest possible arrival time.

Fig. 3
figure 3

Blocked time slots at nodes using predetermined ADRs and AARs

Full size image
Fig. 4
figure 4

Blocked time slots at nodes using separation based on aircraft weight classes

Full size image

The ICAO and FAA define aircraft wake turbulence category based on the aircraft takeoff weight and provide separation minima [16, 17]. In this paper, time-based wake turbulence separation minima of ICAO are used, and the weight classes are shown in Table 1. Tables 2, 3, 4 and 5 show the separation minima between two aircrafts on a single runway. Table 6 indicates the separation minima for departure after arrival on two dependent runways. Separation minima in Tables 2, 3, 4 and 5 are applied when aircraft are operated on the same runway in the same direction. If aircraft are operated in the opposite direction, the separation minimum of 2 min is applied as shown in Fig. 5 [17].

Table 1 ICAO aircraft wake turbulence category
Full size table
Table 2 Separation minima between departing aircraft on the same runway in seconds
Full size table
Table 3 Separation minima for a departing aircraft before an arrival on the same runway in seconds
Full size table
Table 4 Separation minima for an arriving aircraft before a departure on the same runway in seconds
Full size table
Table 5 Separation minima between arriving aircraft on the same runway in seconds
Full size table
Table 6 Separation minima for a departing aircraft before an arrival on the adjacent runway in seconds
Full size table

2.3 Route Assignment

Instead of using pre-assigned taxi routes based on the gate and runway pair, a route is assigned to the flight during the scheduling process. First, the baseline minimum distance route is found from the given gate and runway pair using Dijkstra algorithm based on the geometric distances of the airport node–link model. Alternate routes are searched by sequentially removing links from the original minimum distance route and recalculating the minimum distance route. This process is summarized in Fig. 6. For each aircraft, schedules are computed for all candidate routes. Among the candidate routes, the one with the minimum delay is selected for the flight. The details about the route assignment process can be found in [15].

Fig. 5
figure 5

2-min separation minimum for aircraft traveling in the opposite direction

Full size image
Fig. 6
figure 6

Route generation process [15]

Full size image

3 Scheduling at Incheon International Airport

3.1 Problem Setup

The original scheduling inputs are generated based on the historic Flight Operation Information System (FOIS) data from April 1st, 3rd, and 10th, 2015. All flights were direct flights and connecting or layover flights were not considered.

Figure 7 shows a node–link model of Incheon International Airport [18]. Gate nodes for the passenger terminal located between runways 15R/33L and 16/34 are individually modeled, and those for the two cargo terminals are aggregated into two nodes. Gates are grouped in blocks, and all the gate nodes within a block is connected to one taxiway node as noted with arrows in Fig. 7.

Fig. 7
figure 7

Node–link model of the Incheon International Airport

Full size image

Taxiway transit times are computed by dividing the actual length of the link with the nominal taxi speed of 15 knots. In addition, the nominal taxi speed of five knots is used for the ramp area.

When a departing aircraft enters a node representing the runway threshold, it is assumed to takeoff instantly, and the scheduling is completed. Arrival aircraft are assumed to land at a runway threshold node and to exit the runway at the first node it encounters after covering its landing field length. Table 7 shows the landing field lengths based on the aircraft wake turbulence category and Base of Aircraft Data (BADA) [19]. The speed of landing aircraft is assumed to decrease linearly from 150 knots at the runway threshold node to 15 knots at the runway exit node. The transit times for runway links are computed accordingly.

Runway capacity constraints determined by the separation minima are applied to six runway threshold nodes. Since runways 15R/33L used for arrivals and 15L/33R used for departures are closely spaced parallel runways, Table 6 is used for departure after arrival situations [17]. For arrival after departure, the two runways are considered independent. Runway 16/34 is considered independent. Taxiway junction nodes are constrained by a maximum rate of 269 aircraft per hour. Time that an aircraft occupies the junction is calculated by dividing the sum of the junction width and the aircraft length by the nominal taxi speed. No rate constraints are imposed to gate nodes. Theoretically, simultaneous gate occupancy is possible, but it is not likely to happen since the original input based on historic data has well-spaced gate occupancy. Taxiway link capacity is determined by dividing the length of the link by the sum of the aircraft length and safety distance, which is assumed to be 150 m. Since the ramp area links are approximation of complex taxi lanes, slower taxi speed of five knots are used while removing the maximum link capacity constraints. Since the entrance to the runways are regulated at the runway nodes by the wake turbulence separation minima, link capacity constraints are not enforced at the runways links.

Regarding route assignment, ten routes are generated for each flight unless the total available number of routes is less than ten.

Table 7 Landing field lengths in meters
Full size table
Fig. 8
figure 8

Delay distribution derived from partial arrival priority

Full size image
Table 8 Average delays by scheduling priorities for April 1st, 3rd, and 10th in minutes
Full size table
Fig. 9
figure 9

Average delays by scheduling priorities for April 1st, 3rd, and 10th, 2015 in minutes

Full size image

3.2 Scheduling Results

In this paper, three prioritization strategies for scheduling are considered. The nominal priority is based on the original scheduled gate departure or runway arrival times for a given flight. Arrival priority gives a higher priority to all arrival flights. Finally, a strategy named the partial arrival priority is considered. In this strategy, for all flights with their original departure or arrival times fall within a given time window, the schedules of the arrival flights are calculated first and then the departure flights are scheduled. The process is repeated for the next time window. For this study, 1-h time window is used for testing purpose, but it can be adjusted. Partial arrival strategy can be considered to model the real world operation better because it generally fixes the schedules of the flights that will arrive or depart sooner.

Delays are measured by calculating the difference between the original gate departure times or runway arrival times and the computed gate departure or runway arrival times.

Initial scheduling for nominal priority is performed using the original schedule input of April 1st, 2015. The average delay for all 782 flights was 3.8 min. The average delay of 397 departure flights was 2.2 min, and for 385 arrival flights was 5.5 min. The maximum departure and arrival delays were 21.6 and 23.8 min, respectively.

When the arrival priority strategy is used, the average delay of the total of 782 flights was reduced from 3.8 to 1.0 min. The average delay of 397 departure flights was slightly reduced from 2.2 to 2.0 min. And the average delay of 385 arrival flights was significantly reduced from 5.5 to 0.1 min. The maximum departure delay was 26 min, and the maximum arrival delay was 2.0 min. Compared to the results of the nominal priority, the maximum and average arrival delays were significantly reduced without any adverse effects on the departure delays.

For the partial arrival priority applied to 1-h time windows, the average delay of 782 flights was 1.4 min. Regarding the 397 departure flights, the average delay was 1.8 min. The average arrival delay was 0.9 min. The maximum departure delay was 26 min, and the maximum arrival delay was 11 min. Figure 8 shows the delay distribution for the partial arrival priority. It shows that the delay was less than 5 min for most of the flights and that the maximum delay was less than 30 min.

Additional scheduling is performed using the original schedule inputs of April 3rd and 10th, 2015. The average delays for all three dates are shown in Table 8. The changes in average delays based on scheduling priority are shown in Fig. 9. Table 9 shows the maximum departure and arrival delays for each date. There was one single departure flight with 43.9 min of delay on April 10 using arrival priority. For all other flights, maximum delays were less than 30 min. Figure 10 displays runway utilization at runway 33R on April 10th, 2015, using the arrival priority.

Table 9 Maximum delays by scheduling priorities for April 1st, 3rd and 10th in minutes
Full size table
Fig. 10
figure 10

Example of the runway utilization at runway 33R

Full size image

Both arrival and partial arrival priorities show improved performance. All three days show reduction in the average delays with significant reduction in the arrival delays. For April 1st, 2015, departure delays were also slightly reduced with the arrival biased priorities while slight increments were observed for the other days. These results differ from the previous research in which the arrival priority significantly increased the departure delays, and in particular, the maximum departure delay [15]. The main difference is how the runway constraints are applied. Specifying time varying AARs and ADRs from the recorded flight data used in the previous work [15] do not reflect the physical capability of the runway. Further investigation, including connecting flight constraints and gate occupancy constraints, is required to be more conclusive. However, the current study shows that if the runways can operate close to their maximum throughput capacity governed by the separation minima, arrival-biased prioritizations can significantly reduce arrival delays with minimal impacts on departure delays.

For each case that consists of about 800 flights for the 24-h period, it takes about two to 3 min for the scheduler to compute the solution using a medium performance personal computer. As computational costs are significantly lower than optimization-based scheduling algorithms, it will be particularly useful for applications that require recalculating the schedule repeatedly, needs to evaluate many different prioritization strategies, and require scheduling with longer time horizons.

4 Conclusions

In this paper, aircraft wake turbulence separation minima are applied to the EFCFS scheduler. Scheduling with three prioritization strategies are performed for Incheon International Airport using this enhanced EFCFS. Inputs are generated based on historic flight data from three days in April 2015. The results show that, compared with the nominal priority, both the arrival and partial arrival priority decrease overall delays with significant reduction in the arrival delays. Adverse impacts on the departure delays are minimal with the two arrival-biased prioritization strategies. Further investigations that consider connecting flights and gate occupancy constraints will be performed so that results can be compared to real world operations and to other scheduling schemes.