QUEUEING MODELS FOR
4D AIRCRAFT OPERATIONSTasos Nikoleris and Mark Hansen
EIWAC 2010

Outline• Introduction• Model Formulation• Metering Case
• Ongoing Research

Time-based Operations

Time-based Operations

Time-based Operations• Aircraft execute 4D trajectories to meet Required Times of Arrival with highbut not perfect precision

Time-based Operations• Aircraft execute 4D trajectories to meet Required Times of Arrival with highbut not perfect precision• wind prediction, aerodynamic performance, etc

Time-based Operations• Aircraft execute 4D trajectories to meet Required Times of Arrival with highbut not perfect precision• wind prediction, aerodynamic performance, etc• order of ±10 seconds for a 30 min prediction horizon

Time-based Operations• Aircraft execute 4D trajectories to meet Required Times of Arrival with highbut not perfect precision• wind prediction, aerodynamic performance, etc• order of ±10 seconds for a 30 min prediction horizon➡ Delay to traverse the fix as function of precision ?

Research Goal

Research Goal
• Inputs:

Research Goal
• Inputs:- Schedule of aircraft arrivals at a fix (e.g. runway threshold)Research Goal
• Inputs:- Schedule of aircraft arrivals at a fix (e.g. runway threshold)- Capacity metric (e.g. minimum headway requirements)

Research Goal
• Inputs:- Schedule of aircraft arrivals at a fix (e.g. runway threshold)- Capacity metric (e.g. minimum headway requirements)- Precision of aircraft in flying 4D trajectories

Research Goal
• Inputs:- Schedule of aircraft arrivals at a fix (e.g. runway threshold)- Capacity metric (e.g. minimum headway requirements)- Precision of aircraft in flying 4D trajectories• Estimate queueing delay for each aircraft to cross that fix

Analytical Aircraft Queueing Models

Analytical Aircraft Queueing Models• Aggregate models derived from classical queueing theory:Analytical Aircraft Queueing Models• Aggregate models derived from classical queueing theory:- M(t)/M(t)/1 and M(t)/D(t)/1 (Koopman 1972)

Analytical Aircraft Queueing Models• Aggregate models derived from classical queueing theory:- M(t)/M(t)/1 and M(t)/D(t)/1 (Koopman 1972)- M(t)/Ek(t)/1 (Kivestu and Odoni 1976)

Analytical Aircraft Queueing Models• Aggregate models derived from classical queueing theory:- M(t)/M(t)/1 and M(t)/D(t)/1 (Koopman 1972)- M(t)/Ek(t)/1 (Kivestu and Odoni 1976)- Variance in number of arrivals is built in the modelAnalytical Aircraft Queueing Models• Aggregate models derived from classical queueing theory:- M(t)/M(t)/1 and M(t)/D(t)/1 (Koopman 1972)- M(t)/Ek(t)/1 (Kivestu and Odoni 1976)- Variance in number of arrivals is built in the model• Deterministic approachAnalytical Aircraft Queueing Models• Aggregate models derived from classical queueing theory:- M(t)/M(t)/1 and M(t)/D(t)/1 (Koopman 1972)- M(t)/Ek(t)/1 (Kivestu and Odoni 1976)- Variance in number of arrivals is built in the model• Deterministic approach- Curves of cumulative number of customers (Newell 1979)

Analytical Aircraft Queueing Models• Aggregate models derived from classical queueing theory:- M(t)/M(t)/1 and M(t)/D(t)/1 (Koopman 1972)- M(t)/Ek(t)/1 (Kivestu and Odoni 1976)- Variance in number of arrivals is built in the model• Deterministic approach- Curves of cumulative number of customers (Newell 1979)➡ Scheduled Time AdheRence (STAR) ModelAnalytical Aircraft Queueing Models• Aggregate models derived from classical queueing theory:- M(t)/M(t)/1 and M(t)/D(t)/1 (Koopman 1972)- M(t)/Ek(t)/1 (Kivestu and Odoni 1976)- Variance in number of arrivals is built in the model• Deterministic approach- Curves of cumulative number of customers (Newell 1979)➡ Scheduled Time AdheRence (STAR) Model• Each aircraft has Required Time of Arrival at serverAnalytical Aircraft Queueing Models• Aggregate models derived from classical queueing theory:- M(t)/M(t)/1 and M(t)/D(t)/1 (Koopman 1972)- M(t)/Ek(t)/1 (Kivestu and Odoni 1976)- Variance in number of arrivals is built in the model• Deterministic approach- Curves of cumulative number of customers (Newell 1979)➡ Scheduled Time AdheRence (STAR) Model• Each aircraft has Required Time of Arrival at server• Aircraft meet RTA’s with some stochastic lateness (±)

Outline• Introduction• Model Formulation• Metering Case
• Ongoing ResearchApproachApproach• Aircraft’s arrival time at the fix is normally distributed around their RTA!

&!'"% i
RTA!"#$%

Approach• Aircraft’s arrival time at the fix is normally distributed around their RTA!

&!'"% i
RTA!"#$%

Approach• Aircraft’s arrival time at the fix is normally distributed around their RTA!

&!'"% i
RTA

h
!"#$%

Approach• Aircraft’s arrival time at the fix is normally distributed around their RTA!

h&!'"% i
RTA

• First-Scheduled-First-Served (no overtakings)!"#$%

Model Formulation

Model Formulation• Assigned Scheduled Times of Arrival at a fix RTi

Model Formulation• Assigned Scheduled Times of Arrival at a fix RTi• Arrival time of aircraft i at the fix (unimpeded from queue effects) isModel Formulation• Assigned Scheduled Times of Arrival at a fix RTi• Arrival time of aircraft i at the fix (unimpeded from queue effects) is

Ai = RTi + εi ,εi ~ Normal (0, σi )Model Formulation• Assigned Scheduled Times of Arrival at a fix RTi• Arrival time of aircraft i at the fix (unimpeded from queue effects) is

Ai = RTi + εi ,εi ~ Normal (0, σi )• Minimum allowed headway at the fix hi−1Model Formulation• Assigned Scheduled Times of Arrival at a fix RTi• Arrival time of aircraft i at the fix (unimpeded from queue effects) is

Ai = RTi + εi ,εi ~ Normal (0, σi )• Minimum allowed headway at the fix hi−1
• The departure time from the fix is

Di = max(Ai , Di−1 + hi−1 )Model Formulation• Assigned Scheduled Times of Arrival at a fix RTi• Arrival time of aircraft i at the fix (unimpeded from queue effects) is

Ai = RTi + εi ,εi ~ Normal (0, σi )• Minimum allowed headway at the fix hi−1
• The departure time from the fix is

Di = max(Ai , Di−1 + hi−1 )• Queueing delay is

Wi = Di − Ai

Model Formulation• Assigned Scheduled Times of Arrival at a fix RTi• Arrival time of aircraft i at the fix (unimpeded from queue effects) is

Ai = RTi + εi ,εi ~ Normal (0, σi )• Minimum allowed headway at the fix hi−1
• The departure time from the fix is

Di = max(Ai , Di−1 + hi−1 )• Queueing delay is

Wi = Di − Ai
• How to estimate E[Di ] and Va r [Di ]?

Solution with the Clark Approximation
MethodSolution with the Clark Approximation
Method• For normal X and Y

Solution with the Clark Approximation
Method• For normal X and Y- max( X,Y ) is a non-normal random variableSolution with the Clark Approximation
Method• For normal X and Y- max( X,Y ) is a non-normal random variable• Clark (1961)

Solution with the Clark Approximation
Method• For normal X and Y- max( X,Y ) is a non-normal random variable• Clark (1961)- derives mean and variance of max( X, Y )Solution with the Clark Approximation
Method• For normal X and Y- max( X,Y ) is a non-normal random variable• Clark (1961)- derives mean and variance of max( X, Y )- approximates distribution of max( X, Y ) as normal

Solution with the Clark Approximation
Method• For normal X and Y- max( X,Y ) is a non-normal random variable• Clark (1961)- derives mean and variance of max( X, Y )- approximates distribution of max( X, Y ) as normal• Use Clark Approximation Method recursively to estimate E[Di] andVar[Di]

Accuracy of the Clark Approximation Method

Accuracy of the Clark Approximation Method• Generated a wide range of scenarios

Accuracy of the Clark Approximation Method• Generated a wide range of scenarios• Total of 120 flights with 3 classes of aircraft ( hi = 30, 60, 90 sec)Accuracy of the Clark Approximation Method• Generated a wide range of scenarios• Total of 120 flights with 3 classes of aircraft ( hi = 30, 60, 90 sec)
• Schedule flights at a fix RTi = RTi−1 + hi−1 + b

Accuracy of the Clark Approximation Method• Generated a wide range of scenarios• Total of 120 flights with 3 classes of aircraft ( hi = 30, 60, 90 sec)
• Schedule flights at a fix RTi = RTi−1 + hi−1 + b• 90 operational scenarios:Accuracy of the Clark Approximation Method• Generated a wide range of scenarios• Total of 120 flights with 3 classes of aircraft ( hi = 30, 60, 90 sec)
• Schedule flights at a fix RTi = RTi−1 + hi−1 + b• 90 operational scenarios:- 10 different sequences of hi , where each sequence is determined
randomly but given an equal mix of 30, 60, and 90 second headway values

Accuracy of the Clark Approximation Method• Generated a wide range of scenarios• Total of 120 flights with 3 classes of aircraft ( hi = 30, 60, 90 sec)
• Schedule flights at a fix RTi = RTi−1 + hi−1 + b• 90 operational scenarios:- 10 different sequences of hi , where each sequence is determined
randomly but given an equal mix of 30, 60, and 90 second headway values- b = 0, 10, and 20 seconds (held constant within each sequence)Accuracy of the Clark Approximation Method• Generated a wide range of scenarios• Total of 120 flights with 3 classes of aircraft ( hi = 30, 60, 90 sec)
• Schedule flights at a fix RTi = RTi−1 + hi−1 + b• 90 operational scenarios:- 10 different sequences of hi , where each sequence is determined
randomly but given an equal mix of 30, 60, and 90 second headway values- b = 0, 10, and 20 seconds (held constant within each sequence)- σ = 10 seconds (uniform across all aircraft), 30 seconds (uniform across all
aircraft), and an equal mix of both (with the order determined randomly)Accuracy of the Clark Approximation Method• Generated a wide range of scenarios• Total of 120 flights with 3 classes of aircraft ( hi = 30, 60, 90 sec)
• Schedule flights at a fix RTi = RTi−1 + hi−1 + b• 90 operational scenarios:- 10 different sequences of hi , where each sequence is determined
randomly but given an equal mix of 30, 60, and 90 second headway values- b = 0, 10, and 20 seconds (held constant within each sequence)- σ = 10 seconds (uniform across all aircraft), 30 seconds (uniform across all
aircraft), and an equal mix of both (with the order determined randomly)• Compared estimates of the Clark method with average of 104 Monte Carlosimulation runs

Accuracy tests of Clark Approximation Method

Accuracy tests of Clark Approximation Method

Percent Error in Total
Delay

Absolute Error in Total
Delay (sec)Absolute Error per
Flight (sec)

Buffer0 sec

Buffer Buffer Buffer
0 sec 10 sec 20 sec

Buffer Buffer Buffer
0 sec 10 sec 20 sec

Buffer Buffer
10 sec 20 sec

σ=10-0.62% -3.26% -3.93% 13.78
sec

9.17

2.97

0.14

0.09

0.08

σ=30
-0.49% -1.69% -2.41%
sec

36.5

40.92

31.17

0.35

0.35

0.31

Mix

97.26

79.53

54.07

0.89

0.65

0.44

-1.52% -5.74% -7.7%

Accuracy tests of Clark Approximation Method

Percent Error in Total
Delay

Absolute Error in Total
Delay (sec)Absolute Error per
Flight (sec)

Buffer0 sec

Buffer Buffer Buffer
0 sec 10 sec 20 sec

Buffer Buffer Buffer
0 sec 10 sec 20 sec

Buffer Buffer
10 sec 20 sec

σ=10-0.62% -3.26% -3.93% 13.78
sec

9.17

2.97

0.14

0.09

0.08

σ=30
-0.49% -1.69% -2.41%
sec

36.5

40.92

31.17

0.35

0.35

0.31

Mix

97.26

79.53

54.07

0.89

0.65

0.44

-1.52% -5.74% -7.7%

Accuracy tests of Clark Approximation Method

Percent Error in Total
Delay

Absolute Error in Total
Delay (sec)Absolute Error per
Flight (sec)

Buffer0 sec

Buffer Buffer Buffer
0 sec 10 sec 20 sec

Buffer Buffer Buffer
0 sec 10 sec 20 sec

Buffer Buffer
10 sec 20 sec

σ=10-0.62% -3.26% -3.93% 13.78
sec

9.17

2.97

0.14

0.09

0.08

σ=30
-0.49% -1.69% -2.41%
sec

36.5

40.92

31.17

0.35

0.35

0.31

Mix

97.26

79.53

54.07

0.89

0.65

0.44

-1.52% -5.74% -7.7%

Accuracy tests of Clark Approximation Method

Percent Error in Total
Delay

Absolute Error in Total
Delay (sec)Absolute Error per
Flight (sec)

Buffer0 sec

Buffer Buffer Buffer
0 sec 10 sec 20 sec

Buffer Buffer Buffer
0 sec 10 sec 20 sec

Buffer Buffer
10 sec 20 sec

σ=10-0.62% -3.26% -3.93% 13.78
sec

9.17

2.97

0.14

0.09

0.08

σ=30
-0.49% -1.69% -2.41%
sec

36.5

40.92

31.17

0.35

0.35

0.31

Mix

97.26

79.53

54.07

0.89

0.65

0.44

-1.52% -5.74% -7.7%

Outline• Introduction• Model Formulation• Metering Case
• Ongoing Research

Special case: meteringSpecial case: metering• Minimum allowed separation hSpecial case: metering• Minimum allowed separation h• How much buffer to allow between aircraft?

Special case: metering• Minimum allowed separation h• How much buffer to allow between aircraft?
✓Zero buffer

Special case: metering• Minimum allowed separation h• How much buffer to allow between aircraft?
✓Zero buffer- Efficient, but any unpunctual arrival causes delay upstream

Special case: metering• Minimum allowed separation h• How much buffer to allow between aircraft?
✓Zero buffer- Efficient, but any unpunctual arrival causes delay upstream✓Non-zero buffer

Special case: metering• Minimum allowed separation h• How much buffer to allow between aircraft?
✓Zero buffer- Efficient, but any unpunctual arrival causes delay upstream✓Non-zero buffer- Less efficient, but can absorb stochastic deviations fromschedule

Special case: metering• Minimum allowed separation h• How much buffer to allow between aircraft?
✓Zero buffer- Efficient, but any unpunctual arrival causes delay upstream✓Non-zero buffer- Less efficient, but can absorb stochastic deviations fromschedule• Stochastic deviations more costlySpecial case: metering• Minimum allowed separation h• How much buffer to allow between aircraft?
✓Zero buffer- Efficient, but any unpunctual arrival causes delay upstream✓Non-zero buffer- Less efficient, but can absorb stochastic deviations fromschedule• Stochastic deviations more costly• Trade-offs?

Special case: metering• Minimum allowed separation h• How much buffer to allow between aircraft?
✓Zero buffer- Efficient, but any unpunctual arrival causes delay upstream✓Non-zero buffer- Less efficient, but can absorb stochastic deviations fromschedule• Stochastic deviations more costly• Trade-offs?
• Total Loss = Deterministic + β * Stochastic

Queueing diagram example

Queueing diagram example!"#"$%&'()*"#+(,)-.)/$01234)

'$!"
'#!"
'!!"
N
&!"

1/a

1/h

!

+,-,./01"
23034/56"%!"

78-3.039"
C0<.;,@A.">3B,1"$!"

78-3.039":;4<=6;-=0">3?,59">3034?/5/@A.">3B,1"

#!"
!"
!"

'!!!"

#!!!"

(!!!"

$!!!"

)!!!"

%!!!"
50#()

*!!!"

&!!!"

Queueing diagram example!"#"$%&'()*"#+(,)-.)/$01234)

'$!"
'#!"
'!!"
N
&!"

1/a

1/h

!

+,-,./01"
23034/56"%!"

78-3.039"
C0<.;,@A.">3B,1"$!"

78-3.039":;4<=6;-=0">3?,59">3034?/5/@A.">3B,1"

#!"
!"
!"

'!!!"

#!!!"

(!!!"

$!!!"

)!!!"

• Deterministic ~ N2, Stochastic ~ N

%!!!"
50#()

*!!!"

&!!!"

Model formulation

Model formulation• Insert buffer b between consecutive arrivals

Model formulation• Insert buffer b between consecutive arrivals• Standard Deviation of σ seconds for adherence error distribution

Model formulation• Insert buffer b between consecutive arrivals• Standard Deviation of σ seconds for adherence error distribution• Stochastic Delay Wi :

Model formulation• Insert buffer b between consecutive arrivals• Standard Deviation of σ seconds for adherence error distribution• Stochastic Delay Wi :- Showed that Wi = σ · Zi

Model formulation• Insert buffer b between consecutive arrivals• Standard Deviation of σ seconds for adherence error distribution• Stochastic Delay Wi :Delay to i th flight when σ =1

- Showed that Wi = σ · Zi

Model formulation• Insert buffer b between consecutive arrivals• Standard Deviation of σ seconds for adherence error distribution• Stochastic Delay Wi :Delay to i th flight when σ =1

- Showed that Wi = σ · Zi
• Total expected loss in efficiency for N flights:

E [L] =

�

1/2 · (N − 1) · N · ∆ + β ·

N
�
i=1

�

E [Zi ]·σModel formulation• Insert buffer b between consecutive arrivals• Standard Deviation of σ seconds for adherence error distribution• Stochastic Delay Wi :Delay to i th flight when σ =1

- Showed that Wi = σ · Zi
• Total expected loss in efficiency for N flights:

E [L] =• Normalized buffer�

1/2 · (N − 1) · N · ∆ + β ·∆ = b/σ

N
�
i=1

�

E [Zi ]·σ

Total Loss in Efficiency for 20 Flights

Total Loss in Efficiency for 20 Flights

Total Loss in Efficiency for 20 Flights

b=5, σ=10, β=1
Δ=0.5

Total Loss in Efficiency for 20 Flights

b=5, σ=10, β=1
Δ=0.5

Total Loss in Efficiency for 20 Flights

b=5, σ=10, β=1
Δ=0.5

Total Loss in Efficiency for 20 Flights

Total Loss in Efficiency for 20 Flights

Total Loss in Efficiency for 20 Flights

Optimal Buffers

Optimal Buffers

Outline• Introduction• Model Formulation• Metering Case
• Ongoing Research

Paired Arrivals at SFO

Paired Arrivals at SFO

Paired Arrivals at SFO

Paired Arrivals at SFO• Situation of heavy traffic for landings
and take-offs

Paired Arrivals at SFO• Situation of heavy traffic for landings
and take-offs• Today: Controllers “guide” aircraft tomerging point (5 nmi from 28R)

Paired Arrivals at SFO• Situation of heavy traffic for landings
and take-offs• Today: Controllers “guide” aircraft tomerging point (5 nmi from 28R)
• NextGen: Aircraft assigned RTA’s atmerging point and descend to therunwayPaired Arrivals at SFO• Situation of heavy traffic for landings
and take-offs• Today: Controllers “guide” aircraft tomerging point (5 nmi from 28R)
• NextGen: Aircraft assigned RTA’s atmerging point and descend to therunway• What is optimal metering headway?

ApproachApproach• Find headway between pairs at the merging point:

Approach• Find headway between pairs at the merging point:- Enough time between arrival pairs for a departure pair

Approach• Find headway between pairs at the merging point:- Enough time between arrival pairs for a departure pair
- Not excessive time separation, resulting in efficiency loss

Approach• Find headway between pairs at the merging point:- Enough time between arrival pairs for a departure pair
- Not excessive time separation, resulting in efficiency loss
• Avoid:

Approach• Find headway between pairs at the merging point:- Enough time between arrival pairs for a departure pair
- Not excessive time separation, resulting in efficiency loss
• Avoid:

Approach• Find headway between pairs at the merging point:- Enough time between arrival pairs for a departure pair
- Not excessive time separation, resulting in efficiency loss
• Avoid:Thank you!

Thank you!

Questions?