《航线进度计划》（英文版） lec13 aop3

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