Impact of Departure Time Uncertainty on Runway Scheduling

，，，

College of Civil Aviation，Nanjing University of Aeronautics and Astronautics，Nanjing 211106，P.R.China

（Received 30 October 2020；revised 5 December 2021；accepted 16 December 2021）

Abstract:The flight departure process is affected by various uncertain factors，such as flight delays，scheduling delays and taxi time etc.A reliable and robust departure sequence is very important to the safe and efficient operation for airports.An optimal scheduling model for multi-runway departure considering the arrival aircraft crossing departure runway is developed.A genetic algorithm encoding flight numbers is designed to find a near-optimal solution.After that，further establish a multi-objective dynamic scheduling model and design a hybrid algorithm to solve it，and compare and analyze the results of the two models.A quantitative analysis of departure time based on the kernel density estimation is performed，and Monte Carlo simulations are carried out to explore the impact of flight departure time’s uncertainty on departure scheduling.The results based on historical data from Guangzhou Baiyun Airport are presented，showing the advantage of the proposed model and algorithm.

Key words：uncertainty；departure scheduling；multi-runway scheduling；genetic algorithm

0 Introduction

Runway system is the most critical resource in airports，which typically sets the upper bound of airport movements.Reasonable arrangements of the sequence of landings and takeoffs at runway can significantly improve the safety and efficiency of airport operation.Therefore，the runway scheduling has been an important research topic in air transportation field.

A great amount of research works have been done，which address various types runway scheduling，including optimal operation research on approaches runway，departure runway，and mixed runway for approaches and departures.For instance，Gupta et al.［1］established a mixed-integer linear programming model to optimize flight departure time.Xu et al.［2］proposed a dynamic scheduling model for sequencing arrivals and departures of multi-runway.Hu et al.［3］developed a high-efficiency genetic algorithm to schedule the transportation.Zhang et al.［4-5］established a multi-objective optimization algorithm for the aircraft scheduling based on receding horizon，and an optimization algorithm for multi-runway takeoff and landing scheduling.Ma et al.［6］designed an ordering method of combined arrival and departure scheduling for multi-airport system.

Although the studies on runway scheduling in deterministic scenarios have been extensive，there are few investigations on the optimization of runway scheduling under uncertainies such as weather and inbound delays.Robust optimization and stochastic optimization have been applied in this field.For example，Heidt et al.［7］applied a robust optimization algorithm for runway scheduling under uncertainty.Ng et al.［8］proceeded robust scheduling to the flights with arrival or departure delay，based on an artificial bee colony algorithm.

More specifically，few studies consider the arrival flight’s situation crossing the departure runway while optimizing departure flights.Avella et al.［9］developed an integer programming model considering the influence of arrival flights.Ma et al.［10］established a scheduling optimization model for departure runway in the arrival port.Gupta et al.［11］used a mixed-integer linear program to determine aircraft’s takeoff and landing time.They also analyzed the impact of departure time uncertainty on departure scheduling based on the assumed probability distribution of departure time uncertainty［12］.

A departure scheduling model considering arrival flights crossing the departure runway is proposed in this paper.A genetic algorithm is designed to obtain the reasonable solutions.The characteristics of flight departure time uncertainty are captured based on historical data.The Monte-Carlo simulation is performed to analyze the impact of departure time uncertainty on departure scheduling.Two different scheduling strategies for departure scheduling are compared and analyzed.

1 Model Formulation

The focus of this article is to optimize departure flights at airports with multiple parallel runways.In the multi-runway model assumed in this article，each runway may have arrival and departure flights，and flights from adjacent runways that cross after landing.Therefore，on each runway，there are three kinds of flight scheduling conditions considering the arrival，departure，and crossing flights.Due to scheduling costs，we fix the arrival flight and only schedule the departure and crossing flights.

1.1 Variables definition

The relevant notations in the model are defined as follows.

A：The set of all arriving flights；

D：The set of all departing flights；

C：The set of all the arrival flights crossing the departure runway；

F：The set of all flights；

RC：The runway that can be passed through by the approaching flight；

R：The collection of all runways；

Cr：The corresponding capacity of the runway allocated for the flight；

λir：When the arrival flighti’s arrival runway isr，λir=1，otherwiseλir=0；

sij：Under windless condition，the minimum wake turbulence separation between flightiand flightj，on the same runway，flightiis in front of flightj；

oi：The time occupied by the arrival flightipassing through the departure runway，i∈C；

Tmax：The maximum delay time for departure flights；

Tpi：The estimated time for flightiusing runway；

M：A large number.

The model decision variables are defined as follows.

Tai：Flighti’s actual departure/arrival time/the starting time crossing the departure runway；

xir：When flightiis allocated to runwayrfor departure，xir=1，otherwisexir=0；

wir：When arrival flighticrosses runwayr，wir=1，otherwisewir=0，i∈C；

yij：When flightsiandjare allocated to the same runway，yij=1，otherwiseyij=0；

δij：When flightiis arranged in front of flightj，δij=1，otherwise，δij=0；

uij：When flightipasses through the runway as same as flightj’s departure or arrival one，uij=1，otherwiseuij=0，i∈C，j∈F.

1.2 Objective and constraints

The objective of the model is to minimize flight delays，which can be given as min

The constraints of the model are listed below.

Eq.（1）means that the sum of departure delay and transit delay caused by scheduling is the smallest.Eq.（2）ensures that each departing flight can only be allocated to one runway.Eq.（3）means that the runway of the arrival flight is specified，and does not need to be allocated.Eq.（4）considers that the flight that needs to cross the departure runway only can cross the specified runway that can be crossed，and each flight can only cross one runway.Eq.（5）states that the arrivals and departure cannot exceed runway capacity.Eq.（6）describes the uniqueness of flights order.Eq.（7）means that the wake turbulence separation between different flights on the same runway.Eqs.（8）and（9）require only when both flightsiandjare allocated to one runway，yijis 1，otherwise it is 0.Eq.（10）means that when flights on other runways need to cross the runway，the interval between departure time of the departure flight and the time that the arrival flight begin to cross the runway should be greater than or equal to the time of flights occupying the runway when the flight crosses the runway.Eqs.（11）and（12）require that only when the runway crossed by flightiand the runway is used by flightjare the same，uijis 1，otherwise it is 0.Eq.（13）represents the time interval constraint when two crossing flights cross the same runway one after the other.Eqs.（14）and（15）stipulate that only when the runway crossed by flightiis the same as the runway crossed by flightjon the runway，vijis 1，otherwise it is 0.Eq.（16）means that the maximum delay time constraint for departing flights.Eq.（17）requires the actual time of using the runway should not less than the expected time of using the runway.Eq.（18）requires flights’actual arrival time is equal to the estimated arrival time，that is，the arrival flight will not be scheduled.Eq.（19）stipulates that the actual time to cross the runway shall not be less than the estimated time to cross the runway.Eq.（20）means the value range of decision variables.

1.3 Dynamic model

On the basis of the deterministic model established above，the uncertain flight departure delay is introduced as a random variable，and a dynamic multi-objective flight scheduling model with uncertainty is established.After introducing uncertain flight departure delay as a random variable，flight departure time is no longer a certain value.In order to take into account the efficiency and robustness of the model，the objective function is considered to be the weight of the minimum total delay time of the scheduling result and the minimum total time of the scheduling result change.The weight ratio is set to 0.5 for each of the two objective functions.The weight coefficient can be determined by the specific airport.The actual situation is adjusted.

The following variables to the deterministic model are added.

：The random delay of thekth disturbance flight；

N：The number of disturbances by adding random delays to the scheduled flight，kis the index of disturbance，k=1，2，…，N；

：The estimated departure/arrival time after adding random delay for thekth time；

：The estimated starting time of the flight crossing the runway after thekth random delay is added，i∈C；

：The actual departure/arrival time of the flight after thekth random delay is added；

：The actual starting time of the flight crossing the runway after thekth random delay is added，i∈C.

In the dynamic model，the first objective function is the minimum total delay time.

The second objective function is to minimize the total time of scheduling changes.

Due to the addition of variables such as estimated take-off time after delay，the constraints of the dynamic model are the constraints of the deterministic model and the set of the following constraints.

Eq.（21）is the objective function that minimizes the total delay of scheduling results before disturbance.Eq.（22）is the objective function that minimizes the total time between the scheduling result and the original scheduling result after the disturbance.Eq.（23）is expressed as the original planned departure time of flightifor thekth disturbance and a random delay disturbance is added to obtain the new planned departure time under uncertain conditions.Eq.（24）is expressed as the original planned crossing time of flightifor thekth disturbance，adding a random delay disturbance to obtain the new planned crossing time under uncertain conditions.Eq.（25）is the wake turbulence separation between consecutive flights on the same runway.Eq.（26）means that when flights after disturbance on other runways need to cross the runway，the interval between departure time of the departure flight and the time that arrival flight begin to cross the runway should be greater than or equal to the time of flights occupying the runway when the flight crosses the runway.Eq.（27）represents the time interval of two transiting flights crossing the same runway after disturbances.Eq.（28）stipulates the maximum delay time for departing flights after the disturbance.Eq.（29）stipulates that the actual take-off time after disturbance is not less than the estimated take-off time after disturbance.Eq.（30）stipulates that the actual arrival time after disturbance of the arrival flight is equal to the expected arrival time after the disturbance，that is，the arrival flight after the disturbance is not allocated.Eq.（31）stipulates that the actual runway crossing time after the disturbance is not less than the expected runway crossing time after the disturbance.Eq.（32）specifies the value range of decision variables after disturbance.

2 Algorithm Design

2.1 Genetic algorithm

To solve the model，the following genetic algorithm is proposed.

（1）Coding：This paper codes a series of departing flights based on real number coding.Here，the serial number of code represents the flight position in the queue.The coding example is shown in Fig.1.

Fig.1 Flight coding method

（2）Initialization：The paper randomly generates a sequence of departure flights ofNflights，repeating this processptimes to generate an initial population ofP，and set the number of the initial population as 10.

（3）Selection：The paper chooses the individuals in the population by Roulette.The probability of an individual being selected in this way is proportional to its fitness function.Therefore，individuals with the highest fitness are most likely to be selected for reorganization.At the same time，by adopting the optimal preservation strategy，the individual in the top 20% will be kept in every generation，and the rest will be replaced by the new generation of individuals.

（4）Crossover：This paper randomly selects the truncation point，cutting and re-configuring，and then conducts the collision detection for children after the crossover.If there are conflicts in the crossover，we will process a mapping until no conflict occurs.The diagram is shown in Fig.2.

Fig.2 Flight coding method

（5）Mutation：Since the departing flight is coded with real numbers，the paper conducts a real-value variation method.In order to ensure the feasibility of solutions，when the variation occurs，two variate positions’genes will be swapped.

（6）Fitness function：This paper takes the inverse of the objective function as the fitness function，showing that the shorter the total delay time of the departing flight on the ground，the higher the fitness value.The fitness value during multiple iterations determines the performance of the feasible solution of the population.

2.2 Hybrid algorithm

In the dynamic model，the flight departure time is an uncertain value.So in order to resist the influence of this uncertainty on flight scheduling，it is decided to use a hybrid optimization algorithm combining genetic algorithm and sampling average approximation to solve the problem.The coding，initialization，selection，crossover，and mutation methods of the hybrid algorithm are the same as the genetic algorithm.The fitness function is the reciprocal of the weighted sum of the objective function with the smallest total delay time and the objective function with the smallest total time considering the scheduling change.Based on this idea，a hybrid algorithm framework is designed as shown in Fig.3.

Fig.3 Hybrid algorithm flow-process

According to the algorithm framework，the specific algorithm steps can be listed as follows.

（1）Get the scheduled departure time of the flight from the flight information，and get the initial flight sequence and flight scheduling time.

（2）Substitute the initial departure order into the sampling average approximation method，add random delay disturbance to the original departure time to obtain a new planned departure time，and use the first come first serve（FCFS）method for the new planned departure time to obtain a new actual departure time and the total time value of scheduling change under disturbances.

（3）Repeat step（2）to add delay disturbances for multiple times，and take the average of the total time of scheduling change obtained each time.

（4）Determine whether the average value of the total time of scheduling changes obtained in step（3）is ideal.If it is ideal，output the flight sequence and actual departure time.If not ideal，return to continue to cross and mutate to find other solutions iteratively until the termination condition is met.The termination condition of the hybrid algorithm is also the minimum fitness function.The fitness function is the weight of the minimum total delay time of the scheduling result and the minimum total time of the scheduling result change.The weight ratio is set to 0.5 for each of the two objective functions.The weight coefficient can be specified.The actual situation of the airport is adjusted.

3 Analysis of Impact of Departure Time Uncertainty on Departure Scheduling

In the deterministic model of departure scheduling，the planned departure time is a deterministic value.However，it is not in actual operation，and it would change due to various uncertain factors.By comparing the optimal scheduling results before and after the departure time that is affected by uncertainty disturbances，we can further explore the impact of departure time uncertainty on departure scheduling.

This paper superposes a random variable disturbed value on the originally planned departure time to simulate the flight departure time under the influence of uncertainty.The random variable disturbed value is obtained by fitting the probability distribution to the actual flight departure delays in historical data.When the departure time occurs disturbances，the reschedule strategy under FCFS is as follows.Based on the time after disturbances，in the order of FCFS，generate new departure time after scheduling.Based on the optimization of model and algorithm，the new scheduling strategy is as follows.Keep the calculated flights’departure order under the original plan’s departure time.According to the departure time after disturbances occurred，satisfy the requirement of the interval to carry out new scheduling.And then generate the departure time in the new scheduling.

Taking the model and algorithm built up in this article，the scheduling result generated based on the planned departure time isDMU，and the dynamic rescheduling result based on the departure time after disturbance isDMP.Using dynamic models，the scheduling result generated based on the planned departure time isTMU，and the dynamic rescheduling result based on the departure time after disturbance isTMP.

The difference value of the total delay time before and after rescheduling is used as a predictability index of the scheduling results under the two deterministic scheduling methods.The calculation formulas are as Eqs.（33）and（34）.The predictability index is used to compare the two scheduling methods affected by uncertainty.The lower the predictability index，the less affected by uncertainty.

4 Simulation Results

4.1 Deterministic departure scheduling model and simulation verification algorithm

This paper uses a genetic algorithm to simulate and verify Guangzhou Baiyun Airport’s flight departure scheduling.The algorithm is implemented with MATLAB.The initial population size is 20，the educational generation is 100 generations，the crossover probabilityPc=0.8，and the mutation probabilityPm=0.1.

The runway structure of Guangzhou Baiyun Airport consists of three parallel runways.From north to south，there are runways 01/19，02L/20R，02R/20L，in which runway 01/19 has both arrival and departure flights，and 02L/20R has only departure flights，but there will be arrival flights from runway 02R/20L to cross.Runway 02R/20L only has arrival flights，which will not be considered in the departure flight schedule.The runway diagram of Guangzhou Baiyun Airport is show in Fig.4.

The wake turbulence separationsijis determined by the leading aircraft model and the following aircraft，and the way of take-off and landing.There are four types of aircraft for landings and departures：A380-800 model aircraft（380），the heavy aircraft（H），medium aircraft（M），and light aircraft（L）.According to Guangzhou Baiyun Airport’s operation manual，the wake turbulence separation is shown in Table 1.

Fig.4 Baiyun Airport’s runway structure diagram

Table 1 Wake turbulence separations for different aircraft min

There are 20 flights scheduled from 10：00 to 10：20 on one day at Baiyun Airport，and flight information is shown in Table 2.The aircraft with the initial A indicates that it is an arrival flight，and the aircraft with the initial D indicates that it is a departure flight.The arrival flight for crossing is abbreviated as C，and the crossing interval is one minute.

Table 2 Flights information

Based on the FCFS rule，it is common that arrival flight enjoys higher priority than departure one.The subsequent airplanes line up according to the priority principle and keep the wake turbulence separation.In order to validate the model，the departure flights are scheduled through the genetic algorithm and FCFS rules，respectively.The results are shown in Table 3.

Table 3 FCFS and the time of genetic algorithm scheduling

Based on Tables 2 and 3，the total delay time is calculated to be 49 min by using FCFS method.The total delay time generated by the genetic algorithm designed is down to 28 min，decreased by 21 min（43%）compared with FCFS.

4.2 Departure time uncertainty effect simulation

4.2.1 Probability distribution of departure delay

Firstly，the flight departure delay of Baiyun Airport is obtained based on the historical operation data of the airport.We select the delay time in the busy time period of 10：00 to 10：20 and fit the probability distribution to flight departure time.It is found that delay time is fitted neither by the normal distribution nor exponential distribution.In this case，we use the non-parametric estimation’s kernel density estimation to fit the probability distribution function of departure delay［3］.The probability density curve obtained by the kernel density estimation is shown in Fig.5.

Fig.5 Kernel density of departure delay time in 10:00-10:20

To carry out the Monte-Carlo simulation of the uncertainty impact on departure scheduling，it is necessary to obtain random numbers conforming to the fitted departure delay probability distribution，use the inverse function combined with linear interpolation to generate approximate random numbers，and then get a set of departure time after disturbances［13］.The departure time after disturbances is shown in Table 4.

Table 4 Flight information after disturbances

4.2.2 Simulation analysis of uncertainty influence

The departure time after the disturbance is scheduled separately by two scheduling strategies.The scheduling change time represents the changed departure time after the disturbance under the dynamic rescheduling compared to the original scheduling time.A negative number means that the time is advanced，and a positive one indicates that the time is delayed.We choose the two scheduling methods’simulation results under the same set of disturbance data for presenting，which are shown in Table 5.The predictive index value using the dynamic models and hybrid algorithm is 24.The predictive index value is 50 using the proposed model and algorithm.

Table 5 Scheduling time comparison between genetic algorithm and FCFS

Carrying out Monte-Carlo simulations for many times，the box plots of genetic and hybrid algorithms about the total time of scheduling changes are show in Fig.6.It can be seen from Fig.6 that the distribution range of the total time of genetic algorithm scheduling changes is 35—90 min，in which 75% of the results are less than 70 min，and the average is about 55 min.The total time distribution of the scheduling change of the hybrid algorithm is 5—40 min，in which 75% of the results are less than 30 min，and the average is about 25 min.The average value，range，and median line of the total time of scheduling changes under the hybrid algorithm are smaller than those of under the genetic algorithm method，showing that the scheduling results of the multi-objective dynamic scheduling model using the hybrid algorithm have smaller changes and higher predictabilities.

Fig.6 Comparison of Monte-Carlo simulation results in box plots

5 Conclusions

A multi-runway departure optimal scheduling model considering arrival flights crossing the departure runway is established.A genetic algorithm and a hybrid algorithm are designed to solve the model.The Monte-Carlo simulation is performed to study the influence of departure time uncertainty on three departure schedule strategies.The predictabilities of the three schedule methods under the influence of uncertainty are compared and analyzed.

There are many uncertain factors affecting the flight departure time，including the time to release chocks，taxing time，grounding holding policy imposed，etc.This paper analyzes how the uncertainty of departure time affects departure scheduling based on the development of an optimization model，a genetic algorithm，and a hybrid algorithm based on the FCFS principle.

In future research，various uncertain factors that affect different departure phases shall be considered.Thus，stochastic programing or robust optimization can be employed to provide more reliable and efficient departure sequences.