Airline Operations Lecture #3 1206J Apri29,2003
Airline Operations Lecture #3 1.206J April 29, 2003
Summary Lecture #2 Achieving good passenger service reliability at an acceptable operating costs Disrupted passengers suffer long delays on average( 320 minutes)versus non disrupted passengers(14 minutes) Connecting itineraries have a much higher risk of being disrupted than local itineraries(2.7x) Late disruptions are often difficult to recover the same day, much higher flight delay and cancellations at the end of the day Delays accumulate along the day resulting in relatively high percentage of overnight passengers among disrupted(20%), but still small percentage (0.7 of passengers)
Summary Lecture #2 • Achieving good passenger service reliability at an acceptable operating costs • Disrupted passengers suffer long delays on average (320 minutes) versus non disrupted passengers (14 minutes) • Connecting itineraries have a much higher risk of being disrupted than local itineraries (2.7x) • Late disruptions are often difficult to recover the same day, much higher flight delay and cancellations at the end of the day • Delays accumulate along the day, resulting in relatively high percentage of overnight passengers among disrupted (20%), but still small percentage (0.7% of passengers)
Average flight delay per hour, August 2000 00元0>0 050 s10 三0> 678 101112131415161718192021222324 Planned Arriv al Time(hours)
3ODQQHG $UULYDO 7LPH KRXUV 3RVLWLYH IOLJKW DUULYDO GHOD\ PLQXWHV Average flight delay per hour, August 2000
Our approach Wisely postpone artificially departures to maintain bank integrity and prevent passengers from missing connections Wisely canceled flights if necessary to prevent delays to propagate and the negative effects on passengers We want our solutions to be feasible for aircraft (maintenance)and crews(schedule) Guarantee solution feasibility: Artificially postponing flight departures does not disrupt more crews Maintain flight sequence feasibility (duty) Does not include flight copies that violate crew regulation Maximum Duty Elapsed time Do we guarantee maintenance routing feasibility
Our approach • Wisely postpone artificially departures to maintain bank integrity and prevent passengers from missing connections • Wisely canceled flights if necessary to prevent delays to propagate and the negative effects on passengers • We want our solutions to be feasible for aircraft (maintenance) and crews (schedule) • Guarantee solution feasibility: ¾ Artificially postponing flight departures does not disrupt more crews: • Maintain flight sequence feasibility (duty) • Does not include flight copies that violate crew regulation (Maximum Duty Elapsed Time) • Do we guarantee maintenance routing feasibility?
Summary Lecture #2 Cont Minimize Sum of Disrupted Passengers(M1) Works well(20CPU) for day with severe flight schedule disruptions. Why? Because number of variables relatively small (O(F+ I)and number of constraints O(F+ D) And binary variables Downside: do not consider disrupted passenger and non disrupted passenger delays: May decide to postpone a flight by 30 minutes with 100 passenger on board to recover only 1 disrupted passenger who could have been recovered effectively Minimizing Sum of Passenger Delays M2) Problem becomes much bigger if all the recovery itineraries are included Hard to solve using B&B (M1/M2 )equivalent to FAM/ODF AM): capacity constraints tend to lead to fraction solutions of lp relaxation
Summary Lecture #2 (Cont.) • Minimize Sum of Disrupted Passengers (M1) ¾ Works well (20CPU) for day with severe flight schedule disruptions. Why? • Because number of variables relatively small (O(F + I) and number of constraints O(F + I)) • And binary variables ¾ Downside: do not consider disrupted passenger and non disrupted passenger delays: May decide to postpone a flight by 30 minutes with 100 passenger on board to recover only 1 disrupted passenger who could have been recovered effectively • Minimizing Sum of Passenger Delays (M2) ¾ Problem becomes much bigger if all the recovery itineraries are included ¾ Hard to solve using B&B ¾ (M1/M2) equivalent to (FAM/ODFAM): capacity constraints tend to lead to fraction solutions of LP relaxation
Minimizing sum of Disrupted Passengers Objective: Minimize sum of Mimc∑nxp disrupted passengers pe P Flight coverage constraints ∑x+Zf tETf Aircraft balance for each sub ∑x+y=∑x+ fleet type (f,t血n(j (f, tEOut(j Xf+yf=res(a, ft, . Initial and end of the day aircraft resource constraints Passenger cancellation constraints +∑x2 Missed connected passengers gEC(u)d(gka(f) constraints p∈0l:xra∈0y20 Only flight copy variables, x, have to be binary
p p p P t f f t Tf tt tt ff ff (f ,t) In(j) (f,t) Out(j) f f p f t u f gp g C(u) d(g) a(f ) t t p f,a f Minimize n st : x z 1 xy xy x y Res(a,ft, ) z x x1 [0;1]; x {0,1}; y 0 ∈ ∈ − + ∈ ∈ • • ∈ < ×ρ + = += + += • ρ ≥ + −ρ ≤ ρ ∈ ∈≥ ∑ ∑ ∑ ∑ ∑ ∑ ¾ Objective: Minimize sum of disrupted passengers ¾ Flight coverage constraints ¾ Aircraft balance for each sub fleet type ¾ Initial and end of the day aircraft resource constraints ¾ Passenger cancellation constraints ¾ Missed connected passengers constraints ¾ Only flight copy variables, x, have to be binary Minimizing Sum of Disrupted Passengers
Minimizing passenger delay Need to consider all potential copies of Min∑∑b recovery itineraries for each passenger Large scale problem: 500,000 integer x+z=1Vf∈F variables; 12 hours CPU using B&B deep te first search methodology ∑x+y=∑x2+y (, tEIn( (f, t EOut() ,xF+you ∑Σ8C×x q202x∈{0}yr20
Minimizing passenger delay • Need to consider all potential copies of recovery itineraries for each passenger • Large scale problem: 500,000 integer variables; 12 hours CPU using B&B deep first search methodology i i p p p Pi I p t f f t Tf tt tt ff ff (f ,t) In( j) (f ,t) Out( j) 0 0 f f i p p i I p ti t p ff fi p Pi I p it t pf f b q x z 1 fF xy xy xy j q n q Cx q 0;x {0,1};y 0 Min ∈ ∈ ∈ − + ∈ ∈ + • ∈ ∈ ∈ + = ∀∈ += + + = = δ ≤× ≥∈ ≥ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑
Summary Lecture #2 Cont Approximate models to minimize sum of passenger delay From Model #1, estimate delay if itinerary is disrupted From Model #2, limit the number of itinerary copy to include only good ones Objective function: minimizing estimated passenger dissatisfaction Fine grained down to Passenger Name Record Assign a cost(expected future revenue loss of delay d for PNr p) based on: Fare class Disruption history Loyalty( FFP) Same objective can be used in sorting passengers for recovery priority
Summary Lecture #2 (Cont.) Approximate models to minimize sum of passenger delay • From Model #1, estimate delay if itinerary is disrupted. • From Model #2, limit the number of itinerary copy to include only good ones. Objective function: minimizing estimated passenger dissatisfaction • Fine grained down to Passenger Name Record • Assign a cost (expected future revenue loss of delay d for PNR p) based on: Fare class Disruption history Loyalty (FFP) • Same objective can be used in sorting passengers for recovery priority
Lecture #3 Outline Airline schedule recovery framework Aircraft routing feasibility Disrupted passenger re-routing under seat uncertainty: Heuristics Optimal Optimal with bumping control
Lecture #3 Outline • Airline schedule recovery framework • Aircraft routing feasibility • Disrupted passenger re-routing under seat uncertainty: ¾ Heuristics ¾ Optimal ¾ Optimal with bumping control
Ainine system state Aircraft: position, maintenance, operational Crews: position, disruption stafUs, duty fime, flight fime, etc Passengers: position, destination, PAT, disruption status Crew operations recovery palings Operations forecasts Flight copy generation algorithm Flight departure times, X and flight cancellations Z Aircraft routing based on(X 2) 彐 Feasible route r? No Yes Prevent infeasible aircraft route swaps Modify flight departure solution Obtain feasible aircraft route r and associated optimal solution(X 2) Recovery priority policies Optimal disrupted passenger re-routing Considering seat availability uncertainty
$LUOLQH V\VWHP VWDWH $LUFUDIW SRVLWLRQ PDLQWHQDQFH RSHUDWLRQDO &UHZV SRVLWLRQ GLVUXSWLRQ VWDWXV GXW\ WLPH IOLJKW WLPH HWF 3DVVHQJHUV SRVLWLRQ GHVWLQDWLRQ 3$7 GLVUXSWLRQ VWDWXV )OLJKW FRS\ JHQHUDWLRQ DOJRULWKP 2SHUDWLRQV IRUHFDVWV )OLJKW GHSDUWXUH WLPHV ; DQG IOLJKW FDQFHOODWLRQV = RSWLPL]HU $LUFUDIW URXWLQJ EDVHG RQ ; = ∃ )HDVLEOH URXWH 5" <HV 1R 3UHYHQW LQIHDVLEOH DLUFUDIW URXWH VZDSV 0RGLI\ IOLJKW GHSDUWXUH VROXWLRQ 2EWDLQ IHDVLEOH DLUFUDIW URXWH 5· DQG DVVRFLDWHG RSWLPDO VROXWLRQ ;· =· 2SWLPDO GLVUXSWHG SDVVHQJHU UHURXWLQJ &RQVLGHULQJ VHDW DYDLODELOLW\ XQFHUWDLQW\ 5HFRYHU\ SULRULW\ SROLFLHV &UHZ RSHUDWLRQV UHFRYHU\ 5HSDLU SDLULQJV
