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. [Reference Bosson and Sun20] that considers arrival and departure mixed operations, and calculates the capacity as the inverse of the separation time, between two consecutive aircraft [Reference Di Mascio, Rappoli and Moretti28]. 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 [Reference Balakrishnan and Chandran9]. In literature, the feasible maximum position shifting in TMA is considered as 3 from FCFS in most studies [Reference Balakrishnan and Chandran9], [Reference Dear10], [Reference Hong, Cho, Kim and Choi29], [Reference Lee and Balakrishnan30]. 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.1 Two-stage stochastic programming

Uncertainties in the air traffic system lead to deviations from the actual plan or schedule [Reference Kapolke, Fürstenau, Heidt, Liers, Mittendorf and Weiß31], [Reference Heidt, Helmke, Kapolke, Liers and Martin32]. The two-stage stochastic programming approach, however, provides robust, and better or equal (at least) solutions than deterministic approaches under conditions of uncertainty [Reference Cecen, Cetek and Kaya11]. 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) [Reference Birge and Louveaux33].

(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 [Reference Birge and Louveaux33].

We adopted a scenario-based stochastic optimisation approach, which was initially proposed by Ref. Reference Dantzig34, to generate different sets of variables for each scenario S [Reference Kaya, Bagci and Turkay35]. 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) [Reference Shapiro and Philpott36].

(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 [Reference Cecen, Cetek and Kaya11]. 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) [Reference Birge and Louveaux33].

(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], [Reference Dönmez, Çetek and Kaya38]. 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.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 [Reference Bubalo and Daduna41]. 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.