1.206J/16.77J/ESD.215J
Airline Schedule Planning
Cynthia Barnhart
Spring 2003
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 2
The Extended Crew Pairing
Problem with Aircraft
Maintenance Routing
Outline
– Review of Individual Problems
– Interdependence and motivation for an
alternative approach
– Sequential Approaches
– Integrated Approaches
– Comparison of Models
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
The Maintenance Routing
Problem (MR)
? 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 4
MR 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 5
MR 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 6
MR 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
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
MR String 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 8
Crew Pairing Problem (CP)
? Given:
– Flight Schedule for a fleet family
? Each flight covered exactly once
? Usually daily or weekly schedule
– FAA and Collective Bargaining Agreements
? Rest
? Maximum duty,sit,flying times in a duty
? 8-in-24 rule
? Maximum time-away-from-base
? Brief/debrief
– Crew base locations
– Minimum connection times between aircraft at each
station
– Number of crews at each crew base
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 9
CP Cost Function
? Duty cost is maximum of:
– Flying time
– f1 * elapsed duty time
– Minimum duty pay
? Pairing cost is maximum of:
– Sum of duty costs
– f2 * time-away-from-base
– f3 * number of duties
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
CP Problem Objective
? Find:
– Cost minimizing assignment of crews to
scheduled flights such that each flight is
covered exactly once and all collective
bargaining and FAA work rules are
satisfied (and the number of crews
assigned does not exceed the number
available)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
CP Set Partitioning Model,
Variables and Constraints
? A variable is a pairing,that is,a sequence of
flights beginning and ending at the same crew
base and satisfying all work rules
– Binary variables,= 1 if pairing is assigned to a
crew; = 0 if pairing not flown
? Set partitioning constraints (crew size
constraints often ignored) requiring each
flight to be covered exactly once
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
CP Set Partitioning 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 13
MR and Its Impact on CP
? Maintenance routing problem (MR) finds a feasible
assignment of aircraft to flights to ensure adequate
maintenance opportunities
? Crews need enough time between two sequential
flights to travel through the terminal -- minimum
connect time
? If both flights are covered by the same aircraft,this
connection time can be reduced -- tighter
connections can be permitted
? A short connect is a connection that is crew-
feasible only if both flights are covered by the same
aircraft
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
Research Objective
? Our goal is to improve crew scheduling by
incorporating relevant maintenance routing
decisions
? Exploit the fact that only a subset of the
maintenance routing decisions impact crew
scheduling
– To decrease problem size
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
Motivation
? Crew costs are the second largest
operating expense faced by airlines
? Small improvements in efficiency can
have significant financial impact
? Scheduling options are limited by
maintenance routing decisions made
earlier in the airline planning process
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
MR then CP
Sequential Approach
? Current practice:
– Solve MR
– If flight A is followed by flight B in a
routing string,B can follow A in a crew
pairing,even if the connection is shorter
than the minimum connect time
– Output from MR is input to CP
– All other crew connections must satisfy
maximum connection time
– Restricts set of feasible CP solutions
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
Sequential Solution Approach
Maintenance
Routing
Problem
Crew
Pairing
Network
Short
Connects
Valid
pairings
Crew
Pairing
Problem
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
CP then MR
Sequential Approach
? Klabjan,Johnson,and Nemhauser
– CP costs dominate MR revenues
– Solve CP in which all short connects are
permitted
– Solve MR,enforcing short connects used
by CP
– May lead to infeasibility
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
Integrated Approach
? Solve both problems simultaneously to find optimal
solution that is feasible to both problems
? Short connects are the only link -- crew can’t fly a
tight connection unless the flights share an aircraft
in routing solution
? Cordeau,Stojkovi?,Soumis,and Desrosiers
– Directly integrate string-based models
– Basic maintainance routing and crew pairing variables and
constraints,plus linking constraints
– Benders decomposition approach using a heuristic
branching strategy
– Promising computational results
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
Maintenance Feasibility
? Because crew costs dominate,we will focus
on maintenance feasibility,rather than on
through revenues
? Problem is to minimize crew pairing costs
subject to maintenance feasibility
? Approaches can be easily extended to include
through revenues
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
String Based Approach (MRCP)
? If yr is the variable for a routing string and xp is the
variable for a crew pairing,linking constraint for
short connect t is
where ?tr is 1 if routing string r contains short
connect t and 0 otherwise,and ?pt is 1 if crew
pairing p contains short connect t and 0 otherwise
?? ?? 0ptprtr xy ??
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
MRCP Problem
MR
CP
0
0
0 ?cpxp
?? ?? 0ptprtr xy ??
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 23
MRCP Problem Size
? Variables:
– One for each routing string
– One for each crew pairing
? Constraints:
– Maintenance cover constraints
– Maintenance balance constraints (maintenance
stations only)
– Maintenance aircraft count
– Crew cover constraints
– One linking constraint for each short connect
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 24
Solving MRCP
? Too many columns to enumerate explicitly --
branch-and-price
? Column generation:
– Denote by ?t the dual for the linking constraint of
short connect t
– Reduced cost of a routing string or a pairing is
the same as in the original models,except add ?t
for each short connect t included
– Can modify pricing network by adding -?t to the
connection arc representing this turn
?TRACTABILITY ISSUES…
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 25
Our Objectives
? Guarantee maintenance feasibility
? Allow the user the flexibility to trade off
between solution time and quality
? Leverage the fact that only a portion of
the maintenance routing decisions are
relevant to the crew pairing problem
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 26
Approach
? In the sequential approach,the crew
scheduler is given an MR solution and solves
the corresponding CP
? We’d like to allow the crew scheduler to
choose from a collection of MR solutions the
one which contains the most useful set of
short connects
? Problem,We don’t want to solve one CP for
each MR solution
? Solution,Extended crew pairing model
(ECP)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 27
The Extended Crew Pairing Model
(ECP)
? In addition to choosing crew pairings,select
one maintenance routing solution from a
given set of feasible solutions
? Add constraints that prohibit pairings
containing a short connect from being
selected unless the chosen maintenance
solution also contains that short connect
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 28
Notation
? Pk is the set of feasible pairings for fleet type
k
? Fk is the set of daily flights assigned to fleet
type k
? Tk is the set of short connects for the flights
assigned to fleet type k
? Sk is the set of feasible MR solutions for the
flights assigned to fleet type k
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 29
Notation,cont.
? ?fp is defined to be 1 if flight f is included in
pairing p,else 0
? αts is defined to be 1 if MR solution s includes
short connect t,else 0
? βtp is defined to be 1 if short connect t is
contained in pairing p,else 0
? cp is the cost of pairing p
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 30
Notation,cont.
? ys is a binary decision variable – value 1
indicates that MR solution s is chosen,else 0
? xp is a binary decision variable – value 1
indicates that pairing p is chosen,else 0
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 31
General Formulation
Flights:
short connects:
Convexity:
psxy
y
Ttxy
Ffx
st
xc
ps
Ss
s
k
Ss Pp
ptpsts
k
Pp
pfp
Pp
pp
k
k k
k
k
,}1,0{,
1
0
1
m i n
??
?
????
???
?
? ?
?
?
?
? ?
?
?
??
?
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 32
An Example
? Flights,
A B C D E F G H
? short connects,
A-B A-C C-D
? MR solution (y1) uses
short connects A-C and
C-D
? MR solution (y2) uses
short connect A-B
? Potential pairings:
– A-C-D-F (x1) - $1
– A-B-E-F (x2) - $2
– C-D-G-H (x3) - $4
– B-E-G-H (x4) - $6
? Crew pairing solutions:
– y1 => pairings 1,4 -- $7
– y2 => pairings 2,3 -- $6
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 33
Matrix Representation
A
B
C
D
E
F
G
H
A-B
A-D
D-G
Conv.
y1 y2 x1 x2 x3 x4 rhs
Flights:
short connects:
Convexity,1000011
0000101
0000101
0001010
1110000
1110000
1001100
1101000
1010100
1010100
1101000
1001100
?
??
??
??
?
?
?
?
?
?
?
?
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 34
Solving ECP
? Too many columns to enumerate explicitly --
branch-and-price
? Column generation:
– Doesn’t change for crew variables:
? Denote by ?t the dual for the linking constraint of short
connect t
? Reduced cost of a routing string or a pairing is the same as in
the original models,except add ?t for each short connect t
included
? Can modify pricing network by adding -?t to the connection
arc representing this turn
– Generating a MR solution variable is the same as
solving MR with modified costs
? Minimize negative of duals on short connect connection arcs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 35
Comparison of Models
? Time to solve maintenance pricing
problems
–MRCP generates routing strings
–ECP generates routing solutions
? Might require generating routing strings!
? Re-optimizing with new objective
function; initial column set and known
feasible solution
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 36
Comparison of Models (cont.)
? Size of restricted master problems
– MRCP has one column for each routing
string
– ECP has one column for each routing
solution -- many more columns?!
? Redundancy
? Dominance
? Example
– 14 flights
– 104 feasible routing strings
– 16 maintenance routing solutions
– 11 unique short connect sets
– 6 dominant short connect sets
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 37
ECP Enhancements
? Dramatically reduce the number of MR columns:
– Uniqueness,Eliminate redundant columns
? Example,41 flights,single set of short connects => >>8,700
solutions => 1 column
– Maximal independence,Eliminate dominated
columns
? Only need one column per unique,maximally
independent,maintenance feasible short connect set
? Theoretical bounds and computational
observations
– Example,61 flights => >> 25,000 solutions => 4
required columns
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 38
ECP Enhancements,cont.
? Relax the integrality of MR columns:
– Same number of binary variables as
original CP
? LP relaxation of ECP is tighter than LP
relaxation of a basic integrated approach
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 39
Generating MR Solutions
? Algorithm to generate UMI columns -- can
generate k UMI columns in at most the time
needed to solve k MR problems
? Can generate columns using column
generation to take advantage of dual
information -- pricing problem still yields
UMI columns
? Can still use existing crew pairing generators
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 40
Computational Experiment
? Problem A:
Lower bound,31,396.10
ECP with 16 MR columns,31,396.10
Optimality gap,0%
? Problem B:
Lower bound,25,076.60
ECP with 20 MR columns,25,498.60
Optimality gap,1.7%
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 41
Observations
? Zero optimality gap in instance A doesn’t necessarily
imply sequential approach would yield an optimal
solution – many equivalent crew pairing solutions,
some maintenance feasible and some not
? Number of short connects in an optimal solution is
small relative to total number – UMI sets often
capture many of them
– A,58 max; ~38 per column; 9 used in solution
– B,68 max; ~37 per column; 10 used in solution
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 42
Benefits of ECP
? Ensures maintenance feasibility
? Can be solved heuristically or to optimality,
allowing user to trade off solution time and
quality
? Leverages the fact that only short connect
decisions from the maintenance routing
problem impact crew pairing
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 43
Benefits of ECP,cont.
? No more binary variables than the basic crew
pairing model alone
? Tighter LP relaxation than a basic integrated
approach
? Flexible
– Can take advantage of advances in maintenance
routing solvers and crew pairing generators
– Can incorporate new maintenance constraints
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 44
Conclusions
? Crew scheduling is critical to airline
profitability but quality can be compromised
by making maintenance routing decisions
independently
? A direct integration can be inflexible and
difficult to solve
? ECP provides an alternative approach that
exploits the fact that only some maintenance
routing information is relevant
Airline Schedule Planning
Cynthia Barnhart
Spring 2003
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 2
The Extended Crew Pairing
Problem with Aircraft
Maintenance Routing
Outline
– Review of Individual Problems
– Interdependence and motivation for an
alternative approach
– Sequential Approaches
– Integrated Approaches
– Comparison of Models
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
The Maintenance Routing
Problem (MR)
? 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 4
MR 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 5
MR 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 6
MR 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
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
MR String 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 8
Crew Pairing Problem (CP)
? Given:
– Flight Schedule for a fleet family
? Each flight covered exactly once
? Usually daily or weekly schedule
– FAA and Collective Bargaining Agreements
? Rest
? Maximum duty,sit,flying times in a duty
? 8-in-24 rule
? Maximum time-away-from-base
? Brief/debrief
– Crew base locations
– Minimum connection times between aircraft at each
station
– Number of crews at each crew base
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 9
CP Cost Function
? Duty cost is maximum of:
– Flying time
– f1 * elapsed duty time
– Minimum duty pay
? Pairing cost is maximum of:
– Sum of duty costs
– f2 * time-away-from-base
– f3 * number of duties
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
CP Problem Objective
? Find:
– Cost minimizing assignment of crews to
scheduled flights such that each flight is
covered exactly once and all collective
bargaining and FAA work rules are
satisfied (and the number of crews
assigned does not exceed the number
available)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
CP Set Partitioning Model,
Variables and Constraints
? A variable is a pairing,that is,a sequence of
flights beginning and ending at the same crew
base and satisfying all work rules
– Binary variables,= 1 if pairing is assigned to a
crew; = 0 if pairing not flown
? Set partitioning constraints (crew size
constraints often ignored) requiring each
flight to be covered exactly once
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
CP Set Partitioning 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 13
MR and Its Impact on CP
? Maintenance routing problem (MR) finds a feasible
assignment of aircraft to flights to ensure adequate
maintenance opportunities
? Crews need enough time between two sequential
flights to travel through the terminal -- minimum
connect time
? If both flights are covered by the same aircraft,this
connection time can be reduced -- tighter
connections can be permitted
? A short connect is a connection that is crew-
feasible only if both flights are covered by the same
aircraft
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
Research Objective
? Our goal is to improve crew scheduling by
incorporating relevant maintenance routing
decisions
? Exploit the fact that only a subset of the
maintenance routing decisions impact crew
scheduling
– To decrease problem size
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
Motivation
? Crew costs are the second largest
operating expense faced by airlines
? Small improvements in efficiency can
have significant financial impact
? Scheduling options are limited by
maintenance routing decisions made
earlier in the airline planning process
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
MR then CP
Sequential Approach
? Current practice:
– Solve MR
– If flight A is followed by flight B in a
routing string,B can follow A in a crew
pairing,even if the connection is shorter
than the minimum connect time
– Output from MR is input to CP
– All other crew connections must satisfy
maximum connection time
– Restricts set of feasible CP solutions
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
Sequential Solution Approach
Maintenance
Routing
Problem
Crew
Pairing
Network
Short
Connects
Valid
pairings
Crew
Pairing
Problem
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
CP then MR
Sequential Approach
? Klabjan,Johnson,and Nemhauser
– CP costs dominate MR revenues
– Solve CP in which all short connects are
permitted
– Solve MR,enforcing short connects used
by CP
– May lead to infeasibility
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
Integrated Approach
? Solve both problems simultaneously to find optimal
solution that is feasible to both problems
? Short connects are the only link -- crew can’t fly a
tight connection unless the flights share an aircraft
in routing solution
? Cordeau,Stojkovi?,Soumis,and Desrosiers
– Directly integrate string-based models
– Basic maintainance routing and crew pairing variables and
constraints,plus linking constraints
– Benders decomposition approach using a heuristic
branching strategy
– Promising computational results
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
Maintenance Feasibility
? Because crew costs dominate,we will focus
on maintenance feasibility,rather than on
through revenues
? Problem is to minimize crew pairing costs
subject to maintenance feasibility
? Approaches can be easily extended to include
through revenues
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
String Based Approach (MRCP)
? If yr is the variable for a routing string and xp is the
variable for a crew pairing,linking constraint for
short connect t is
where ?tr is 1 if routing string r contains short
connect t and 0 otherwise,and ?pt is 1 if crew
pairing p contains short connect t and 0 otherwise
?? ?? 0ptprtr xy ??
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
MRCP Problem
MR
CP
0
0
0 ?cpxp
?? ?? 0ptprtr xy ??
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 23
MRCP Problem Size
? Variables:
– One for each routing string
– One for each crew pairing
? Constraints:
– Maintenance cover constraints
– Maintenance balance constraints (maintenance
stations only)
– Maintenance aircraft count
– Crew cover constraints
– One linking constraint for each short connect
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 24
Solving MRCP
? Too many columns to enumerate explicitly --
branch-and-price
? Column generation:
– Denote by ?t the dual for the linking constraint of
short connect t
– Reduced cost of a routing string or a pairing is
the same as in the original models,except add ?t
for each short connect t included
– Can modify pricing network by adding -?t to the
connection arc representing this turn
?TRACTABILITY ISSUES…
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 25
Our Objectives
? Guarantee maintenance feasibility
? Allow the user the flexibility to trade off
between solution time and quality
? Leverage the fact that only a portion of
the maintenance routing decisions are
relevant to the crew pairing problem
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 26
Approach
? In the sequential approach,the crew
scheduler is given an MR solution and solves
the corresponding CP
? We’d like to allow the crew scheduler to
choose from a collection of MR solutions the
one which contains the most useful set of
short connects
? Problem,We don’t want to solve one CP for
each MR solution
? Solution,Extended crew pairing model
(ECP)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 27
The Extended Crew Pairing Model
(ECP)
? In addition to choosing crew pairings,select
one maintenance routing solution from a
given set of feasible solutions
? Add constraints that prohibit pairings
containing a short connect from being
selected unless the chosen maintenance
solution also contains that short connect
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 28
Notation
? Pk is the set of feasible pairings for fleet type
k
? Fk is the set of daily flights assigned to fleet
type k
? Tk is the set of short connects for the flights
assigned to fleet type k
? Sk is the set of feasible MR solutions for the
flights assigned to fleet type k
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 29
Notation,cont.
? ?fp is defined to be 1 if flight f is included in
pairing p,else 0
? αts is defined to be 1 if MR solution s includes
short connect t,else 0
? βtp is defined to be 1 if short connect t is
contained in pairing p,else 0
? cp is the cost of pairing p
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 30
Notation,cont.
? ys is a binary decision variable – value 1
indicates that MR solution s is chosen,else 0
? xp is a binary decision variable – value 1
indicates that pairing p is chosen,else 0
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 31
General Formulation
Flights:
short connects:
Convexity:
psxy
y
Ttxy
Ffx
st
xc
ps
Ss
s
k
Ss Pp
ptpsts
k
Pp
pfp
Pp
pp
k
k k
k
k
,}1,0{,
1
0
1
m i n
??
?
????
???
?
? ?
?
?
?
? ?
?
?
??
?
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 32
An Example
? Flights,
A B C D E F G H
? short connects,
A-B A-C C-D
? MR solution (y1) uses
short connects A-C and
C-D
? MR solution (y2) uses
short connect A-B
? Potential pairings:
– A-C-D-F (x1) - $1
– A-B-E-F (x2) - $2
– C-D-G-H (x3) - $4
– B-E-G-H (x4) - $6
? Crew pairing solutions:
– y1 => pairings 1,4 -- $7
– y2 => pairings 2,3 -- $6
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 33
Matrix Representation
A
B
C
D
E
F
G
H
A-B
A-D
D-G
Conv.
y1 y2 x1 x2 x3 x4 rhs
Flights:
short connects:
Convexity,1000011
0000101
0000101
0001010
1110000
1110000
1001100
1101000
1010100
1010100
1101000
1001100
?
??
??
??
?
?
?
?
?
?
?
?
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 34
Solving ECP
? Too many columns to enumerate explicitly --
branch-and-price
? Column generation:
– Doesn’t change for crew variables:
? Denote by ?t the dual for the linking constraint of short
connect t
? Reduced cost of a routing string or a pairing is the same as in
the original models,except add ?t for each short connect t
included
? Can modify pricing network by adding -?t to the connection
arc representing this turn
– Generating a MR solution variable is the same as
solving MR with modified costs
? Minimize negative of duals on short connect connection arcs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 35
Comparison of Models
? Time to solve maintenance pricing
problems
–MRCP generates routing strings
–ECP generates routing solutions
? Might require generating routing strings!
? Re-optimizing with new objective
function; initial column set and known
feasible solution
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 36
Comparison of Models (cont.)
? Size of restricted master problems
– MRCP has one column for each routing
string
– ECP has one column for each routing
solution -- many more columns?!
? Redundancy
? Dominance
? Example
– 14 flights
– 104 feasible routing strings
– 16 maintenance routing solutions
– 11 unique short connect sets
– 6 dominant short connect sets
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 37
ECP Enhancements
? Dramatically reduce the number of MR columns:
– Uniqueness,Eliminate redundant columns
? Example,41 flights,single set of short connects => >>8,700
solutions => 1 column
– Maximal independence,Eliminate dominated
columns
? Only need one column per unique,maximally
independent,maintenance feasible short connect set
? Theoretical bounds and computational
observations
– Example,61 flights => >> 25,000 solutions => 4
required columns
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 38
ECP Enhancements,cont.
? Relax the integrality of MR columns:
– Same number of binary variables as
original CP
? LP relaxation of ECP is tighter than LP
relaxation of a basic integrated approach
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 39
Generating MR Solutions
? Algorithm to generate UMI columns -- can
generate k UMI columns in at most the time
needed to solve k MR problems
? Can generate columns using column
generation to take advantage of dual
information -- pricing problem still yields
UMI columns
? Can still use existing crew pairing generators
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 40
Computational Experiment
? Problem A:
Lower bound,31,396.10
ECP with 16 MR columns,31,396.10
Optimality gap,0%
? Problem B:
Lower bound,25,076.60
ECP with 20 MR columns,25,498.60
Optimality gap,1.7%
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 41
Observations
? Zero optimality gap in instance A doesn’t necessarily
imply sequential approach would yield an optimal
solution – many equivalent crew pairing solutions,
some maintenance feasible and some not
? Number of short connects in an optimal solution is
small relative to total number – UMI sets often
capture many of them
– A,58 max; ~38 per column; 9 used in solution
– B,68 max; ~37 per column; 10 used in solution
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 42
Benefits of ECP
? Ensures maintenance feasibility
? Can be solved heuristically or to optimality,
allowing user to trade off solution time and
quality
? Leverages the fact that only short connect
decisions from the maintenance routing
problem impact crew pairing
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 43
Benefits of ECP,cont.
? No more binary variables than the basic crew
pairing model alone
? Tighter LP relaxation than a basic integrated
approach
? Flexible
– Can take advantage of advances in maintenance
routing solvers and crew pairing generators
– Can incorporate new maintenance constraints
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 44
Conclusions
? Crew scheduling is critical to airline
profitability but quality can be compromised
by making maintenance routing decisions
independently
? A direct integration can be inflexible and
difficult to solve
? ECP provides an alternative approach that
exploits the fact that only some maintenance
routing information is relevant
