1.206J/16.77J/ESD.215J
Airline Schedule Planning
Cynthia Barnhart
Spring 2003
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 2
1.963/1.206J/16.77J/ESD.215J
The Schedule Design Problem
? Outline
– Problem Definition and Objective
– Schedule Design with Constant Market Share
– Schedule Design with Variable Market Share
– Schedule Design Solution Algorithm
– Results
– Next Steps
– A Look to the Future in Airline Schedule Optimization
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
Assign aircraft types to flight legs
such that contribution is maximized
Airline Schedule Planning
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
Select optimal set of flight legs
in a schedule
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 4
Objectives
? Given origin-destination demands and
fares,fleet composition and size,fleet
operating characteristics and costs
? Find the revenue maximizing flight
schedule
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 5
Schedule Design,Fixed Flight
Network,Flexible Schedule
Approach
? Fleet assignment model with time windows
– Allows flights to be re-timed slightly (plus/
minus 10 minutes) to allow for improved
utilization of aircraft and improved capacity
assignments
?Initial step in integrating flight schedule
design and fleet assignment decisions
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 6
Schedule Design,Optional
Flights,Flexible Schedule
Approach
? Fleet assignment with,optional” flight legs
– Additional flight legs representing varying flight
departure times
– Additional flight legs representing new flights
– Option to eliminate existing flights from future
flight network
?Incremental Schedule Design
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
Integrated,Incremental Schedule
Design and Fleet Assignment Models
Addition Candidates
Mandatory Flight List
Deletion CandidatesBase Schedule
Optional Flight List
Master Flight List
Select optimal set of flight legs from master flight list
Assign fleet types to flight legs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 8
Demand and Supply Interactions
A BMarket Share
450
A B
100
150
100
100
Market Share
410
A BMarket Share
300
100
200
40
100
190
120
150
Non-Linear
Interactions
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 9
Schedule Design,Constant
Market Share Model
? Constant market share model
–Integrated Schedule Design and
Fleet Assignment Model (ISD-
FAM)
–Utilize recapture mechanism to
adjust demand approximately
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
ISD-FAM,Example
A BMarket Share
450
100
150
100
100
Market Share
450
100
150
100
100
A B
100 + recap1
150 + recap2
100 + recap3A B
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
ISD-FAM Formulation
Kk ??
? ?? ?
? ?? ?
??
Pp Pr
r
pr
r
pp
Kk Li
ikik
tfa r ebfa r efcMin )(
~
,,
1
,
??
? Kk
ik
f
0
),,(
,
,,
),,(
,
,,
???? ??
??
??
tokOi
ik
tok
tokIi
ik
tok
fyfy
k
kCLi
ik
Oo
tok
Nfy
n
?? ??
?? )(
,,,
? ?1,0
,
?
ik
f 0
,,
?
tok
y
F
iL??
tok,,?
Subject to:
i
Pr Pp
r
p
r
p
p
i
Pr Pp
r
p
p
i
k
kik
QtbtS E A TSf ??? ? ?? ??
? ?? ?
??
,
p
Pr
r
p
Dt ??
?
0?
r
p
t
Li ??
Pp ??
,
1
ki
kK
f
?
??
O
iL??
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
ISD-FAM Formulation
Kk ??
? ?? ?
? ?? ?
??
Pp Pr
r
pr
r
pp
Kk Li
ikik
tfa r ebfa r efcMin )(
~
,,
1
,
??
? Kk
ik
f
0
),,(
,
,,
),,(
,
,,
???? ??
??
??
tokOi
ik
tok
tokIi
ik
tok
fyfy
k
kCLi
ik
Oo
tok
Nfy
n
?? ??
?? )(
,,,
? ?1,0
,
?
ik
f 0
,,
?
tok
y
F
iL??
tok,,?
Subject to:
i
Pr Pp
r
p
r
p
p
i
Pr Pp
r
p
p
i
k
kik
QtbtS E A TSf ??? ? ?? ??
? ?? ?
??
,
p
Pr
r
p
Dt ??
?
0?
r
p
t
Li ??
Pp ??
,
1
ki
kK
f
?
??
O
iL??
Flight Selection
FAM
PMM
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 13
ISD-FAM Formulation
Kk ??
? ?? ?
? ?? ?
??
Pp Pr
r
pr
r
pp
Kk Li
ikik
tfa r ebfa r efcMin )(
~
,,
1
,
??
? Kk
ik
f
0
),,(
,
,,
),,(
,
,,
???? ??
??
??
tokOi
ik
tok
tokIi
ik
tok
fyfy
k
kCLi
ik
Oo
tok
Nfy
n
?? ??
?? )(
,,,
? ?1,0
,
?
ik
f 0
,,
?
tok
y
F
iL??
tok,,?
Subject to:
i
Pr Pp
r
p
r
p
p
i
Pr Pp
r
p
p
i
k
kik
QtbtS E A TSf ??? ? ?? ??
? ?? ?
??
,
p
Pr
r
p
Dt ??
?
0?
r
p
t
Li ??
Pp ??
,
1
ki
kK
f
?
??
O
iL??
Flight Selection
FAM
PMM
Fleet Assignment
Spill + Recapture
Schedule Design
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
Schedule Design,Variable
Market Share Model
? Variable market share model
–Extended Schedule Design and
Fleet Assignment Model (ESD-
FAM)
–Utilize demand correction term to
adjust demand explicitly
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
Demand Correction Terms
ESD-FAM,Demand Correction
A BMarket Share
450
100
150
100
100
A B
100
150+40+40
A BMarket Share
410
40
100
190
120
100 + 0
150 + 40
100 + 20
80
150
-30
2nd degree
correctionData Quality Issue
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
ESD-FAM Formulation
Kk ??
? ?
,,
:
( ) 1
O
r r p
k i k i p p r p q q p q q
k K i L p P r P p P p qqP
M i n c f f a r e b f a r e t f a r e D f a r e D Z
? ? ? ? ? ??
??
? ? ? ? ? ?
??
??
? ? ? ? ? ?
,
1
ki
kK
f
?
?
?
,,
,,,,
(,,) (,,)
0
k i k i
k o t k o t
i I k o t i O k o t
y f y f
??
??
? ? ? ?
??
,,,
()
n
k o t k i k
o O i C L k
y f N
??
??
??
? ?1,0
,
?
ik
f
0
,,
?
tok
y
F
iL??
tok,,?
Subj ect to,
? ?
,
1
O
p p p r p r r
i q q k i k i p i p p i
p P k K r P p P r P p PqP
D Z f S E A T S t b t Q? ? ?
? ? ? ? ? ??
? ? ? ? ? ?
? ? ? ? ? ? ?
? ?1
O
pr
q q p p
rPqP
D Z t D
??
? ? ? ?
??
0?
r
p
t
Li ??
Pp ??
,
1
ki
kK
f
?
?
?
O
iL??
,
0
q k i
kK
Zf
?
??
?
? ?i L q??
,
()
1
q k i q
i L q k K
Z f N
??
? ? ?
??
O
qP??
? ?0,1
q
Z ?
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
ESD-FAM Formulation
Kk ??
? ?
,,
:
( ) 1
O
r r p
k i k i p p r p q q p q q
k K i L p P r P p P p qqP
M i n c f f a r e b f a r e t f a r e D f a r e D Z
? ? ? ? ? ??
??
? ? ? ? ? ?
??
??
? ? ? ? ? ?
,
1
ki
kK
f
?
?
?
,,
,,,,
(,,) (,,)
0
k i k i
k o t k o t
i I k o t i O k o t
y f y f
??
??
? ? ? ?
??
,,,
()
n
k o t k i k
o O i C L k
y f N
??
??
??
? ?1,0
,
?
ik
f
0
,,
?
tok
y
F
iL??
tok,,?
Subj ect to,
? ?
,
1
O
p p p r p r r
i q q k i k i p i p p i
p P k K r P p P r P p PqP
D Z f S E A T S t b t Q? ? ?
? ? ? ? ? ??
? ? ? ? ? ?
? ? ? ? ? ? ?
? ?1
O
pr
q q p p
rPqP
D Z t D
??
? ? ? ?
??
0?
r
p
t
Li ??
Pp ??
,
1
ki
kK
f
?
?
?
O
iL??
,
0
q k i
kK
Zf
?
??
?
? ?i L q??
,
()
1
q k i q
i L q k K
Z f N
??
? ? ?
??
O
qP??
? ?0,1
q
Z ?
ISD-FAM
Market Share Adjustment
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
ESD-FAM Formulation
Kk ??
? ?
,,
:
( ) 1
O
r r p
k i k i p p r p q q p q q
k K i L p P r P p P p qqP
M i n c f f a r e b f a r e t f a r e D f a r e D Z
? ? ? ? ? ??
??
? ? ? ? ? ?
??
??
? ? ? ? ? ?
,
1
ki
kK
f
?
?
?
,,
,,,,
(,,) (,,)
0
k i k i
k o t k o t
i I k o t i O k o t
y f y f
??
??
? ? ? ?
??
,,,
()
n
k o t k i k
o O i C L k
y f N
??
??
??
? ?1,0
,
?
ik
f
0
,,
?
tok
y
F
iL??
tok,,?
Subj ect to,
? ?
,
1
O
p p p r p r r
i q q k i k i p i p p i
p P k K r P p P r P p PqP
D Z f S E A T S t b t Q? ? ?
? ? ? ? ? ??
? ? ? ? ? ?
? ? ? ? ? ? ?
? ?1
O
pr
q q p p
rPqP
D Z t D
??
? ? ? ?
??
0?
r
p
t
Li ??
Pp ??
,
1
ki
kK
f
?
?
?
O
iL??
,
0
q k i
kK
Zf
?
??
?
? ?i L q??
,
()
1
q k i q
i L q k K
Z f N
??
? ? ?
??
O
qP??
? ?0,1
q
Z ?
ISD-FAM
Market Share Adjustment
Constant
Market Share
Schedule Design
& Fleet Assgn.
Market Share Adjustment
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
Solution Algorithm
START
Calculate new demand
for the resulting schedule
Update modifiers
STOP
YES
Identify itineraries that
cause discrepancies
NO
Has the
stopping criteria
been met?
Solve I/ESD-FAM
Contribution 1
Obtain revenue estimates
from PMM
Contribution 2
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
State Of The Practice/ Theory
Practice:
? Most schedule decisions
made without optimization
? At least one major airline
uses Fleet Assignment with
Time Windows
? Implementation of
Incremental Schedule
Design approach underway
at a major airline
Theory:
? Models and algorithms for
incremental schedule
design have been
developed and prototyped
? Validation in progress
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
Computational Experiences
? ISD-FAM requires long runtimes and large
amounts of memory
– ~ 40 minutes on a workstation class computer
for medium size (800 legs) schedules
– ~ 20 hours on a 6-processor workstation,
running parallel CPLEX for full size (2,000 legs)
schedules
? ESD-FAM takes even longer runtimes and
exhausts the memory in some cases
– 40 mins (ISD-FAM) vs,12 hrs (ESD-FAM) on
same medium size schedule
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
Schedule Design,Results
? Demand and supply interactions
– ESD-FAM captures interactions more accurately
? Resulting schedules operate fewer flights
– Lower operating costs
– Fewer aircraft required
? ~$100 - $350 million improvement annually
– Compared to planners’ schedules
– Exclude benefits from saved aircraft
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 23
Schedule Design Results
? Results are subject to several caveats
– Plans are often disrupted
– Competitors’ responses
– Underlying assumptions
? Deterministic demand
? Optimal control of passengers
? Demand forecast
? Recapture rates/Demand correction terms
?Nonetheless,significant improvements are
achievable
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 24
Potential for Improved Results
? Replace IFAM with SFAM
Kk ??
? ? ? ?
11
m
S
S
SS
M
mm
nn
mn
M i n C f
?
?
??
??
??
? ? ? ?
11
1
m
S
S
SS
M
i
mm
nn
mn
f
?
?
?
??
??
???
? ? ? ? ? ? ? ?
,,
,,,,
(,,) 1 1 (,,) 1 1
0
mm
SS
SS
S S S S
MM
k i k i
m m m m
k o t k o t
n n n n
i I k o t m n i O k o t m n
y f y f
??
??
??
??
? ? ? ?
? ? ? ? ? ?
? ? ? ?? ? ? ? ? ?
? ? ? ?
,,
( ) 1 1
m
S
S
SS
n
M
k
mm
k o t k
nn
o A i C L k m n
y f N
?
?
?
??
? ? ? ?
??? ? ? ?
? ? ? ?0,1S
m
n
f
?
? 0
,,
?
tok
y
Li ??
tok,,?
Subject to:
?1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 25
SFAM Basic Concept
? Isolate network effects
– Spill occurs only on constrained legs
Potentially
Constrained
Flight Leg
Unconstrained
Flight Leg
Potentially
Binding
Itinerary
Non- Binding
Itinerary FAMIFAM
1
2
3
4
5
6
7
8
9
S
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 26
A Look to the Future,Airline
Schedule Planning Integration
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
l t i t
ir r ft ti
r li
Integrating crew
scheduling and
fleet assignment
models yields:
? Additional 3%
savings in total
operating,spill and
crew costs
?Fleeting costs
increase by about
1%
?Crew costs
decrease by about
7%
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 27
A Look to the Future,Real-time
Decision Making
? For a typical airline,about 10% of scheduled
revenue flights are affected by irregularities (like
inclement weather,maintenance problems,etc.)
? According to the New York Times,irregular
operations (due mostly to weather) result in more
than $440 million per year in lost revenue,crew
overtime pay,and passenger hospitality costs
?Increasing use and acceptance of optimization-based
decision support tools for operations recovery
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 28
A Look to the Future,Robust
Scheduling
? Issue,Optimizing,plans” results in
minimized planned costs,not realized costs
– Optimized plans have little slack,resulting in
? Increased likelihood of plan,breakage” during
operations
? Fewer recovery options
? Challenge,Building,robust” plans that
achieve minimal realized costs
Airline Schedule Planning
Cynthia Barnhart
Spring 2003
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 2
1.963/1.206J/16.77J/ESD.215J
The Schedule Design Problem
? Outline
– Problem Definition and Objective
– Schedule Design with Constant Market Share
– Schedule Design with Variable Market Share
– Schedule Design Solution Algorithm
– Results
– Next Steps
– A Look to the Future in Airline Schedule Optimization
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
Assign aircraft types to flight legs
such that contribution is maximized
Airline Schedule Planning
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
Select optimal set of flight legs
in a schedule
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 4
Objectives
? Given origin-destination demands and
fares,fleet composition and size,fleet
operating characteristics and costs
? Find the revenue maximizing flight
schedule
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 5
Schedule Design,Fixed Flight
Network,Flexible Schedule
Approach
? Fleet assignment model with time windows
– Allows flights to be re-timed slightly (plus/
minus 10 minutes) to allow for improved
utilization of aircraft and improved capacity
assignments
?Initial step in integrating flight schedule
design and fleet assignment decisions
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 6
Schedule Design,Optional
Flights,Flexible Schedule
Approach
? Fleet assignment with,optional” flight legs
– Additional flight legs representing varying flight
departure times
– Additional flight legs representing new flights
– Option to eliminate existing flights from future
flight network
?Incremental Schedule Design
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
Integrated,Incremental Schedule
Design and Fleet Assignment Models
Addition Candidates
Mandatory Flight List
Deletion CandidatesBase Schedule
Optional Flight List
Master Flight List
Select optimal set of flight legs from master flight list
Assign fleet types to flight legs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 8
Demand and Supply Interactions
A BMarket Share
450
A B
100
150
100
100
Market Share
410
A BMarket Share
300
100
200
40
100
190
120
150
Non-Linear
Interactions
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 9
Schedule Design,Constant
Market Share Model
? Constant market share model
–Integrated Schedule Design and
Fleet Assignment Model (ISD-
FAM)
–Utilize recapture mechanism to
adjust demand approximately
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
ISD-FAM,Example
A BMarket Share
450
100
150
100
100
Market Share
450
100
150
100
100
A B
100 + recap1
150 + recap2
100 + recap3A B
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
ISD-FAM Formulation
Kk ??
? ?? ?
? ?? ?
??
Pp Pr
r
pr
r
pp
Kk Li
ikik
tfa r ebfa r efcMin )(
~
,,
1
,
??
? Kk
ik
f
0
),,(
,
,,
),,(
,
,,
???? ??
??
??
tokOi
ik
tok
tokIi
ik
tok
fyfy
k
kCLi
ik
Oo
tok
Nfy
n
?? ??
?? )(
,,,
? ?1,0
,
?
ik
f 0
,,
?
tok
y
F
iL??
tok,,?
Subject to:
i
Pr Pp
r
p
r
p
p
i
Pr Pp
r
p
p
i
k
kik
QtbtS E A TSf ??? ? ?? ??
? ?? ?
??
,
p
Pr
r
p
Dt ??
?
0?
r
p
t
Li ??
Pp ??
,
1
ki
kK
f
?
??
O
iL??
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
ISD-FAM Formulation
Kk ??
? ?? ?
? ?? ?
??
Pp Pr
r
pr
r
pp
Kk Li
ikik
tfa r ebfa r efcMin )(
~
,,
1
,
??
? Kk
ik
f
0
),,(
,
,,
),,(
,
,,
???? ??
??
??
tokOi
ik
tok
tokIi
ik
tok
fyfy
k
kCLi
ik
Oo
tok
Nfy
n
?? ??
?? )(
,,,
? ?1,0
,
?
ik
f 0
,,
?
tok
y
F
iL??
tok,,?
Subject to:
i
Pr Pp
r
p
r
p
p
i
Pr Pp
r
p
p
i
k
kik
QtbtS E A TSf ??? ? ?? ??
? ?? ?
??
,
p
Pr
r
p
Dt ??
?
0?
r
p
t
Li ??
Pp ??
,
1
ki
kK
f
?
??
O
iL??
Flight Selection
FAM
PMM
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 13
ISD-FAM Formulation
Kk ??
? ?? ?
? ?? ?
??
Pp Pr
r
pr
r
pp
Kk Li
ikik
tfa r ebfa r efcMin )(
~
,,
1
,
??
? Kk
ik
f
0
),,(
,
,,
),,(
,
,,
???? ??
??
??
tokOi
ik
tok
tokIi
ik
tok
fyfy
k
kCLi
ik
Oo
tok
Nfy
n
?? ??
?? )(
,,,
? ?1,0
,
?
ik
f 0
,,
?
tok
y
F
iL??
tok,,?
Subject to:
i
Pr Pp
r
p
r
p
p
i
Pr Pp
r
p
p
i
k
kik
QtbtS E A TSf ??? ? ?? ??
? ?? ?
??
,
p
Pr
r
p
Dt ??
?
0?
r
p
t
Li ??
Pp ??
,
1
ki
kK
f
?
??
O
iL??
Flight Selection
FAM
PMM
Fleet Assignment
Spill + Recapture
Schedule Design
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
Schedule Design,Variable
Market Share Model
? Variable market share model
–Extended Schedule Design and
Fleet Assignment Model (ESD-
FAM)
–Utilize demand correction term to
adjust demand explicitly
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
Demand Correction Terms
ESD-FAM,Demand Correction
A BMarket Share
450
100
150
100
100
A B
100
150+40+40
A BMarket Share
410
40
100
190
120
100 + 0
150 + 40
100 + 20
80
150
-30
2nd degree
correctionData Quality Issue
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
ESD-FAM Formulation
Kk ??
? ?
,,
:
( ) 1
O
r r p
k i k i p p r p q q p q q
k K i L p P r P p P p qqP
M i n c f f a r e b f a r e t f a r e D f a r e D Z
? ? ? ? ? ??
??
? ? ? ? ? ?
??
??
? ? ? ? ? ?
,
1
ki
kK
f
?
?
?
,,
,,,,
(,,) (,,)
0
k i k i
k o t k o t
i I k o t i O k o t
y f y f
??
??
? ? ? ?
??
,,,
()
n
k o t k i k
o O i C L k
y f N
??
??
??
? ?1,0
,
?
ik
f
0
,,
?
tok
y
F
iL??
tok,,?
Subj ect to,
? ?
,
1
O
p p p r p r r
i q q k i k i p i p p i
p P k K r P p P r P p PqP
D Z f S E A T S t b t Q? ? ?
? ? ? ? ? ??
? ? ? ? ? ?
? ? ? ? ? ? ?
? ?1
O
pr
q q p p
rPqP
D Z t D
??
? ? ? ?
??
0?
r
p
t
Li ??
Pp ??
,
1
ki
kK
f
?
?
?
O
iL??
,
0
q k i
kK
Zf
?
??
?
? ?i L q??
,
()
1
q k i q
i L q k K
Z f N
??
? ? ?
??
O
qP??
? ?0,1
q
Z ?
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
ESD-FAM Formulation
Kk ??
? ?
,,
:
( ) 1
O
r r p
k i k i p p r p q q p q q
k K i L p P r P p P p qqP
M i n c f f a r e b f a r e t f a r e D f a r e D Z
? ? ? ? ? ??
??
? ? ? ? ? ?
??
??
? ? ? ? ? ?
,
1
ki
kK
f
?
?
?
,,
,,,,
(,,) (,,)
0
k i k i
k o t k o t
i I k o t i O k o t
y f y f
??
??
? ? ? ?
??
,,,
()
n
k o t k i k
o O i C L k
y f N
??
??
??
? ?1,0
,
?
ik
f
0
,,
?
tok
y
F
iL??
tok,,?
Subj ect to,
? ?
,
1
O
p p p r p r r
i q q k i k i p i p p i
p P k K r P p P r P p PqP
D Z f S E A T S t b t Q? ? ?
? ? ? ? ? ??
? ? ? ? ? ?
? ? ? ? ? ? ?
? ?1
O
pr
q q p p
rPqP
D Z t D
??
? ? ? ?
??
0?
r
p
t
Li ??
Pp ??
,
1
ki
kK
f
?
?
?
O
iL??
,
0
q k i
kK
Zf
?
??
?
? ?i L q??
,
()
1
q k i q
i L q k K
Z f N
??
? ? ?
??
O
qP??
? ?0,1
q
Z ?
ISD-FAM
Market Share Adjustment
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
ESD-FAM Formulation
Kk ??
? ?
,,
:
( ) 1
O
r r p
k i k i p p r p q q p q q
k K i L p P r P p P p qqP
M i n c f f a r e b f a r e t f a r e D f a r e D Z
? ? ? ? ? ??
??
? ? ? ? ? ?
??
??
? ? ? ? ? ?
,
1
ki
kK
f
?
?
?
,,
,,,,
(,,) (,,)
0
k i k i
k o t k o t
i I k o t i O k o t
y f y f
??
??
? ? ? ?
??
,,,
()
n
k o t k i k
o O i C L k
y f N
??
??
??
? ?1,0
,
?
ik
f
0
,,
?
tok
y
F
iL??
tok,,?
Subj ect to,
? ?
,
1
O
p p p r p r r
i q q k i k i p i p p i
p P k K r P p P r P p PqP
D Z f S E A T S t b t Q? ? ?
? ? ? ? ? ??
? ? ? ? ? ?
? ? ? ? ? ? ?
? ?1
O
pr
q q p p
rPqP
D Z t D
??
? ? ? ?
??
0?
r
p
t
Li ??
Pp ??
,
1
ki
kK
f
?
?
?
O
iL??
,
0
q k i
kK
Zf
?
??
?
? ?i L q??
,
()
1
q k i q
i L q k K
Z f N
??
? ? ?
??
O
qP??
? ?0,1
q
Z ?
ISD-FAM
Market Share Adjustment
Constant
Market Share
Schedule Design
& Fleet Assgn.
Market Share Adjustment
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
Solution Algorithm
START
Calculate new demand
for the resulting schedule
Update modifiers
STOP
YES
Identify itineraries that
cause discrepancies
NO
Has the
stopping criteria
been met?
Solve I/ESD-FAM
Contribution 1
Obtain revenue estimates
from PMM
Contribution 2
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
State Of The Practice/ Theory
Practice:
? Most schedule decisions
made without optimization
? At least one major airline
uses Fleet Assignment with
Time Windows
? Implementation of
Incremental Schedule
Design approach underway
at a major airline
Theory:
? Models and algorithms for
incremental schedule
design have been
developed and prototyped
? Validation in progress
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
Computational Experiences
? ISD-FAM requires long runtimes and large
amounts of memory
– ~ 40 minutes on a workstation class computer
for medium size (800 legs) schedules
– ~ 20 hours on a 6-processor workstation,
running parallel CPLEX for full size (2,000 legs)
schedules
? ESD-FAM takes even longer runtimes and
exhausts the memory in some cases
– 40 mins (ISD-FAM) vs,12 hrs (ESD-FAM) on
same medium size schedule
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
Schedule Design,Results
? Demand and supply interactions
– ESD-FAM captures interactions more accurately
? Resulting schedules operate fewer flights
– Lower operating costs
– Fewer aircraft required
? ~$100 - $350 million improvement annually
– Compared to planners’ schedules
– Exclude benefits from saved aircraft
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 23
Schedule Design Results
? Results are subject to several caveats
– Plans are often disrupted
– Competitors’ responses
– Underlying assumptions
? Deterministic demand
? Optimal control of passengers
? Demand forecast
? Recapture rates/Demand correction terms
?Nonetheless,significant improvements are
achievable
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 24
Potential for Improved Results
? Replace IFAM with SFAM
Kk ??
? ? ? ?
11
m
S
S
SS
M
mm
nn
mn
M i n C f
?
?
??
??
??
? ? ? ?
11
1
m
S
S
SS
M
i
mm
nn
mn
f
?
?
?
??
??
???
? ? ? ? ? ? ? ?
,,
,,,,
(,,) 1 1 (,,) 1 1
0
mm
SS
SS
S S S S
MM
k i k i
m m m m
k o t k o t
n n n n
i I k o t m n i O k o t m n
y f y f
??
??
??
??
? ? ? ?
? ? ? ? ? ?
? ? ? ?? ? ? ? ? ?
? ? ? ?
,,
( ) 1 1
m
S
S
SS
n
M
k
mm
k o t k
nn
o A i C L k m n
y f N
?
?
?
??
? ? ? ?
??? ? ? ?
? ? ? ?0,1S
m
n
f
?
? 0
,,
?
tok
y
Li ??
tok,,?
Subject to:
?1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 25
SFAM Basic Concept
? Isolate network effects
– Spill occurs only on constrained legs
Potentially
Constrained
Flight Leg
Unconstrained
Flight Leg
Potentially
Binding
Itinerary
Non- Binding
Itinerary FAMIFAM
1
2
3
4
5
6
7
8
9
S
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 26
A Look to the Future,Airline
Schedule Planning Integration
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
l t i t
ir r ft ti
r li
Integrating crew
scheduling and
fleet assignment
models yields:
? Additional 3%
savings in total
operating,spill and
crew costs
?Fleeting costs
increase by about
1%
?Crew costs
decrease by about
7%
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 27
A Look to the Future,Real-time
Decision Making
? For a typical airline,about 10% of scheduled
revenue flights are affected by irregularities (like
inclement weather,maintenance problems,etc.)
? According to the New York Times,irregular
operations (due mostly to weather) result in more
than $440 million per year in lost revenue,crew
overtime pay,and passenger hospitality costs
?Increasing use and acceptance of optimization-based
decision support tools for operations recovery
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 28
A Look to the Future,Robust
Scheduling
? Issue,Optimizing,plans” results in
minimized planned costs,not realized costs
– Optimized plans have little slack,resulting in
? Increased likelihood of plan,breakage” during
operations
? Fewer recovery options
? Challenge,Building,robust” plans that
achieve minimal realized costs
