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.206J/16.77J/ESD.215J
The Fleet Assignment Problem
? Outline
– Problem Definition and Objective
– Fleet Assignment Network Representation
– Fleet Assignment Model
– Fleet Assignment Solution
? Branch-and-bound
– Results
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
Route individual aircraft honoring
maintenance restrictions
Assign aircraft types to flight legs
such that contribution is maximized
Contribution = Revenue - Costs
Airline Schedule Planning
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
Select optimal set of flight legs
in a schedule
Assign crew (pilots and/or flight
attendants) to flight legs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 4
Problem Definition
Given:
– Flight Schedule
? Each flight covered exactly once by one fleet type
– Number of Aircraft by Equipment Type
? Can’t assign more aircraft than are available,for each
type
– Turn Times by Fleet Type at each Station
– Other Restrictions,Maintenance,Gate,Noise,
Runway,etc.
– Operating Costs,Spill and Recapture Costs,
Total Potential Revenue of Flights,by Fleet
Type
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 5
Problem Objective
Find:
– Cost minimizing (or profit maximizing)
assignment of aircraft fleets to scheduled
flights such that maintenance requirements
are satisfied,conservation of flow (balance)
of aircraft is achieved,and the number of
aircraft used does not exceed the number
available (in each fleet type)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 6
Definitions (again)
? Spill
– passengers that are denied booking due to
capacity restrictions
? Recapture
– passengers that are recaptured back to the
airline after being spilled from another
flight leg
? For each fleet - flight combination:
Cost ? Operating cost + Spill cost
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
Fleet Assignment References
? Abara (1989),Daskin and Panayotopoulos
(1989),Hane,Barnhart,Johnson,Marsten,
Neumhauser,and Sigismondi (1995)
? Hane,et al.,The Fleet Assignment Problem,
Solving a Large Integer Program,”
Mathematical Programming,Vol,70,2,pp,211-
232,1995
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 8
Network Representation
? Topologically sorted time-line network
– Nodes,
? Flight arrivals/ departures (time and space)
– Arcs:
? Flight arcs,one arc for each scheduled flight
? Ground arcs,allow aircraft to sit on the ground
between flights
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 9
Time-Line Network
8:00 12:00 16:00 20:00 8:00 12:00 16:00 20:00
City A
City B
City C
City D
? Ground arcs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
Time-Line Network
?,Daily” problem
– Wrap-around (or overnight) arcs
Washington,D.C.
Baltimore
New York
Boston
Time
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
Constraints
? Cover Constraints
– Each flight must be assigned to exactly one fleet
? Balance Constraints
– Number of aircraft of a fleet type arriving at a station
must equal the number of aircraft of that fleet type
departing
? Aircraft Count Constraints
– Number of aircraft of a fleet type used cannot exceed
the number available
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
Objective Function
For each fleet - flight combination,Cost ?
Operating cost + Spill cost
? Operating cost associated with assigning a fleet type
k to a flight leg j is relatively straightforward to
compute
– Can capture range restrictions,noise restrictions,water
restrictions,etc,by assigning,infinite” costs
? Spill cost for flight leg j and fleet assignment k =
average revenue per passenger on j * MAX(0,
unconstrained demand for j – number of seats on k)
– Unclear how to compute revenue for flight legs,given
revenue is associated with itineraries
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 13
Spill Cost Computation and
Underlying Assumption
Given,
– Spill cost for flight leg j and fleet assignment k =
average revenue per passenger on j * MAX(0,
unconstrained demand for j – number of seats on
k)
Implication,
– A passenger might be spilled from some,but not
all,of the flight legs in his/ her itinerary
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
FAM Spill Calculation Heuristics
? Fare Allocation
– Full fare - the full fare is assigned to each leg of the
itinerary
– Partial fare - the fare divided by the number of legs is
assigned to each leg of the itinerary
– Shared fare - the fare divided by the number of capacitated
legs is assigned to each capacitated leg in the itinerary
? Spill Cost for each variable
– Representative Fare
? A,spill fare” is calculated; each passenger spilled results in a loss of
revenue equal to the spill fare
– Integration
? Sort each itinerary by fare,spill costs are sum of x lowest fare
passengers,where x = max{0,demand - capacity}
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
An Illustrative Example
X Y Z
flight 1 flight 2Fleet Type SeatsA 100
B 200
Market
Average
FareItinerary
No,of
Pax
1 $200X-Y 75
$225Y-Z 2 150
X-Z 1-2 $300 75
$30,000 $38,125A-A 50 X-Z,75 Y-Z
$15,625A-B $11,250
B-A $22,500 $28,125
Fleet Assign,Full Alloc.Partial Alloc,Actual Opt.
B-B $3,750 $5,625
Fl,1- Fl,2 SpillSpill Spill Spilled Pax
31,875
12,500
28,125
5,625
25 X-Z,25 X-Y
125 Y-Z
25 Y-Z
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
Spill Calculation,Results
? For a 3 fleet,226 flights problem:
– The best representative fare solution results in a
gap with the optimal solution of $2,600/day
– Using a shared fare scheme and integration
approach,we found a solution with an $8/day
gap.
? By simply modifying the basic spill model,
significant gains can be achieved
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
FAM-PMIX,Measures the Spill
Approximation Error
Fleeting
decision
FAM
PMIX
Net
revenues
Operating
costs
Fleeting
contributions
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
Passenger Mix
? Passenger Mix Model (PMIX)
– Kniker (1998)
– Given a fixed,fleeted schedule,unconstrained
passenger demands by itinerary (requests),and
recapture rates find maximum revenue for
passengers on each flight leg
Network Effects and RecapturePMIX
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
FAM Notations
? Decision Variables
– fk,i equals 1 if fleet type k is assigned to flight leg i,and 0
otherwise
– yk,o,t is the number of aircraft of fleet type k,on the ground at
station o,and time t
? Parameters
– Ck,i is the cost of assigning fleet k to flight leg i
– Nk is the number of available aircraft of fleet type k
– tn is the,count time”
? Sets
– L is the set of all flight legs i
– K is the set of all fleet types k
– O is the set of all stations o
– CL(k) is the set of all flight arcs for fleet type k crossing the
count time
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
Fleet Assignment Model (FAM)
Kk ??
? ?
? ?Kk Li
ikik
fcM i n
,,
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
Li ??
tok,,?
Subject to:
Hane et al,(1995),Abara (1989),and Jacobs,Smith and
Johnson (2000)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
FAM Solution
? Exploitation of problem structure and
understanding context are important
– Node consolidation
– Islands
? Branch-and-Bound
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
Time-Line Network
I J
A CF H
D E
B G
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 23
Node Consolidation
I J
A CF H
D E
B G
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 24
Islands
I J
A CF H
D E
B G
K L
? For non-maintenance stations,the minimum
number of aircraft on the ground at some
point in time during the day is 0
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 25
Fleet Assignment Model and
Islands (FAM)
? Implications to number of ground
variables and,required throughs”
– Required through,same aircraft (type)
must fly a sequence of flights
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 26
Branch-and-Bound,FAM Branching
Strategies
? Variable branching
– Set xik = 0 or xik = 1
–,Unbalanced” branches,xik = 0 branch is not as
effective as xik = 1 branch
–,Small” decisions
? Set one variable at a time… might have to solve a number of LPs
? Special ordered set branching
– Set x1k + x2k +…+ x mk= 0 or x1k + x2k +…+ x mk= 1
– More,balanced” branches
–,Larger” decisions
? Allow LP maximal flexibility to select solution,might need to
solve fewer LPs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 27
Branch-and-Bound Termination
Criteria
? Branch-and-bound finds a provable optimal solution
when all branches are pruned
? Branch-and-bound can be terminated prematurely if
solution time limits exist or optimality is not the
objective
– Terminate the algorithm when the lower bound on the
optimal solution for a minimization problem is close
enough to the incumbent IP solution
? Stop when integrality gap is small
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 28
Solution
? Solve fleet assignment problems for large
domestic carriers (10-14 fleets,2000-3500
flights) within 10-20 minutes of computation
time on workstation class computers
? Hane,et al.,The Fleet Assignment Problem,
Solving a Large Integer Program,”
Mathematical Programming,Vol,70,2,pp,211-
232,1995
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 29
FAM Shortcomings,Network Effects
A B C
( 50,$400 )
( Demand,Fare )
Spill Cost
$0
Fleet Type
i
ii
iii
iv
Capacity
80
100
120
150 Network Effects
Leg Interdependence
( 80,$200 ) ( 90,$250 )
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 30
( 50,$400 )9AM
FAM Shortcomings,NO Recapture
A B C
( 80,$200 ) ( 90,$250 )
( Demand,Fare )
30
20
( 20,$400 )10AM
Recapture Rate
X 0.3 = 9 recaptured passengers
29
100 seats 100 seats
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 31
Itinerary-Based Fleet Assignment
? Impossible to estimate airline profit
exactly using link-based costs
? Enhance basic fleet assignment model to
include passenger flow decision variables
– Associate operating costs with fleet assignment
variables
– Associate revenues with passenger flow variables
(PMIX)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 32
Itinerary-based Fleet Assignment
Definition
? Given
– a fixed schedule,
– number of available aircraft of different types,
– unconstrained passenger demands by itinerary,
and
– recapture rates,
Find maximum contribution
Network effectsODFAM
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 33
Kk ??
,,
()
rr
k i k i p p r p
k K i L p P r P
M i n c f f a r e b f a r e t
? ? ? ?
??? ? ? ?
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
Li ??
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 ??
Itinerary-Based FAM (IFAM)
Kniker (1998)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 34
Kk ??
,,
()
rr
k i k i p p r p
k K i L p P r P
M i n c f f a r e b f a r e t
? ? ? ?
??? ? ? ?
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
Li ??
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 ??
Itinerary-Based FAM (IFAM)
Kniker (1998)
FAM
PMMConsistent Spill + Recapture
Fleet Assignment
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 35
Kk ??
,,
()
rr
k i k i p p r p
k K i L p P r P
M i n c f f a r e b f a r e t
? ? ? ?
??? ? ? ?
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
Li ??
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 ??
Itinerary-Based FAM (IFAM)
Kniker (1998)
1
3
2
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 36
IFAM LP
IFAM Solution Algorithm
START
Build Restricted
Master Problem
(RMP)
Solve LP Relax.
STOP
Any
rows or columns
added
YES
Branch and Bound
NO
Preprocessing
1
Row Generation
2
Column Gen.
3
Feas
YES
NO
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 37
Implementation Details
? Computer
– Workstation class
computer
– 2 GB RAM
– CPLEX 6.5
? Full size schedule
– ~2,000 legs
– ~76,000 itineraries
– ~21,000 markets
– 9 fleet types
? RMP constraint matrix
size
– ~77,000 columns
– ~11,000 rows
? Final size
– ~86,000 columns
– ~19,800 rows
? Solution time
– LP,> 1.5 hours
– IP,> 4 hours
88% Saving from Row Generation
> 95% Saving from Column Generation
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 38
IFAM Contributions
? Annual improvements over basic FAM
– Network Effects,~$30 million
– Recapture,~$70 million
? These estimates are upper bounds on
achievable improvements
? Actual improvements will be smaller
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 39
( 50,$400 )9AM
Caveats
A B C
( 80,$200 ) ( 70,$250 )
( Demand,Fare )
X 0.3 = 9 recaptured passengers30
20
( 20,$400 )10AM
Recapture Rate
2,Deterministic
Demand
4,Optimal
Control of Paxs
1,Recapture Rate
Errors
3,Demand
Forecast Errors
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 40
Recapture Rate Sensitivity
Fleeting Contribution
Estimated
Revenue
IFAM
Fleeting Decision
Solve PMM
with varied
recapture rates
Operating Cost
Specified
Recapture Rate
? PMM flows
passengers on
fleeted schedule
assuming full
knowledge of
passenger choices
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 41
Recapture Rate Sensitivity
Recapture Rate Sensitivity
0
1,000
2,000
3,000
4,000
5,000
6,000
7,000
8,000
0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5
Recapture Rate Multiplier ( ?)
Im
pr
ov
em
en
t o
ve
r
Ba
sic
FA
M
($/
da
y)
Sensitivity of IFAM
Improvement gained from network effects alone
Improvement gained from network effects and recapture
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 42
Fleeting Contribution
Estimated
Revenue
IFAM Sensitivity Analysis
? Simulations
FAM
or
IFAM
Fleeting Decision
Passenger
Allocation
Simulation
Operating Cost
Average
Demand
? Simulate 500
realizations of
demand based on
Poisson distributions
Realizations
Demand
Variations
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 43
Fleeting Contribution
Estimated
Revenue
IFAM Sensitivity Analysis
? Simulations
FAM
or
IFAM
Fleeting Decision
Passenger
Allocation
Simulation
Operating Cost
Average
Demand
? Simulate 500
realizations of
demand based on
Poisson distributions
Realizations
Demand
Variations
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 44
FAM IFAM Di f f eren c e ( IFAM - FAM )
P roblem 1N-3A
Rev en ue 4,85 8,08 9$ 4,91 8,69 1$ 60,6 02$
O pe r at i ng Cost 2,02 0,95 9$ 2,02 1,30 0$ 341$
Con trib ut i on 2,83 7,13 0$ 2,89 7,39 1$ 60,2 61$
P roblem 2N-3A
Rev en ue 3,52 6,62 2$ 3,51 3,99 6$ ( 12,6 26 )$
O pe r at i ng Cost 2,25 5,25 4$ 2,23 4,17 2$ ( 21,0 82 )$
Con trib ut i on 1,27 1,36 8$ 1,27 9,82 3$ 8,45 5$
$/ da y
Realizations
Demand
VariationsIFAM vs,FAM
Demand Stochasticity
Demand deviation ~14%
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 45
IFAM vs,FAM
Demand Stochasticity
M od e l Se n s i t i vi t y t o D e m an d F or e c as t E r r or s
$ 1, 0 0
$ 1, 1 0
$ 1, 2 0
$ 1, 3 0
$ 1, 4 0
$ 1, 5 0
$ 1, 6 0
$ 1, 7 0
$ 1, 8 0
- 5 % - 4 % - 3 % - 2 % - 1 % 0 + 1 % + 2 % + 3 % + 4 % + 5 %
S i m u l at e d D e m an d s ( % of F or e c as t e d D e m an d )
C
on
t
r
ib
u
t
i
on
s
(
$
m
i
ll
ion
/d
a
y)
F A M I F A M
Forecast Errors Realizations
Demand
Variations
Demand deviation ~15%Data Quality Issue
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 46
FAM IFAM Di f f eren c e ( IFAM - FAM )
P roblem 1N-3A
Rev en ue 4,83 4,66 4$ 4,87 4,29 8$ 39,6 34$
O pe r at i ng Cost 2,02 0,95 9$ 2,02 1,30 0$ 341$
Con trib ut i on 2,81 3,70 5$ 2,85 2,99 8$ 39,2 93$
P roblem 2N-3A
Rev en ue 3,50 1,60 0$ 3,50 3,14 9$ 1,54 9$
O pe r at i ng Cost 2,25 5,25 4$ 2,23 4,17 2$ ( 21,0 82 )$
Con trib ut i on 1,24 6,34 6$ 1,26 8,97 7$ 22,6 31$
$/ da y
IFAM vs,FAM
Demand Stochasticity
Optimal Control of Passengers
Forecast Errors
From our analysis,there is evidence suggesting that
network effects dominate demand uncertainty
in hub-and-spoke fleet assignment problems.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 47
Another Fleet Assignment
Model and Solution
Approach…
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 48
Subnetwork-Based FAM
? IFAM has tractability issues
? Limited opportunities for further IFAM extension
? Need alternative kernel
– Capture network effects
– Maintain tractability
Tractability
Modeling
Accuracy
FAM
IFAM
SFAM
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 49
Basic Concept
? Isolate network effects
– Spill occurs only on constrained legs
? < 30% of total legs are potentially constrained
? < 6% of total itineraries are potentially binding
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 50
Modeling Challenges
? Utilize composite variables (Armacost,2000;
Barnhart,Farahat and Lohatepanont,2001)
3 F le e t T y p e s, A,B,a n d C
1 2 3 4 5 6 7 8 9
A A A B B B C C C
A B C A B C A B C
?Challenges
?Efficient column enumeration
1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 51
Implementation
? Partition construction
– Construct a complete partition
– Subdivide the complete partition
? Parsimonious column enumeration
– Potentially constrained leg might become
unconstrained if assigned bigger aircraft
Remove up to 97% of otherwise necessary columns
1 2 3 4 5 6 7 8 9
A A A B B B C C C
A B C A B C A B C
1 2 3 4 5 6 7 8
A A A B C
A B C A B C
3 F le e t T y p e s, A,B,a n d C
1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 52
SFAM Formulation
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:
FAM solution algorithm applies
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 53
Results
? 1,888 Flights
? 9 Fleet Types
? 75,484 Itineraries
P artiti on Max No,of No,of
F l i gh t Leg s S ub ne tw ork s
?
1
4 2,0 21
?
2
4 2,0 13
?
3
4 2,0 01
?
4
4 1,9 86
?
5
4 1,9 72
?
6
6 1,9 22
?
7
6 1,9 20
?
8
7 1,9 15
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 54
Partition Construction
? Allow,spill dependent” subnetworks
– Merge spill dependent subnetworks when solution has a
spill calculation error
Potentially
Constrained
Flight Leg
Unconstrained
Flight Leg
Potentially
Binding
Itinerary
Non- Binding
Itinerary
1
2
3
4
5
6
7
8
9
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 55
Runtime
Prepr oc es s LP IP T otal
F AM - 97 893 990
SFAM( ?
1
) 6 103 419 528
SFAM( ?
2
) 9 103 631 743
SFAM( ?
3
) 11 121 485 617
SFAM( ?
4
) 16 109 815 940
SFAM( ?
5
) 22 111 376 509
SFAM( ?
6
) 285 153 1,495 1,933
SFAM( ?
7
) 342 203 2,480 3,025
SFAM( ?
8
) 1,007 249 1,187 2,443
IFAM - 100 6,831 6,931
Runti m e ( s ec )
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 56
Solution Quality
IP - LP Gap
F A M 36
S F A M( ?
1
) + 48,4 07 2,81 1
S F A M( ?
2
) + 48,9 28 191
S F A M( ?
3
) + 50,1 80 162
S F A M( ?
4
) + 50,3 31 69
S F A M( ?
5
) + 50,3 44 53
S F A M( ?
6
) + 50,3 33 543
S F A M( ?
7
) + 50,2 41 758
S F A M( ?
8
) + 50,2 32 198
IF A M + 48,6 91 5,13 2
Con tr i bu ti on ( $/ da y )
21,1 78,8 15
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 57
SFAM,Results & Conclusions
? Testing performed on full size schedules
? SFAM can achieve optimal solutions equivalent to
IFAM’s
? Because of formulation structure,SFAM produces
tighter LP relaxations
? Tighter LP relaxations lead to quicker solution times
? SFAM has great potential for further integration or
extension
– Time windows
– Stochastic demand
– Schedule design
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 58
Extending Fleet Assignment
Models to Include
“Incremental” Schedule
Design…
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 59
Airline Schedule Planning Process
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
Fleet Assignment with Time Windows,A step to
integrate schedule design and fleet assignment
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 60
Fleet Assignment with Time
Windows (FAMTW)
? Assume that departure times (and arrival)
times are NOT fixed for each flight,instead
there is a time window for departures
– Publication of schedule is several months out
– Passenger forecasts won’t change for minor re-
timings
– Produce a better fleet assignment
? Save money (operating costs,spill costs)
? Free up aircraft by,tightening” the schedule
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 61
Time Window Flight Network
B O S
O R D
& %
' $
A
A
A
A
A
AU
A
A
A
A
A
AU
A
A
A
A
A
AU ￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?A
A
A
A
A
AU
A
A
A
A
A
AU
A
A
A
A
A
AU ￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?
A B C D
q q q q q q q q q q q
q q q q q q q q q q q
F i g u r e 1, T i m e w i n d o w ° i g h t n e t w o r k
1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 62
The New Model
? Replace single flight arc with cluster of flight
“copies”
– Try various window widths and copy intervals
– Maintain bank structure to ensure appropriate
passenger connection times are still met
? Change cover constraints to accommodate
flight copies
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 63
Modified Notations for FAMTW
? Decision Variables
– fn,k,i equals 1 if fleet type k is assigned to copy n of flight
leg i,and 0 otherwise
? Parameters
– Cn,k,i is the assignment cost of assigning fleet k to copy
n of flight leg i
? Sets
– Nki is the set of all copies of flight leg i
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 64
Fleet Assignment with Time
Windows Model (FAMTW)
? ? ?
? ? ?Li Kk Nn
iknikn
ki
fCM i n,,,,
0
}1,0{
0
1
,,
,,
)(),(
,,,,
),,(),(
,,,,
),,(),(
,,,,
,,
?
?
??
????
?
??
??
? ?
??
??
? ?
??
tok
ikn
k
kCLni
ikn
Oo
tok
tokOni
ikntok
tokIni
ikntok
Kk Nn
ikn
y
f
Nfy
fyfy
f
n
ki
Kk
tok
Li
??
?
??
,,
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 65
Network Pre-Processing To
Reduce Model Size
? Node consolidation
? Redundant flight copies elimination
? Islands
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 66
Direct Solution Technique (DST)
? Branch-and-bound with Specialized
Branching
? Specialized branching:
– Special ordered sets (SOS)
B O S
O R D
& %
' $
A
A
A
A
A
AU
A
A
A
A
A
AU
A
A
A
A
A
AU ￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?A
A
A
A
A
AU
A
A
A
A
A
AU
A
A
A
A
A
AU ￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?
A B C D
q q q q q q q q q q q
q q q q q q q q q q q
F i g u r e 1, T i m e w i n d o w ° i g h t n e t w o r k
1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 67
Iterative Solution Technique (IST)
Motivation
? Not all flights need multiple flight copies,
generate as needed
? Solve larger problems,perhaps more quickly
than the Direct Solution Technique (DST)
? Make the problem smaller -- this may be
useful if we would like to merge FAMTW
with other models
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 68
Solution Analysis
Time Window Width
w i d th = 0 w i d th = 2 0 w i d th = 4 0
D ai l y C os t I m p r ov e m e n t I m p r ov e m e n t
T ot al 28,4 69,0 66 12 6,55 3 21 2,87 3
P1 O p e r at i on 25,7 92,4 33 16,7 51 24 3,78 9
S p i l l 2,67 6,63 2 (3 7,19 8) (3 0,91 6)
T ot al 29,3 39,8 82 68,1 07 92,0 84
P2 O p e r at i on 26,0 81,0 53 12,7 77 5,40 6
S p i l l 3,25 8,82 9 55,3 30 86,6 78
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 69
Solution Analysis
Flight Copy Interval
Improvements in optimal objective function
value when using 20-minute time windows
I n te r v al = 20 I n te r v al = 5 I n te r v al = 1
P1 122,743 126,553 126,882
P2 67,320 67,819 67,139
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 70
Solution Analysis
Re-fleeting and Re-timing
P 1-20,5 P 2-20,5
# R e -f l e e te d 236 207
% R e -f l e e te d 14.56% 10.16%
# R e -ti m e d 129 111
% R e -ti m e d 7.96% 5.45%
A v g,t i m e S h i f t 8.84 m i n,8.41 m i n
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 71
Solution Analysis
Aircraft Utilization
Do time windows allow us to save
aircraft?
T W = 0 T W = 2 0
a / c r e q ' d c o s t a / c r e q ' d c o s t
P1 365 2 8,2 6 1,3 0 2 363 2 8,1 1 4,9 1 3
P2 428 2 9,0 0 0,1 7 5 426 2 8,9 6 5,4 0 9
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 72
Free Flight
FAMTW Application to Free FlightP ro bl em # o f F l eet s # o f F l i g hts # o f A i rcr a ft
P1 2 456 112
P2 3 1,4 4 5 299
P3 7 2,0 3 7 432
Data Sets
Results
P1 P2 P3
B as e M i n # M i n A / C B as e M i n # M i n A / C B as e M i n # M i n A / C
B as e w / R B T A / C w / R B T B as e w / R B T A / C w / R B T B as e w / R B T A / C w / R B T
F A M
C os t ( m i l l i on $ / da y ) 8,23 8,21 8,23 8,22 20,1 5 20,1 2 20,1 5 20,1 4 28,9 6 28,8 9 29,0 0 28,9 6
C os t I nc r e as e ( $/ da y ) - 21,4 06 - 40 7 - 15,2 63 - 32,3 65 0 - 6,83 0 - 73,1 24 41,4 15 1,32 0
# of A i r c r af t s av e d - - - 3 4 10
F A M T W
C os t ( m i l l i on $ / da y ) 8,21 8,20 8,21 8,21 20,1 2 20,0 8 20,1 2 20,1 1 28,8 9 * 28,9 5 28,9 1
C os t I nc r e as e ( $/ da y ) - 11,6 13 0 - 7,04 3 - 31,7 29 6,28 3 - 8,83 9 - 59,8 07 17,0 97
# of A i r c r af t s av e d - 1 1 5 9 17
* D i d n ot r e a c h s ol u t i on,
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 74
Conclusions
? Time windows can provide significant cost savings,as well as
a potential for freeing aircraft
? Good run times for DST,especially because copies need not
be placed at a fine interval
? IST provides problem size,capacity” so that FAMTW may
be enhanced,integrated with other models,etc.
? Applications,Don’t underestimate value of modeling
Airline Schedule Planning
Cynthia Barnhart
Spring 2003
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 2
1.206J/16.77J/ESD.215J
The Fleet Assignment Problem
? Outline
– Problem Definition and Objective
– Fleet Assignment Network Representation
– Fleet Assignment Model
– Fleet Assignment Solution
? Branch-and-bound
– Results
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
Route individual aircraft honoring
maintenance restrictions
Assign aircraft types to flight legs
such that contribution is maximized
Contribution = Revenue - Costs
Airline Schedule Planning
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
Select optimal set of flight legs
in a schedule
Assign crew (pilots and/or flight
attendants) to flight legs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 4
Problem Definition
Given:
– Flight Schedule
? Each flight covered exactly once by one fleet type
– Number of Aircraft by Equipment Type
? Can’t assign more aircraft than are available,for each
type
– Turn Times by Fleet Type at each Station
– Other Restrictions,Maintenance,Gate,Noise,
Runway,etc.
– Operating Costs,Spill and Recapture Costs,
Total Potential Revenue of Flights,by Fleet
Type
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 5
Problem Objective
Find:
– Cost minimizing (or profit maximizing)
assignment of aircraft fleets to scheduled
flights such that maintenance requirements
are satisfied,conservation of flow (balance)
of aircraft is achieved,and the number of
aircraft used does not exceed the number
available (in each fleet type)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 6
Definitions (again)
? Spill
– passengers that are denied booking due to
capacity restrictions
? Recapture
– passengers that are recaptured back to the
airline after being spilled from another
flight leg
? For each fleet - flight combination:
Cost ? Operating cost + Spill cost
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
Fleet Assignment References
? Abara (1989),Daskin and Panayotopoulos
(1989),Hane,Barnhart,Johnson,Marsten,
Neumhauser,and Sigismondi (1995)
? Hane,et al.,The Fleet Assignment Problem,
Solving a Large Integer Program,”
Mathematical Programming,Vol,70,2,pp,211-
232,1995
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 8
Network Representation
? Topologically sorted time-line network
– Nodes,
? Flight arrivals/ departures (time and space)
– Arcs:
? Flight arcs,one arc for each scheduled flight
? Ground arcs,allow aircraft to sit on the ground
between flights
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 9
Time-Line Network
8:00 12:00 16:00 20:00 8:00 12:00 16:00 20:00
City A
City B
City C
City D
? Ground arcs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
Time-Line Network
?,Daily” problem
– Wrap-around (or overnight) arcs
Washington,D.C.
Baltimore
New York
Boston
Time
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
Constraints
? Cover Constraints
– Each flight must be assigned to exactly one fleet
? Balance Constraints
– Number of aircraft of a fleet type arriving at a station
must equal the number of aircraft of that fleet type
departing
? Aircraft Count Constraints
– Number of aircraft of a fleet type used cannot exceed
the number available
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
Objective Function
For each fleet - flight combination,Cost ?
Operating cost + Spill cost
? Operating cost associated with assigning a fleet type
k to a flight leg j is relatively straightforward to
compute
– Can capture range restrictions,noise restrictions,water
restrictions,etc,by assigning,infinite” costs
? Spill cost for flight leg j and fleet assignment k =
average revenue per passenger on j * MAX(0,
unconstrained demand for j – number of seats on k)
– Unclear how to compute revenue for flight legs,given
revenue is associated with itineraries
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 13
Spill Cost Computation and
Underlying Assumption
Given,
– Spill cost for flight leg j and fleet assignment k =
average revenue per passenger on j * MAX(0,
unconstrained demand for j – number of seats on
k)
Implication,
– A passenger might be spilled from some,but not
all,of the flight legs in his/ her itinerary
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
FAM Spill Calculation Heuristics
? Fare Allocation
– Full fare - the full fare is assigned to each leg of the
itinerary
– Partial fare - the fare divided by the number of legs is
assigned to each leg of the itinerary
– Shared fare - the fare divided by the number of capacitated
legs is assigned to each capacitated leg in the itinerary
? Spill Cost for each variable
– Representative Fare
? A,spill fare” is calculated; each passenger spilled results in a loss of
revenue equal to the spill fare
– Integration
? Sort each itinerary by fare,spill costs are sum of x lowest fare
passengers,where x = max{0,demand - capacity}
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
An Illustrative Example
X Y Z
flight 1 flight 2Fleet Type SeatsA 100
B 200
Market
Average
FareItinerary
No,of
Pax
1 $200X-Y 75
$225Y-Z 2 150
X-Z 1-2 $300 75
$30,000 $38,125A-A 50 X-Z,75 Y-Z
$15,625A-B $11,250
B-A $22,500 $28,125
Fleet Assign,Full Alloc.Partial Alloc,Actual Opt.
B-B $3,750 $5,625
Fl,1- Fl,2 SpillSpill Spill Spilled Pax
31,875
12,500
28,125
5,625
25 X-Z,25 X-Y
125 Y-Z
25 Y-Z
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
Spill Calculation,Results
? For a 3 fleet,226 flights problem:
– The best representative fare solution results in a
gap with the optimal solution of $2,600/day
– Using a shared fare scheme and integration
approach,we found a solution with an $8/day
gap.
? By simply modifying the basic spill model,
significant gains can be achieved
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
FAM-PMIX,Measures the Spill
Approximation Error
Fleeting
decision
FAM
PMIX
Net
revenues
Operating
costs
Fleeting
contributions
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
Passenger Mix
? Passenger Mix Model (PMIX)
– Kniker (1998)
– Given a fixed,fleeted schedule,unconstrained
passenger demands by itinerary (requests),and
recapture rates find maximum revenue for
passengers on each flight leg
Network Effects and RecapturePMIX
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
FAM Notations
? Decision Variables
– fk,i equals 1 if fleet type k is assigned to flight leg i,and 0
otherwise
– yk,o,t is the number of aircraft of fleet type k,on the ground at
station o,and time t
? Parameters
– Ck,i is the cost of assigning fleet k to flight leg i
– Nk is the number of available aircraft of fleet type k
– tn is the,count time”
? Sets
– L is the set of all flight legs i
– K is the set of all fleet types k
– O is the set of all stations o
– CL(k) is the set of all flight arcs for fleet type k crossing the
count time
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
Fleet Assignment Model (FAM)
Kk ??
? ?
? ?Kk Li
ikik
fcM i n
,,
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
Li ??
tok,,?
Subject to:
Hane et al,(1995),Abara (1989),and Jacobs,Smith and
Johnson (2000)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
FAM Solution
? Exploitation of problem structure and
understanding context are important
– Node consolidation
– Islands
? Branch-and-Bound
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
Time-Line Network
I J
A CF H
D E
B G
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 23
Node Consolidation
I J
A CF H
D E
B G
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 24
Islands
I J
A CF H
D E
B G
K L
? For non-maintenance stations,the minimum
number of aircraft on the ground at some
point in time during the day is 0
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 25
Fleet Assignment Model and
Islands (FAM)
? Implications to number of ground
variables and,required throughs”
– Required through,same aircraft (type)
must fly a sequence of flights
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 26
Branch-and-Bound,FAM Branching
Strategies
? Variable branching
– Set xik = 0 or xik = 1
–,Unbalanced” branches,xik = 0 branch is not as
effective as xik = 1 branch
–,Small” decisions
? Set one variable at a time… might have to solve a number of LPs
? Special ordered set branching
– Set x1k + x2k +…+ x mk= 0 or x1k + x2k +…+ x mk= 1
– More,balanced” branches
–,Larger” decisions
? Allow LP maximal flexibility to select solution,might need to
solve fewer LPs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 27
Branch-and-Bound Termination
Criteria
? Branch-and-bound finds a provable optimal solution
when all branches are pruned
? Branch-and-bound can be terminated prematurely if
solution time limits exist or optimality is not the
objective
– Terminate the algorithm when the lower bound on the
optimal solution for a minimization problem is close
enough to the incumbent IP solution
? Stop when integrality gap is small
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 28
Solution
? Solve fleet assignment problems for large
domestic carriers (10-14 fleets,2000-3500
flights) within 10-20 minutes of computation
time on workstation class computers
? Hane,et al.,The Fleet Assignment Problem,
Solving a Large Integer Program,”
Mathematical Programming,Vol,70,2,pp,211-
232,1995
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 29
FAM Shortcomings,Network Effects
A B C
( 50,$400 )
( Demand,Fare )
Spill Cost
$0
Fleet Type
i
ii
iii
iv
Capacity
80
100
120
150 Network Effects
Leg Interdependence
( 80,$200 ) ( 90,$250 )
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 30
( 50,$400 )9AM
FAM Shortcomings,NO Recapture
A B C
( 80,$200 ) ( 90,$250 )
( Demand,Fare )
30
20
( 20,$400 )10AM
Recapture Rate
X 0.3 = 9 recaptured passengers
29
100 seats 100 seats
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 31
Itinerary-Based Fleet Assignment
? Impossible to estimate airline profit
exactly using link-based costs
? Enhance basic fleet assignment model to
include passenger flow decision variables
– Associate operating costs with fleet assignment
variables
– Associate revenues with passenger flow variables
(PMIX)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 32
Itinerary-based Fleet Assignment
Definition
? Given
– a fixed schedule,
– number of available aircraft of different types,
– unconstrained passenger demands by itinerary,
and
– recapture rates,
Find maximum contribution
Network effectsODFAM
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 33
Kk ??
,,
()
rr
k i k i p p r p
k K i L p P r P
M i n c f f a r e b f a r e t
? ? ? ?
??? ? ? ?
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
Li ??
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 ??
Itinerary-Based FAM (IFAM)
Kniker (1998)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 34
Kk ??
,,
()
rr
k i k i p p r p
k K i L p P r P
M i n c f f a r e b f a r e t
? ? ? ?
??? ? ? ?
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
Li ??
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 ??
Itinerary-Based FAM (IFAM)
Kniker (1998)
FAM
PMMConsistent Spill + Recapture
Fleet Assignment
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 35
Kk ??
,,
()
rr
k i k i p p r p
k K i L p P r P
M i n c f f a r e b f a r e t
? ? ? ?
??? ? ? ?
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
Li ??
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 ??
Itinerary-Based FAM (IFAM)
Kniker (1998)
1
3
2
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 36
IFAM LP
IFAM Solution Algorithm
START
Build Restricted
Master Problem
(RMP)
Solve LP Relax.
STOP
Any
rows or columns
added
YES
Branch and Bound
NO
Preprocessing
1
Row Generation
2
Column Gen.
3
Feas
YES
NO
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 37
Implementation Details
? Computer
– Workstation class
computer
– 2 GB RAM
– CPLEX 6.5
? Full size schedule
– ~2,000 legs
– ~76,000 itineraries
– ~21,000 markets
– 9 fleet types
? RMP constraint matrix
size
– ~77,000 columns
– ~11,000 rows
? Final size
– ~86,000 columns
– ~19,800 rows
? Solution time
– LP,> 1.5 hours
– IP,> 4 hours
88% Saving from Row Generation
> 95% Saving from Column Generation
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 38
IFAM Contributions
? Annual improvements over basic FAM
– Network Effects,~$30 million
– Recapture,~$70 million
? These estimates are upper bounds on
achievable improvements
? Actual improvements will be smaller
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 39
( 50,$400 )9AM
Caveats
A B C
( 80,$200 ) ( 70,$250 )
( Demand,Fare )
X 0.3 = 9 recaptured passengers30
20
( 20,$400 )10AM
Recapture Rate
2,Deterministic
Demand
4,Optimal
Control of Paxs
1,Recapture Rate
Errors
3,Demand
Forecast Errors
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 40
Recapture Rate Sensitivity
Fleeting Contribution
Estimated
Revenue
IFAM
Fleeting Decision
Solve PMM
with varied
recapture rates
Operating Cost
Specified
Recapture Rate
? PMM flows
passengers on
fleeted schedule
assuming full
knowledge of
passenger choices
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 41
Recapture Rate Sensitivity
Recapture Rate Sensitivity
0
1,000
2,000
3,000
4,000
5,000
6,000
7,000
8,000
0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5
Recapture Rate Multiplier ( ?)
Im
pr
ov
em
en
t o
ve
r
Ba
sic
FA
M
($/
da
y)
Sensitivity of IFAM
Improvement gained from network effects alone
Improvement gained from network effects and recapture
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 42
Fleeting Contribution
Estimated
Revenue
IFAM Sensitivity Analysis
? Simulations
FAM
or
IFAM
Fleeting Decision
Passenger
Allocation
Simulation
Operating Cost
Average
Demand
? Simulate 500
realizations of
demand based on
Poisson distributions
Realizations
Demand
Variations
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 43
Fleeting Contribution
Estimated
Revenue
IFAM Sensitivity Analysis
? Simulations
FAM
or
IFAM
Fleeting Decision
Passenger
Allocation
Simulation
Operating Cost
Average
Demand
? Simulate 500
realizations of
demand based on
Poisson distributions
Realizations
Demand
Variations
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 44
FAM IFAM Di f f eren c e ( IFAM - FAM )
P roblem 1N-3A
Rev en ue 4,85 8,08 9$ 4,91 8,69 1$ 60,6 02$
O pe r at i ng Cost 2,02 0,95 9$ 2,02 1,30 0$ 341$
Con trib ut i on 2,83 7,13 0$ 2,89 7,39 1$ 60,2 61$
P roblem 2N-3A
Rev en ue 3,52 6,62 2$ 3,51 3,99 6$ ( 12,6 26 )$
O pe r at i ng Cost 2,25 5,25 4$ 2,23 4,17 2$ ( 21,0 82 )$
Con trib ut i on 1,27 1,36 8$ 1,27 9,82 3$ 8,45 5$
$/ da y
Realizations
Demand
VariationsIFAM vs,FAM
Demand Stochasticity
Demand deviation ~14%
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 45
IFAM vs,FAM
Demand Stochasticity
M od e l Se n s i t i vi t y t o D e m an d F or e c as t E r r or s
$ 1, 0 0
$ 1, 1 0
$ 1, 2 0
$ 1, 3 0
$ 1, 4 0
$ 1, 5 0
$ 1, 6 0
$ 1, 7 0
$ 1, 8 0
- 5 % - 4 % - 3 % - 2 % - 1 % 0 + 1 % + 2 % + 3 % + 4 % + 5 %
S i m u l at e d D e m an d s ( % of F or e c as t e d D e m an d )
C
on
t
r
ib
u
t
i
on
s
(
$
m
i
ll
ion
/d
a
y)
F A M I F A M
Forecast Errors Realizations
Demand
Variations
Demand deviation ~15%Data Quality Issue
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 46
FAM IFAM Di f f eren c e ( IFAM - FAM )
P roblem 1N-3A
Rev en ue 4,83 4,66 4$ 4,87 4,29 8$ 39,6 34$
O pe r at i ng Cost 2,02 0,95 9$ 2,02 1,30 0$ 341$
Con trib ut i on 2,81 3,70 5$ 2,85 2,99 8$ 39,2 93$
P roblem 2N-3A
Rev en ue 3,50 1,60 0$ 3,50 3,14 9$ 1,54 9$
O pe r at i ng Cost 2,25 5,25 4$ 2,23 4,17 2$ ( 21,0 82 )$
Con trib ut i on 1,24 6,34 6$ 1,26 8,97 7$ 22,6 31$
$/ da y
IFAM vs,FAM
Demand Stochasticity
Optimal Control of Passengers
Forecast Errors
From our analysis,there is evidence suggesting that
network effects dominate demand uncertainty
in hub-and-spoke fleet assignment problems.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 47
Another Fleet Assignment
Model and Solution
Approach…
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 48
Subnetwork-Based FAM
? IFAM has tractability issues
? Limited opportunities for further IFAM extension
? Need alternative kernel
– Capture network effects
– Maintain tractability
Tractability
Modeling
Accuracy
FAM
IFAM
SFAM
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 49
Basic Concept
? Isolate network effects
– Spill occurs only on constrained legs
? < 30% of total legs are potentially constrained
? < 6% of total itineraries are potentially binding
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 50
Modeling Challenges
? Utilize composite variables (Armacost,2000;
Barnhart,Farahat and Lohatepanont,2001)
3 F le e t T y p e s, A,B,a n d C
1 2 3 4 5 6 7 8 9
A A A B B B C C C
A B C A B C A B C
?Challenges
?Efficient column enumeration
1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 51
Implementation
? Partition construction
– Construct a complete partition
– Subdivide the complete partition
? Parsimonious column enumeration
– Potentially constrained leg might become
unconstrained if assigned bigger aircraft
Remove up to 97% of otherwise necessary columns
1 2 3 4 5 6 7 8 9
A A A B B B C C C
A B C A B C A B C
1 2 3 4 5 6 7 8
A A A B C
A B C A B C
3 F le e t T y p e s, A,B,a n d C
1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 52
SFAM Formulation
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:
FAM solution algorithm applies
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 53
Results
? 1,888 Flights
? 9 Fleet Types
? 75,484 Itineraries
P artiti on Max No,of No,of
F l i gh t Leg s S ub ne tw ork s
?
1
4 2,0 21
?
2
4 2,0 13
?
3
4 2,0 01
?
4
4 1,9 86
?
5
4 1,9 72
?
6
6 1,9 22
?
7
6 1,9 20
?
8
7 1,9 15
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 54
Partition Construction
? Allow,spill dependent” subnetworks
– Merge spill dependent subnetworks when solution has a
spill calculation error
Potentially
Constrained
Flight Leg
Unconstrained
Flight Leg
Potentially
Binding
Itinerary
Non- Binding
Itinerary
1
2
3
4
5
6
7
8
9
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 55
Runtime
Prepr oc es s LP IP T otal
F AM - 97 893 990
SFAM( ?
1
) 6 103 419 528
SFAM( ?
2
) 9 103 631 743
SFAM( ?
3
) 11 121 485 617
SFAM( ?
4
) 16 109 815 940
SFAM( ?
5
) 22 111 376 509
SFAM( ?
6
) 285 153 1,495 1,933
SFAM( ?
7
) 342 203 2,480 3,025
SFAM( ?
8
) 1,007 249 1,187 2,443
IFAM - 100 6,831 6,931
Runti m e ( s ec )
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 56
Solution Quality
IP - LP Gap
F A M 36
S F A M( ?
1
) + 48,4 07 2,81 1
S F A M( ?
2
) + 48,9 28 191
S F A M( ?
3
) + 50,1 80 162
S F A M( ?
4
) + 50,3 31 69
S F A M( ?
5
) + 50,3 44 53
S F A M( ?
6
) + 50,3 33 543
S F A M( ?
7
) + 50,2 41 758
S F A M( ?
8
) + 50,2 32 198
IF A M + 48,6 91 5,13 2
Con tr i bu ti on ( $/ da y )
21,1 78,8 15
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 57
SFAM,Results & Conclusions
? Testing performed on full size schedules
? SFAM can achieve optimal solutions equivalent to
IFAM’s
? Because of formulation structure,SFAM produces
tighter LP relaxations
? Tighter LP relaxations lead to quicker solution times
? SFAM has great potential for further integration or
extension
– Time windows
– Stochastic demand
– Schedule design
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 58
Extending Fleet Assignment
Models to Include
“Incremental” Schedule
Design…
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 59
Airline Schedule Planning Process
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
Fleet Assignment with Time Windows,A step to
integrate schedule design and fleet assignment
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 60
Fleet Assignment with Time
Windows (FAMTW)
? Assume that departure times (and arrival)
times are NOT fixed for each flight,instead
there is a time window for departures
– Publication of schedule is several months out
– Passenger forecasts won’t change for minor re-
timings
– Produce a better fleet assignment
? Save money (operating costs,spill costs)
? Free up aircraft by,tightening” the schedule
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 61
Time Window Flight Network
B O S
O R D
& %
' $
A
A
A
A
A
AU
A
A
A
A
A
AU
A
A
A
A
A
AU ￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?A
A
A
A
A
AU
A
A
A
A
A
AU
A
A
A
A
A
AU ￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?
A B C D
q q q q q q q q q q q
q q q q q q q q q q q
F i g u r e 1, T i m e w i n d o w ° i g h t n e t w o r k
1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 62
The New Model
? Replace single flight arc with cluster of flight
“copies”
– Try various window widths and copy intervals
– Maintain bank structure to ensure appropriate
passenger connection times are still met
? Change cover constraints to accommodate
flight copies
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 63
Modified Notations for FAMTW
? Decision Variables
– fn,k,i equals 1 if fleet type k is assigned to copy n of flight
leg i,and 0 otherwise
? Parameters
– Cn,k,i is the assignment cost of assigning fleet k to copy
n of flight leg i
? Sets
– Nki is the set of all copies of flight leg i
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 64
Fleet Assignment with Time
Windows Model (FAMTW)
? ? ?
? ? ?Li Kk Nn
iknikn
ki
fCM i n,,,,
0
}1,0{
0
1
,,
,,
)(),(
,,,,
),,(),(
,,,,
),,(),(
,,,,
,,
?
?
??
????
?
??
??
? ?
??
??
? ?
??
tok
ikn
k
kCLni
ikn
Oo
tok
tokOni
ikntok
tokIni
ikntok
Kk Nn
ikn
y
f
Nfy
fyfy
f
n
ki
Kk
tok
Li
??
?
??
,,
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 65
Network Pre-Processing To
Reduce Model Size
? Node consolidation
? Redundant flight copies elimination
? Islands
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 66
Direct Solution Technique (DST)
? Branch-and-bound with Specialized
Branching
? Specialized branching:
– Special ordered sets (SOS)
B O S
O R D
& %
' $
A
A
A
A
A
AU
A
A
A
A
A
AU
A
A
A
A
A
AU ￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?A
A
A
A
A
AU
A
A
A
A
A
AU
A
A
A
A
A
AU ￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?
￠
￠
￠
￠
￠
￠?
A B C D
q q q q q q q q q q q
q q q q q q q q q q q
F i g u r e 1, T i m e w i n d o w ° i g h t n e t w o r k
1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 67
Iterative Solution Technique (IST)
Motivation
? Not all flights need multiple flight copies,
generate as needed
? Solve larger problems,perhaps more quickly
than the Direct Solution Technique (DST)
? Make the problem smaller -- this may be
useful if we would like to merge FAMTW
with other models
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 68
Solution Analysis
Time Window Width
w i d th = 0 w i d th = 2 0 w i d th = 4 0
D ai l y C os t I m p r ov e m e n t I m p r ov e m e n t
T ot al 28,4 69,0 66 12 6,55 3 21 2,87 3
P1 O p e r at i on 25,7 92,4 33 16,7 51 24 3,78 9
S p i l l 2,67 6,63 2 (3 7,19 8) (3 0,91 6)
T ot al 29,3 39,8 82 68,1 07 92,0 84
P2 O p e r at i on 26,0 81,0 53 12,7 77 5,40 6
S p i l l 3,25 8,82 9 55,3 30 86,6 78
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 69
Solution Analysis
Flight Copy Interval
Improvements in optimal objective function
value when using 20-minute time windows
I n te r v al = 20 I n te r v al = 5 I n te r v al = 1
P1 122,743 126,553 126,882
P2 67,320 67,819 67,139
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 70
Solution Analysis
Re-fleeting and Re-timing
P 1-20,5 P 2-20,5
# R e -f l e e te d 236 207
% R e -f l e e te d 14.56% 10.16%
# R e -ti m e d 129 111
% R e -ti m e d 7.96% 5.45%
A v g,t i m e S h i f t 8.84 m i n,8.41 m i n
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 71
Solution Analysis
Aircraft Utilization
Do time windows allow us to save
aircraft?
T W = 0 T W = 2 0
a / c r e q ' d c o s t a / c r e q ' d c o s t
P1 365 2 8,2 6 1,3 0 2 363 2 8,1 1 4,9 1 3
P2 428 2 9,0 0 0,1 7 5 426 2 8,9 6 5,4 0 9
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 72
Free Flight
FAMTW Application to Free FlightP ro bl em # o f F l eet s # o f F l i g hts # o f A i rcr a ft
P1 2 456 112
P2 3 1,4 4 5 299
P3 7 2,0 3 7 432
Data Sets
Results
P1 P2 P3
B as e M i n # M i n A / C B as e M i n # M i n A / C B as e M i n # M i n A / C
B as e w / R B T A / C w / R B T B as e w / R B T A / C w / R B T B as e w / R B T A / C w / R B T
F A M
C os t ( m i l l i on $ / da y ) 8,23 8,21 8,23 8,22 20,1 5 20,1 2 20,1 5 20,1 4 28,9 6 28,8 9 29,0 0 28,9 6
C os t I nc r e as e ( $/ da y ) - 21,4 06 - 40 7 - 15,2 63 - 32,3 65 0 - 6,83 0 - 73,1 24 41,4 15 1,32 0
# of A i r c r af t s av e d - - - 3 4 10
F A M T W
C os t ( m i l l i on $ / da y ) 8,21 8,20 8,21 8,21 20,1 2 20,0 8 20,1 2 20,1 1 28,8 9 * 28,9 5 28,9 1
C os t I nc r e as e ( $/ da y ) - 11,6 13 0 - 7,04 3 - 31,7 29 6,28 3 - 8,83 9 - 59,8 07 17,0 97
# of A i r c r af t s av e d - 1 1 5 9 17
* D i d n ot r e a c h s ol u t i on,
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 74
Conclusions
? Time windows can provide significant cost savings,as well as
a potential for freeing aircraft
? Good run times for DST,especially because copies need not
be placed at a fine interval
? IST provides problem size,capacity” so that FAMTW may
be enhanced,integrated with other models,etc.
? Applications,Don’t underestimate value of modeling
