Airline Operations

Lecture #2

1.206J
April 27, 2003
 Summary Lecture #1

• Airline schedules (Aircraft, crew,

passengers) are optimized leading to:
¾ Little slacks (idle time)
¾ Schedule dependencies
¾ Delay chain effects
• Causes of schedule disruptions
¾ Shortages of airline resources
¾ Shortages of airport resources
• Complex airline resource regulations
¾ Aircraft maintenance
¾ Pilots
 Airline Schedules Recovery

¾ Schedule Recovery Model (SRM)

650
¾ Aircraft Recovery Model (ARM)
¾ Crew Recovery Model (CRM)
¾ Passenger Flow Model (PFM) $5 0 &5 0 3)0
¾ Journey Management
¾ Passenger Re-accommodation 3DV
3DVVVHQJH
HQJHUU 5H
5HDDFFRP
FRPPPRG
RGDDWLRQ
 Summary Lecture #1 (Cont.)

• Airline schedules recovery problems

¾ Aircraft maintenance module:
• Objective: feasibility only
¾ Crew schedule recovery module
• Objective: to minimize disruptions, recover the disrupted
with minimum flight schedule disruptions and control
Flight Time Count
• Complex rules
¾ 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

Admissible operating cost region

Feasible operating space
Passenger
dissatisfaction

Operating costs
 )OLJKW GHOD\V DQG IOLJKW FDQFHOODWLRQV
,13876
3DVVHQJ HU ERRNLQJV IRU HDFK VFK HGXOHG LWLQHUDU\

35(352&(66,
<HV
'LVUXSWHG"
1R
1*

$VVLJQ DOO QRQGLVUXSWHG SDVV HQJ HUV

%XLOG WKH OLVW RI GLVUXSWHG
WR WKHLU SODQQHG LWLQHUDULHV
SDVVHQJ HUV /

5HPRYH VHDWV IURP UHPDLQLQJ LQYHQWRU\

6RUW / DFFRUGLQJ WR VHUYLFH SROLF\

5HFRUG SDVVHQJHU
5HFRUG SDVVHQJ HU GHOD\
G HOD \

<HV
3'&
,V / ‘ " (1'

1R

7DNH Q H[W GLVUXSWHG SDVV HQJ HU LQ / 3DVVHQJHU 'HOD\ 6WDWLVWLFV

)LQG EHVW UHFRYHU\ LWLQHUDU \ DQG DVVLJQ SDV VHQJ HU

5HPRYH VHDW IURP UHPDLQLQJ LQYHQWRU\

5HFRUG SDVVHQJ HU G HOD \

 Flight and passenger delays

30

25

20 Passengers
(minutes)

15 Flight Delay

10
Passenger/flight = 170%
5

Flight delays underestimate passenger delays

Key explanation lies in the disrupted passengers
 Disrupted passengers versus non disrupted
passengers

Av. Delay
August 2000 % Passengers % Delays
(minutes)
Disrupted
320 minutes 3.2% 40%
passengers
Non disrupted
16 minutes 96.8% 60%
passengers

¾ Disrupted passengers experience long delays in general because 20%

of them are stranded overnight (delay propagation results in more
disruptions later during the day)
¾ 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)
 Risk of being disrupted

Passenger type Connecting Local

Scheduled passenger mix 35% 65%
Disrupted passenger mix 60% 40%
Caused by flight cancellations 52% 100%
Caused by missed connections 48%

¾ Although fewer planned connecting passengers, higher

number are disrupted
¾ The risk of a passenger to be disrupted is 2.75 times
greater for connecting (5.5%) than for local (2%)
¾ Does not bode well for hub-and-spoke with banks
 Passenger disruption: important factors

• Disruption time & Route frequency

$Y 'HOD\ RI GLVUXSW HG SDVVHQJHUV




5 

16

KR XUV

Average delay of the disrupted

14


12
passengers (hours)

10 


8 R2 = 0.93

6
          

4
RQ UR XW HV Z LW K IUHTXHQF\ !

0
8 10 12 14 16 18 20 22 24
disruption time in window (+/- 1hour)
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

PC
Cockpit Crew rest at SMF
PC
SMF-LAX

PC LAX-SMF
CC SNA-SJC
A CC CC: deadheading
SNA-RNO

DFW-SNA SNA-SEA
DFW-LAX

A
ONT-LAX

LAX-ONT A
Aircraft
maintenance at
ONT

PC: Pilot Crew; CC: Cabin Crew; A: Aircraft

Source: Sabre, 1998
 Disruption Impacts; Solutions and Constraints

Disruption Impacts Solutions Constraints

• Flight delays • Hold flights • Aircraft balance
• Broken crew pairings • Cancel flights • Market protection
• Resource shortage • Aggregate flights • Fleet/crew
• Crew unavailability compatibility
• Divert aircraft
• Disrupted maintenance • Resource positioning
• Swap resources
• Gate problems
• Use spare aircraft • Maintenance
• Baggage handling requirements
problems • Use reserve crews
• Deadhead crews • Crew legalities
• others
• Layover crews • Union contracts
• Others
 Disruption Impacts; Solutions and Constraints

Disruption Impacts Solutions Constraints

• Flight delays • Hold flights • Aircraft balance
• Broken crew pairings • Cancel flights • Market protection
• Resource shortage • Aggregate flights • Fleet/crew
• Crew unavailability compatibility
• Divert aircraft
• Disrupted maintenance • Resource positioning
• Swap resources
• Gate problems
• Use spare aircraft • Maintenance
• Baggage handling requirements
problems • Use reserve crews
• Deadhead crews • Crew legalities
• others
• Layover crews • Union contracts
• Others
 Aircraft route swaps

Schedule No Swapping Swapping

A1;F1
Delay F1
A2;F2 A2;F2 A2;F1
Delay F2
A3;F3 A3;F3 A3;F2
Delay F3 A1;F1 A1;F3

time time

Swapping useful to:

+ Spread the delays informally, converge toward bank integrity
+ Postpone the shortage problem
+ Recover from irregularities
Constraints: Crew compatibility and legalities
 SCHEDULE

BOS
EWR

ORD

MIA
time IAH
HYPOTHETICAL CASE: Flights not canceled (NC)

BOS
EWR

ORD

MIA
time IAH
 ACTUAL OPERATIONS

BOS
EWR

ORD

MIA
time IAH
 ACTUAL OPERATIONS: Flights canceled (C)

BOS
EWR

ORD

MIA
time IAH
 Flight cancellation benefits passengers
when…
BOS
EWR

Low loads in canceled flights

ORD

MIA
time But often crew disruptions…
IAH
Unless canceled flights
belong to the same crew duty
Severe delay
sequence
Strong down line
Passenger disruptions
 Airline Schedule Recovery Problem:
Assumptions

• At a given time of the day, we assume

that airline controllers know the state
of the system:
¾ Locations and availability of resources
• Aircraft
• Pilot and flight attendant crews
¾ Passenger states (i,e., disrupted or not) and
locations/destinations
 Airline Recovery Model, ARM
(G. Yu et al.)

 
min  ∑ ∑ d ft × x ft + ∑ cf × z f 
 
 f ∈F t∈Tf f ∈F 
Ops cost + Cancellation cost
st :
∑ x ft + zf =1 Flight coverage
t∈Tf

∑ x ft + yft − = ∑ x ft + yft + Aircraft balance

f ∈Ft f ∈Ft
dj oj

∑ x 0f + y0f + = j0 Initial resource at airports

0
f ∈Foj

∑ x f_ + yf_ − = j− End of the day resource at airports

_
f ∈F
dj

x ft ∈ {0,1}; yft ≥ 0

• Objective is to minimize operating cost

(flight delay and cancellation costs)
 Aircraft route schedule

S1

Aircraft A

Aircraft B

S2
Aircraft actual operations: unexpected delay
(e.g., aircraft technical problem)

delay
S1

Aircraft A

Aircraft B

S2
Passenger actual itineraries Operations decision #3:
don’t cancel & postpone aircraft B

delay
S1

Aircraft A

Aircraft B

S2
 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:
¾ Aircraft ready times
S3

S2

S1
 Flight copy generations

• We have developed a technique to

minimize the number of flight copies
• Four types of flight copies are generated:
¾ Aircraft ready times
¾ Copies to prevent passengers from missing
connections
S3

S2

S1
 Flight copy generations

• We have developed a technique to

minimize the number of flight copies
• Four types of flight copies are generated:
¾ Aircraft ready times
¾ Copies to prevent passengers from missing
connections
¾ Consequence of type 2, aircraft postponement
propagation
S3

S2

S1
 Flight copy generations

• We have developed a technique to

minimize the number of flight copies
• Four types of flight copies are generated:
¾ Aircraft ready times
¾ Copies to prevent passengers from missing
connections
¾ Consequence of type 2, aircraft postponement
propagation
¾ Schedule (for cancellations)
S3

S2

S1
 Flight copy generations

• We have developed a technique to minimize the number of

flight copies
• Four types of flight copies are generated:
¾ Aircraft ready times
¾ Copies to prevent passengers from missing connections
¾ Consequence of type 2, aircraft postponement propagation
¾ 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)

¾ Given a sequence of flights assigned to a crew (duty), add feasibility
constraints
¾ 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)
 X1 + X2 <= 1)
S3

X1
X2

S2

S1
 Maintaining crew feasibility

• Respect planned duty period (constraints)

¾ Given a sequence of flights assigned to a crew (duty), add feasibility
constraints
¾ 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)
¾ Maximum total flying time (not affected)
¾ 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

S2

S1
 Maintaining crew feasibility

• Respect planned duty period (constraints)

¾ Given a sequence of flights assigned to a crew (duty), add feasibility constraints
¾ 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)
¾ Maximum total flying time (not affected)
¾ 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))
 Minimizing Sum of Disrupted
Passengers
  ¾ Objective: Minimize sum of
Minimize  ∑ np ×ρp  disrupted passengers
 p∈P 
 
¾
∑ xft + zf = 1
Flight coverage constraints
st :
t∈Tf
¾ Aircraft balance for each sub
∑ xft + yft− = ∑ xft + yft+ fleet type
(f ,t)∈In( j) (f ,t)∈Out( j)

∑ f f = Res(a,ft, •)
x •
+ y• ¾ Initial and end of the day
aircraft resource constraints
ρp ≥ zf ¾ Passenger cancellation
constraints
xft + ∑ xgu − ρp ≤ 1 ¾ Missed connected passengers
g∈C(u) d(g)<a(f )
constraints

ρp ∈[0;1]; xft ,a ∈{0,1}; yft ≥ 0

¾ Only flight copy variables, x,
have to be binary
 Minimizing passenger delay

• Need to consider all potential recovery Min ∑ ∑ bipqip

itineraries for each passenger p∈P i∈Ip

• Large scale problem: 500,000 integer ∑ x ft + zf = 1 ∀f ∈ F

t∈Tf
variables; 12 hours CPU using B&B deep
first search methodology ∑ x ft + yft − = ∑ x ft + y ft +
(f ,t)∈In( j) (f ,t)∈Out( j)

∑ x 0f + y0f + = j•
Investigated approximate ∑ p = np
q i

approaches that meet the time i∈Ip

constraint requirements ∑ ∑ δtfi qip ≤ Cf × x ft

p∈P i∈Ip

q ip ≥ 0; x ft ∈{0,1}; y ft ≥ 0
  
Minimize  ∑ np ×ρp 
 p∈P 
 
st : ∑ ∑ xft ,a + zf = 1
t∈Tf a∈Af

∑ xft ,a + yft − = ∑ xft ,a + yft +

f ∈Ft f ∈Ft
dj oj

∑ x0f ,a + y0f + = j0,a

f ∈F0
oj

ρp ≥ zf
xft + ∑ xgu − ρp ≤ 1
g∈C(u) d(g) <a(f )

ρp ∈[0;1]; xft ,a ∈{0,1}; yft ≥ 0

Total delay = ∑ D(DP) × N(DP) + ∑ D(NDP) × N(NDP)

NDP = TP − DP
Minimize(∑ D(DP)
 × N(DP) + ∑ D(TP − DP) × N(TP − DP)

Estimate delay of disrupted passenger using PDC

 Objective function

• Objective function:
¾ Fine grained to Passenger Name Record
¾ Estimate each passenger dissatisfaction:
assign a cost (expected future revenue loss
of delay d for PNR p)
¾ Let the model chose flight decisions
• Enforcing feasibility:
¾ Minimizing crew disruptions
¾ Preventing maintenance routing infeasibility
 $LUOLQH V\VWHP VWDWH
$LUFUDIW SRVLWLRQ PDLQWHQDQFH RSHUDWLRQDO
&UHZV SRVLWLRQ GLVUXSWLRQ VWDWXV GXW\ WLPH IOLJKW WLPH HWF
3DVVHQJHUV SRVLWLRQ GHVWLQDWLRQ 3$7 GLVUXSWLRQ VWDWXV

&UHZ RSHUDWLRQV UHFRYHU\

2SHUDWLRQV IRUHFDVWV
5HSDLU SDLULQJV

)OLJKW FRS\ JHQHUDWLRQ DOJRULWKP

RSWLPL]HU

)OLJKW GHSDUWXUH WLPHV ; DQG IOLJKW FDQFHOODWLRQV =

$LUFUDIW URXWLQJ EDVHG RQ ; = 

∃ )HDVLEOH URXWH 5"

1R

<HV 3UHYHQW LQIHDVLEOH DLUFUDIW URXWH VZDSV

0RGLI\ IOLJKW GHSDUWXUH VROXWLRQ
2EWDLQ IHDVLEOH DLUFUDIW URXWH 5·
DQG DVVRFLDWHG RSWLPDO VROXWLRQ ;· =· 

2SWLPDO GLVUXSWHG SDVVHQJHU UHURXWLQJ

5HFRYHU\ SULRULW\ SROLFLHV
&RQVLGHULQJ VHDW DYDLODELOLW\ XQFHUWDLQW\
 Routing passengers

Several optimizations models that route passengers to their

destinations are used depending on the service priority rules

Passenger service priority rule

Priority given to booked Recovery priority among Routing algorithm
passengers over disrupted disrupted passengers
FDFS for disrupted; local first The Passenger Delay Calculator
Yes
when same disruption time (PDC)
No Optimal passenger recovery The Passenger Mix model (PMIX)
Yes Optimal passenger recovery Combination of PDC+PMIX
Stochastic PDC; Don’t know
FDFS for disrupted; local first exact seat capacity before
Yes
when same disruption time boarding ends due to potential no
shows
 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:
¾ Does not disrupt additional crew duties
¾ Recover aircraft plan
¾ Maintain overhead costs
¾ Found 10% to 20% reduction in passenger disruptions for bad days
of operations, using a sophisticated simulation environment
¾ Run fast and meet real time AOCC needs
• Airline long term profitability: higher service reliability
improves customer retention and long term revenues
• Future research:
¾ 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