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 Fleet Assignment Problem Outline Problem Definition and Objective Fleet Assignment Network Representation Fleet Assignment model Fleet Assignment Solution Branch-and-bound Results 2/212021 Barnhart 1.206J/16.77J/ES D 2 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 2 1.206J/16.77J/ESD.215J The Fleet Assignment Problem • Outline – Problem Definition and Objective – Fleet Assignment Network Representation – Fleet Assignment Model – Fleet Assignment Solution • Branch-and-bound – Results
Airline schedule planning Schedule design Select optimal set of fight legs in a schedule Fleet Assignment Assign aircraft types to flight legs such that contribution is maximized Aircraft routi Contribution revenue- Costs Assign crew(pilots and/or flight Crew Scheduling attendants) to flight legs 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 3 Route individual aircraft honoring maintenance restrictions Assign aircraft types to flight legs such that contribution is maximized Contribution = Revenue - Costs Airline Schedule Planning Schedule Design Fleet Assignment Aircraft Routing Crew Scheduling Select optimal set of flight legs in a schedule Assign crew (pilots and/or flight attendants) to flight legs
Problem definition Given Flight Schedule Each flight covered exactly once by one fleet type Number of aircraft by equipment Type Cant assign more aircraft than are available, for each type Turn Times by Fleet Type at each Station Other restrictions: Maintenance. Gate Noise Runway, etc Operating costs spill and recapture costs Total Potential Revenue of Flights, by Fleet Type 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 4 Problem Definition Given: – Flight Schedule • Each flight covered exactly once by one fleet type – Number of Aircraft by Equipment Type • Can’t assign more aircraft than are available, for each type – Turn Times by Fleet Type at each Station – Other Restrictions: Maintenance, Gate, Noise, Runway, etc. – Operating Costs, Spill and Recapture Costs, Total Potential Revenue of Flights, by Fleet Type
Problem Objective Find Cost minimizing ( or profit maximizing assignment of aircraft fleets to scheduled flights such that maintenance requirements are satisfied. conservation of flow (balance) of aircraft is achieved, and the number of aircraft used does not exceed the number available (in each fleet type 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 5 Problem Objective Find: – Cost minimizing (or profit maximizing) assignment of aircraft fleets to scheduled flights such that maintenance requirements are satisfied, conservation of flow (balance) of aircraft is achieved, and the number of aircraft used does not exceed the number available (in each fleet type)
Definitions(again p passengers that are denied booking due to capacity restrictions Recapture passengers that are recaptured back to the airline after being spilled from another flight les For each fleet- flight combination Cost= Operating cost Spill cost 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 6 Definitions (again) • Spill – passengers that are denied booking due to capacity restrictions • Recapture – passengers that are recaptured back to the airline after being spilled from another flight leg • For each fleet - flight combination: Cost Operating cost + Spill cost
Fleet Assignment References Abara( 1989), Daskin and Panayotopoulos 1989),Hane, Barnhart, Johnson, Marsten, Neumhauser, and Sigismondi(1995) Hane, et al. The Fleet Assignment Problem Solving a large integer program Mathematical programming, Vol. 70, 2, PP 211 232.1995 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 7 Fleet Assignment References • Abara (1989), Daskin and Panayotopoulos (1989), Hane, Barnhart, Johnson, Marsten, Neumhauser, and Sigismondi (1995) • Hane, et al. “The Fleet Assignment Problem, Solving a Large Integer Program,” Mathematical Programming, Vol. 70, 2, pp. 211- 232, 1995
Network representation Topologically sorted time-line network Nodes Flght arrivals/ departures(time and space) Arcs Flight arcs: one arc for each scheduled flight Ground arcs: allow aircraft to sit on the ground between flights 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 8 Network Representation • Topologically sorted time-line network – Nodes: • Flight arrivals/ departures (time and space) – Arcs: • Flight arcs: one arc for each scheduled flight • Ground arcs: allow aircraft to sit on the ground between flights
Time-Line Network Ground arcs City a City B City c City d 8:0012:0016:0020:00 8:0012:0016:002000 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 9 Time-Line Network 8:00 12:00 16:00 20:00 8:00 12:00 16:00 20:00 City A City B City C City D • Ground arcs
Time-Line Network Daily"p1 roblem Wrap-around (or overnight) arcs Washington, D.C. Baltimore Boston 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 10 Time-Line Network • “Daily” problem – Wrap-around (or overnight) arcs Washington, D.C. Baltimore New York Boston Time
