1206J/1677J/ESD215J Airline Schedule Planning Cynthia barnhart spring 2003
1.206J/16.77J/ESD.215J Airline Schedule Planning Cynthia Barnhart Spring 2003
Aircraft maintenance routing utline Problem Definition and Objective Network Representation String model Solution approach Branch-and-price Extension: Combined Fleet Assignment and Aircraft routing 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 2 Aircraft Maintenance Routing Outline – Problem Definition and Objective – Network Representation – String Model – Solution Approach – Branch-and-price – Extension: Combined Fleet Assignment and Aircraft Routing
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 3 Airline Schedule Planning Schedule Design Fleet Assignment Aircraft Routing Crew Scheduling
Airline schedule planning Schedule Design Fleet Assignment Str Aircraft routing Based FAM 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 StringBased FAM
Problem definition Given Flight 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 flights Maintenance costs per aircraft 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 5 Problem Definition • 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
Problem Objective ind 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 6 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
FAA Maintenance requirements ecks Maintenance required every 60 hours of flying Airlines maintain aircraft every 40-45 hours of flying with the maximum time between checks restricted to three to four calendar days 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 7 FAA Maintenance Requirements • “A” Checks – Maintenance required every 60 hours of flying – Airlines maintain aircraft every 40-45 hours of flying with the maximum time between checks restricted to three to four calendar days
FAM Representation of Maintenance constraints Maintenance arcs for fleet k included in time line network at each maintenance station for k ach arc Begins at an aircraft arrival+ turn time pans minimum maintenance time Constraints added to FAM for each aircraft type k, equiring a minimum number of aircraft of type k on the set of maintenance arcs Ensures that sufficient maintenance opportunities exist One aircraft might be serviced daily and others not at all 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 8 FAM Representation of Maintenance Constraints • Maintenance arcs for fleet k included in time line network at each maintenance station for k • Each arc – Begins at an aircraft arrival + turn time – Spans minimum maintenance time • Constraints added to FAM for each aircraft type k, requiring a minimum number of aircraft of type k on the set of “maintenance arcs” – Ensures that sufficient maintenance opportunities exist – One aircraft might be serviced daily and others not at all
Hub-and-Spoke vs Point-to-Point Networks Domestic U.S. carriers with hub-and-spoke networks find that approximate maintenance constraints result in maintenance feasible routings Sufficient number of opportunities at hubs to swap aircraft assignments so that aircraft get to maintenance stations as needed pproximate maintenance constraints often do not result in maintenance feasible routings for point-to- point networks Flying time between visits to maintenance stations often too lons 2/212021 Barnhart 1.206J/16.77J/ES D 2 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 9 Hub-and-Spoke vs. Point-to-Point Networks • Domestic U.S. carriers with hub-and-spoke networks find that approximate maintenance constraints result in maintenance feasible routings – Sufficient number of opportunities at hubs to swap aircraft assignments so that aircraft get to maintenance stations as needed • Approximate maintenance constraints often do not result in maintenance feasible routings for point-topoint networks – Flying time between visits to maintenance stations often too long
Network representation Connection network Nodes Flight arrivals/ departures(time and space rcs Flight arcs: one arc for each scheduled flight Connection arcs: allow aircraft to connect between flights 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 10 Network Representation • Connection network – Nodes: • Flight arrivals/ departures (time and space) – Arcs: • Flight arcs: one arc for each scheduled flight • Connection arcs: allow aircraft to connect between flights