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 Crew Scheduling Problem
? Outline
– Problem Definition
– Sequential Solution Approach
– Crew Pairing Optimization Model
– Branch-and-Price Solution
? Branching strategies
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
Why Crew Scheduling?
? Second largest operating expense (after fuel)
? OR success story
? Complex problems with many remaining
opportunities
? A case study for techniques to solve large IPs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 4
Airline Schedule Planning
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 5
The Crew Scheduling Problem
? Assign crews to cover all flights for a given
fleet type
? Minimize cost
– Time paid for flying
–,Penalty” pay
? Side constraints
– Balance
– Robustness
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 6
Network Flow Problem?
? Complex feasibility rules
?Non-linear objective function
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
Building Blocks
T o D o
9:00
10:00
11:00
12:00
1:00
2:00
3:00
Dut y
Ju n e
S ched ule
Flight Pairing
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 8
Duty Periods
Definition,
A duty period is a day-long sequence of
consecutive flights that can be assigned to a single
crew,to be followed by a period of rest
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 9
Duty Rules
Rules:
? Flights are sequential in space/time
? Maximum flying time
? Minimum idle/sit/connect time
? Maximum idle/sit/connect time
? Maximum duty time
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
Duty Cost Function
? Maximum of:
– Total flying time
– fd * total duty time
– Minimum guaranteed duty pay
? Primarily compensates for flying time,but
also compensates for,undesirable” schedules
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
Pairings
Definition,
A sequence of duty periods,interspersed with
periods of rest,that begins and ends at a crew
domicile
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
Pairing Rules
Rules:
? First duty starts/last duty ends at domicile
? Duties are sequential in space/time
? Minimum rest between duties
? Maximum layover time
? Maximum number of days away from base
? 8-in-24 rule
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 13
Pairing Cost Function
? Maximum of:
– Sum of duty costs
– fp * total time away from base (TAFB)
– Minimum guaranteed pairing pay
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
Schedules
Rules:
? Minimum rest between pairings
? Maximum monthly flying time
? Maximum time on duty
? Minimum total number of days off
Two key differences:
? Cost function focuses on crew preferences
? Schedules individuals rather than complete crews
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
Crew Scheduling Problems
Crew Scheduling Problem
Crew Sche duli ng Problem
Crew Pai ring Assign me nt
Crew Pai ring Assign me nt
Dai ly
We ekl y
Exce pti on
Bi dli ne
Rost ering
Cockpi t Crews Ca bin Crews
C r e w S c h e d u l i n g P r o b l e m
C r e w P a i r i n g A s s i g n m e n t
D a i l y
W e e k l y
E x c e p t i o n
B i d l i n e
R o s t e r i n g
C r e w S c h e d u l i n g P r o b l e m
C r e w P a i r i n g A s s i g n m e n t
D a i l y
W e e k l y
E x c e p t i o n
B i d l i n e
R o s t e r i n g
Dome st ic Inte rnat iona l
Cock pit Cr ew s
C r ew S ch ed u li n g P r o b le m
C r ew P ai r in g A s s ig n m en t
D ai ly
W ee k ly
E x ce p ti o n
B id li n e
R o s te r in g
Cock pit Cr ew s
Cr ew S ch ed u li n g P r o b le m
Cr ew P ai r in g A ssi g n m en t
D ai ly
W ee k ly
E x ce p ti o n
Bidline
Ro ste r in g
Cabin Crew s
C r ew S ch ed u li n g P r o b le m
C r ew P ai r in g A s s ig n m en t
D ai ly
W ee k ly
E x ce p ti o n
B id li n e
R o s te r in g
Cabin Crews
C r ew S ch ed u li n g P r o b le m
C r ew P ai r in g A s s ig n m en t
D ai ly
W ee k ly
E x ce p ti o n
B id li n e
R o s te r in g
R ec ove ry Proble m
D o m e s t i c I n t e r n a t i o n a l
C o c k p i t C r e w s
C r e w S c h e d u l i n g P r o b l e m
C r e w P a i r i n g A s s i g n m e n t
D a i l y
W e e k l y
E x c e p t i o n
B i d l i n e
R o s t e r i n g
C o c k p i t C r e w s
C r e w S c h e d u l i n g P r o b l e m
C r e w P a i r i n g A s s i g n m e n t
D a i l y
W e e k l y
E x c e p t i o n
B i d l i n e
R o s t e r i n g
C a b i n C r e w s
C r e w S c h e d u l i n g P r o b l e m
C r e w P a i r i n g A s s i g n m e n t
D a i l y
W e e k l y
E x c e p t i o n
B i d l i n e
R o s t e r i n g
C a b i n C r e w s
C r e w S c h e d u l i n g P r o b l e m
C r e w P a i r i n g A s s i g n m e n t
D a i l y
W e e k l y
E x c e p t i o n
B i d l i n e
R o s t e r i n g
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
Pairing Problems
? Select a minimum cost set of pairings such
that every flight is included in exactly one
pairing
? Crew Pairing Decomposition
– Daily
– Weekly
– Exceptions
– Transitions
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
Daily
? All flights operating four or more times per
week
? Chosen pairings will be repeated each day
? Multi-day pairings will be flown by multiple
crews
? Flights cannot be repeated in a pairing
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
Example
MON TUE WED THU FRI SAT SUN
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
D u t y A D u t y BD u t y C
D u t y AD u t y B D u t y C
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
Example,cont.
MON TUE WED THU FRI SAT SUN
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
Duty A Duty B
Duty C
Duty A
Duty B Duty C
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
Weekly
? Cover all flights scheduled in a week-long
period
? Fleet assignment on a particular flight leg can
vary by day of week
? Identify flights by day-of-week as well as
flight number,location,time
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
Exceptions
? Cover all flights in,broken pairings”
? Cover all flights that are scheduled at most
three times/week
? Identify flights by day-of-week as well as
flight number,location,time
? Generate,weekly” pairings
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
Transition
? Cover flights in pairings that cross the end of
the month
? Identify flights by date as well as flight
number,location,time,day-of-week
? Generate pairings connecting two different
flight schedules
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 23
Crew Planning
Daily
Problem Exceptions Transition
broken
pairings
broken
pairings
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 24
Assignment Problems
? Specified at the individual level
? Incorporates rest,vacation time,medical
leave,training
? Focus is not on cost but crew needs/
preferences
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 25
The Bidline Problem
? Pairings are constructed into generic
schedules
? Schedules are posted and crew members bid
for specific schedules
? More senior crew members given greater
priority
? Commonly used in the U.S.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 26
The Rostering Problem
? Personalized pairings are constructed
? Incorporates crew vacation requests,training
needs,etc.
? Higher priority given to more senior crew
members
? Typical outside the U.S.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 27
Pairing vs,Assignment
? Similarities
– Sequencing flights to form pairings ?
sequencing pairings to form schedules
– Set partitioning formulations (possibly with
side constraints)
? Differences
– Complete crews vs,single crew member
– Objective function
– Time horizon
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 28
Cockpit vs,Cabin
? Cockpit crews stay together; cabin crews do
not
? Cockpit crew makeup is fixed; cabin needs
can vary by demand
? Cabin crew members have a wider range of
aircraft they can staff
? Cockpit crew members receive higher salaries
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 29
Domestic vs,International
? Domestic U.S,networks of large carriers are
predominantly hub-and-spoke
– With many connection opportunities
– Domestic networks are usually daily
? International networks are typically point-to-
point
– More of a need to use deadheads
– International networks are typically weekly
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 30
Recovery Problem
? Given a disruption,adjust the crew schedule
so that it becomes feasible
? What is our objective?
– Return to original schedule as quickly as possible?
– Minimize passenger disruptions?
– Minimize cost?
? Limited time horizon -- need fast heuristics
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 31
Focus,Daily Domestic Cockpit
Crew Pairing Problem
? Problem description
? Formulation
? Solution approaches
? Computational results
? Integration with aircraft routing,FAM
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 32
The Crew Pairing Problem
Given a set of flights (corresponding to an
individual fleet type or fleet family),choose a
minimum cost set of pairings such that every
flight is covered exactly once (i.e,every flight is
contained in exactly one pairing)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 33
Notation
? Pk is the set of feasible pairings for fleet type k
? Fk is the set of daily flights assigned to fleet
type k
? ?fp is defined to be 1 if flight f is included in
pairing p,else 0
? cp is the cost of pairing p
? 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 34
Formulation
k
k
Pp }1,0{
Ff 1
m i n
???
????
?
?
?
p
Pp
pfp
Pp
pp
x
x
st
xc
k
k
?
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 35
Is this an easy problem?
? Linear objective function
? No complex feasibility rules
? Easy to write/intuitive
? Small number of constraints
? Huge number of integer variables
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 36
How do we solve it?
? We need branch-and-bound to solve the
IP
? We need column generation to solve the
individual LP relaxations
? Branch-and-price combines the two
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 37
Column Generation Review
? Column generation solves linear programs
with a large number of variables
? Start with a restricted master – a subset of the
variables
? Solve to optimality
? Input the duals to a pricing problem and look
for negative reduced cost columns
? Repeat
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 38
Generating Crew Pairings
? Start with enough columns to ensure a
feasible solution (may need to use artificial
variables)
? Solve Restricted Master problem
? Look for one or more negative reduced cost
columns for each crew base; add to Restricted
Master problem and re-solve
? If no new columns are found,LP is optimal
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 39
Crew Pairing Reduced Cost
Reduced cost of pairing p is:
?
?
?
?
?
kFf
ffp
pd
p T A F Bfd
??
p ay } g u ar an t eem i n,*,ofco s t d u t y m ax {
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 40
Formulation
k
k
Pp }1,0{
Ff 1
m i n
???
????
?
?
?
p
Pp
pfp
Pp
pp
x
x
st
xc
k
k
?
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 41
Pricing as a Shortest Path Problem
? A pairing can be seen as a path,where nodes
represent flights and arcs represent valid
connections
? Paths must start/end at a given crew base
? For daily problem,paths cannot repeat a
flight
? Paths must satisfy duty and pairing rules
? Path costs can be computed via labels
corresponding to pairing reduced costs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 42
Network Structure
? Connection arc network
– Nodes represent flights
– Arcs represent (potentially) feasible connections
? Multiple copies of the network in order to
construct multi-day pairings
? Source/sink nodes at the crew base
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 43
Network Example
BOS
BOS - CIN
8 - 9:50
BOS - DCA
8 - 9:27
DCA - ORD
10:15 - 1:30
CIN - SFO
4:30 - 7:15
CIN - DE T
10:30 - 12:15
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 44
Multi-Day Network
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 45
Labels
Feasibility:
? Pairing,
– Min rest between duties
– Max rest between duties
– Max # of duties
? Duty:
– Max flying
– Max duty time
– Min idle (connection
arcs)
– Max idle (connections
arcs)
Cost:
? Pairing -- max of:
– Sum of duty costs
– fp * TAFB
– min guarantee pay
? Duty -- max of:
– Total flying time
– fd * total duty time
– min guarantee pay
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 46
Labels,cont.
Labels have to track:
? Current duty:
– Flying time in current
duty
– Total elapsed time in
current duty
– Current duty cost
? Pairing:
– Pairing TAFB
– Sum of completed
duties’ costs
– # completed duties
– Current pairing reduced
cost
Labels also contain:
? Label id
? Previous flight
? Previous flight’s label
id
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 47
Processing Labels
? For each node (in topological order)
– For each label at that node
? For each connection arc out of that node
– Process the arc
– If a label is created,check existing labels for
dominance
– If the node ends at the crew base and reduced cost
is negative,a potential column’s been found
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 48
Processing Labels,cont.
Flight repeat?
Given:
Label
Arc
Sto p
Yes
Valid for
duty?
No
Stop
No
Valid for
pairing?
Yes
N ew l ab el
Yes
Stop
No
Valid for duty:
? Doesn’t violate max duty time
? Doesn’t violate max idle time
? Doesn’t violate max flying time
New label:
? Update duty time
? Update flying time
? Update duty cost
? Update pairing red,cost
? Update pairing TAFB
? Update sum of duty costs
Valid for pairing:
? Doesn’t violate number of duties
? Doesn’t violate min layover
?Doesn’t violate max TAFB
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 49
Column Generation and Network
Structure
– Duty assignment networks
? Large number of arcs
– One arc per duty
– Can be hundreds of connections per duty
– Ex,363 flights,7838 duties,1.65 M connections
? Fewer labels per path - duty rules are built in
– Flight assignment networks
? Smaller number of arcs
– One arc per flight
– Typically not more than 30 connections per flight
? Larger number of labels
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 50
Branch-and-Bound Review
Root
nodex1 = 1 x1 = 0
Integer --
u.b,
< u.b.
x2 = 1 x2 = 0
< u.b,Prune --> u.b.
x3 = 1 x3 = 0
Infeas.< u.b.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 51
Heuristic Solution Approach
? Branch-and-bound with only root node
LP solved using column generation
– No feasible solution may exist in the
columns generated to solve the root node
LP
– Conventional wisdom,need some,bad”
columns to get a,good” solution
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 52
Branch-and-Price
? Need a branching rule that is compatible with
column generation
– Rule must be enforceable without changing the
structure of the pricing problem
? Multi-label shortest path problem
– Branching based on variable dichotomy is not
compatible
? Cannot restrict the shortest path algorithm from
finding a path (that is,a pairing)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 53
Variable Dichotomy Branching
? Given a fractional solution to the crew
pairing problem,pick p s.t,0 < xp < 1
? Two new problems,{xp = 1,xp = 0}
? Drawbacks:
– Imbalance
– Maximum depth of tree
– Enforcing in the pricing problem:
? xp = 1 is easy
? xp = 0 is hard
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 54
Branching on Follow-Ons
? Given a fractional solution,there must
be two flights f1,f2 such that f1 is
followed by f2 a fractional amount in the
solution
– Pairing f1-f2-f3 has value 1/2 and pairing f1-
f4 has value 1/2
? Branch on {f1 is/is not followed by f2}
– More balanced
– Fewer branching levels
– Easy to enforce in pricing problem
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 55
How to Alter Network to Enforce
Branching Decision
? If follow-on flights a-b required
– Remove all connection arcs from a to flights
other than b
– Remove all connection arcs into b from flights
other than a
? If follow-on flights a-b disallowed
– Remove all connection arcs from a to b
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 56
How to Select Flight Pairs for
Branching
? Sum current LP solution values of all possible
flight follow-ons
? Branch on the follow-on with the greatest
value
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 57
Computational Results
American Airlines (1993):
? 25,000+ crew members
? Save $20+ million/year
? Solutions in 4 - 10 hours
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 58
Other Crew Scheduling Research
Topics
? Cabin crew scheduling
? Integrating pairing and assignment
? Robust planning
? Recovery
? Integrated models
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 Crew Scheduling Problem
? Outline
– Problem Definition
– Sequential Solution Approach
– Crew Pairing Optimization Model
– Branch-and-Price Solution
? Branching strategies
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
Why Crew Scheduling?
? Second largest operating expense (after fuel)
? OR success story
? Complex problems with many remaining
opportunities
? A case study for techniques to solve large IPs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 4
Airline Schedule Planning
Schedule Design
Fleet Assignment
Aircraft Routing
Crew Scheduling
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 5
The Crew Scheduling Problem
? Assign crews to cover all flights for a given
fleet type
? Minimize cost
– Time paid for flying
–,Penalty” pay
? Side constraints
– Balance
– Robustness
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 6
Network Flow Problem?
? Complex feasibility rules
?Non-linear objective function
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
Building Blocks
T o D o
9:00
10:00
11:00
12:00
1:00
2:00
3:00
Dut y
Ju n e
S ched ule
Flight Pairing
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 8
Duty Periods
Definition,
A duty period is a day-long sequence of
consecutive flights that can be assigned to a single
crew,to be followed by a period of rest
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 9
Duty Rules
Rules:
? Flights are sequential in space/time
? Maximum flying time
? Minimum idle/sit/connect time
? Maximum idle/sit/connect time
? Maximum duty time
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
Duty Cost Function
? Maximum of:
– Total flying time
– fd * total duty time
– Minimum guaranteed duty pay
? Primarily compensates for flying time,but
also compensates for,undesirable” schedules
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
Pairings
Definition,
A sequence of duty periods,interspersed with
periods of rest,that begins and ends at a crew
domicile
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
Pairing Rules
Rules:
? First duty starts/last duty ends at domicile
? Duties are sequential in space/time
? Minimum rest between duties
? Maximum layover time
? Maximum number of days away from base
? 8-in-24 rule
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 13
Pairing Cost Function
? Maximum of:
– Sum of duty costs
– fp * total time away from base (TAFB)
– Minimum guaranteed pairing pay
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
Schedules
Rules:
? Minimum rest between pairings
? Maximum monthly flying time
? Maximum time on duty
? Minimum total number of days off
Two key differences:
? Cost function focuses on crew preferences
? Schedules individuals rather than complete crews
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
Crew Scheduling Problems
Crew Scheduling Problem
Crew Sche duli ng Problem
Crew Pai ring Assign me nt
Crew Pai ring Assign me nt
Dai ly
We ekl y
Exce pti on
Bi dli ne
Rost ering
Cockpi t Crews Ca bin Crews
C r e w S c h e d u l i n g P r o b l e m
C r e w P a i r i n g A s s i g n m e n t
D a i l y
W e e k l y
E x c e p t i o n
B i d l i n e
R o s t e r i n g
C r e w S c h e d u l i n g P r o b l e m
C r e w P a i r i n g A s s i g n m e n t
D a i l y
W e e k l y
E x c e p t i o n
B i d l i n e
R o s t e r i n g
Dome st ic Inte rnat iona l
Cock pit Cr ew s
C r ew S ch ed u li n g P r o b le m
C r ew P ai r in g A s s ig n m en t
D ai ly
W ee k ly
E x ce p ti o n
B id li n e
R o s te r in g
Cock pit Cr ew s
Cr ew S ch ed u li n g P r o b le m
Cr ew P ai r in g A ssi g n m en t
D ai ly
W ee k ly
E x ce p ti o n
Bidline
Ro ste r in g
Cabin Crew s
C r ew S ch ed u li n g P r o b le m
C r ew P ai r in g A s s ig n m en t
D ai ly
W ee k ly
E x ce p ti o n
B id li n e
R o s te r in g
Cabin Crews
C r ew S ch ed u li n g P r o b le m
C r ew P ai r in g A s s ig n m en t
D ai ly
W ee k ly
E x ce p ti o n
B id li n e
R o s te r in g
R ec ove ry Proble m
D o m e s t i c I n t e r n a t i o n a l
C o c k p i t C r e w s
C r e w S c h e d u l i n g P r o b l e m
C r e w P a i r i n g A s s i g n m e n t
D a i l y
W e e k l y
E x c e p t i o n
B i d l i n e
R o s t e r i n g
C o c k p i t C r e w s
C r e w S c h e d u l i n g P r o b l e m
C r e w P a i r i n g A s s i g n m e n t
D a i l y
W e e k l y
E x c e p t i o n
B i d l i n e
R o s t e r i n g
C a b i n C r e w s
C r e w S c h e d u l i n g P r o b l e m
C r e w P a i r i n g A s s i g n m e n t
D a i l y
W e e k l y
E x c e p t i o n
B i d l i n e
R o s t e r i n g
C a b i n C r e w s
C r e w S c h e d u l i n g P r o b l e m
C r e w P a i r i n g A s s i g n m e n t
D a i l y
W e e k l y
E x c e p t i o n
B i d l i n e
R o s t e r i n g
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
Pairing Problems
? Select a minimum cost set of pairings such
that every flight is included in exactly one
pairing
? Crew Pairing Decomposition
– Daily
– Weekly
– Exceptions
– Transitions
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
Daily
? All flights operating four or more times per
week
? Chosen pairings will be repeated each day
? Multi-day pairings will be flown by multiple
crews
? Flights cannot be repeated in a pairing
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
Example
MON TUE WED THU FRI SAT SUN
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
D u t y A D u t y BD u t y C
D u t y AD u t y B D u t y C
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
Example,cont.
MON TUE WED THU FRI SAT SUN
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
D u t y A D u t y B D u t y C
Duty A Duty B
Duty C
Duty A
Duty B Duty C
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
Weekly
? Cover all flights scheduled in a week-long
period
? Fleet assignment on a particular flight leg can
vary by day of week
? Identify flights by day-of-week as well as
flight number,location,time
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
Exceptions
? Cover all flights in,broken pairings”
? Cover all flights that are scheduled at most
three times/week
? Identify flights by day-of-week as well as
flight number,location,time
? Generate,weekly” pairings
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
Transition
? Cover flights in pairings that cross the end of
the month
? Identify flights by date as well as flight
number,location,time,day-of-week
? Generate pairings connecting two different
flight schedules
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 23
Crew Planning
Daily
Problem Exceptions Transition
broken
pairings
broken
pairings
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 24
Assignment Problems
? Specified at the individual level
? Incorporates rest,vacation time,medical
leave,training
? Focus is not on cost but crew needs/
preferences
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 25
The Bidline Problem
? Pairings are constructed into generic
schedules
? Schedules are posted and crew members bid
for specific schedules
? More senior crew members given greater
priority
? Commonly used in the U.S.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 26
The Rostering Problem
? Personalized pairings are constructed
? Incorporates crew vacation requests,training
needs,etc.
? Higher priority given to more senior crew
members
? Typical outside the U.S.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 27
Pairing vs,Assignment
? Similarities
– Sequencing flights to form pairings ?
sequencing pairings to form schedules
– Set partitioning formulations (possibly with
side constraints)
? Differences
– Complete crews vs,single crew member
– Objective function
– Time horizon
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 28
Cockpit vs,Cabin
? Cockpit crews stay together; cabin crews do
not
? Cockpit crew makeup is fixed; cabin needs
can vary by demand
? Cabin crew members have a wider range of
aircraft they can staff
? Cockpit crew members receive higher salaries
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 29
Domestic vs,International
? Domestic U.S,networks of large carriers are
predominantly hub-and-spoke
– With many connection opportunities
– Domestic networks are usually daily
? International networks are typically point-to-
point
– More of a need to use deadheads
– International networks are typically weekly
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 30
Recovery Problem
? Given a disruption,adjust the crew schedule
so that it becomes feasible
? What is our objective?
– Return to original schedule as quickly as possible?
– Minimize passenger disruptions?
– Minimize cost?
? Limited time horizon -- need fast heuristics
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 31
Focus,Daily Domestic Cockpit
Crew Pairing Problem
? Problem description
? Formulation
? Solution approaches
? Computational results
? Integration with aircraft routing,FAM
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 32
The Crew Pairing Problem
Given a set of flights (corresponding to an
individual fleet type or fleet family),choose a
minimum cost set of pairings such that every
flight is covered exactly once (i.e,every flight is
contained in exactly one pairing)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 33
Notation
? Pk is the set of feasible pairings for fleet type k
? Fk is the set of daily flights assigned to fleet
type k
? ?fp is defined to be 1 if flight f is included in
pairing p,else 0
? cp is the cost of pairing p
? 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 34
Formulation
k
k
Pp }1,0{
Ff 1
m i n
???
????
?
?
?
p
Pp
pfp
Pp
pp
x
x
st
xc
k
k
?
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 35
Is this an easy problem?
? Linear objective function
? No complex feasibility rules
? Easy to write/intuitive
? Small number of constraints
? Huge number of integer variables
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 36
How do we solve it?
? We need branch-and-bound to solve the
IP
? We need column generation to solve the
individual LP relaxations
? Branch-and-price combines the two
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 37
Column Generation Review
? Column generation solves linear programs
with a large number of variables
? Start with a restricted master – a subset of the
variables
? Solve to optimality
? Input the duals to a pricing problem and look
for negative reduced cost columns
? Repeat
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 38
Generating Crew Pairings
? Start with enough columns to ensure a
feasible solution (may need to use artificial
variables)
? Solve Restricted Master problem
? Look for one or more negative reduced cost
columns for each crew base; add to Restricted
Master problem and re-solve
? If no new columns are found,LP is optimal
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 39
Crew Pairing Reduced Cost
Reduced cost of pairing p is:
?
?
?
?
?
kFf
ffp
pd
p T A F Bfd
??
p ay } g u ar an t eem i n,*,ofco s t d u t y m ax {
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 40
Formulation
k
k
Pp }1,0{
Ff 1
m i n
???
????
?
?
?
p
Pp
pfp
Pp
pp
x
x
st
xc
k
k
?
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 41
Pricing as a Shortest Path Problem
? A pairing can be seen as a path,where nodes
represent flights and arcs represent valid
connections
? Paths must start/end at a given crew base
? For daily problem,paths cannot repeat a
flight
? Paths must satisfy duty and pairing rules
? Path costs can be computed via labels
corresponding to pairing reduced costs
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 42
Network Structure
? Connection arc network
– Nodes represent flights
– Arcs represent (potentially) feasible connections
? Multiple copies of the network in order to
construct multi-day pairings
? Source/sink nodes at the crew base
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 43
Network Example
BOS
BOS - CIN
8 - 9:50
BOS - DCA
8 - 9:27
DCA - ORD
10:15 - 1:30
CIN - SFO
4:30 - 7:15
CIN - DE T
10:30 - 12:15
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 44
Multi-Day Network
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 45
Labels
Feasibility:
? Pairing,
– Min rest between duties
– Max rest between duties
– Max # of duties
? Duty:
– Max flying
– Max duty time
– Min idle (connection
arcs)
– Max idle (connections
arcs)
Cost:
? Pairing -- max of:
– Sum of duty costs
– fp * TAFB
– min guarantee pay
? Duty -- max of:
– Total flying time
– fd * total duty time
– min guarantee pay
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 46
Labels,cont.
Labels have to track:
? Current duty:
– Flying time in current
duty
– Total elapsed time in
current duty
– Current duty cost
? Pairing:
– Pairing TAFB
– Sum of completed
duties’ costs
– # completed duties
– Current pairing reduced
cost
Labels also contain:
? Label id
? Previous flight
? Previous flight’s label
id
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 47
Processing Labels
? For each node (in topological order)
– For each label at that node
? For each connection arc out of that node
– Process the arc
– If a label is created,check existing labels for
dominance
– If the node ends at the crew base and reduced cost
is negative,a potential column’s been found
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 48
Processing Labels,cont.
Flight repeat?
Given:
Label
Arc
Sto p
Yes
Valid for
duty?
No
Stop
No
Valid for
pairing?
Yes
N ew l ab el
Yes
Stop
No
Valid for duty:
? Doesn’t violate max duty time
? Doesn’t violate max idle time
? Doesn’t violate max flying time
New label:
? Update duty time
? Update flying time
? Update duty cost
? Update pairing red,cost
? Update pairing TAFB
? Update sum of duty costs
Valid for pairing:
? Doesn’t violate number of duties
? Doesn’t violate min layover
?Doesn’t violate max TAFB
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 49
Column Generation and Network
Structure
– Duty assignment networks
? Large number of arcs
– One arc per duty
– Can be hundreds of connections per duty
– Ex,363 flights,7838 duties,1.65 M connections
? Fewer labels per path - duty rules are built in
– Flight assignment networks
? Smaller number of arcs
– One arc per flight
– Typically not more than 30 connections per flight
? Larger number of labels
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 50
Branch-and-Bound Review
Root
nodex1 = 1 x1 = 0
Integer --
u.b,
< u.b.
x2 = 1 x2 = 0
< u.b,Prune --> u.b.
x3 = 1 x3 = 0
Infeas.< u.b.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 51
Heuristic Solution Approach
? Branch-and-bound with only root node
LP solved using column generation
– No feasible solution may exist in the
columns generated to solve the root node
LP
– Conventional wisdom,need some,bad”
columns to get a,good” solution
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 52
Branch-and-Price
? Need a branching rule that is compatible with
column generation
– Rule must be enforceable without changing the
structure of the pricing problem
? Multi-label shortest path problem
– Branching based on variable dichotomy is not
compatible
? Cannot restrict the shortest path algorithm from
finding a path (that is,a pairing)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 53
Variable Dichotomy Branching
? Given a fractional solution to the crew
pairing problem,pick p s.t,0 < xp < 1
? Two new problems,{xp = 1,xp = 0}
? Drawbacks:
– Imbalance
– Maximum depth of tree
– Enforcing in the pricing problem:
? xp = 1 is easy
? xp = 0 is hard
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 54
Branching on Follow-Ons
? Given a fractional solution,there must
be two flights f1,f2 such that f1 is
followed by f2 a fractional amount in the
solution
– Pairing f1-f2-f3 has value 1/2 and pairing f1-
f4 has value 1/2
? Branch on {f1 is/is not followed by f2}
– More balanced
– Fewer branching levels
– Easy to enforce in pricing problem
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 55
How to Alter Network to Enforce
Branching Decision
? If follow-on flights a-b required
– Remove all connection arcs from a to flights
other than b
– Remove all connection arcs into b from flights
other than a
? If follow-on flights a-b disallowed
– Remove all connection arcs from a to b
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 56
How to Select Flight Pairs for
Branching
? Sum current LP solution values of all possible
flight follow-ons
? Branch on the follow-on with the greatest
value
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 57
Computational Results
American Airlines (1993):
? 25,000+ crew members
? Save $20+ million/year
? Solutions in 4 - 10 hours
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 58
Other Crew Scheduling Research
Topics
? Cabin crew scheduling
? Integrating pairing and assignment
? Robust planning
? Recovery
? Integrated models
