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 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
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 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
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 2/212021 Barnhart 1.206J/16.77J/ES D 2 15J
2/21/2021 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 crewfeasible only if both flights are covered by the same aircraft
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 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
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 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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