1206J/1677J/ESD215J Airline schedule planning ynthia barnhart Spring 2003
1.206J/16.77J/ESD.215J Airline Schedule Planning Cynthia Barnhart Spring 2003
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 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
The Maintenance routing Problem Mri riven Flght Schedule for a single fleet Each flight covered exactly once by fleet Number of Aircraft by Equipment Type Cant assign more aircraft than are available FAA Maintenance Requirements Turn Times at each Station Through revenues for pairs or sequences of lights Maintenance costs per aircraft 2/212021 Barnhart 1.206J/16.77J/ES D 2 15J
2/21/2021 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
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 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
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 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
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 2/212021 Barnhart 1.206J/16.77J/ES D 2 15J
2/21/2021 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
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 2/212021 Barnhart 1.206J/16.77J/ES D 2 15J
2/21/2021 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
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 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
CP CoSt Function Duty cost is maximum of: Flying time 米 elapse ed duty time Minimum duty pay Pairing cost is maximum of Sum of duty costs f, time-away-from-base f, x number of duties 2/212021 Barnhart 1.206J/16.77J/ES D 2 15J
2/21/2021 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
CP Problem Obiective ●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 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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)