Aircraft sequencing under the uncertainty of the runway occupancy times of arrivals during the backtrack procedure

Abstract

In some small airports, a parallel taxiway is not built due to space restrictions or financial issues; hence, the runway itself is often used as a taxiway in this type of airport. After touch down, aircraft move to the U-turn area at the end of the runway and turn 180 degrees, then move back to the desired point, such as a gate or the apron, using the runway. The runway is blocked to other arrivals and departures during this process. This process, called backtrack or back-taxi, can result in high delays for both arrivals and departures. Runway occupancy times (ROTs) vary depending on numerous conditions, including pilot performance, weather conditions, aircraft type, etc. Although there are speed restrictions and procedures announced in advance, the actual performance can be uncertain. In addition, most aircraft can make a U-turn as soon as they sufficiently reduce their speed before they reach the U-turn area especially if they are already delayed. These situations bring enormous uncertainties for traffic management at such an airport. Controllers may need help to sequence aircraft, particularly in busy traffic. In this study, a stochastic mathematical model is developed to sequence arrival/departure operations at such an airport considering the ROT uncertainties of arrivals. The objective function of the developed model is determined as the minimisation of the total delay. ROT data was obtained by observing radar tracks of 120 arriving flights. Reasonable ROT scenarios with various probabilities to represent ROT uncertainties were integrated into the mathematical modeling. In addition, two different sequencing approaches are presented as well as the first come first serve (FCFS) approach. As a result, the proposed stochastic approach provides robust sequences applicable for all ROT scenarios with significant delay savings up to an average of 18.4% and 39.5% compared to deterministic and FCFS approaches, respectively.

Nomenclature

AIP

Aeronautical Information Publication

ASSP

Aircraft Sequencing and Scheduling Problem

AST

Average Solution Time

ATCo

Air Traffic Controller

CPS

Constrained Position Shifting

DET

Deterministic Model

ETA-D

Expected Times of Arrivals and Departures

FCFS

First Come First Serve

GAMS

General Algebraic Modeling System

MPS

Maximum Position Shifting

ROT

Runway Occupancy Time

RP-STC

Here And Now Solution

STC

Stochastic Model

TMA

Terminal Manoeuvering Area

VES

The Value of Expected Solutions

VSS

The Value of The Stochastic Solution

1.0 Introduction

The demand for airports around the world is increasing, and structural or operational developments are needed to meet this increase in demand [1]. Structural developments may not be possible at some airports due to space restrictions, as well as cost [2]. Authorities first seek operational improvements in terms of air traffic management at this type of airport [3]–[5]. Some small airports still do not have taxiways due to space restrictions or higher construction costs. For this type of airport, after the aircraft has landed, they return from the U-turn area at the end of the runway and perform the taxi movement on the runway. Departures also may take off by making a 180-degree turn after they have gone to the end of the runway depending on the direction of operation. One of the most important problems at such airports is the long and uncertain runway occupancy times (ROTs) [6]. The ROT of an aircraft may differ depending on numerous factors, including weather conditions, pilot performance, type of aircraft, etc. Even for the same aircraft, or for the same pilot on different flights, the ROT of each flight can be different. Even for professionals, these factors are not obvious and are difficult to assess [7]. Although the taxi speeds and operational procedures of the aircraft are specified in the Aeronautical Information Publication (AIP) of the airport, the actual operations that take place do not exactly follow these procedures. In addition, some aircraft can make a U-turn as soon as they sufficiently reduce their speed before they reach the U-turn area, especially if they are already delayed. At such airports, authorities determine a separation requirement with a protective approach and apply this for all aircraft regardless of the aircraft type. Furthermore, because of the uncertainty, an extra separation buffer is applied by controllers [7]. For one airport of this type, which was used for our case study, the minimum separation requirement was declared as 6 minutes in the AIP, however, the controllers apply 7 minutes using an additional 1-minute buffer for consecutive arrivals to provide safe operations [8]. Other operations are blocked while an aircraft is on the runway, departure aircraft can take off as soon as the arrival aircraft vacates the runway and if there is no incoming flight coming in to land.

To manage air traffic at this type of airport, air traffic controllers (ATCos) make sequencing plans that consider separation requirements and uncertain parameters, such as the ROT of arrivals. Deterministic sequences are planned that assume all aircraft will leave the runway with an expected ROT. In this study, two different sequencing approaches are presented as well as the first come first serve (FCFS) approach. However, the ROT of aircraft can be higher or shorter than the expected ROT. As an alternative approach, the possible ROTs can be reflected in the model as a source of uncertainty with various probabilities. Using stochastic programming, robust, efficient and safe sequences can be obtained that consider all probabilities.

In addition to the above-mentioned issues, delay constraints and constrained position shifting strategy are integrated into the model to provide reasonable waiting times and fair sequences, respectively. The latest landing and departure times of aircraft are restricted by using delay constraints, hence significant air delays and ground waiting times are prevented for each flight. Allowing arbitrary deviations from the FCFS method can result in impractical sequences and may result in unfair position shifting among airlines [9]. To prevent this situation Dear [10] offered constrained position shifting (CPS) that only allows for an aircraft to be moved by up to a specified maximum number of position shifts (MPS) from its original FCFS order. In this study, the CPS strategy was also integrated into mathematical modeling to prevent impractical sequences and various CPS scenarios were examined.

1.1 Literature

Since airspace and ground operations contain various uncertainties, stochastic programming methods are used to obtain robust aircraft sequences and schedules. Uncertainties have been considered in the literature, including weather conditions [11]–[14], terminal manoeuvering area (TMA) entry times [15], and flight times [16], [17], etc. for airborne operations. There are also studies that consider uncertainties on the ground. In one of these studies, Lee and Balakrishnan [18] performed a series of fast time simulations to examine various sources of uncertainty, such as pushback times, runway exit times, taxi speeds and runway separation times. They used SIMMOD as a discrete event simulation tool to simulate these events with actual flight schedules. They emphasised that the simulations demonstrated that ground delays increase as the level of uncertainty increases in most circumstances. Chen et al. [19] used multi-objective fuzzy rule-based systems to quantify taxi time uncertainties based on historical data. They suggested that their proposed approach could provide more robust solutions and reduce taxi time delays for further analyses thanks to accurate predictions. Bosson and Sun [20] presented a fast-time decision support algorithm for solving the integrated aircraft routing and flight scheduling problems under the uncertainty of release and due times of arrivals and departures. In their study, a multi-stage stochastic programming approach with sample average approximation was used to solve the problem. They emphasised that the stochastic approach offers better use of airport resources with reduced taxi and gate waiting times. Brownlee et al. [21] presented an adaptive Mamdani fuzzy rule-based system to estimate taxi times and the associated uncertainties. They also adopted the Quickest Path Problem with Time Windows algorithm to use fuzzy taxi time estimates. As a result, they concluded that their approach provided more robust routes and reduced taxi delays. Solveling et al. [22] presented a two-stage stochastic runway planning model for the scheduling of airport runway operations in the presence of various uncertainties: pushback delay, time spent on the taxiway and deviation from the estimated arrival time. They concluded that the stochastic approach has some potential benefits compared to the FCFS approach under the uncertainties in dense traffic. Agogino and Rios [23] presented a binary programming approach and an evolutionary algorithm that considers the take-off time uncertainty of departures. They found that as the level of uncertainty increases the performance of the models decreases, and emphasised that the presented algorithm provides good results even under a high level of uncertainty. Murça [24] presented an optimisation approach to sequence departure aircraft considering taxi-out times. They suggested that the presented approach was robust and showed positive results that reduced runway delays and taxi-out times, as well as increased predictability of takeoff time. Gotteland et al. [25] compared several optimisation strategies in terms of the minimisation of the time spent between gates and runways considering ground speed uncertainties. They emphasised the importance of considering speed as an uncertainty source since estimating the exact position of aircraft on the ground is quite difficult. Wang et al. [26] handled the airport ground movement problem by developing a chance-constrained programming model. They integrated the taxi time uncertainties into their model as several scenarios. They also modified the sequential quickest routing method with a local heuristic algorithm to solve the proposed model. As a result, they obtained better result in terms of the average simulated taxi times comparing the other state of art routing methods.

Most simulation and optimisation studies have shown the importance of considering uncertainties in ground operations, such as taxi in-out times, pushback times, etc. However, ROT uncertainties are as important as these because the runway is blocked, and capacity reduces during the procedure. Particularly for airports with a single runway and no taxiways, ROT uncertainties need to be handled with more attention.

1.2 Contribution of the study

To the best knowledge of the author, no studies in the literature consider ROT uncertainties with the backtrack procedure despite the ROT uncertainty being potentially very high for this type of runway and as some airports do not have any opportunity for structural improvements due to space or other restrictions. For this type of airport, the only option to increase runway capacity is an operational enhancement. In this study, a new two-stage stochastic mathematical model for the aircraft sequencing and scheduling problem (ASSP) for a single-runway with a backtrack procedure is developed that considers arrival ROT uncertainties and the objective of minimising the total delay. The proposed model provides robust sequences for this type of airport and decreases delays and increases runway capacity. Thus, significant financial gains can be achieved by providing operational improvements instead of structural changes at such airports. Other specificities of the study are summarised as follows:

• • The presented model is easy to apply and maintains safe operations.

• • It provides robust sequences that are feasible for all scenarios, hence there is no need for controllers to re-sequence aircraft. Therefore, it reduces the workload of controllers.

• • A realistic TMA management strategy is provided that considers arrival and departure operations together.

• • By considering the various CPS scenarios, a bridge between theory and practice is demonstrated.

• • This study considers a real-life problem, and to solve the problem ROT uncertainty scenarios were generated based on real observations from the flight radar tracks.

• • Three different sequencing approaches are presented as well as the stochastic programming approach (see the methodology section).

2.0 Methodology

2.1 Airport layout and flight operations

The aerodrome structure of an airport in Turkey was used as a case study. The airport has a 3000 m runway and no parallel taxiway, the layout is given in Fig. 1 [8]. The backtrack procedure can be carried out for both arrivals and departures depending on the direction of operation. In this study, only one-way operations were considered so the backtrack procedure was applied only for arrivals. The runway at this airport, however, is blocked for both arrivals and departures during the procedure, thus arrival and departure operations were considered together in this study. Arrivals backtrack and taxi along the runway whereas departures use the runway only to take off. After backtracking, arrivals exit the runway from taxiway B. Departures use taxiway C and take-off from the beginning of Runway 13. The study assumed that arrivals fly at a constant average speed on their final approach from the final approach fix, which is 8.94 nm far from the touchdown point. Departures were assumed to taxi to the holding point at a constant speed.

Figure 1. Airport layout.

2.2 Determination of the ROT scenarios

After landing, arrivals decrease landing speed until they reach their taxi speed. After reaching a suitable speed, the aircraft perform a U-turn and taxi to the apron on the runway. Procedures expect that the U-turn is made at the end of the runway. However, in reality, some aircraft make a U-turn as soon as they reach a suitable speed. Also, even if the same type of aircraft makes a U-turn at the same point, the ROTs may still change due to other factors, such as wind or pilot performance. In this study, a total of 120 arrival operation were observed based on radar tracks. All aircraft that landed on Runway 13 were medium-type aircraft and scheduled flights. The types of aircraft were from the A320 (including A319 and A320) or B737 (including B737-700, B737-800 and B737-900) families and belonged to three different airlines. The observations were carried out on six different days over two different periods, one summer and one winter to reflect the effect of different weather conditions on the model. Mann-U Whitney tests were performed to examine if there were significant differences between the A320 and B737 families and between the observation periods in terms of average ROT and no significant differences were found between manufacturer types (Means: A320 = 263.4, B737 = 246.7, p = 0.136, Z: –1.491) or between the observation periods (Means: Summer = 257.9, Winter = 249.2, p = 0.425, Z: –0.798). In addition, the Kruskal-Wallis H test was performed to find out whether the differences existed between the airlines; however, no significant differences were found (Means: A1 = 263.9, A2 = 245.6, A3 = 243.2, p:0.199, χ²: 3,225, df:2). Note that these non-parametric tests were used because at least one variable did not show normal distribution in the analysis. Figures 2, 3, and 4 show the distribution of ROTs considering the observation period, manufacturer types and airlines.

Figure 2. Histogram of the ROT distribution based on observation periods.

Figure 3. Histogram of the ROT distribution based on the aircraft manufacturer type.

Figure 4. Histogram of the ROT distribution based on airlines.

Based on these results, it was determined that all data should be used together and that the intervals should be set at 30 seconds to generate reasonable scenarios for the mathematical model. The histogram of observed ROTs of all aircraft is presented in Fig. 5.

As presented in Table 1, the highest number of observations was obtained for 29 aircraft in the range of 224–254 seconds, while the lowest number of observations was obtained for 2 aircraft between 134 and 164 seconds. Medians of the ROT intervals were selected to represent each ROT interval. The scenarios integrated into the mathematical model and the probabilities of these scenarios were based on the frequencies presented in Table 1.

The value of ROTs given in Table 1 is the same for all aircraft under each scenario. For example, in Scenario 1 the median of the ROT is 149 seconds, this represents that the ROT of aircraft is expected between 134 and 164 seconds in this scenario. In the stochastic model, each scenario is added to the objective function with its probability, therefore the objective function considers all scenarios together with various probabilities and gives one sequence decision that is feasible for all the scenarios (see Section 3.1).

2.3 Determination of the Traffic and CPS scenarios

The average daily number of flights (commercial and general aviation) at the airport was recorded as 35.5 in 2021 [27]. For our analysis, various traffic demand scenarios were generated to simulate the current low traffic volume and possible future traffic growth. The ultimate capacity of the runway was calculated as 20 flights an hour based on the analytical model presented by Mascio et al. [20] that considers arrival and departure mixed operations, and calculates the capacity as the inverse of the separation time, between two consecutive aircraft [28]. However, higher aircraft demand scenarios were also considered to observe the behaviour of the models in cases of overcapacity. Due to the scarce traffic at the airport, generic uniform distribution was used to obtain various expected times of arrivals and departures (ETA-D) scenarios. In addition, different arrival/departure mix scenarios were also considered to observe the sensitivity of runway capacity to arrival/departure rates.

Various CPS scenarios were generated to observe the sensitivity of the models to the maximum allowed position change. The CPS scenarios provided optimised sequences where the aircraft cannot significantly deviate from its position in the FCFS sequence to protect fairness among airlines, decrease ATCo workload, and increase the applicability of the optimal sequences in real life [9]. In literature, the feasible maximum position shifting in TMA is considered as 3 from FCFS in most studies [9], [10], [29], [30]. We generated different CPS scenarios with up to 3 position shifts and solved these scenarios for all ETA samples for the stochastic model. Also, a sample ETA-D scenario was selected to compare the behaviour of the models under different CPS conditions.

Table 1. ROT scenarios and probabilities

Figure 5. Histogram of the ROT distributions.

3.0 Mathematical modelling

3.1 Two-stage stochastic programming

Uncertainties in the air traffic system lead to deviations from the actual plan or schedule [31], [32]. The two-stage stochastic programming approach, however, provides robust, and better or equal (at least) solutions than deterministic approaches under conditions of uncertainty [11]. Two types of decisions are made in this approach: the first stage and the second stage. The decision of the sequencing of aircraft is considered to be the first stage of the problem and this decision variable is represented by an x vector. The first stage decisions are also referred to as “here-and-now” decisions taken before the realisation of random events. After the realisation of these random events ( ${\rm{\xi }})$ , the full information is obtained and the second stage decisions or corrective actions, (y) are taken. In our case, a random vector is the set of uncertainties including ROTs. The corrective actions are airborne delays for arrivals and queue delays for departures. A general formulation of the two-stage stochastic linear program is presented in (s1-s4) [33].

(s1) \begin{align} \text{Min}\ {c^T}x + E[Q\left(x, \xi\right)\!]\end{align}

(s2) \begin{align}s.t.\;\;\;Ax = b,\;x \geqslant 0\end{align}

(s3) \begin{align}\text{Min}\ q{\left( {\rm{\xi }} \right)^T}y\end{align}

(s4) \begin{align}s.t.\;\;\;T\left( {\rm{\xi }} \right)x - W\left( {\rm{\xi }} \right)y = h\left( {\rm{\xi }} \right),\;y \geqslant 0\end{align}

• • $Q\left( {x,{\rm{\xi }}} \right)$ is the optimal value of the second stage problem.

• • ${\rm{\xi }} = \left( {q,\;h,\;T,\;W} \right)$ are the random elements.

• • T and W are called technological and recourse matrices, respectively.

• • q is the second-stage objective vector.

• • h is the right-hand side vector in the second stage [33].

We adopted a scenario-based stochastic optimisation approach, which was initially proposed by Ref. 34, to generate different sets of variables for each scenario S [35]. The random vector ${\rm{\xi }}$ is supposed to have a limited number of possible scenarios ${\xi _1},\;{\xi _2},\; \ldots \;{\xi _K}$ each with its own probability $\;{p_1},\;{p_2},\; \ldots \;{p_K}$ . The expectation in the objective function of the first-stage problem can be represented as the summation of (s5) [36].

(s5) \begin{align}E\left[ {Q\left( {x,{\rm{\xi }}} \right)} \right] = \;\mathop \sum \limits_{k = 1}^K {p_K}Q\left( {x,{\xi _K}} \right)\end{align}

The here and now solution (RP-STC) represents the solution of the stochastic model considering all uncertainties. The value of expected solutions for deterministic VES(DET) and FCFS approaches VES(FCFS) were calculated by finding the objective function value of the stochastic model for the fixed aircraft sequence decisions obtained from the deterministic and FCFS models, respectively [11]. We considered two different VES(DET) models. In the first model, it was considered that sequences are planned in a protective way, a more cautious approach to consistently ensure sufficient separation, by assuming all arrivals will occupy the runway for 7 minutes, and this model is referred to as VES(PROT). This protective approach considers the worst-case scenario for the ROTs of arrivals. In the second approach, it is assumed that the sequences are planned by considering all arrivals will occupy the runway based on the highest possible ROT found in our analysis. In this case, the ROT of arrivals is 239 seconds, which was the scenario we identified with the highest possibility. This approach is referred to as VES(POSS). It is expected that the first approach always provides a feasible solution but may result in higher delays, while the second approach provides better sequences in terms of delays, however, the sequences cannot be applicable (or infeasible) for higher ROT scenarios than the expected ROT. The infeasible solutions indicate that there was an optimal first stage sequence decision (solution); however, these sequences were not applicable for the second stage of the problem when the ROT uncertainties are included in the problem.

As a result, we compared the RP-STC model with the VES(POSS), VES(PROT) and VES(FCFS) models. From this point, to be concise while stating the outputs obtained from the above-mentioned models, the terms STC, POSS, PROT and FCFS are used respectively. The value of the stochastic solution (VSS) is cited as a performance indicator that represents the possible gain from solving the stochastic model, and this is the difference between the value of expected solutions and the stochastic model given in (s6) [33].

(s6) \begin{align}VSS = VES - RP\end{align}

As a result, the differences between the STC model and the other models are referred to as VSS(PROT), VSS(POSS), and VSS(FCFS), respectively.

Table 2. Sets

Table 3. Parameters

Table 4. First stage decision variables

3.2 The aircraft sequencing and scheduling problem

The aircraft sequencing and scheduling problem for a single runway describes the sequencing of arrivals and departures with an objective under several operational constraints, such as safety or flight time. Tables 2–6 give the sets, parameters, first and second stage decision variables and the constraints of the problem, respectively.

Equations (1) and (2) determine the arrival touchdown times and departure times for each ROT scenario, respectively. The maximum airborne delays for arrivals and queue delays for departures are limited to 1,800 seconds by Equations (3) and (4), respectively. Arrivals are assumed to be delayed by the controller, if necessary, before arriving at the final approach fix.

Table 5. Second stage decision variables

Table 6. Constraints

Table 7. Separations

Table 8. Objective function

Separations must be ensured between successive aircraft. ICAO regulates the separations for landing and take-off phases depending on the wake turbulence categories of aircraft [37], [38]. However, a higher separation time than the ICAO wake turbulence separations is required in our case. For this type of runway, the minimum separation requirements are determined by authorities, based on the ROTs of aircraft. In our case, 7-minutes separations must be ensured between successive arrivals, and 1-minute separation must be ensured after a departure aircraft has taken off. Departure aircraft can take off after an arrival vacates the runway. Table 7 shows the separation requirement of the runway in our study.

Constraints (5) and (6) ensure the safe separation between successive aircraft. Equation (7) calculates the position of the ith aircraft. Equations (8) and (9) ensure that the absolute value of position shifting of an aircraft is less than or equal to MPS.

Equation (10), given in Table 8, calculates the total delays for each scenario. Equation (11) describes the objective function to minimise the total delay by considering all scenarios and probabilities.

4.0 Results

The CPLEX solver, which is a built-in solver for linear programming, mixed-integer programming and quadratic programming problems in the General Algebraic Modeling System (GAMS), was used to solve all the samples. CPLEX guarantees the optimal results of linear problems if the function “option optcr” is set to 0 in GAMS which is a high-level programming language used for mathematical optimisation [39], [40]. The samples were solved using a computer with 32 GB of RAM and an Intel Core i7 CPU operating up to 4.6 GHz.

4.1 Toy problem

First, we examined a toy problem which included a demand of ten aircraft per hour. The sequence decisions given by the models in the first stage of the problem and the delay in minutes obtained in the second stage by realising the sequence decisions under ROT uncertainties are presented in Fig. 6.

As seen in Fig. 6, significant deviations from FCFS were observed for all models. STC and POSS models resulted in the same sequence for the toy problem. Although the PROT model resulted in the lowest total departure delays, it resulted in the highest total arrival delays. Significant arrival delay savings were achieved in the STC and POSS models, at the expense of a small increase in departure delays compared to the PROT model. Similarly, significant departure delay savings were achieved in the STC and POSS models, at the expense of a small increase in arrival delays compared to FCFS. Total delays for each ROT scenario are given in Table 9 for each model.

Table 9. Total delays (min.) in the ROT scenarios for the toy problem

Sc: Scenario

Figure 6. Sequence decisions for the toy problem.

As presented in Table 9, the STC and POSS models resulted in lower delays than the PROT model for all scenarios except scenario 9. This is because the PROT model makes the sequence decisions in the first stage by considering the highest ROT scenario. FCFS, on the other hand, resulted in the highest delays in each ROT scenario. Although STC and POSS models resulted in the same sequences for the toy problem, these models can be differentiated in terms of the sequence decisions given in the first stage and hence the delay outputs in the second stage. Different ETA-D examples at higher traffic numbers are shown below to present deeper analyses and clearer comparisons between the models.

4.2 Numerical results

Ten different ETA-D samples were solved for all four models. As a result, 40 samples were run with the no-CPS condition applied. The total delays corresponding to the probabilistic sums in these samples are given in minutes in Table 10.

Table 10. Total delays (min.) in the ETA-D samples

As shown in Table 10, the STC model provides an average of 0.65%, 18.4% and 38.51% total delay savings compared to the POSS, PROT and FCFS models, respectively. Although the POSS model provided better results than the PROT and FCFS models, the sequencing decisions obtained by this model were not applicable in 40% of the ETA samples. The reason for this is that operational constraints cannot be satisfied in the second stage of the problem when the sequencing decisions taken in the first stage are applied under the ROT uncertainties. As expected, the PROT model provided feasible and applicable sequences for all samples; however, the sequences resulted in higher delays compared to the STC model. The FCFS model resulted in the highest delays among the models. As a result, the STC model presented the sequences, which are applicable for all samples and provided better results compared to deterministic and FCFS approaches. Table 11 shows the average of the total delay per aircraft in the ETA-D samples for all models.

Table 11. Total delay per aircraft in the ETA-D samples

The overall delay tolerance of the airport operators or airlines is known as practical capacity. For example, if the practical capacity is set at 5 minutes this means that companies can tolerate a 5-minute total delay per aircraft. If the practical capacity is exceeded, the airport capacity is saturated [41]. When the 5-minute total delay per aircraft was considered as the practical capacity saturation limit in our case, the STC model provided sequences in which the practical capacity was not exceeded in 70% of the samples. The FCFS approach could not provide solutions in which the 5-minute practical capacity was not exceeded, while the POSS and PROT models provided solutions without practical capacity saturation for 40% and 30% of the samples. The practical capacity limit is changeable depending on the tolerance of the authorities and airlines. Therefore, the sequences that resulted in 5-minute over-practical capacity do not mean they were not feasible. For example, when we considered a 7-minute practical capacity, the STC model provided sequences without capacity saturation for 100% of samples. Although the PROT model resulted in higher delays compared to the POSS model, it achieved reasonable solutions for 90% of the samples, considering the 7-minute practical capacity. These results indicate that if the authorities have a relatively high delay tolerance, the PROT model decreases the ATCo workload by providing applicable sequences without the requirement of resequencing compared to the POSS model. However, these sequences do result in higher delays, and all these deficiencies are compensated with the STC approach. Table 12 shows the average arrival and departure delays per aircraft for all models in all ETA-D samples.

Table 12. Arrival and departure delays per aircraft

Although the STC model provided significant gains in terms of total delay, some of the models, however, provided better results than the STC model when arrival and departure delays were considered separately. In addition, the average arrival/departure delay rates of the model significantly differentiated from each other. For example, while the FCFS model resulted in similar delays for arrivals and departures, PROT resulted in the highest arrival delays and lowest departure delays.

Considering only arrival delays VSS(POSS), VSS(PROT) and VSS(FCFS) were found to be –6.6%, 28.3% and –3.2%, respectively. When considering departure delays these values were 17.3%, –132% and 80.2%, respectively. Although VSS(PROT) for departures seems to be a very high loss as a percentage, it corresponds to an average of 0.41-minute delay per departure. However, VSS(PROT) for arrivals corresponds to an average delay saving of 1.47 minutes per arrival. Although it seems that the POSS model provided better results than the STC model in terms of the total of the average arrival and departure delay per aircraft, this is not a clear comparison since there are infeasible solutions with the POSS model. If the feasible solutions of the models are compared, the average arrival delay per aircraft corresponds to 3.62 and 3.49 minutes for STC and POSS models, respectively. The departure delay per aircraft, on the other hand, corresponds to 0.71 and 0.87 minutes per aircraft. As a result, the STC model still provides a 0.03-minute delay saving in terms of the total arrival and departure delay per aircraft. It can be concluded that although some of the models presented better results when the arrival and departure delays are considered separately, the STC model always provided delay savings compared to other models in terms of total delays. The reason for this is that the objective function of the models considers the minimisation of the total delay.

The average solution times (ASTs) of the models were also compared to find out the computational efficiency of the models. Figure 7 shows the AST of each ETA-D sample for all models.

Figure 7. AST of each ETA-D sample.

As shown in Fig. 7, the highest AST was for the PROT model. In this model, since 7-minute ROTs are considered in the first stage of the problem, it may be difficult to produce a sequence that satisfies the delay constraints for the demand of 20 aircraft per hour. After the PROT model, the next highest AST was for the STC model. The ASTs of the STC model are relatively high as the stochastic approach attempts to present a sequence that simultaneously satisfies all ROT probabilities. In the POSS model, on the other hand, it is easier to sequence 20 aircraft in a 1-hour operation compared to the PROT model, since the highest ROT probability is considered when deciding the sequences in the first stage. In the FCFS model, since the sequences are fixed, the solutions are obtained very quickly.

4.3 CPS analyses

Although the STC model provides significant gains compared to other models, it can result in the sequences requiring a high number of position shifts for the aircraft in the sequence which increases ATCo workload and so cannot be treated as a valid option. The CPS strategy was included in the models to provide fair and practical sequences. Ten different ETA-D samples were run for the STC model considering three different CPS scenarios in addition to the No-CPS condition presented above. The averages of total delays in the ten ETA-D samples under different CPS conditions are given for the STC model in Fig. 8. The left axis of Fig. 8 shows the total delays in minutes, and the right axis shows the ASTs in seconds.

Figure 8. Total delays for the STC model in the CPS scenarios.

As Fig. 8 shows, as the number of allowed MPS increases the performance of the STC model increases. Also, the AST of each run increases as the number of MPS increases. Lower solution times were obtained for the more limited position shifting scenarios since the solution space is narrower. To compare the STC model and the other models under various CPS conditions we selected an ETA-D sample and solved it for each model. Figure 9 shows the total delays obtained by these models for each CPS scenario.

Figure 9. Total delays in the CPS scenarios.

As seen in Fig. 9, although the STC model resulted in the same delay as the POSS and PROT models for 1-CPS scenario, it provided better results than the deterministic models for higher MPS numbers. Considering that the three-position shifting approach is reasonable for TMA operations, it can be concluded that the STC still provides better results than the other models even under CPS conditions. Note that the FCFS model provides a fixed sequence and does not change depending on the CPS scenarios.

4.4 Sensitivity to arrival rate and traffic demand increases

The above analyses include a 50%–50% arrival/departure rate; however, the arrival rate can affect the total delays since the increase in the number of arrivals increases the total ROT. We solved different arrival/departure mix scenarios to observe the sensitivity of the models to the arrival rate, the results are given in Fig. 10. As expected, it was found that the total delays increase in all models as the rate of arrival increases. A dramatic increase in the total delay was observed between the arrival rate scenarios, for example, the total delay increased up to 330% between the 40% arrival rate scenario to the 60% scenario for the PROT model. The results indicate that the runway structure is highly sensitive to arrival rate. The STC model provided better results than the FCFS and PROT models for all arrival rate scenarios except one. It resulted in the same delay as the POSS model in the 40% arrival rate scenario. In conclusion, the STC model still provided better or equal solutions for various arrival rates. Note that for arrival rates greater than 60% there were no feasible solutions provided by the models as the delay constraints of the models could not be satisfied.

The overcapacity condition was also examined in this study by analysing an ETA-D sample with 10% demand increments for an hour. The solution time was limited to 600 seconds. Table 13 shows the results in terms of the total delays in minutes.

Table 13. Total delays in the demand increase scenarios

^*There was no optimal solution for the first stage of the problem within the solution time limits.

Figure 10. Total delays (min.) in the arrival rate scenarios.

The infeasible solutions in Table 13 indicate that there was an optimal first stage sequence decision (solution), however, these sequences were not applicable for the second stage of the problem. However, in some cases, an optimal solution was not found within the solution time limit for the first stage of the problem. Although the STC model provided optimal results for scenarios with a demand of up to 24 aircraft, it could not provide an optimal solution within the solution time where the demand was for 26 aircraft or higher. The STC model resulted in a 6.8-minute average delay per aircraft for the 24 aircraft demand scenario indicating that the 7-minute practical capacity limit was still not saturated with this demand. Although the POSS model resulted in the same delays as the STC model for 20 and 22 aircraft demands, the first stage decisions for the POSS model were not feasible for 24 aircraft demand scenarios and higher demands. On the other hand, the PROT model could only find an optimal solution for a 20-aircraft demand per hour, and the result was 13.9% worse than the STC and POSS models. Although the FCFS order was feasible up to 24 aircraft demand for an hour, the results of this model were significantly higher in terms of the total delays than the other models. As a result, it can be concluded that the STC model showed better performance than the other models for demand increase scenarios.

5.0 Discussion and conclusion

In this study, a stochastic approach has been presented to sequence arrival and departures for a runway with backtrack procedures considering the ROT uncertainty of arrivals. In addition, two different deterministic approaches, as well as the FCFS approach, have been presented in this study. First, the FCFS order was considered, which is easy to apply; however resulted in high arrival and departure delays. The PROT model was then considered to reflect a protective approach. In this approach, sequences are decided in the first stage of the problem considering that all arrivals will occupy the runway for the longest duration. This approach provided feasible sequences for each ROT scenario in all ETA-D samples for the demand of 20 aircraft per hour; however, resulted in higher delays than the STC and POSS models. The last model, POSS, was more reasonable in terms of expected ROT. In this approach, the sequence decisions are made in the first stage of the problem as if all arrival aircraft will occupy the runway for the duration of the most probable ROT scenario. This approach provided shorter delays compared to PROT and FCFS models; however, the sequences were not feasible in some of the ETA-D samples. This situation requires the re-sequencing of aircraft and increases the workload of the ATCos. On the other hand, the STC approach eliminated all the shortcomings of the models mentioned above by providing shorter delays and more resilient sequences for all ROT scenarios.

As indicated in the results section, the stochastic programming approach provided an average of 0.11 and 2.9 minutes air delay and ground delay savings per aircraft, respectively, compared to the FCFS. If we assume that the arrivals are delayed at the final approach fix by using level-off flight and the departures wait at the holding point in idle configuration these delay savings correspond to approximately 4 and 18.61 kg fuel savings per aircraft, respectively. (Note that fuel calculations are carried out based on BADA 3.11 [42] considering nominal conditions and the A320 is selected as a representative of all medium type of aircraft.) The total fuel savings in an hour correspond to approximately 226 kg for 20 flight operations with a 50%–50% arrival departure rate. Considering the cumulative savings, it can be concluded that the proposed model has considerable potential for high traffic numbers in airports with backtrack procedures. If we remember the toy problem with ten aircraft, the proposed stochastic approach provided approximately 1.13 delay savings per aircraft compared to FCFS. These values indicate that the proposed approach presented efficient solutions even in low traffic numbers; however, savings of the proposed model increase as the number of aircraft increases. The proposed model also increases the on-time performance of the flights by decreasing the delay per aircraft. This may also provide increasing passenger satisfaction for airlines.

Considering the results of the STC model in the no-CPS condition and at a 20-aircraft demand, the model provided solutions for 100% of the samples without the 7-minute practical capacity saturation limit. When this traffic demand each hour for such a runway configuration is considered, these results may be found reasonable. Note also that the backtrack procedure causes high ROT, and this reduces the capacity of the runway.

Although the STC model provided better results for different ETA-D samples for no-CPS conditions, the sequences obtained by these models may not be applicable in real operational situations. To eliminate this, the constrained position shifting strategy was integrated into the models. As a result, it was found that the performance of the STC model increases as the allowed MPS increases. The STC model still provides better performance than the other models under various CPS conditions and the VSSs increase as the MPS increase in most of the CPS scenarios. STC and deterministic approaches resulted in the same delays for ETA-D samples in the 1-CPS scenario. Considering that the reasonable number of CPS is implied as three in the literature, it can be emphasised that the STC model is still advantageous compared to other models even under these CPS conditions.

The sensitivity of models to arrival/departure rates and traffic demand increase were also examined. The results indicated that the runway structure is highly sensitive to an increase in the arrival rate. The STC model still provides better or at least equal solutions for all arrival/departure rate scenarios compared to the other models. At the end of the study, we examined overcapacity conditions with scenarios increasing in 10% demand and restricting the solution time limit to 600 seconds. The STC approach provided optimal results for demand scenarios up to 24 aircraft with a 6.8-minute average delay per aircraft. The results indicated that the STC model still provides better or equal results than the other models for scenarios up to 24 aircraft per hour.

In conclusion, a stochastic approach provided better results and more robust sequences compared to deterministic and FCFS approaches for a high majority of the ETA-D samples considering various CPS, arrival rate, and traffic demand scenarios.

6.0 Limitations and future works

In this study, only medium category aircraft were considered, based on the aircraft type in our dataset. Although the ROT of arrivals can vary among the same type of aircraft, different ROT scenarios for different categories of aircraft can be integrated into the models and these may increase the sensitivity of the proposed approach. However, this requires a different case study where different categories of aircraft operations are carried out. Also, two-way operations can be considered to reflect the ROT uncertainty of departures, as well as arrivals for further analyses.

ROT predictions based on historical data can provide more efficient sequences, but the stochastic approach is still reasonable as aircraft ROTs are still uncertain due to many external factors. For example, a sequence made by estimating the ROTs of arrivals may lose its validity due to sudden changes in wind speed and/or direction. However, in the stochastic approach, sequences are presented by considering all ROT scenarios based on historical data. For this reason, in future studies, a machine learning approach for this type of airport can be developed and compared with the stochastic approach to observe the possible gains or losses of the stochastic approach.