1206J/1677J/ESD215J Airline Schedule Planning Cynthia barnhart spring 2003
1.206J/16.77J/ESD.215J Airline Schedule Planning Cynthia Barnhart Spring 2003
1206/16.77J/ESD215J The Crew Scheduling problem Outline Problem definition Sequential Solution Approach Crew Pairing optimization model Branch-and-Price solution Branching strategies 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
Why Crew scheduling? secone nd largest operating expense (after fuel) OR Success story Complex problems with many remaining opportunities a case study for techniques to solve large Ip 2/212021 Barnhart 1.206J/16.77J/ES D 2 15J
2/21/2021 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
Airline schedule planning Schedule Design Fleet Assignment Aircraft routing Crew Scheduling 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 4 Airline Schedule Planning Schedule Design Fleet Assignment Aircraft Routing Crew Scheduling
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 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
Network flow problem? Complex feasibility rules Non-linear objective function 2/212021 Barnhart 1.206J/16.77J/ES D 2 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 6 Network Flow Problem? • Complex feasibility rules •Non-linear objective function
Building blocks To Do une 10:00 Flight Duty Pairing Schedule 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 7 Building Blocks To Do 9:00 10:00 11:00 12:00 1:00 2:00 3:00 Duty June Flight Pairing Schedule
Duty Periods Definition a duty period is a day-long sequence of consecutive flights that can be assigned to a single cren, to be followed by a period of rest 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
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 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
Duty Cost Function Maximum of Total flying time fa total duty time Minimum guaranteed duty pay Primarily compensates for flying time, but also compensates for undesirable" schedules 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 10 Duty Cost Function • Maximum of: – Total flying time – f d * total duty time – Minimum guaranteed duty pay • Primarily compensates for flying time, but also compensates for “undesirable” schedules