《航线进度计划》（英文版） lec14 Shan Lan Robust scheduling

Courtesy of Shan Lan, Cindy Barnhart and John-Paul Clarke. Used with permission New Approaches to Add robustness into Airline schedules Shan Lan, Cindy Barnhart and John-Paul clarke Center for Transportation and Logistics Massachusetts Institute of Technology May5,2002

New Approaches to Add Robustness into Airline Schedules Shan Lan, Cindy Barnhart and John-Paul Clarke Center for Transportation and Logistics Massachusetts Institute of Technology May 5 , 2002 Courtesy of Shan Lan, Cindy Barnhart and John-Paul Clarke. Used with permission

Outline Background Motivation and our contributions Overview of Robust Airline Schedule Planning Robust Aircraft Maintenance Routing -reduce delay propagation Flight Schedule Retiming -reduce passenger missed connections Summary and Future Research Directions

2 Outline Background, Motivation and Our Contributions Overview of Robust Airline Schedule Planning Robust Aircraft Maintenance Routing – reduce delay propagation Flight Schedule Retiming – reduce passenger missed connections Summary and Future Research Directions

Airline Schedule Planning Process Schedule Design Fleet Assignment Maintenance Routing Crew Scheduling Most existing planning models assume that aircraft, crew, and passengers will operate as planned

3 Schedule Design Crew Scheduling Fleet Assignment Maintenance Routing Airline Schedule Planning Process Most existing planning models assume that aircraft, crew, and passengers will operate as planned

Airline Operations Many reasons can cause delays Severe weather conditions, unexpected aircraft and personnel failures, congested traffic, etc Delays may propagate through the network Long delays and cancellations cause schedule disruptions Airlines must reschedule aircraft/crew and re accommodate passengers Huge revenue loss: Delays cost consumers and airlines about $6.5 billion in 2000(Air Transport Association)

4 Airline Operations Many reasons can cause delays ➢ Severe weather conditions, unexpected aircraft and personnel failures, congested traffic, etc. Delays may propagate through the network Long delays and cancellations cause schedule disruptions Airlines must reschedule aircraft/crew and re￾accommodate passengers Huge revenue loss: ➢ Delays cost consumers and airlines about $6.5 billion in 2000 (Air Transport Association)

Flight Delays Cancellations Trend(1995-1999)(Bratu and Barnhart, 2002) Significant increase(80%)in flights delayed more than 45 min Significant increase(500%)in the number of cancelled flights Year 2000 ( Bratu and Barnhart, 2002) 30% of flights delayed >3.5% of flights cancelled Future: Air traffic in US is expected to double in the next 10-15 years (Schaefer et al. (2001) Each 1% increase in air traffic >a 5% increase in delays (Schaefer et al. (2001)) Lead to more frequent and serious delay and schedule disruptions 5

5 Flight Delays & Cancellations Trend (1995-1999) (Bratu and Barnhart, 2002) ➢ Significant increase (80%) in flights delayed more than 45 min ➢ Significant increase (500%) in the number of cancelled flights Year 2000 (Bratu and Barnhart, 2002) ➢ 30% of flights delayed ➢ 3.5% of flights cancelled Future: ➢ Air traffic in US is expected to double in the next 10-15 years (Schaefer et al. (2001)) ➢ Each 1% increase in air traffic → a 5% increase in delays (Schaefer et al. (2001)) ➢ Lead to more frequent and serious delay and schedule disruptions

Passenger Disruptions Passengers are disrupted if their planned itineraries are infeasible because flights cancellation Insufficient time to connect 4%of passengers disrupted in 2000 (Bratu and Barnhart, 2002) Half of them are connecting passengers Very long delays for disrupted passengers Average delay for disrupted passengers is approx. 419 minutes (versus 14 min delay for non-disrupted passengers)(Bratu and Barnhart, 2002) Significant revenue loss 6

6 Passenger Disruptions Passengers are disrupted if their planned itineraries are infeasible because ➢ flights cancellation ➢ Insufficient time to connect 4% of passengers disrupted in 2000 (Bratu and Barnhart, 2002) ➢ Half of them are connecting passengers Very long delays for disrupted passengers ➢ Average delay for disrupted passengers is approx. 419 minutes (versus 14 min delay for non-disrupted passengers) (Bratu and Barnhart, 2002) Significant revenue loss

Our Contributions Provide alternative definitions for robustness in the context of airline schedule planning Develop an optimization model and solution approach that can generate aircraft maintenance routes to minimize delay propagation Develop optimization models and solution approach to minimize the expected total number of passengers missing connection, and analyze the model properties Proof-of-concept results show that these approaches are promIsIng Develop integrated models for more robustness

7 Our Contributions Provide alternative definitions for robustness in the context of airline schedule planning Develop an optimization model and solution approach that can generate aircraft maintenance routes to minimize delay propagation Develop optimization models and solution approach to minimize the expected total number of passengers missing connection, and analyze the model properties Proof-of-concept results show that these approaches are promising Develop integrated models for more robustness

Outline Background Motivation and our contributions Overview of Robust Airline Schedule Planning How to deal with schedule disruptions Challenges of building robust airline schedules Definitions of robustness Robust airline schedule planning approaches Robust Aircraft Maintenance Routing -- reduce delay propagation Flight Schedule Retiming -reduce passenger missed connections Summary and Future Research Directions 8

8 Outline Background, Motivation and Our Contributions Overview of Robust Airline Schedule Planning ➢ How to deal with schedule disruptions ➢ Challenges of building robust airline schedules ➢ Definitions of robustness ➢ Robust airline schedule planning approaches Robust Aircraft Maintenance Routing -- reduce delay propagation Flight Schedule Retiming – reduce passenger missed connections Summary and Future Research Directions

How to Deal with Schedule Disruptions Two ways to deal with schedule disruptions Re-optimize schedule after disruptions occur(operation stage) Build robustness into the schedules(planning stage) Existing planning systems do not have effective methods to manage disruptions A more robust plan can reduce the effect of disruptions on the operations reduce operation costs and improve quality of service Robust airline schedule planning methods are needed

9 How to Deal with Schedule Disruptions Two ways to deal with schedule disruptions ➢ Re-optimize schedule after disruptions occur (operation stage) ➢ Build robustness into the schedules (planning stage) Existing planning systems do not have effective methods to manage disruptions A more robust plan can reduce the effect of disruptions on the operations ➔ reduce operation costs and improve quality of service Robust airline schedule planning methods are needed

Challenges of Building Robust Plans Lack of a systematic way to define robustness in the context of airline schedule planning Aircraft, crew and passenger flows interact in the hub-and-spoke network Huge problem size> tractability issue Difficult to balance robustness and costs 10

10 Challenges of Building Robust Plans Lack of a systematic way to define robustness in the context of airline schedule planning Aircraft, crew and passenger flows interact in the hub-and-spoke network Huge problem size → tractability issue Difficult to balance robustness and costs