Airline Operations Lecture #2 1.206J April 27, 2003 Summary Lecture #1 ? Airline schedules (Aircraft, crew, passengers) are optimized leading to: GBE Little slacks (idle time) GBE Schedule dependencies GBE Delay chain effects Causes of schedule disruptions GBE Shortages of airline resources GBE Shortages of airport resources Complex airline resource regulations GBE Aircraft maintenance GBE Pilots Airline Schedules Recovery GBE Schedule Recovery Model (SRM) GBE Aircraft Recovery Model (ARM) GBE Crew Recovery Model (CRM) GBE Passenger Flow Model (PFM) GBE Journey Management GBE Passenger Re-accommodation G36G35G30 G24G24G35G35G30G30 G26G26G35G35G30G30 G33G33G29G30G29G30 G33G44G56G33G44G56G56G56G48G51G4AG48G48G51 G48G55 G55G35G48G35G48G44G44G46G46G46G52G50 G46G52G50G50G50G52G47G52G47G44G44G57 G57G4CG4CG52G52G51G51 Summary Lecture #1 (Cont.) Airline schedules recovery problems GBE Aircraft maintenance module: Objective: feasibility only GBE Crew schedule recovery module Objective: to minimize disruptions, recover the disrupted with minimum flight schedule disruptions and control Flight Time Count Complex rules GBE Passenger schedule recovery module Objective: to minimize passenger delays, ill will, gap between expected and delivered service Complexity: – Priority rules (booked over disrupted, priority among disrupted: network, user, FFP, fare class) – Seat availability uncertainty Lecture #2 Outline Passengers are important to satisfy Tricks to prevent schedule disruptions and recover schedules Traditional ARM; Model shortcomings Interdependency of passengers and aircraft operations Our approach: Minimizing sum of disrupted passenger Flight copy generation and solution feasibility Minimizing sum of passenger delays Proxy of minimizing sum of passenger delays Simulation environment Conclusion Importance of delivering services as expected in airline industry Very competitive industry Low profit margin (5% in 2000, best year) Dissatisfied customers might shop next to competitors, jeopardizing your profitability On time service is not prime factor to attract customers but it contributes to loyalty Passenger delay distribution is not continuous, few passengers suffer high delays Passenger dissatisfaction function with respect to delays is not linear Clear objective: minimize passenger ill will with same operations costs Trade off: Passenger service reliability versus operating costs Operating costs Passenger dissatisfaction Admissible operating cost region Feasible operating space G36G52G55G57 G2F G44G46G46G52G55G47G4CG51G4A G57G52 G56G48G55G59G4CG46G48G53G52G4FG4CG46G5C G27G4CG56G55G58G53G57G48G47G22 G3CG48G56 G31G52 G35G48G50G52G59G48G56G48G44G57 G49G55G52G50 G55G48G50G44G4CG51G4CG51G4AG4CG51G59G48G51G57G52G55G5C G37G44G4EG48G51G48G5BG57 G47G4CG56G55G58G53G57G48G47G53G44G56G56G48G51G4AG48G55 G4CG51 G2F G35G48G50G52G59G48G56G48G44G57G56G49G55G52G50 G55G48G50G44G4CG51G4CG51G4AG4CG51G59G48G51G57G52G55G5C G24G56G56G4CG4AG51G44G4FG4F G51G52G51G10G47G4CG56G55G58G53G57G48G47 G53G44G56G56G48G51G4AG48G55G56 G57G52G57G4BG48G4CG55 G53G4FG44G51G51G48G47G4CG57G4CG51G48G55G44G55G4CG48G56 G25G58G4CG4FG47G57G4BG48G4FG4CG56G57G52G49G47G4CG56G55G58G53G57G48G47 G53G44G56G56G48G51G4AG48G55G56G0F G2F G29G4FG4CG4AG4BG57 G47G48G4FG44G5CG56G44G51G47 G49G4FG4CG4AG4BG57 G46G44G51G46G48G4FG4FG44G57G4CG52G51G56 G33G44G56G56G48G51G4AG48G55 G45G52G52G4EG4CG51G4AG56 G49G52G55 G48G44G46G4B G56G46G4BG48G47G58G4FG48G47 G4CG57G4CG51G48G55G44G55G5C G2CG56 G2F G20G91 G22 G3CG48G56 G31G52 G28G31G27 G35G48G46G52G55G47 G53G44G56G56G48G51G4AG48G55 G47G48G4FG44G5C G29G4CG51G47G45G48G56G57 G55G48G46G52G59G48G55G5CG4CG57G4CG51G48G55G44G55G5CG44G51G47G44G56G56G4CG4AG51G53G44G56G56G48G51G4AG48G55 G33G44G56G56G48G51G4AG48G55 G27G48G4FG44G5C G36G57G44G57G4CG56G57G4CG46G56 G2CG31G33G38G37G36 G33G35G28G33G35G32G26G28G36G36G2C G31G2A G33G27G26 G35G48G46G52G55G47 G53G44G56G56G48G51G4AG48G55 G47G48G4FG44G5C Flight and passenger delays 0 5 10 15 20 25 30 ( m i nut e s ) Passengers Flight Delay Flight delays underestimate passenger delays Key explanation lies in the disrupted passengers Passenger/flight = 170% Disrupted passengers versus non disrupted passengers GBE Disrupted passengers experience long delays in general because 20% of them are stranded overnight (delay propagation results in more disruptions later during the day) GBE Although a small percentage, disrupted passengers account for 40% of the total passenger delay and most of the severely delayed passengers (80% of passengers delayed by more than 4 hours) Non disrupted passengers Disrupted passengers August 2000 60%96.8%16 minutes 40%3.2%320 minutes % Delays% Passengers Av. Delay (minutes) Risk of being disrupted GBE Although fewer planned connecting passengers, higher number are disrupted GBE The risk of a passenger to be disrupted is 2.75 times greater for connecting (5.5%) than for local (2%) GBE Does not bode well for hub-and-spoke with banks 100%52%Caused by flight cancellations 40%60%Disrupted passenger mix Caused by missed connections Scheduled passenger mix Passenger type 48% 65%35% LocalConnecting Passenger disruption: important factors Disruption time & Route frequency R 2 = 0.93 0 2 4 6 8 10 12 14 16 8 1012141618202 24 disruption time in window (+/- 1hour) A v er age del ay of t he di s r upt ed pas s enger s ( hour s ) G35G15G20G13G11G1CG18 G13 G14 G15 G16 G17 G18 G19 G1A G1B G1C G15G16G17G18G19G1AG1BG1CG14G13G14G14G14G15 G52G51 G55G52G58G57G48G56 G5AG4CG57G4B G49G55G48G54G58G48G51G46G5CG21G20 G24G59 G27 G48 G4F G44 G5C G52 G49 G47 G4C G56G55G58 G53G57 G48 G47 G53G44 G56G56 G48 G51 G4A G48 G55G56 G0B G4B G52 G58 G55G56G0C Passenger service reliability study: Conclusions Disrupted passengers are important: 80% of the passengers delayed by more than 4 hours are disrupted Minimizing the sum of disrupted passengers while recovering the schedule might be a good idea… Resource Dependability: Ripple effects Source: Sabre, 1998 DFW-LAX LAX-ONT DFW-SNA LAX-SMF PC CC A PC CC A Cockpit Crew rest at SMF SNA-SJC SNA-RNO SNA-SEA SMF-LAX ONT-LAX Aircraft maintenance at ONT PC CC: deadheading A PC: Pilot Crew; CC: Cabin Crew; A: Aircraft Disruption Impacts; Solutions and Constraints Flight delays Broken crew pairings Resource shortage Crew unavailability Disrupted maintenance Gate problems Baggage handling problems others ? Hold flights Cancel flights Aggregate flights Divert aircraft Swap resources Use spare aircraft Use reserve crews Deadhead crews Layover crews Aircraft balance Market protection Fleet/crew compatibility Resource positioning Maintenance requirements Crew legalities Union contracts Others Disruption Impacts Solutions Constraints Disruption Impacts; Solutions and Constraints Flight delays Broken crew pairings Resource shortage Crew unavailability Disrupted maintenance Gate problems Baggage handling problems others Hold flights Cancel flights Aggregate flights Divert aircraft Swap resources Use spare aircraft Use reserve crews Deadhead crews Layover crews Aircraft balance Market protection Fleet/crew compatibility Resource positioning Maintenance requirements Crew legalities Union contracts Others Disruption Impacts Solutions Constraints Aircraft route swaps Swapping useful to: + Spread the delays informally, converge toward bank integrity + Postpone the shortage problem + Recover from irregularities Constraints: Crew compatibility and legalities A1;F1 A2;F2 A3;F3 A1;F3 A2;F1 A3;F2 Schedule Swapping time time Delay F1 Delay F2 Delay F3 No Swapping A3;F3 A1;F1 A2;F2 SCHEDULE time BOS EWR ORD MIA IAH HYPOTHETICAL CASE: Flights not canceled (NC) time BOS EWR MIA IAH ORD ACTUAL OPERATIONS time BOS EWR ORD MIA IAH ACTUAL OPERATIONS: Flights canceled (C) time BOS EWR MIA IAH ORD Flight cancellation benefits passengers when… time BOS EWR MIA IAH ORD Low loads in canceled flights Strong down line Passenger disruptions Severe delay But often crew disruptions… Unless canceled flights belong to the same crew duty sequence Airline Schedule Recovery Problem: Assumptions At a given time of the day, we assume that airline controllers know the state of the system: GBE Locations and availability of resources Aircraft Pilot and flight attendant crews GBE Passenger states (i,e., disrupted or not) and locations/destinations Airline Recovery Model, ARM (G. Yu et al.) tt ff ff fFtT fF f t ff tT f tt tt ff ff fF fF dj oj 00 ff 0 0 fF oj __ ff _ fF dj min d x c z st : xz1 xy xy xy j xy Flight coverage Aircraft balance Initial resource at ai Ops cost + Cancellatio rports n cost ∈∈ ∈ ∈ ?+ ∈∈ + ∈ ? ∈ ?? ×+ ×?? ?? += += + += + ∑∑ ∑ ∑ ∑∑ ∑ ∑ tt ff j x{0,1};y0 End of the day resource at airports ? = ∈≥ Objective is to minimize operating cost (flight delay and cancellation costs) Aircraft route schedule S1 H S2 Aircraft A Aircraft B Aircraft actual operations: unexpected delay (e.g., aircraft technical problem) S1 H S2 delay Aircraft A Aircraft B Passenger actual itineraries Operations decision #3: don’t cancel & postpone aircraft B S1 H S2 delay Aircraft A Aircraft B Flight copy generations We have developed a technique to minimize the number of flight copies Flight copy generations We have developed a technique to minimize the number of flight copies Four types of flight copies are generated: GBE Aircraft ready times S3 H S2 S1 Flight copy generations We have developed a technique to minimize the number of flight copies Four types of flight copies are generated: GBE Aircraft ready times GBE Copies to prevent passengers from missing connections S3 H S2 S1 Flight copy generations We have developed a technique to minimize the number of flight copies Four types of flight copies are generated: GBE Aircraft ready times GBE Copies to prevent passengers from missing connections GBE Consequence of type 2, aircraft postponement propagation S3 H S2 S1 Flight copy generations We have developed a technique to minimize the number of flight copies Four types of flight copies are generated: GBE Aircraft ready times GBE Copies to prevent passengers from missing connections GBE Consequence of type 2, aircraft postponement propagation GBE Schedule (for cancellations) S3 H S2 S1 Flight copy generations We have developed a technique to minimize the number of flight copies Four types of flight copies are generated: GBE Aircraft ready times GBE Copies to prevent passengers from missing connections GBE Consequence of type 2, aircraft postponement propagation GBE Schedule (for cancellations) Claim: We generate the minimum set of copies to capture one optimal solution Had we generated copies every minute (as proposed in literature), we would typically have to generate between 5 and 10 times as many flight copies (10,000 to 20,000 per day of operations), which would greatly increase running time and may jeopardize solution feasibility because of running time Maintaining crew feasibility Respect planned duty period (constraints) GBE Given a sequence of flights assigned to a crew (duty), add feasibility constraints GBE Not always needed because either the flight terminates the crew duty assignment or some reserve crews can be used (typically at hubs); up to the user to define these constraints (shadow prices indicates the benefit for the passengers of relaxing the constraint) S3 H S2 S1 X1 X2 X1 + X2 <= 1) Maintaining crew feasibility Respect planned duty period (constraints) GBE Given a sequence of flights assigned to a crew (duty), add feasibility constraints GBE Not always needed because either the flight terminates the crew duty assignment or some reserve crews can be used (typically at hubs); up to the user to define these constraints (shadow prices indicates the benefit for the passengers of relaxing the constraint) Satisfy regulatory constraints (Flight copies) GBE Maximum total flying time (not affected) GBE Maximum total elapsed time (MTET); iterative algorithm: if by adding a flight copy, the associated crew’s elapsed time exceeds MTET, don’t generate copy, otherwise do S3 H S2 S1 Maintaining crew feasibility Respect planned duty period (constraints) GBE Given a sequence of flights assigned to a crew (duty), add feasibility constraints GBE Not always needed because either the flight terminates the crew duty assignment or some reserve crews can be used (typically at hubs); up to the user to define these constraints (shadow prices indicates the benefit for the passengers of relaxing the constraint) Satisfy regulatory constraints (Flight copies) GBE Maximum total flying time (not affected) GBE Maximum total elapsed time (MTET); iterative algorithm: if by adding a flight copy, the associated crew’s elapsed time exceeds MTET, don’t generate copy, otherwise do Model solutions do not result in any additional crew disruptions due to postponement decisions; keep control on overhead operating costs Several models to minimize the crew disruption impact and minimize the cost of crew disruptions, but these models assume the flight operations are given. They can be used as complement to our models (Desrosier et al. (optimal); Yu et al. (heuristic)) pp pP t ff tT f tt tt ff ff (f ,t) In(j) (f,t) Out(j) ff pf tu fgp g C(u)d(g) a(f) tt pf,a f Minimize n st : x z 1 xy xy xyRes(a,ft,) z xx1 [0;1]; x {0,1}; y 0 ∈ ∈ ?+ ∈∈ ?? ∈< ?? ×ρ ?? ?? += += + += ? ρ ≥ +?ρ ≤ ρ ∈∈≥ ∑ ∑ ∑∑ ∑ ∑ GBE Objective: Minimize sum of disrupted passengers GBE Flight coverage constraints GBE Aircraft balance for each sub fleet type GBE Initial and end of the day aircraft resource constraints GBE Passenger cancellation constraints GBE Missed connected passengers constraints GBE Only flight copy variables, x, have to be binary Minimizing Sum of Disrupted Passengers Minimizing passenger delay Need to consider all potential recovery itineraries for each passenger Large scale problem: 500,000 integer variables; 12 hours CPU using B&B deep first search methodology ii pp pPiI p t ff tT f tt tt ff ff (f ,t) In(j) (f,t) Out(j) 00 ff i pp iI p ti t pff fi pPiI p it t pf f bq xz1 fF xy xy xy j qn qCx q0;x{0,1};y0 Min ∈∈ ∈ ?+ ∈∈ + ? ∈ ∈∈ += ?∈ += + += = δ≤× ≥∈ ≥ ∑∑ ∑ ∑∑ ∑ ∑ ∑∑ Investigated approximate approaches that meet the time constraint requirements pp pP t f,a f tTaA ff tt tt f,a f f,a f fF fF dj oj 00 f,a f 0,a 0 fF oj pf tu fgp g C(u) d(g) a(f) tt pf,a f Minimize n st : x z 1 xy xy xyj z xx1 [0;1]; x {0,1}; y 0 ∈ ∈∈ ?+ ∈∈ + ∈ ∈< ?? ×ρ?? ?? += += + += ρ ≥ +?ρ ≤ ρ ∈∈≥ ∑ ∑∑ ∑∑ ∑ ∑ Estimate delay of disrupted passenger using PDC Total delay = D(DP) N(DP) D(NDP) N(NDP) NDP TP DP Minimize( D(DP) N(DP) D(TP DP) N(TP DP) ∑× +∑ × =? ∑× +∑?×? G04 Objective function Objective function: GBE Fine grained to Passenger Name Record GBE Estimate each passenger dissatisfaction: assign a cost (expected future revenue loss of delay d for PNR p) GBE Let the model chose flight decisions Enforcing feasibility: GBE Minimizing crew disruptions GBE Preventing maintenance routing infeasibility G24G4CG55G4FG4CG51G48 G56G5CG56G57G48G50 G56G57G44G57G48G1D G24G4CG55G46G55G44G49G57G1D G53G52G56G4CG57G4CG52G51G0F G50G44G4CG51G57G48G51G44G51G46G48G0F G52G53G48G55G44G57G4CG52G51G44G4F G26G55G48G5AG56G1D G53G52G56G4CG57G4CG52G51G0F G47G4CG56G55G58G53G57G4CG52G51 G56G57G44G57G58G56G0F G47G58G57G5C G57G4CG50G48G0F G49G4FG4CG4AG4BG57 G57G4CG50G48G0F G48G57G46G11 G33G44G56G56G48G51G4AG48G55G56G1D G53G52G56G4CG57G4CG52G51G0F G47G48G56G57G4CG51G44G57G4CG52G51G0F G33G24G37G0F G47G4CG56G55G58G53G57G4CG52G51 G56G57G44G57G58G56 G29G4FG4CG4AG4BG57 G46G52G53G5C G4AG48G51G48G55G44G57G4CG52G51 G44G4FG4AG52G55G4CG57G4BG50 G32G53G48G55G44G57G4CG52G51G56 G49G52G55G48G46G44G56G57G56 G29G4FG4CG4AG4BG57 G47G48G53G44G55G57G58G55G48 G57G4CG50G48G56G0F G3BG0D G44G51G47 G49G4FG4CG4AG4BG57 G46G44G51G46G48G4FG4FG44G57G4CG52G51G56 G3DG0D G52G53G57G4CG50G4CG5DG48G55 G24G4CG55G46G55G44G49G57 G55G52G58G57G4CG51G4A G45G44G56G48G47 G52G51 G0BG3BG0DG0FG3DG0DG0C ? G29G48G44G56G4CG45G4FG48 G55G52G58G57G48 G35G22 G3CG48G56 G31G52 G33G55G48G59G48G51G57 G4CG51G49G48G44G56G4CG45G4FG48 G44G4CG55G46G55G44G49G57 G55G52G58G57G48 G56G5AG44G53G56 G30G52G47G4CG49G5C G49G4FG4CG4AG4BG57 G47G48G53G44G55G57G58G55G48 G56G52G4FG58G57G4CG52G51 G32G45G57G44G4CG51 G49G48G44G56G4CG45G4FG48 G44G4CG55G46G55G44G49G57 G55G52G58G57G48 G35GB7 G44G51G47 G44G56G56G52G46G4CG44G57G48G47 G52G53G57G4CG50G44G4F G56G52G4FG58G57G4CG52G51 G0BG3BGB7G0DG0FG3DGB7G0DG0C G32G53G57G4CG50G44G4F G47G4CG56G55G58G53G57G48G47 G53G44G56G56G48G51G4AG48G55 G55G48G10G55G52G58G57G4CG51G4A G26G52G51G56G4CG47G48G55G4CG51G4A G56G48G44G57 G44G59G44G4CG4FG44G45G4CG4FG4CG57G5C G58G51G46G48G55G57G44G4CG51G57G5C G35G48G46G52G59G48G55G5C G53G55G4CG52G55G4CG57G5C G53G52G4FG4CG46G4CG48G56 G26G55G48G5A G52G53G48G55G44G57G4CG52G51G56 G55G48G46G52G59G48G55G5CG0F G35G48G53G44G4CG55 G53G44G4CG55G4CG51G4AG56 Routing passengers Several optimizations models that route passengers to their destinations are used depending on the service priority rules Recovery priority among disrupted passengers Priority given to booked passengers over disrupted FDFS for disrupted; local first when same disruption time Optimal passenger recovery Optimal passenger recovery FDFS for disrupted; local first when same disruption time Combination of PDC+PMIXYes Stochastic PDC; Don’t know exact seat capacity before boarding ends due to potential no shows The Passenger Mix model (PMIX) The Passenger Delay Calculator (PDC) Routing algorithm Yes No Yes Passenger service priority rule Passenger routing algorithm performance PMIX provides the optimal passenger routings; We found that PDC is close to optimality (PMIX) to route the passengers When passengers are disrupted at the hub (flight cancellation or missed connection), PDC provides the optimal recovery most of the time because only one route typically goes from the hub to destination airport (hub and spoke topology); Only when passengers are disrupted at the origin spoke (first flight canceled), does PDC might provide sub-optimal solution origin destination Conclusion and future research Propose new airline operations recovery models that reduce passenger disruptions and: GBE Does not disrupt additional crew duties GBE Recover aircraft plan GBE Maintain overhead costs GBE Found 10% to 20% reduction in passenger disruptions for bad days of operations, using a sophisticated simulation environment GBE Run fast and meet real time AOCC needs Airline long term profitability: higher service reliability improves customer retention and long term revenues Future research: GBE Estimate the impact of different disrupted passenger’s priority strategies (e.g. Passenger routing: recovery priority given to business passengers over leisure passengers; Optimization: minimize the revenue of disrupted passengers) on overall passenger population