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)