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
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
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
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)
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
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
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
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
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
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
11
Definitions of Robustness
? Minimize cost
? Minimize aircraft/passenger/crew delays and
disruptions
? Easy to recover (aircraft,crew,passengers)
? Isolate disruptions and reduce the downstream
impact
12
Robust Airline Schedule Planning
This Thesis Kang & Clarke
Rosenberger,
et al,(2001)
This Thesis Ageeva &
Clarke(2000)
Kang & Clarke
This thesis
Yen & Birge,
Schaefer,et al,
(2001)
Chebalov &
Klabjan
Min
Cost
Ease of
recovery
Min delays/
disruptions
Isolation of
disruptions
Schedule Design
Fleet Assignment
Maintenance Routing
Crew Scheduling
13
Where Should We Start?
? Difficult to balance cost that airlines are willing to pay
for robustness versus cost of operation
? Looking for robust solution without significant added
costs
? Aircraft maintenance routing problem,The financial impact is
relatively small ? It is more a feasibility problem
? How to route aircraft has impacts on flight delays and
cancellations,passengers,crews
? Question:
? What robustness can be achieved for the maintenance routing
problem?
14
Outline
? Background,Motivation and Our Contributions
? Overview of Robust Airline Schedule Planning
? Robust Aircraft Maintenance Routing – reduce delay
propagation
? Delay Propagation
? Modeling Idea
? String based formulation
? Solution approach
? Proof-of-concept results
? Flight Schedule Retiming – reduce passenger missed
connections
? Summary and Future Research Directions
15
Delay Propagation
? Arrival delay may cause departure delay for the next
flight that is using the same aircraft if there is not
enough slack between these two flights
? Delay propagation may cause schedule,passenger
and crew disruptions for downstream flights
(especially at hubs)
f1
MTT f2
f1’
f2’
16
Propagated Delay vs,Independent Delay
? Flight delay may be divided into two categories:
? Propagated delay
? Caused by inbound aircraft delay – function of routing
? 20-30% of total delay (Continental Airlines)
? Independent delay
? Caused by other factors – not a function of routing
17
Definitions
i
j
Slack Min Turn Time
PDT
PAT
ADT
AAT
PD IAD
TAD
j’
i’ i’’ PD IDD
TDD
ijjj
ijjj
ijiij
ijij
ijij
PDT A DI A D
PDT D DI D D
S l a ckT A DPD
M T TP T TS l a ck
PATP D TP T T
??
??
??
??
??
)0,m ax (
Planned Turn Time
18
Modeling Idea
? Delays propagate along aircraft routes
? Only limited slack can be added
? Appropriately located slack can prevent delay
propagation
? Routing aircraft intelligently ?better allocated slack
? Essentially add slack where advantageous,reducing
slack where less needed
19
Illustration of the Idea
f1
MTT
f2
f3
f1’
f4
MTT
Original routing
f3’
New routing
f1
MTT
f2
f3
f1’
f4
MTT
20
Modeling Issues
? Difficult to use leg-based models to track the delay
propagation
? One variable (string) for each aircraft route between
two maintenances (Barnhart,et al,1998)
? A string,a sequence of connected flights that begins and ends at
maintenance stations
? Delay propagation for each route can be determined
? Need to determine delays for each feasible route
? Most of the feasible routes haven’t been realized yet
? PD and TAD are a function of routing
? PD and TAD for these routes can’t be found in the historical data
? IAD is not a function of routing and can be calculated by tracking
the route of each individual aircraft in the historical data
21
Generating Flight Delays
for Any Feasible Route
? Step1,Determine propagated delays from historical
data,
? PDij = max (TADi – slackij,0)
? Step 2,Determine Independent Arrival Delays (IAD)
from historical data:
? IADj= TADj – PDij
? Step 3,Determine TAD and PD for feasible routes:
? For the first flight on each string,New_TAD = IAD
? New_PDij =max (New_TADi – slackij,0)
? New_TADj= IADj+ New_PDij
22
String Based Formulation
Ssx
Ggy
Nypxr
Fiyyx
Fiyyx
Fixa
ts
xpdE
s
g
Gg
gg
Ss
ss
aiai
Ss
s
didi
Ss
s
s
Ss
is
s
s
sji
s
ij
i
i
???
???
??
??????
?????
???
??
?
?
?
? ?
??
??
?
??
?
?
?
?
?
},1,0{
,0
,0
,0
,1
:.
))((m i n
,,
,,
),(
23
? ?? ?? ? ??? ????? s sji sijss sji sijss sji sijs pdExpdExpdxE )][(m i n][m i n)]([m i n ),(),(),(
Objective Function Coefficient
? Random variables (PD) can be replaced by their mean
? Distribution of Total Arrival Delay
? Possible distributions analyzed,Normal,Exponential,Gamma,
Weibull,Lognormal,etc,
? Our statistical analysis shows that lognormal distribution is the
best fit
? A closed form of expected value function can be
obtained
)))()/l n ((1()( 221 ???? mempdE ?????
24
Solution Approach
? This formulation is a deterministic mixed-integer
program with a huge number of 0-1 variables
? Branch-and-price
? Branch-and-Bound with a linear programming relaxation solved at
each node of the branch-and-bound tree using column generation
? IP solution
? A special branching strategy,branching on follow-ons (Ryan and
Foster 1981,Barnhart et al,1998)
25
Computational Results
? Test Networks
? Data divided into two sets,
? First data set (Jul 2000) used to build model and generate routes
? Second data set (Aug 2000) used to test these new routes
26
Results - Delays
? July 2000 data
? August 2000 data
27
Results - Delay Distribution
? Total delays for existing and new routings
28
Results - Passenger Disruptions
? Disruptions calculated at the flight level
? If a flight was cancelled,all passengers on that flight is disrupted
? If actual departure time of flight B – actual arrival time of flight A <
minimum connecting time ? all passengers connecting from A to
B are disrupted
29
Outline
? Background,Motivation and Our Contributions
? Overview of Robust Airline Schedule Planning
? Robust Aircraft Maintenance Routing
? Flight Schedule Retiming – reduce passenger missed
connections
? Passenger delays and disruptions
? Modeling Idea
? Formulations and their properties
? Solution approach
? Proof-of-concept results
? Summary and Future Research Directions
30
Passenger Delays and Disruptions
? Flight delay and passenger delay (Bratu and Barnhart,
2002)
? Passenger delay caused by disruptions is the most
critical part
? Minimize number of disrupted passengers
?A good proxy for passenger delays
31
Definitions Related to Passenger
Disruption
Slack MCT
PCT
PDTAATPAT ADT
ACT
If ACT – MCT < 0,passengers are disrupted
32
Minimize Passenger Missed Connections
? If the slack is,eaten” by flight delay,passengers are
disrupted
? Adding more slack can be good for connecting
passengers,but can result in reduced productivity
? Appropriately located slack can prevent passenger
disruptions
? Moving flight departure times in a small time window
can lead to better allocated slack
33
Illustration of the Idea
Airport A
Airport B
Airport C
Airport D
2f
3f
1f
Suppose 100 passengers in flight f2 will connect to f3
?2f
P (misconnect)= 0.3,
E(disrupted pax) = 30
P(misconnect)=0.2,
E(disrupted pax) =20
?Expected disrupted passengers reduced,10
34
Where to Apply
? Whether a passenger will be disrupted
depends on flight delays,a function of
fleeting and routing
? Before solving maintenance routing
? Impact of the propagation of flight delays won’t
be considered
? New fleeting and routing solution may cause
delay propagate in a different way ? may
eventually change the number of disrupted
passengers
? After solving fleeting and routing
problem
? Delay propagation has been considered
? Need to maintain the current fleeting and routing
solution
Schedule
Design
Crew
Scheduling
Fleet
Assignment
Maintenance
Routing
35
Connection-Based Formulation
? Objective
? minimize the expected total number of passengers missing connection
? Constraints:
? For each flight,exactly one copy will be selected.
? For each connection,exactly one copy will be selected and this
selected copy must connect the selected flight-leg copies.
? The current fleeting and routing solution cannot be altered.
1,if 2,if 3,if
1,jf 2,jf 3,jf
1,1,jix
3,2,jix
36
Connection-Based Formulation
? Theorem 1:
? The second set of constraints
are redundant and can be
relaxed
? Theorem 2:
? The integrality of the connection
variables can be relaxed? ?
? ? nif
miCjnix
jCimjfx
iCjnifx
jix
if
ts
DPxEM i n
ni
ji
mj
n
ji
ni
m
ji
m n
ji
n
ni
mjni
jiji
mn
mn
mn
mn
mnmn
,;1,0;),(,,;1,0
);(,,,
);(,,,;,,1;,1
..
,
,
,,
,,
,
,
,,,
,,
??
???
???
???
??
??
?
?
?
?
?
?
?
?
?
?
?
?
? ?
?
?
37
Alternative Connection-based
Formulations
? Formulation II
? ?
? ? nif
miCjnix
miCjniffx
jix
if
ts
DPxEM i n
ni
ji
mjniji
m n
ji
n
ni
mjni
jiji
mn
mn
mn
mnmn
,;1,0;),(,,;1,0;),(,,,1;,,1;,1
..
,
,
,,,
,
,
,,,
,,
??
???
?????
??
??
?
?
?
?
?
?
?
?
?
? ?
?
?
? Formulation III
? ?
? ?,),(,,,1,0;,,1,0;,,)(;,,)(;,,1;,1
..
,
,
,
)(
,
,
)(
,
,
,
,,,
,,
miCjnix
nif
mjfjCx
nifiCx
jix
if
ts
DPxEM i n
mn
mn
mn
mn
mnmn
ji
ni
mj
jCi n
ji
ni
iCj m
ji
n m
ji
n
ni
mjni
jiji
?
?
?
?
?
???
??
??
??
??
??
?
?
?
?
?
?
?
? ?
? ?
? ?
?
?
?
?
38
Model Properties
? Theorems on constraints:
? The second set of constraints are redundant and can be relaxed
in formulations two and three
? The integrality constraints of the connection variables can be
relaxed in formulations two and three
? Theorem on LP relaxations
? The LP relaxation of formulation one is at least as strong as those
of formulations two and three
39
Problem Size
? A network from a major US airline used by Barnhart
et al,(2001)
? 2,044 flights and 76,641 itineraries,
? Suppose 7 copies will be generated for each flight (if 5 minutes
interval is used,7 copies correspond to a 30 minute time window)
? Assume on average every flight connects to 12 flights with
connecting passengers.
Number of
Variable
Number of Integer
Variables
Number of
Rows
F1 1,216,180 14,308 345,436
F2 1,216,180 14,308 30,660
F3 1,216,180 14,308 1,203,916
40
How to Maintain Current Fleeting and
Routing Solution
? For an aircraft maintenance route,the planned turn
time >= minimum turn time
? Force,if the time between the arrival of flight
copy and the departure of flight copy is less
than the minimum turn time,
? The upper bounds will be set to zero for these x
variables
0,,?mjnix
nif,mjf,
1,if 2,if 3,if
1,jf 2,jf 3,jf
1,1,jix
3,2,jix
41
Solution Approach
? Random variables can be replaced by their mean
? Deterministic Problem
? Distribution of
? Branch-and-Price
? ? ? ???? ?????????? ?
mjni jijimjni jijimjni jiji mnmnmnmnmnmn
DPExDPxEDPxE
,,,,,,,,,,,,,,,
mn jiDP,
p
pcDP ji
ji mn ???
??
1 pr obw it h
pr obw it h
,0
,,
,
? ?M C TA A TA DTp nm ij ?? p r o b -- gc o ns i d e r i nby d e t e r m i n e d bec a n P r o b i l i t y
42
Computational Results
? Network
? We use the same four networks,but add all flights together and
form one network with total 278 flights.
? Data divided into two sets,
? First data set (Jul 2000) used to build model and generate
schedule
? Second data set (Aug 2000) used to test the new schedule
? Strength of the formulations
43
Computational Results
? Assume 30 minute minimum connecting time
? For July 2000 data
? For August 2000 data
44
Computational Results
? August 2000 data
? Assume 25 minute minimum connecting time
? Assume 20 minute minimum connecting time
45
Computational Results
? How many copies to generate
46
Outline
? Background,Motivation and Our Contributions
? Overview of Robust Airline Schedule Planning
? Robust Maintenance Routing
? Flight Schedule Retiming
? Summary and Future Research Directions
? Summary of Contributions
? Future Research Directions
47
Summary of 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 connections,and analyze the model
properties
? Proof-of-concept results show that these approaches
are promising
? Develop integrated models for more robustness
48
Future Research Directions
? Integrated Models
? Integrated robust aircraft maintenance routing with fleet
assignment
? Robust aircraft maintenance routing with time window
? Integrated flight schedule re-timing with FAMTW
? Other approaches
? Fleet assignment with minimal expected cost
? Fleet assignment under demand uncertainty
? Aircraft routes with swap opportunities
? Aircraft routes with short cycles
49
Computational Results
? July 2000 data
? Assume 25 minute minimum connecting time
? Assume 20 minute minimum connecting time
50
Impact on Passengers
? Disruptions calculated at the flight level
? If a flight was cancelled,all passengers on that flight is disrupted
? If actual departure time of flight B – actual arrival time of flight A < minimum
connecting time ? all passengers connecting from A to B are disrupted
? Number of disrupted passengers only calculated for connections
between flights that both have ASQP records
? ASQP has records only for domestic flights flown by jet airplanes and major
airlines
? Actual departure and arrival times for flights without ASQP records are
unknown ? Assume no disruptions for these flights
? Passengers only counted as disrupted once
? If passenger is disrupted on any flight leg of itinerary,passenger not
counted as disrupted on the following flight legs
51
Passenger Delays and Disruptions
? Passenger delays
? the difference between scheduled and actual arrival time at
passengers’ destination
? Passengers are disrupted if their planned itineraries
are infeasible
? Flight delay and passenger delay (Bratu and Barnhart,
2002)
52
Passenger Disruption
? Disrupted passengers
? Significant numbers,4% ?20-30 million in U.S.
? Experience very long delay
? Contribute to more than half of the total passenger delay
? Cause huge revenue loss
? Destroy airlines’ image
? Reduce disrupted passengers
? Passenger delay caused by disruption is the most critical part
? Hard to determine the delays for each disrupted passengers
?Minimize number of disrupted passengers
53
LP Solution
? Algorithm for LP relaxation
? Step 0,Create initial feasible solution
? Step 1,Solve the restricted master problem (RMP)
– Find optimal solution to RMP with a subset of all strings
? Step 2,Solve the pricing problem
– Generate strings with negative reduced cost
– If no string is generated,stop,the LP is solved
? Step 3,Construct a new restricted master problem
– Add the strings generated
– Go to step 1
54
Notation
? S,set of feasible strings
? F,set of flights
? G,set of ground variables
?,set of strings ending (starting) with flight i
?, binary decision variable for each feasible string s
? y,integer variable to count number of aircraft on the ground at maintenance
stations
?, number of aircraft on the ground before (after) flight i departs at
the maintenance station from which flight i departs
?, number of aircraft on the ground before (after) flight i arrives at
the maintenance station from which flight i arrives
sx
)( ?? ii SS
)(,,?? didi yy
)(,,?? aiai yy
55
Notation (Cont.)
?, propagated delay from flight i to flight j if flight i and
flight j are in string s
?, indicator variable,equals 1 if flight i is in string s,and
equals 0 otherwise
?, number of times string s crosses the count time,a single
point time at which to count aircraft
?, number of times ground arc g crosses the count time
? N, number of planes available.
sijpd
isa
sr
gp
56
Data
? Airline Service Quality Performance (ASQP) provides
good source of delay information
? ASQP provides flight operation information:
? For all domestic flights served by jet aircraft by major airlines in
U.S.
? Planned departure time and arrival time,actual departure time
and arrival time (including wheels-off and wheels-on time,taxi-out
and taxi-in time,airborne time)
? Aircraft tail number for each flight
? Cancelled flights (reasons for cancellation,and aircraft tail
number are not available)
57
Effect of Cancellations
? For cancelled flights in the historical data
? we don’t know which aircraft supposed to fly them
? We don’t have the delay information
? We assume the propagated delays for these flights are zero
? Lower cancellation rates
? Less passengers disrupted because of cancellation
? More passengers disrupted because of flight delays
? 7 days in Aug 2000 with very few cancellations
(cancellation rate = 0.19%)
? For Aug 2000,65% of disrupted passengers are disrupted
because of flight delays
? For 7 selected days in Aug 2000,92% of disrupted passengers
are disrupted because of flight delays
58
Results - Low Cancellation Days
? Passenger disruptions for 7 selected days in Aug
2000 with very few cancellations
? Reduction in number of disrupted passengers per
non-cancelled flights is same as that for entire month
N e t w o r k D - p a x T o t a l N u m D - p a x
R e d u c e d D - p a x R e d u c e d ( % )
N1 8 51 1 3,6 %
N2 45 209 1 7,7 %
N3 6 197 3,0 %
N4 100 455 1 8,0 %
T o t a l 159 912 1 4,8 %
59
Extensions
? Combine with scheduling
? More slacks may be added ?further reduce delay propagation
? Combine with fleet assignment
? Need to determine cost for propagated delay
? More feasible strings ? better solution
? Minimum turn time is a function of fleet type
? Integrate with fleet assignment and schedule
generation
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
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
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
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)
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
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
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
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
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
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
11
Definitions of Robustness
? Minimize cost
? Minimize aircraft/passenger/crew delays and
disruptions
? Easy to recover (aircraft,crew,passengers)
? Isolate disruptions and reduce the downstream
impact
12
Robust Airline Schedule Planning
This Thesis Kang & Clarke
Rosenberger,
et al,(2001)
This Thesis Ageeva &
Clarke(2000)
Kang & Clarke
This thesis
Yen & Birge,
Schaefer,et al,
(2001)
Chebalov &
Klabjan
Min
Cost
Ease of
recovery
Min delays/
disruptions
Isolation of
disruptions
Schedule Design
Fleet Assignment
Maintenance Routing
Crew Scheduling
13
Where Should We Start?
? Difficult to balance cost that airlines are willing to pay
for robustness versus cost of operation
? Looking for robust solution without significant added
costs
? Aircraft maintenance routing problem,The financial impact is
relatively small ? It is more a feasibility problem
? How to route aircraft has impacts on flight delays and
cancellations,passengers,crews
? Question:
? What robustness can be achieved for the maintenance routing
problem?
14
Outline
? Background,Motivation and Our Contributions
? Overview of Robust Airline Schedule Planning
? Robust Aircraft Maintenance Routing – reduce delay
propagation
? Delay Propagation
? Modeling Idea
? String based formulation
? Solution approach
? Proof-of-concept results
? Flight Schedule Retiming – reduce passenger missed
connections
? Summary and Future Research Directions
15
Delay Propagation
? Arrival delay may cause departure delay for the next
flight that is using the same aircraft if there is not
enough slack between these two flights
? Delay propagation may cause schedule,passenger
and crew disruptions for downstream flights
(especially at hubs)
f1
MTT f2
f1’
f2’
16
Propagated Delay vs,Independent Delay
? Flight delay may be divided into two categories:
? Propagated delay
? Caused by inbound aircraft delay – function of routing
? 20-30% of total delay (Continental Airlines)
? Independent delay
? Caused by other factors – not a function of routing
17
Definitions
i
j
Slack Min Turn Time
PDT
PAT
ADT
AAT
PD IAD
TAD
j’
i’ i’’ PD IDD
TDD
ijjj
ijjj
ijiij
ijij
ijij
PDT A DI A D
PDT D DI D D
S l a ckT A DPD
M T TP T TS l a ck
PATP D TP T T
??
??
??
??
??
)0,m ax (
Planned Turn Time
18
Modeling Idea
? Delays propagate along aircraft routes
? Only limited slack can be added
? Appropriately located slack can prevent delay
propagation
? Routing aircraft intelligently ?better allocated slack
? Essentially add slack where advantageous,reducing
slack where less needed
19
Illustration of the Idea
f1
MTT
f2
f3
f1’
f4
MTT
Original routing
f3’
New routing
f1
MTT
f2
f3
f1’
f4
MTT
20
Modeling Issues
? Difficult to use leg-based models to track the delay
propagation
? One variable (string) for each aircraft route between
two maintenances (Barnhart,et al,1998)
? A string,a sequence of connected flights that begins and ends at
maintenance stations
? Delay propagation for each route can be determined
? Need to determine delays for each feasible route
? Most of the feasible routes haven’t been realized yet
? PD and TAD are a function of routing
? PD and TAD for these routes can’t be found in the historical data
? IAD is not a function of routing and can be calculated by tracking
the route of each individual aircraft in the historical data
21
Generating Flight Delays
for Any Feasible Route
? Step1,Determine propagated delays from historical
data,
? PDij = max (TADi – slackij,0)
? Step 2,Determine Independent Arrival Delays (IAD)
from historical data:
? IADj= TADj – PDij
? Step 3,Determine TAD and PD for feasible routes:
? For the first flight on each string,New_TAD = IAD
? New_PDij =max (New_TADi – slackij,0)
? New_TADj= IADj+ New_PDij
22
String Based Formulation
Ssx
Ggy
Nypxr
Fiyyx
Fiyyx
Fixa
ts
xpdE
s
g
Gg
gg
Ss
ss
aiai
Ss
s
didi
Ss
s
s
Ss
is
s
s
sji
s
ij
i
i
???
???
??
??????
?????
???
??
?
?
?
? ?
??
??
?
??
?
?
?
?
?
},1,0{
,0
,0
,0
,1
:.
))((m i n
,,
,,
),(
23
? ?? ?? ? ??? ????? s sji sijss sji sijss sji sijs pdExpdExpdxE )][(m i n][m i n)]([m i n ),(),(),(
Objective Function Coefficient
? Random variables (PD) can be replaced by their mean
? Distribution of Total Arrival Delay
? Possible distributions analyzed,Normal,Exponential,Gamma,
Weibull,Lognormal,etc,
? Our statistical analysis shows that lognormal distribution is the
best fit
? A closed form of expected value function can be
obtained
)))()/l n ((1()( 221 ???? mempdE ?????
24
Solution Approach
? This formulation is a deterministic mixed-integer
program with a huge number of 0-1 variables
? Branch-and-price
? Branch-and-Bound with a linear programming relaxation solved at
each node of the branch-and-bound tree using column generation
? IP solution
? A special branching strategy,branching on follow-ons (Ryan and
Foster 1981,Barnhart et al,1998)
25
Computational Results
? Test Networks
? Data divided into two sets,
? First data set (Jul 2000) used to build model and generate routes
? Second data set (Aug 2000) used to test these new routes
26
Results - Delays
? July 2000 data
? August 2000 data
27
Results - Delay Distribution
? Total delays for existing and new routings
28
Results - Passenger Disruptions
? Disruptions calculated at the flight level
? If a flight was cancelled,all passengers on that flight is disrupted
? If actual departure time of flight B – actual arrival time of flight A <
minimum connecting time ? all passengers connecting from A to
B are disrupted
29
Outline
? Background,Motivation and Our Contributions
? Overview of Robust Airline Schedule Planning
? Robust Aircraft Maintenance Routing
? Flight Schedule Retiming – reduce passenger missed
connections
? Passenger delays and disruptions
? Modeling Idea
? Formulations and their properties
? Solution approach
? Proof-of-concept results
? Summary and Future Research Directions
30
Passenger Delays and Disruptions
? Flight delay and passenger delay (Bratu and Barnhart,
2002)
? Passenger delay caused by disruptions is the most
critical part
? Minimize number of disrupted passengers
?A good proxy for passenger delays
31
Definitions Related to Passenger
Disruption
Slack MCT
PCT
PDTAATPAT ADT
ACT
If ACT – MCT < 0,passengers are disrupted
32
Minimize Passenger Missed Connections
? If the slack is,eaten” by flight delay,passengers are
disrupted
? Adding more slack can be good for connecting
passengers,but can result in reduced productivity
? Appropriately located slack can prevent passenger
disruptions
? Moving flight departure times in a small time window
can lead to better allocated slack
33
Illustration of the Idea
Airport A
Airport B
Airport C
Airport D
2f
3f
1f
Suppose 100 passengers in flight f2 will connect to f3
?2f
P (misconnect)= 0.3,
E(disrupted pax) = 30
P(misconnect)=0.2,
E(disrupted pax) =20
?Expected disrupted passengers reduced,10
34
Where to Apply
? Whether a passenger will be disrupted
depends on flight delays,a function of
fleeting and routing
? Before solving maintenance routing
? Impact of the propagation of flight delays won’t
be considered
? New fleeting and routing solution may cause
delay propagate in a different way ? may
eventually change the number of disrupted
passengers
? After solving fleeting and routing
problem
? Delay propagation has been considered
? Need to maintain the current fleeting and routing
solution
Schedule
Design
Crew
Scheduling
Fleet
Assignment
Maintenance
Routing
35
Connection-Based Formulation
? Objective
? minimize the expected total number of passengers missing connection
? Constraints:
? For each flight,exactly one copy will be selected.
? For each connection,exactly one copy will be selected and this
selected copy must connect the selected flight-leg copies.
? The current fleeting and routing solution cannot be altered.
1,if 2,if 3,if
1,jf 2,jf 3,jf
1,1,jix
3,2,jix
36
Connection-Based Formulation
? Theorem 1:
? The second set of constraints
are redundant and can be
relaxed
? Theorem 2:
? The integrality of the connection
variables can be relaxed? ?
? ? nif
miCjnix
jCimjfx
iCjnifx
jix
if
ts
DPxEM i n
ni
ji
mj
n
ji
ni
m
ji
m n
ji
n
ni
mjni
jiji
mn
mn
mn
mn
mnmn
,;1,0;),(,,;1,0
);(,,,
);(,,,;,,1;,1
..
,
,
,,
,,
,
,
,,,
,,
??
???
???
???
??
??
?
?
?
?
?
?
?
?
?
?
?
?
? ?
?
?
37
Alternative Connection-based
Formulations
? Formulation II
? ?
? ? nif
miCjnix
miCjniffx
jix
if
ts
DPxEM i n
ni
ji
mjniji
m n
ji
n
ni
mjni
jiji
mn
mn
mn
mnmn
,;1,0;),(,,;1,0;),(,,,1;,,1;,1
..
,
,
,,,
,
,
,,,
,,
??
???
?????
??
??
?
?
?
?
?
?
?
?
?
? ?
?
?
? Formulation III
? ?
? ?,),(,,,1,0;,,1,0;,,)(;,,)(;,,1;,1
..
,
,
,
)(
,
,
)(
,
,
,
,,,
,,
miCjnix
nif
mjfjCx
nifiCx
jix
if
ts
DPxEM i n
mn
mn
mn
mn
mnmn
ji
ni
mj
jCi n
ji
ni
iCj m
ji
n m
ji
n
ni
mjni
jiji
?
?
?
?
?
???
??
??
??
??
??
?
?
?
?
?
?
?
? ?
? ?
? ?
?
?
?
?
38
Model Properties
? Theorems on constraints:
? The second set of constraints are redundant and can be relaxed
in formulations two and three
? The integrality constraints of the connection variables can be
relaxed in formulations two and three
? Theorem on LP relaxations
? The LP relaxation of formulation one is at least as strong as those
of formulations two and three
39
Problem Size
? A network from a major US airline used by Barnhart
et al,(2001)
? 2,044 flights and 76,641 itineraries,
? Suppose 7 copies will be generated for each flight (if 5 minutes
interval is used,7 copies correspond to a 30 minute time window)
? Assume on average every flight connects to 12 flights with
connecting passengers.
Number of
Variable
Number of Integer
Variables
Number of
Rows
F1 1,216,180 14,308 345,436
F2 1,216,180 14,308 30,660
F3 1,216,180 14,308 1,203,916
40
How to Maintain Current Fleeting and
Routing Solution
? For an aircraft maintenance route,the planned turn
time >= minimum turn time
? Force,if the time between the arrival of flight
copy and the departure of flight copy is less
than the minimum turn time,
? The upper bounds will be set to zero for these x
variables
0,,?mjnix
nif,mjf,
1,if 2,if 3,if
1,jf 2,jf 3,jf
1,1,jix
3,2,jix
41
Solution Approach
? Random variables can be replaced by their mean
? Deterministic Problem
? Distribution of
? Branch-and-Price
? ? ? ???? ?????????? ?
mjni jijimjni jijimjni jiji mnmnmnmnmnmn
DPExDPxEDPxE
,,,,,,,,,,,,,,,
mn jiDP,
p
pcDP ji
ji mn ???
??
1 pr obw it h
pr obw it h
,0
,,
,
? ?M C TA A TA DTp nm ij ?? p r o b -- gc o ns i d e r i nby d e t e r m i n e d bec a n P r o b i l i t y
42
Computational Results
? Network
? We use the same four networks,but add all flights together and
form one network with total 278 flights.
? Data divided into two sets,
? First data set (Jul 2000) used to build model and generate
schedule
? Second data set (Aug 2000) used to test the new schedule
? Strength of the formulations
43
Computational Results
? Assume 30 minute minimum connecting time
? For July 2000 data
? For August 2000 data
44
Computational Results
? August 2000 data
? Assume 25 minute minimum connecting time
? Assume 20 minute minimum connecting time
45
Computational Results
? How many copies to generate
46
Outline
? Background,Motivation and Our Contributions
? Overview of Robust Airline Schedule Planning
? Robust Maintenance Routing
? Flight Schedule Retiming
? Summary and Future Research Directions
? Summary of Contributions
? Future Research Directions
47
Summary of 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 connections,and analyze the model
properties
? Proof-of-concept results show that these approaches
are promising
? Develop integrated models for more robustness
48
Future Research Directions
? Integrated Models
? Integrated robust aircraft maintenance routing with fleet
assignment
? Robust aircraft maintenance routing with time window
? Integrated flight schedule re-timing with FAMTW
? Other approaches
? Fleet assignment with minimal expected cost
? Fleet assignment under demand uncertainty
? Aircraft routes with swap opportunities
? Aircraft routes with short cycles
49
Computational Results
? July 2000 data
? Assume 25 minute minimum connecting time
? Assume 20 minute minimum connecting time
50
Impact on Passengers
? Disruptions calculated at the flight level
? If a flight was cancelled,all passengers on that flight is disrupted
? If actual departure time of flight B – actual arrival time of flight A < minimum
connecting time ? all passengers connecting from A to B are disrupted
? Number of disrupted passengers only calculated for connections
between flights that both have ASQP records
? ASQP has records only for domestic flights flown by jet airplanes and major
airlines
? Actual departure and arrival times for flights without ASQP records are
unknown ? Assume no disruptions for these flights
? Passengers only counted as disrupted once
? If passenger is disrupted on any flight leg of itinerary,passenger not
counted as disrupted on the following flight legs
51
Passenger Delays and Disruptions
? Passenger delays
? the difference between scheduled and actual arrival time at
passengers’ destination
? Passengers are disrupted if their planned itineraries
are infeasible
? Flight delay and passenger delay (Bratu and Barnhart,
2002)
52
Passenger Disruption
? Disrupted passengers
? Significant numbers,4% ?20-30 million in U.S.
? Experience very long delay
? Contribute to more than half of the total passenger delay
? Cause huge revenue loss
? Destroy airlines’ image
? Reduce disrupted passengers
? Passenger delay caused by disruption is the most critical part
? Hard to determine the delays for each disrupted passengers
?Minimize number of disrupted passengers
53
LP Solution
? Algorithm for LP relaxation
? Step 0,Create initial feasible solution
? Step 1,Solve the restricted master problem (RMP)
– Find optimal solution to RMP with a subset of all strings
? Step 2,Solve the pricing problem
– Generate strings with negative reduced cost
– If no string is generated,stop,the LP is solved
? Step 3,Construct a new restricted master problem
– Add the strings generated
– Go to step 1
54
Notation
? S,set of feasible strings
? F,set of flights
? G,set of ground variables
?,set of strings ending (starting) with flight i
?, binary decision variable for each feasible string s
? y,integer variable to count number of aircraft on the ground at maintenance
stations
?, number of aircraft on the ground before (after) flight i departs at
the maintenance station from which flight i departs
?, number of aircraft on the ground before (after) flight i arrives at
the maintenance station from which flight i arrives
sx
)( ?? ii SS
)(,,?? didi yy
)(,,?? aiai yy
55
Notation (Cont.)
?, propagated delay from flight i to flight j if flight i and
flight j are in string s
?, indicator variable,equals 1 if flight i is in string s,and
equals 0 otherwise
?, number of times string s crosses the count time,a single
point time at which to count aircraft
?, number of times ground arc g crosses the count time
? N, number of planes available.
sijpd
isa
sr
gp
56
Data
? Airline Service Quality Performance (ASQP) provides
good source of delay information
? ASQP provides flight operation information:
? For all domestic flights served by jet aircraft by major airlines in
U.S.
? Planned departure time and arrival time,actual departure time
and arrival time (including wheels-off and wheels-on time,taxi-out
and taxi-in time,airborne time)
? Aircraft tail number for each flight
? Cancelled flights (reasons for cancellation,and aircraft tail
number are not available)
57
Effect of Cancellations
? For cancelled flights in the historical data
? we don’t know which aircraft supposed to fly them
? We don’t have the delay information
? We assume the propagated delays for these flights are zero
? Lower cancellation rates
? Less passengers disrupted because of cancellation
? More passengers disrupted because of flight delays
? 7 days in Aug 2000 with very few cancellations
(cancellation rate = 0.19%)
? For Aug 2000,65% of disrupted passengers are disrupted
because of flight delays
? For 7 selected days in Aug 2000,92% of disrupted passengers
are disrupted because of flight delays
58
Results - Low Cancellation Days
? Passenger disruptions for 7 selected days in Aug
2000 with very few cancellations
? Reduction in number of disrupted passengers per
non-cancelled flights is same as that for entire month
N e t w o r k D - p a x T o t a l N u m D - p a x
R e d u c e d D - p a x R e d u c e d ( % )
N1 8 51 1 3,6 %
N2 45 209 1 7,7 %
N3 6 197 3,0 %
N4 100 455 1 8,0 %
T o t a l 159 912 1 4,8 %
59
Extensions
? Combine with scheduling
? More slacks may be added ?further reduce delay propagation
? Combine with fleet assignment
? Need to determine cost for propagated delay
? More feasible strings ? better solution
? Minimum turn time is a function of fleet type
? Integrate with fleet assignment and schedule
generation
