1.206J/16.77J/ESD.215J
Airline Schedule Planning
Cynthia Barnhart
Spring 2003
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 2
Aircraft Maintenance Routing
Outline
– Problem Definition and Objective
– Network Representation
– String Model
– Solution Approach
– Branch-and-price
– Extension,Combined Fleet Assignment and
Aircraft Routing
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
Airline Schedule Planning
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 4
Airline Schedule Planning
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
String-
Based
FAM
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 5
Problem Definition
? Given:
– Flight Schedule for a single fleet
? Each flight covered exactly once by fleet
– Number of Aircraft by Equipment Type
? Can’t assign more aircraft than are available
– FAA Maintenance Requirements
– Turn Times at each Station
– Through revenues for pairs or sequences of flights
– Maintenance costs per aircraft
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 6
Problem Objective
? Find:
– Revenue maximizing assignment of aircraft of a
single fleet to scheduled flights such that each
flight is covered exactly once,maintenance
requirements are satisfied,conservation of flow
(balance) of aircraft is achieved,and the number
of aircraft used does not exceed the number
available
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
FAA Maintenance Requirements
?,A” Checks
– Maintenance required every 60 hours of flying
– Airlines maintain aircraft every 40-45 hours of
flying with the maximum time between checks
restricted to three to four calendar days
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 8
FAM Representation of
Maintenance Constraints
? Maintenance arcs for fleet k included in time line
network at each maintenance station for k
? Each arc
– Begins at an aircraft arrival + turn time
– Spans minimum maintenance time
? Constraints added to FAM for each aircraft type k,
requiring a minimum number of aircraft of type k
on the set of,maintenance arcs”
– Ensures that sufficient maintenance opportunities exist
– One aircraft might be serviced daily and others not at all
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 9
Hub-and-Spoke vs,Point-to-Point
Networks
? Domestic U.S,carriers with hub-and-spoke
networks find that approximate maintenance
constraints result in maintenance feasible routings
– Sufficient number of opportunities at hubs to swap
aircraft assignments so that aircraft get to maintenance
stations as needed
? Approximate maintenance constraints often do not
result in maintenance feasible routings for point-to-
point networks
– Flying time between visits to maintenance stations often
too long
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
Network Representation
? Connection network
– Nodes,
? Flight arrivals/ departures (time and space)
– Arcs:
? Flight arcs,one arc for each scheduled flight
? Connection arcs,allow aircraft to connect between
flights
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
Connection Network
M1
A1
A2
A3
M2
Fli gh t A r c
Con ne c ti on A r c
T imeline
A B C
D
E
F
G
H
J
K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
Connection vs,Time-line Network
? Network Size
– Time-line network typically has more arcs than
connection network
? Model capabilities
– Connection network provides richer modeling
possibilities
? Through revenues can be captured easily
? Disallowed or forced connections can be modeled
easily
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 13
String Model,Variable Definition
? A string is a sequence of flights beginning and
ending at a maintenance station with maintenance
following the last flight in the sequence
– Departure time of the string is the departure time of
the first flight in the sequence
– Arrival time of the string is the arrival time of the last
flight in the sequence + maintenance time
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
String Model,Constraints
? Maintenance constraints
– Satisfied by variable definition
? Cover constraints
– Each flight must be assigned to exactly one string
? Balance constraints
– Needed only at maintenance stations
? Fleet size constraints
– The number of strings and connection arcs crossing the
count time cannot exceed the number of aircraft in the
fleet
NOTE,If the problem is daily,each string can
contain a flight at most once! Assume we focus on
weekly problem.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
Model Strengths and Weaknesses
? Nonlinearities and complex constraints can
be handled relatively easily
? Model size
– Number of variables
– Number of constraints
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
Notations
K i s t h e s e t o f ° e e t s
x
k
i s a n a u g m e n t e d s t r i n g v a r i a b l e e q u a l t o 1 i f s 2 S i s ° o w n b y ° e e t k i n t h e s o l u t i o n,a n d
e q u a l t o 0 o t h e r w i s e
y
k
c o u n t s t h e n u m b e r o f a i r c r a f t o f ° e e t k o n t h e g r o u n d a t m a i n t e n a n c e s t a t i o n s
e
k
i ; a
( e
k
i ; d
) i s t h e e v e n t n u m b e r f o r ° e e t k c o r r e s p o n d i n g t o t h e a r r i v a l ( d e p a r t u r e ) o f ° i g h t i
a t s o m e m a i n t e n a n c e s t a t i o n
e
+ ; k
i ; a
( e
+ ; k
i ; d
) i s t h e n e x t e v e n t f o r k a t t h a t s t a t i o n a f t e r t h e a r r i v a l ( d e p a r t u r e ) o f i
e
? ; k
i ; a
( e
? ; k
i ; d
) i s t h e e v e n t a t t h a t s t a t i o n p r e c e d i n g t h e a r r i v a l ( d e p a r t u r e ) o f i
G
k
i s t h e s e t o f g r o u n d v a r i a b l e s f o r ° e e t k
S
?
i
i s t h e s e t o f a u g m e n t e d s t r i n g s e n d i n g w i t h ° i g h t i a n d m a i n t e n a n c e
S
+
i
i s t h e s e t o f a u g m e n t e d s t r i n g s b e g i n n i n g w i t h ° i g h t i
a
i s
e q u a l s 1 i f ° i g h t i 2 F i s i n a u g m e n t e d s t r i n g s,a n d e q u a l s 0 o t h e r w i s e
c
k
s
i s t h e c o s t o f ° y i n g a u g m e n t e d s t r i n g s w i t h ° e e t k
r
k
s
i s t h e n u m b e r o f t i m e s ( p o s s i b l y g r e a t e r t h a n 1 ) a u g m e n t e d s t r i n g s a s s i g n e d t o ° e e t k
c r o s s e s t h e c o u n t t i m e
p
k
j
i s t h e n u m b e r o f t i m e s ( 0 o r 1 ) g r o u n d a r c j 2 G
k
f o r ° e e t k c r o s s e s t h e c o u n t t i m e
N
k
i s t h e n u m b e r o f p l a n e s i n ° e e t k
1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
Aircraft Maintenance Routing,
String Model
min
P
k2K
P
s2S
ck
s
xk
sP
k2K
P
s2S
a
is
xk
s
= 1; 8i2 F
P
s2S
+
i
xk
s
?yk
(e
? ;k
i;d;ek
i;d
)
+ yk
(ek
i;d;e
+ ;k
i;d
)
= 0; 8i2 F;8k2 K
?
P
s2S
?
i
xk
s
?yk
(e
? ;k
i;a;ek
i;a
)
+ yk
(ek
i;a;e
+ ;k
i;a
)
= 0; 8i2 F;8k2 K
P
s2S
rk
s
xk
s
+
P
j2Gk
pk
j
yk
j
Nk; 8k2 K
yk
j
? 0; 8j2 Gk;8k2 K
x
k
s 2 f 0;1g; 8s 2 S;8k2 K:
( 1)?
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
Model Solution
? Integer program
– Branch-and-bound with too many variables to consider
all of them
– Solve Linear Program using Column Generation
? Branch-and-Price
– Branch-and-bound with bounding provided by solving
LP’s using column generation,at each node of the
branch-and-bound tree
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
LP Solution,Column Generation
? Step 1,Solve Restricted Master Problem
? Step 2,Solve Pricing Problem (generate
columns)
? Step 3,If columns generated,return to Step
1; otherwise STOP
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
Generating The Right Variables
? Find a Variable with,Negative-Reduced
Cost”
– From Linear Programming Theory
? reduced cost of each string between two nodes = cost
- sum of the dual variables associated with flights in
string + constant
– Not feasible to compute reduced cost for each
variable,instead exploit problem structure
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
The Pricing Problem,A
Constrained Shortest Path
Problem
? If the,Length” of the shortest path is
– negative,a variable has been identified for inclusion in
the LP;
– non-negative,the optimal LP solution is found
Washington,D.C.
Baltimore
New York
Boston
TimeTime-Line Network
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
Pricing Problem Solution
? Find negative reduced cost route between
maintenance stations
? Price-out columns by running a shortest path
procedure with costs on arcs modified
? Ensure that shortest path solution satisfies
maintenance constraints
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 23
Path Lengths in Modified
Network
M1
A1
A2
A3
M2
Fli gh t A r c
Con ne c ti on A r c
T imeline
A B C
D
E
F
G
H
J
K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 24
Maintenance Requirements and
the Pricing Problem Solution
? Maximum Elapsed Time Requirement
– Unconstrained,simple shortest path computation
– Computationally inexpensive
? Maximum Flying Time Requirement
– Constrained shortest path procedure
? Additional labels need to be maintained
– Computationally expensive
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 25
Maximum Flying Time
Requirement,Multiple Labels and
Dominance
? Label i has cost c(i) and elapsed flying time t(i)
? Label i dominates label i+1 if c(i) ______
c(i+1) and t(i) _______ t(i+1)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 27
Branch-and-Price Challenge
? Devise Branching Strategy that:
– Is Compatible with Column Generation
Subproblem
? Does not destroy tractability of pricing problem
? Conventional branching based on variable dichotomy
does not work
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 28
Branching Strategy
? Branch on follow-ons:
– Identify two fractional strings s and s’
– Select flight i(1) contained in both strings
? One exists because __________________________
– Select flight i(2) contained in s but not s’
? One exists because __________________________
– Select i(1)-i(2) pair such that i(1) is followed immediately
by i(2) in s
? Such a pair exists
______________________________________
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 29
Branches
? Left branch,force flight i(1) to be followed
by i(2) if i(1) and i(2) are in the string
– To enforce,eliminate any connection arcs
including i(1) or i(2) but not both
? Right branch,do not allow flight i(1) to be
followed by i(2)
– To enforce,eliminate any connection arcs from
i(1) to i(2)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 30
Summary,Branch-and-Price
? At each node of the Branch-and-Bound tree
– Column generation used to solve LP
? Column Generation
– Allows huge LPs to be solved by considering only a
subset of all variables (columns)
– Solves shortest path subproblem repeatedly to generate
additional columns as needed
? Nontrivial Implementations
– New branching strategies necessary
– Ongoing research
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 31
Extensions,Combined Fleeting
and Routing
? Motivation,Long-haul applications
– Approximate maintenance constraints in FAM
might result in,maintenance-infeasible”
solutions
– Exact maintenance constraints necessary
? Need to model individual aircraft routings
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 32
Objective
? Minimize operating costs plus approximate
spill costs minus through revenues
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 33
Model Solution
? Branch-and-Price
– Branch on,fleet-flight” pairs
? Provides a partition of flights to fleets
? Enforce by
_________________________________________
– For each resulting fleet specific aircraft routing
problem
? Branch on follow-ons
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 34
Case Study
? Data provided by a major US long haul airline
– 1162 flights per week serving 55 cities worldwide
– 11 fleet types and 75 aircraft
– 8 maintenance stations
? Subproblems generated to perform scenario
analyses quickly
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 35
Problem Sizes
P r o b l e m
N ame
#
F l e e t s
#
F l i g h t s
P1
P2
P3
P4
P5
P6
2
2
4
4
7
11
126
403
360
536
546
1162
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 36
Effect of Maintenance
Requirements
P r obl e m
nam e
# f l igh t s
( # f l e e t s )
Sh or t e s t P at h
P r obl e m
Sol ut ion
T im e
Sol ut ion
V al ue
P1 12 6 ( 2) U n c o n s t r a i n e d
C o n s t r a i n e d
7s
17s
2960369,00
2960369,00
P2 40 8 ( 2) U n c o n s t r a i n e d
C o n s t r a i n e d
2m 1s
6m 43 s
10611441,00
10641120,00
P4 53 6 ( 4) U n c o n s t r a i n e d
C o n s t r a i n e d
38 m 38 s
4h 14 m 22 s
13624637,45
13563334,35
P5 54 6 ( 7) U n c o n s t r a i n e d
C o n s t r a i n e d
23 m 11 s
1h 45 m 46 s
16286255,29
16179416,08
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 37
Summary
? New model and solution approach for the combined fleet
assignment and aircraft routing problems
? Computational experiments showed:
– Near-optimal solutions in reasonable run times
– Maintenance feasible solutions ensured
– Through revenues captured
? One step closer to integration of overall airline scheduling
process
Airline Schedule Planning
Cynthia Barnhart
Spring 2003
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 2
Aircraft Maintenance Routing
Outline
– Problem Definition and Objective
– Network Representation
– String Model
– Solution Approach
– Branch-and-price
– Extension,Combined Fleet Assignment and
Aircraft Routing
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
Airline Schedule Planning
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 4
Airline Schedule Planning
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
String-
Based
FAM
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 5
Problem Definition
? Given:
– Flight Schedule for a single fleet
? Each flight covered exactly once by fleet
– Number of Aircraft by Equipment Type
? Can’t assign more aircraft than are available
– FAA Maintenance Requirements
– Turn Times at each Station
– Through revenues for pairs or sequences of flights
– Maintenance costs per aircraft
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 6
Problem Objective
? Find:
– Revenue maximizing assignment of aircraft of a
single fleet to scheduled flights such that each
flight is covered exactly once,maintenance
requirements are satisfied,conservation of flow
(balance) of aircraft is achieved,and the number
of aircraft used does not exceed the number
available
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
FAA Maintenance Requirements
?,A” Checks
– Maintenance required every 60 hours of flying
– Airlines maintain aircraft every 40-45 hours of
flying with the maximum time between checks
restricted to three to four calendar days
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 8
FAM Representation of
Maintenance Constraints
? Maintenance arcs for fleet k included in time line
network at each maintenance station for k
? Each arc
– Begins at an aircraft arrival + turn time
– Spans minimum maintenance time
? Constraints added to FAM for each aircraft type k,
requiring a minimum number of aircraft of type k
on the set of,maintenance arcs”
– Ensures that sufficient maintenance opportunities exist
– One aircraft might be serviced daily and others not at all
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 9
Hub-and-Spoke vs,Point-to-Point
Networks
? Domestic U.S,carriers with hub-and-spoke
networks find that approximate maintenance
constraints result in maintenance feasible routings
– Sufficient number of opportunities at hubs to swap
aircraft assignments so that aircraft get to maintenance
stations as needed
? Approximate maintenance constraints often do not
result in maintenance feasible routings for point-to-
point networks
– Flying time between visits to maintenance stations often
too long
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
Network Representation
? Connection network
– Nodes,
? Flight arrivals/ departures (time and space)
– Arcs:
? Flight arcs,one arc for each scheduled flight
? Connection arcs,allow aircraft to connect between
flights
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
Connection Network
M1
A1
A2
A3
M2
Fli gh t A r c
Con ne c ti on A r c
T imeline
A B C
D
E
F
G
H
J
K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
Connection vs,Time-line Network
? Network Size
– Time-line network typically has more arcs than
connection network
? Model capabilities
– Connection network provides richer modeling
possibilities
? Through revenues can be captured easily
? Disallowed or forced connections can be modeled
easily
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 13
String Model,Variable Definition
? A string is a sequence of flights beginning and
ending at a maintenance station with maintenance
following the last flight in the sequence
– Departure time of the string is the departure time of
the first flight in the sequence
– Arrival time of the string is the arrival time of the last
flight in the sequence + maintenance time
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
String Model,Constraints
? Maintenance constraints
– Satisfied by variable definition
? Cover constraints
– Each flight must be assigned to exactly one string
? Balance constraints
– Needed only at maintenance stations
? Fleet size constraints
– The number of strings and connection arcs crossing the
count time cannot exceed the number of aircraft in the
fleet
NOTE,If the problem is daily,each string can
contain a flight at most once! Assume we focus on
weekly problem.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
Model Strengths and Weaknesses
? Nonlinearities and complex constraints can
be handled relatively easily
? Model size
– Number of variables
– Number of constraints
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
Notations
K i s t h e s e t o f ° e e t s
x
k
i s a n a u g m e n t e d s t r i n g v a r i a b l e e q u a l t o 1 i f s 2 S i s ° o w n b y ° e e t k i n t h e s o l u t i o n,a n d
e q u a l t o 0 o t h e r w i s e
y
k
c o u n t s t h e n u m b e r o f a i r c r a f t o f ° e e t k o n t h e g r o u n d a t m a i n t e n a n c e s t a t i o n s
e
k
i ; a
( e
k
i ; d
) i s t h e e v e n t n u m b e r f o r ° e e t k c o r r e s p o n d i n g t o t h e a r r i v a l ( d e p a r t u r e ) o f ° i g h t i
a t s o m e m a i n t e n a n c e s t a t i o n
e
+ ; k
i ; a
( e
+ ; k
i ; d
) i s t h e n e x t e v e n t f o r k a t t h a t s t a t i o n a f t e r t h e a r r i v a l ( d e p a r t u r e ) o f i
e
? ; k
i ; a
( e
? ; k
i ; d
) i s t h e e v e n t a t t h a t s t a t i o n p r e c e d i n g t h e a r r i v a l ( d e p a r t u r e ) o f i
G
k
i s t h e s e t o f g r o u n d v a r i a b l e s f o r ° e e t k
S
?
i
i s t h e s e t o f a u g m e n t e d s t r i n g s e n d i n g w i t h ° i g h t i a n d m a i n t e n a n c e
S
+
i
i s t h e s e t o f a u g m e n t e d s t r i n g s b e g i n n i n g w i t h ° i g h t i
a
i s
e q u a l s 1 i f ° i g h t i 2 F i s i n a u g m e n t e d s t r i n g s,a n d e q u a l s 0 o t h e r w i s e
c
k
s
i s t h e c o s t o f ° y i n g a u g m e n t e d s t r i n g s w i t h ° e e t k
r
k
s
i s t h e n u m b e r o f t i m e s ( p o s s i b l y g r e a t e r t h a n 1 ) a u g m e n t e d s t r i n g s a s s i g n e d t o ° e e t k
c r o s s e s t h e c o u n t t i m e
p
k
j
i s t h e n u m b e r o f t i m e s ( 0 o r 1 ) g r o u n d a r c j 2 G
k
f o r ° e e t k c r o s s e s t h e c o u n t t i m e
N
k
i s t h e n u m b e r o f p l a n e s i n ° e e t k
1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
Aircraft Maintenance Routing,
String Model
min
P
k2K
P
s2S
ck
s
xk
sP
k2K
P
s2S
a
is
xk
s
= 1; 8i2 F
P
s2S
+
i
xk
s
?yk
(e
? ;k
i;d;ek
i;d
)
+ yk
(ek
i;d;e
+ ;k
i;d
)
= 0; 8i2 F;8k2 K
?
P
s2S
?
i
xk
s
?yk
(e
? ;k
i;a;ek
i;a
)
+ yk
(ek
i;a;e
+ ;k
i;a
)
= 0; 8i2 F;8k2 K
P
s2S
rk
s
xk
s
+
P
j2Gk
pk
j
yk
j
Nk; 8k2 K
yk
j
? 0; 8j2 Gk;8k2 K
x
k
s 2 f 0;1g; 8s 2 S;8k2 K:
( 1)?
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
Model Solution
? Integer program
– Branch-and-bound with too many variables to consider
all of them
– Solve Linear Program using Column Generation
? Branch-and-Price
– Branch-and-bound with bounding provided by solving
LP’s using column generation,at each node of the
branch-and-bound tree
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
LP Solution,Column Generation
? Step 1,Solve Restricted Master Problem
? Step 2,Solve Pricing Problem (generate
columns)
? Step 3,If columns generated,return to Step
1; otherwise STOP
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
Generating The Right Variables
? Find a Variable with,Negative-Reduced
Cost”
– From Linear Programming Theory
? reduced cost of each string between two nodes = cost
- sum of the dual variables associated with flights in
string + constant
– Not feasible to compute reduced cost for each
variable,instead exploit problem structure
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
The Pricing Problem,A
Constrained Shortest Path
Problem
? If the,Length” of the shortest path is
– negative,a variable has been identified for inclusion in
the LP;
– non-negative,the optimal LP solution is found
Washington,D.C.
Baltimore
New York
Boston
TimeTime-Line Network
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
Pricing Problem Solution
? Find negative reduced cost route between
maintenance stations
? Price-out columns by running a shortest path
procedure with costs on arcs modified
? Ensure that shortest path solution satisfies
maintenance constraints
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 23
Path Lengths in Modified
Network
M1
A1
A2
A3
M2
Fli gh t A r c
Con ne c ti on A r c
T imeline
A B C
D
E
F
G
H
J
K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 24
Maintenance Requirements and
the Pricing Problem Solution
? Maximum Elapsed Time Requirement
– Unconstrained,simple shortest path computation
– Computationally inexpensive
? Maximum Flying Time Requirement
– Constrained shortest path procedure
? Additional labels need to be maintained
– Computationally expensive
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 25
Maximum Flying Time
Requirement,Multiple Labels and
Dominance
? Label i has cost c(i) and elapsed flying time t(i)
? Label i dominates label i+1 if c(i) ______
c(i+1) and t(i) _______ t(i+1)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 27
Branch-and-Price Challenge
? Devise Branching Strategy that:
– Is Compatible with Column Generation
Subproblem
? Does not destroy tractability of pricing problem
? Conventional branching based on variable dichotomy
does not work
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 28
Branching Strategy
? Branch on follow-ons:
– Identify two fractional strings s and s’
– Select flight i(1) contained in both strings
? One exists because __________________________
– Select flight i(2) contained in s but not s’
? One exists because __________________________
– Select i(1)-i(2) pair such that i(1) is followed immediately
by i(2) in s
? Such a pair exists
______________________________________
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 29
Branches
? Left branch,force flight i(1) to be followed
by i(2) if i(1) and i(2) are in the string
– To enforce,eliminate any connection arcs
including i(1) or i(2) but not both
? Right branch,do not allow flight i(1) to be
followed by i(2)
– To enforce,eliminate any connection arcs from
i(1) to i(2)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 30
Summary,Branch-and-Price
? At each node of the Branch-and-Bound tree
– Column generation used to solve LP
? Column Generation
– Allows huge LPs to be solved by considering only a
subset of all variables (columns)
– Solves shortest path subproblem repeatedly to generate
additional columns as needed
? Nontrivial Implementations
– New branching strategies necessary
– Ongoing research
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 31
Extensions,Combined Fleeting
and Routing
? Motivation,Long-haul applications
– Approximate maintenance constraints in FAM
might result in,maintenance-infeasible”
solutions
– Exact maintenance constraints necessary
? Need to model individual aircraft routings
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 32
Objective
? Minimize operating costs plus approximate
spill costs minus through revenues
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 33
Model Solution
? Branch-and-Price
– Branch on,fleet-flight” pairs
? Provides a partition of flights to fleets
? Enforce by
_________________________________________
– For each resulting fleet specific aircraft routing
problem
? Branch on follow-ons
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 34
Case Study
? Data provided by a major US long haul airline
– 1162 flights per week serving 55 cities worldwide
– 11 fleet types and 75 aircraft
– 8 maintenance stations
? Subproblems generated to perform scenario
analyses quickly
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 35
Problem Sizes
P r o b l e m
N ame
#
F l e e t s
#
F l i g h t s
P1
P2
P3
P4
P5
P6
2
2
4
4
7
11
126
403
360
536
546
1162
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 36
Effect of Maintenance
Requirements
P r obl e m
nam e
# f l igh t s
( # f l e e t s )
Sh or t e s t P at h
P r obl e m
Sol ut ion
T im e
Sol ut ion
V al ue
P1 12 6 ( 2) U n c o n s t r a i n e d
C o n s t r a i n e d
7s
17s
2960369,00
2960369,00
P2 40 8 ( 2) U n c o n s t r a i n e d
C o n s t r a i n e d
2m 1s
6m 43 s
10611441,00
10641120,00
P4 53 6 ( 4) U n c o n s t r a i n e d
C o n s t r a i n e d
38 m 38 s
4h 14 m 22 s
13624637,45
13563334,35
P5 54 6 ( 7) U n c o n s t r a i n e d
C o n s t r a i n e d
23 m 11 s
1h 45 m 46 s
16286255,29
16179416,08
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 37
Summary
? New model and solution approach for the combined fleet
assignment and aircraft routing problems
? Computational experiments showed:
– Near-optimal solutions in reasonable run times
– Maintenance feasible solutions ensured
– Through revenues captured
? One step closer to integration of overall airline scheduling
process
