Airline Operations
Lecture #2
1.206J
April 27, 2003
Summary Lecture #1
? Airline schedules (Aircraft, crew,
passengers) are optimized leading to:
GBE Little slacks (idle time)
GBE Schedule dependencies
GBE Delay chain effects
Causes of schedule disruptions
GBE Shortages of airline resources
GBE Shortages of airport resources
Complex airline resource regulations
GBE Aircraft maintenance
GBE Pilots
Airline Schedules Recovery
GBE Schedule Recovery Model (SRM)
GBE Aircraft Recovery Model (ARM)
GBE Crew Recovery Model (CRM)
GBE Passenger Flow Model (PFM)
GBE Journey Management
GBE Passenger Re-accommodation
G36G35G30
G24G24G35G35G30G30 G26G26G35G35G30G30 G33G33G29G30G29G30
G33G44G56G33G44G56G56G56G48G51G4AG48G48G51 G48G55
G55G35G48G35G48G44G44G46G46G46G52G50
G46G52G50G50G50G52G47G52G47G44G44G57
G57G4CG4CG52G52G51G51
Summary Lecture #1 (Cont.)
Airline schedules recovery problems
GBE Aircraft maintenance module:
Objective: feasibility only
GBE Crew schedule recovery module
Objective: to minimize disruptions, recover the disrupted
with minimum flight schedule disruptions and control
Flight Time Count
Complex rules
GBE Passenger schedule recovery module
Objective: to minimize passenger delays, ill will, gap
between expected and delivered service
Complexity:
– Priority rules (booked over disrupted, priority among
disrupted: network, user, FFP, fare class)
– Seat availability uncertainty
Lecture #2 Outline
Passengers are important to satisfy
Tricks to prevent schedule disruptions and recover schedules
Traditional ARM; Model shortcomings
Interdependency of passengers and aircraft operations
Our approach: Minimizing sum of disrupted passenger
Flight copy generation and solution feasibility
Minimizing sum of passenger delays
Proxy of minimizing sum of passenger delays
Simulation environment
Conclusion
Importance of delivering services
as expected in airline industry
Very competitive industry
Low profit margin (5% in 2000, best year)
Dissatisfied customers might shop next to
competitors, jeopardizing your profitability
On time service is not prime factor to attract
customers but it contributes to loyalty
Passenger delay distribution is not continuous, few
passengers suffer high delays
Passenger dissatisfaction function with respect to
delays is not linear
Clear objective: minimize passenger ill will with
same operations costs
Trade off: Passenger service
reliability versus operating costs
Operating costs
Passenger
dissatisfaction
Admissible operating cost region
Feasible operating space
G36G52G55G57 G2F G44G46G46G52G55G47G4CG51G4A G57G52 G56G48G55G59G4CG46G48G53G52G4FG4CG46G5C
G27G4CG56G55G58G53G57G48G47G22
G3CG48G56 G31G52
G35G48G50G52G59G48G56G48G44G57 G49G55G52G50 G55G48G50G44G4CG51G4CG51G4AG4CG51G59G48G51G57G52G55G5C
G37G44G4EG48G51G48G5BG57 G47G4CG56G55G58G53G57G48G47G53G44G56G56G48G51G4AG48G55 G4CG51 G2F
G35G48G50G52G59G48G56G48G44G57G56G49G55G52G50 G55G48G50G44G4CG51G4CG51G4AG4CG51G59G48G51G57G52G55G5C
G24G56G56G4CG4AG51G44G4FG4F G51G52G51G10G47G4CG56G55G58G53G57G48G47 G53G44G56G56G48G51G4AG48G55G56
G57G52G57G4BG48G4CG55 G53G4FG44G51G51G48G47G4CG57G4CG51G48G55G44G55G4CG48G56
G25G58G4CG4FG47G57G4BG48G4FG4CG56G57G52G49G47G4CG56G55G58G53G57G48G47
G53G44G56G56G48G51G4AG48G55G56G0F G2F
G29G4FG4CG4AG4BG57 G47G48G4FG44G5CG56G44G51G47 G49G4FG4CG4AG4BG57 G46G44G51G46G48G4FG4FG44G57G4CG52G51G56
G33G44G56G56G48G51G4AG48G55 G45G52G52G4EG4CG51G4AG56 G49G52G55 G48G44G46G4B G56G46G4BG48G47G58G4FG48G47 G4CG57G4CG51G48G55G44G55G5C
G2CG56 G2F G20G91 G22
G3CG48G56
G31G52
G28G31G27
G35G48G46G52G55G47 G53G44G56G56G48G51G4AG48G55 G47G48G4FG44G5C
G29G4CG51G47G45G48G56G57 G55G48G46G52G59G48G55G5CG4CG57G4CG51G48G55G44G55G5CG44G51G47G44G56G56G4CG4AG51G53G44G56G56G48G51G4AG48G55
G33G44G56G56G48G51G4AG48G55 G27G48G4FG44G5C G36G57G44G57G4CG56G57G4CG46G56
G2CG31G33G38G37G36
G33G35G28G33G35G32G26G28G36G36G2C
G31G2A
G33G27G26
G35G48G46G52G55G47 G53G44G56G56G48G51G4AG48G55 G47G48G4FG44G5C
Flight and passenger delays
0
5
10
15
20
25
30
(
m
i
nut
e
s
)
Passengers
Flight Delay
Flight delays underestimate passenger delays
Key explanation lies in the disrupted passengers
Passenger/flight = 170%
Disrupted passengers versus non disrupted
passengers
GBE Disrupted passengers experience long delays in general because 20%
of them are stranded overnight (delay propagation results in more
disruptions later during the day)
GBE Although a small percentage, disrupted passengers account for 40%
of the total passenger delay and most of the severely delayed
passengers (80% of passengers delayed by more than 4 hours)
Non disrupted
passengers
Disrupted
passengers
August 2000
60%96.8%16 minutes
40%3.2%320 minutes
% Delays% Passengers
Av. Delay
(minutes)
Risk of being disrupted
GBE Although fewer planned connecting passengers, higher
number are disrupted
GBE The risk of a passenger to be disrupted is 2.75 times
greater for connecting (5.5%) than for local (2%)
GBE Does not bode well for hub-and-spoke with banks
100%52%Caused by flight cancellations
40%60%Disrupted passenger mix
Caused by missed connections
Scheduled passenger mix
Passenger type
48%
65%35%
LocalConnecting
Passenger disruption: important factors
Disruption time & Route frequency
R
2
= 0.93
0
2
4
6
8
10
12
14
16
8 1012141618202 24
disruption time in window (+/- 1hour)
A
v
er
age del
ay
of
t
he
di
s
r
upt
ed
pas
s
enger
s
(
hour
s
)
G35G15G20G13G11G1CG18
G13
G14
G15
G16
G17
G18
G19
G1A
G1B
G1C
G15G16G17G18G19G1AG1BG1CG14G13G14G14G14G15
G52G51 G55G52G58G57G48G56 G5AG4CG57G4B G49G55G48G54G58G48G51G46G5CG21G20
G24G59
G27
G48
G4F
G44
G5C
G52
G49
G47
G4C
G56G55G58
G53G57
G48
G47
G53G44
G56G56
G48
G51
G4A
G48
G55G56
G0B
G4B
G52
G58
G55G56G0C
Passenger service reliability study:
Conclusions
Disrupted passengers are
important: 80% of the passengers
delayed by more than 4 hours are
disrupted
Minimizing the sum of disrupted
passengers while recovering the
schedule might be a good idea…
Resource Dependability: Ripple effects
Source: Sabre, 1998
DFW-LAX
LAX-ONT
DFW-SNA
LAX-SMF
PC
CC
A
PC
CC
A
Cockpit Crew rest at SMF
SNA-SJC
SNA-RNO
SNA-SEA
SMF-LAX
ONT-LAX
Aircraft
maintenance at
ONT
PC
CC: deadheading
A
PC: Pilot Crew; CC: Cabin Crew; A: Aircraft
Disruption Impacts; Solutions and Constraints
Flight delays
Broken crew pairings
Resource shortage
Crew unavailability
Disrupted maintenance
Gate problems
Baggage handling
problems
others
? Hold flights
Cancel flights
Aggregate flights
Divert aircraft
Swap resources
Use spare aircraft
Use reserve crews
Deadhead crews
Layover crews
Aircraft balance
Market protection
Fleet/crew
compatibility
Resource positioning
Maintenance
requirements
Crew legalities
Union contracts
Others
Disruption Impacts Solutions Constraints
Disruption Impacts; Solutions and Constraints
Flight delays
Broken crew pairings
Resource shortage
Crew unavailability
Disrupted maintenance
Gate problems
Baggage handling
problems
others
Hold flights
Cancel flights
Aggregate flights
Divert aircraft
Swap resources
Use spare aircraft
Use reserve crews
Deadhead crews
Layover crews
Aircraft balance
Market protection
Fleet/crew
compatibility
Resource positioning
Maintenance
requirements
Crew legalities
Union contracts
Others
Disruption Impacts Solutions Constraints
Aircraft route swaps
Swapping useful to:
+ Spread the delays informally, converge toward bank integrity
+ Postpone the shortage problem
+ Recover from irregularities
Constraints: Crew compatibility and legalities
A1;F1
A2;F2
A3;F3
A1;F3
A2;F1
A3;F2
Schedule Swapping
time time
Delay F1
Delay F2
Delay F3
No Swapping
A3;F3
A1;F1
A2;F2
SCHEDULE
time
BOS
EWR
ORD
MIA
IAH
HYPOTHETICAL CASE: Flights not canceled (NC)
time
BOS
EWR
MIA
IAH
ORD
ACTUAL OPERATIONS
time
BOS
EWR
ORD
MIA
IAH
ACTUAL OPERATIONS: Flights canceled (C)
time
BOS
EWR
MIA
IAH
ORD
Flight cancellation benefits passengers
when…
time
BOS
EWR
MIA
IAH
ORD
Low loads in canceled flights
Strong down line
Passenger disruptions
Severe delay
But often crew disruptions…
Unless canceled flights
belong to the same crew duty
sequence
Airline Schedule Recovery Problem:
Assumptions
At a given time of the day, we assume
that airline controllers know the state
of the system:
GBE Locations and availability of resources
Aircraft
Pilot and flight attendant crews
GBE Passenger states (i,e., disrupted or not) and
locations/destinations
Airline Recovery Model, ARM
(G. Yu et al.)
tt
ff ff
fFtT fF
f
t
ff
tT
f
tt tt
ff ff
fF fF
dj oj
00
ff 0
0
fF
oj
__
ff
_
fF
dj
min d x c z
st :
xz1
xy xy
xy j
xy
Flight coverage
Aircraft balance
Initial resource at ai
Ops cost + Cancellatio
rports
n cost
∈∈ ∈
∈
?+
∈∈
+
∈
?
∈
??
×+ ×??
??
+=
+= +
+=
+
∑∑ ∑
∑
∑∑
∑
∑
tt
ff
j
x{0,1};y0
End of the day resource at airports
?
=
∈≥
Objective is to minimize operating cost
(flight delay and cancellation costs)
Aircraft route schedule
S1
H
S2
Aircraft A
Aircraft B
Aircraft actual operations: unexpected delay
(e.g., aircraft technical problem)
S1
H
S2
delay
Aircraft A
Aircraft B
Passenger actual itineraries Operations decision #3:
don’t cancel & postpone aircraft B
S1
H
S2
delay
Aircraft A
Aircraft B
Flight copy generations
We have developed a technique to
minimize the number of flight copies
Flight copy generations
We have developed a technique to
minimize the number of flight copies
Four types of flight copies are generated:
GBE Aircraft ready times
S3
H
S2
S1
Flight copy generations
We have developed a technique to
minimize the number of flight copies
Four types of flight copies are generated:
GBE Aircraft ready times
GBE Copies to prevent passengers from missing
connections
S3
H
S2
S1
Flight copy generations
We have developed a technique to
minimize the number of flight copies
Four types of flight copies are generated:
GBE Aircraft ready times
GBE Copies to prevent passengers from missing
connections
GBE Consequence of type 2, aircraft postponement
propagation
S3
H
S2
S1
Flight copy generations
We have developed a technique to
minimize the number of flight copies
Four types of flight copies are generated:
GBE Aircraft ready times
GBE Copies to prevent passengers from missing
connections
GBE Consequence of type 2, aircraft postponement
propagation
GBE Schedule (for cancellations)
S3
H
S2
S1
Flight copy generations
We have developed a technique to minimize the number of
flight copies
Four types of flight copies are generated:
GBE Aircraft ready times
GBE Copies to prevent passengers from missing connections
GBE Consequence of type 2, aircraft postponement propagation
GBE Schedule (for cancellations)
Claim: We generate the minimum set of copies to capture
one optimal solution
Had we generated copies every minute (as proposed in
literature), we would typically have to generate between 5
and 10 times as many flight copies (10,000 to 20,000 per day
of operations), which would greatly increase running time
and may jeopardize solution feasibility because of running
time
Maintaining crew feasibility
Respect planned duty period (constraints)
GBE Given a sequence of flights assigned to a crew (duty), add feasibility
constraints
GBE Not always needed because either the flight terminates the crew duty
assignment or some reserve crews can be used (typically at hubs); up to the
user to define these constraints (shadow prices indicates the benefit for the
passengers of relaxing the constraint)
S3
H
S2
S1
X1
X2
X1 + X2 <= 1)
Maintaining crew feasibility
Respect planned duty period (constraints)
GBE Given a sequence of flights assigned to a crew (duty), add feasibility
constraints
GBE Not always needed because either the flight terminates the crew duty
assignment or some reserve crews can be used (typically at hubs); up to the
user to define these constraints (shadow prices indicates the benefit for the
passengers of relaxing the constraint)
Satisfy regulatory constraints (Flight copies)
GBE Maximum total flying time (not affected)
GBE Maximum total elapsed time (MTET); iterative algorithm: if by adding a
flight copy, the associated crew’s elapsed time exceeds MTET, don’t
generate copy, otherwise do
S3
H
S2
S1
Maintaining crew feasibility
Respect planned duty period (constraints)
GBE Given a sequence of flights assigned to a crew (duty), add feasibility constraints
GBE Not always needed because either the flight terminates the crew duty assignment or
some reserve crews can be used (typically at hubs); up to the user to define these
constraints (shadow prices indicates the benefit for the passengers of relaxing the
constraint)
Satisfy regulatory constraints (Flight copies)
GBE Maximum total flying time (not affected)
GBE Maximum total elapsed time (MTET); iterative algorithm: if by adding a flight
copy, the associated crew’s elapsed time exceeds MTET, don’t generate copy,
otherwise do
Model solutions do not result in any additional crew disruptions due to
postponement decisions; keep control on overhead operating costs
Several models to minimize the crew disruption impact and minimize the
cost of crew disruptions, but these models assume the flight operations are
given. They can be used as complement to our models (Desrosier et al.
(optimal); Yu et al. (heuristic))
pp
pP
t
ff
tT
f
tt tt
ff ff
(f ,t) In(j) (f,t) Out(j)
ff
pf
tu
fgp
g C(u)d(g) a(f)
tt
pf,a f
Minimize n
st : x z 1
xy xy
xyRes(a,ft,)
z
xx1
[0;1]; x {0,1}; y 0
∈
∈
?+
∈∈
??
∈<
??
×ρ
??
??
+=
+= +
+= ?
ρ ≥
+?ρ ≤
ρ ∈∈≥
∑
∑
∑∑
∑
∑
GBE Objective: Minimize sum of
disrupted passengers
GBE Flight coverage constraints
GBE Aircraft balance for each sub
fleet type
GBE Initial and end of the day
aircraft resource constraints
GBE Passenger cancellation
constraints
GBE Missed connected passengers
constraints
GBE Only flight copy variables, x,
have to be binary
Minimizing Sum of Disrupted
Passengers
Minimizing passenger delay
Need to consider all potential recovery
itineraries for each passenger
Large scale problem: 500,000 integer
variables; 12 hours CPU using B&B deep
first search methodology
ii
pp
pPiI
p
t
ff
tT
f
tt tt
ff ff
(f ,t) In(j) (f,t) Out(j)
00
ff
i
pp
iI
p
ti t
pff
fi
pPiI
p
it t
pf f
bq
xz1 fF
xy xy
xy j
qn
qCx
q0;x{0,1};y0
Min
∈∈
∈
?+
∈∈
+
?
∈
∈∈
+= ?∈
+= +
+=
=
δ≤×
≥∈ ≥
∑∑
∑
∑∑
∑
∑
∑∑
Investigated approximate
approaches that meet the time
constraint requirements
pp
pP
t
f,a f
tTaA
ff
tt tt
f,a f f,a f
fF fF
dj oj
00
f,a f 0,a
0
fF
oj
pf
tu
fgp
g C(u) d(g) a(f)
tt
pf,a f
Minimize n
st : x z 1
xy xy
xyj
z
xx1
[0;1]; x {0,1}; y 0
∈
∈∈
?+
∈∈
+
∈
∈<
??
×ρ??
??
+=
+= +
+=
ρ ≥
+?ρ ≤
ρ ∈∈≥
∑
∑∑
∑∑
∑
∑
Estimate delay of disrupted passenger using PDC
Total delay = D(DP) N(DP) D(NDP) N(NDP)
NDP TP DP
Minimize( D(DP) N(DP) D(TP DP) N(TP DP)
∑× +∑ ×
=?
∑× +∑?×?
G04
Objective function
Objective function:
GBE Fine grained to Passenger Name Record
GBE Estimate each passenger dissatisfaction:
assign a cost (expected future revenue loss
of delay d for PNR p)
GBE Let the model chose flight decisions
Enforcing feasibility:
GBE Minimizing crew disruptions
GBE Preventing maintenance routing infeasibility
G24G4CG55G4FG4CG51G48 G56G5CG56G57G48G50 G56G57G44G57G48G1D
G24G4CG55G46G55G44G49G57G1D G53G52G56G4CG57G4CG52G51G0F G50G44G4CG51G57G48G51G44G51G46G48G0F G52G53G48G55G44G57G4CG52G51G44G4F
G26G55G48G5AG56G1D G53G52G56G4CG57G4CG52G51G0F G47G4CG56G55G58G53G57G4CG52G51 G56G57G44G57G58G56G0F G47G58G57G5C G57G4CG50G48G0F G49G4FG4CG4AG4BG57 G57G4CG50G48G0F G48G57G46G11
G33G44G56G56G48G51G4AG48G55G56G1D G53G52G56G4CG57G4CG52G51G0F G47G48G56G57G4CG51G44G57G4CG52G51G0F G33G24G37G0F G47G4CG56G55G58G53G57G4CG52G51 G56G57G44G57G58G56
G29G4FG4CG4AG4BG57 G46G52G53G5C G4AG48G51G48G55G44G57G4CG52G51 G44G4FG4AG52G55G4CG57G4BG50
G32G53G48G55G44G57G4CG52G51G56 G49G52G55G48G46G44G56G57G56
G29G4FG4CG4AG4BG57 G47G48G53G44G55G57G58G55G48 G57G4CG50G48G56G0F G3BG0D G44G51G47 G49G4FG4CG4AG4BG57 G46G44G51G46G48G4FG4FG44G57G4CG52G51G56 G3DG0D
G52G53G57G4CG50G4CG5DG48G55
G24G4CG55G46G55G44G49G57 G55G52G58G57G4CG51G4A G45G44G56G48G47 G52G51 G0BG3BG0DG0FG3DG0DG0C
? G29G48G44G56G4CG45G4FG48 G55G52G58G57G48 G35G22
G3CG48G56
G31G52
G33G55G48G59G48G51G57 G4CG51G49G48G44G56G4CG45G4FG48 G44G4CG55G46G55G44G49G57 G55G52G58G57G48 G56G5AG44G53G56
G30G52G47G4CG49G5C G49G4FG4CG4AG4BG57 G47G48G53G44G55G57G58G55G48 G56G52G4FG58G57G4CG52G51
G32G45G57G44G4CG51 G49G48G44G56G4CG45G4FG48 G44G4CG55G46G55G44G49G57 G55G52G58G57G48 G35GB7
G44G51G47 G44G56G56G52G46G4CG44G57G48G47 G52G53G57G4CG50G44G4F G56G52G4FG58G57G4CG52G51 G0BG3BGB7G0DG0FG3DGB7G0DG0C
G32G53G57G4CG50G44G4F G47G4CG56G55G58G53G57G48G47 G53G44G56G56G48G51G4AG48G55 G55G48G10G55G52G58G57G4CG51G4A
G26G52G51G56G4CG47G48G55G4CG51G4A G56G48G44G57 G44G59G44G4CG4FG44G45G4CG4FG4CG57G5C G58G51G46G48G55G57G44G4CG51G57G5C
G35G48G46G52G59G48G55G5C G53G55G4CG52G55G4CG57G5C G53G52G4FG4CG46G4CG48G56
G26G55G48G5A G52G53G48G55G44G57G4CG52G51G56 G55G48G46G52G59G48G55G5CG0F
G35G48G53G44G4CG55 G53G44G4CG55G4CG51G4AG56
Routing passengers
Several optimizations models that route passengers to their
destinations are used depending on the service priority rules
Recovery priority among
disrupted passengers
Priority given to booked
passengers over disrupted
FDFS for disrupted; local first
when same disruption time
Optimal passenger recovery
Optimal passenger recovery
FDFS for disrupted; local first
when same disruption time
Combination of PDC+PMIXYes
Stochastic PDC; Don’t know
exact seat capacity before
boarding ends due to potential no
shows
The Passenger Mix model (PMIX)
The Passenger Delay Calculator
(PDC)
Routing algorithm
Yes
No
Yes
Passenger service priority rule
Passenger routing algorithm
performance
PMIX provides the optimal passenger routings; We found
that PDC is close to optimality (PMIX) to route the
passengers
When passengers are disrupted at the hub (flight
cancellation or missed connection), PDC provides the
optimal recovery most of the time because only one route
typically goes from the hub to destination airport (hub and
spoke topology); Only when passengers are disrupted at
the origin spoke (first flight canceled), does PDC might
provide sub-optimal solution
origin destination
Conclusion and future research
Propose new airline operations recovery models that reduce
passenger disruptions and:
GBE Does not disrupt additional crew duties
GBE Recover aircraft plan
GBE Maintain overhead costs
GBE Found 10% to 20% reduction in passenger disruptions for bad days
of operations, using a sophisticated simulation environment
GBE Run fast and meet real time AOCC needs
Airline long term profitability: higher service reliability
improves customer retention and long term revenues
Future research:
GBE Estimate the impact of different disrupted passenger’s priority
strategies (e.g. Passenger routing: recovery priority given to
business passengers over leisure passengers; Optimization:
minimize the revenue of disrupted passengers) on overall passenger
population