Transcript slot allocation

Resource Rationing and
Exchange Methods in Air Traffic
Management
Michael Ball
R.H. Smith School of Business & Institute for Systems Research
University of Maryland
College Park, MD
joint work with Thomas Vossen
1
Motivation for Ground Delay Programs: airline
schedules “assume” good weather
SFO: scheduled arrivals:
VMC airport acceptance rate:
IMC airport acceptance rate:
Ground Delay Programs
delayed
departures
delayed departures
delayed arrivals/
no airborne holding
delayed departures
Collaborative Decision-Making
Traditional Traffic Flow Management:
• Flow managers alter routes/schedules of individual flights
to achieve system wide performance objectives
Collaborative Decision-Making (CDM)
• Airlines and airspace operators (FAA) share information
and collaborate in determining resource allocation; airlines
have more control over economic tradeoffs
CDM in GDP context:
• CDM-net: communications network that allows real-time
information exchange
• Allocation procedures that increase airline control and
encourage airline provision of up-to-date information
GDPs under CDM
Resource Allocation Process:
• FAA: initial “fair” slot allocation
[Ration-by-schedule]
• Airlines: flight-slot assignments/reassignments
[Cancellations and substitutions]
• FAA: periodic reallocation to maximize slot utilization
[Compression]
Note:
- reduced capacity is partitioned into sequence of arrival slots
- ground delays are derived from delays in arrival time
Issues
• What is an ideal (fair) allocation?
• How can an allocation be generated that is
very close to the ideal while taking into
account dynamic problem aspects?
• How can airlines exchange resources they
receive as part of their allocation?
Issues
• What is an ideal (fair) allocation?
• How can an allocation be generated that is
very close to the ideal while taking into
account dynamic problem aspects?
• How can airlines exchange resources they
receive as part of their allocation?
Determining fair shares
Sketch:
• Assume slots are divisible
– leads to probabilistic allocation schemes
• Approach: impose properties that schemes need to satisfy
– fairness properties
– structural properties (consistency, sequence-independence)
OAG
Schedule
AA654
US345
AA455
…
…
…
vs
Slots
Available
Allocation Principles
How to allocate limited set
of resources among
several competing
claimants???
First-come, firstserved: strict priority
system based on oag times
 RBS
1
Equal access: all
claimants have equal priority
% slots received by airline
= % flights scheduled in time
period
1
2
1
3
1
4
1
5
1
6
1
7
1
Comparison
• First-come/first-served – RBS:
– implicitly assumes there are enough slots to go around,
i.e. all flights will be flown
– lexicographically minimizes max delay
– implicitly treats flights as independent economic
entities
• Equal Access:
– implicitly assumes there are not enough slots to go
around – some flight/airlines will not receive all the
slots they need
– does not acknowledge that some flights cannot use
some slots
– strict interpretation leads to Shapley Value
Equal Access to Usable Slots:
Proportional Random Assignment (PRA)
UA33
US25
UA19
US31
US19
Flight
shares
Slot 1
Slot 2
Slot 3
Slot 4
Slot 5
UA33
1/2
1/8
1/8
1/8
1/8
UA19
1/2
1/8
1/8
1/8
1/8
US25
-
1/4
1/4
1/4
1/4
US31
-
1/4
1/4
1/4
1/4
US19
-
1/4
1/4
1/4
1/4
1
1.25
1.50
1.75
2
.75
1.50
2.25
3
1
1
Cum wgt
UA
US
Airlines alloc
UA
US
1
1
1
Empirical Comparison
Deviation PRA vs. RBS (LaGuardia)
Minutes/flights
25
NWA
ACA
COA
UAL
AAL
DAL
USA
15
5
-5
-15
4/
3/
01
4/
10
/0
1
4/
17
/0
1
4/
24
/0
1
3/
6/
01
3/
13
/0
1
3/
20
/0
1
3/
27
/0
1
2/
6/
01
2/
13
/0
1
2/
20
/0
1
2/
27
/0
1
1/
9/
01
1/
16
/0
1
1/
23
/0
1
1/
30
/0
1
1/
2/
01
-25
• On the aggregate, both methods give similar shares
• No systematic biases
GDP
Issues
• What is an ideal (fair) allocation?
• How can an allocation be generated that is
very close to the ideal while taking into
account dynamic problem aspects?
• How can airlines exchange resources they
receive as part of their allocation?
GDPs as Balanced Just-in-Time Scheduling Problem
flts
“ideal”
nb production rate
Possible
deviation measures
Xb Cumulative
production
na
time
• Airlines = products, flights = product quantities
• Minimize deviation between “ideal” rate and actual production
GDP Situation
flts
“Release times” defined by scheduled arrivals
na
Xa
slots
Questions:
• What are appropriate “production rates” ?
• How to minimize deviations ?
• Managing program dynamics
GDP Situation
flts
“Release times” defined by scheduled arrivals
na
Xa
slots
Questions:
• What are appropriate “production rates” ? ANS: RBS
• How to minimize deviations ?
• Managing program dynamics
Models and Algorithms for Minimizing Deviation
from Ideal Allocation
• General class of problems: minimize deviation between
actual slot allocation and ideal slot allocation
Variants based on:
– Objective function (deviation measures)
– Constraints on feasible allocations
• Minimize cumulative/maximum deviation:
– complex network flow model (based on JIT scheduling models)
can solve most variants
• Minimize sum of deviations between jth slot allocated to
airline a and ideal location for airline a’s jth slot:
– Assignment model
– Greedy algorithm for several cases
GDPs and Flight Exemptions
• GDPs are applied to an “included set” of flights
• Two significant classes of flights destined for the
airport during the GDP time period are exempted:
– Flights in the air
– Flights originating at airports greater than a certain
distance away from the GDP airport
• Question: Do exemptions induce a systematic
bias in the relative treatment of airlines during a
GDP??
Analysis of Flight Exemptions (Logan Airport)
4/
21
/0
1
AAL
4/
14
/0
1
4/
7/
01
USA
3/
31
/0
1
DAL
3/
24
/0
1
3/
17
/0
1
UCA
3/
10
/0
1
3/
3/
01
UAL
2/
24
/0
1
2/
17
/0
1
COA
2/
10
/0
1
CJC
2/
3/
01
1/
27
/0
1
1/
13
/0
1
1/
20
/0
1
TWA
40
30
20
10
0
-10
-20
-30
-40
1/
6/
01
Minutes/Flight
Deviation RBS (standard) vs RBS (+exemptions), Boston
GDPs
Flight exemptions introduce systematic biases:
• USA (11m/flt), UCA (18m/flt) “lose” under exemptions
Reducing Exemption Bias
Objective :
• Use deviation model to mitigate exemption bias
– i.e. “inverse” compression
Approach:
• RBS applied to all flights whose arrival times fall within
GDP time window  ideal allocation
• Set of exempted flights are defined as before (there are good
reasons they are exempted)
• Time slots given to exempted flights “count against”
allocation
• Delays allocated to non-exempted flights so as to minimize
overall deviation from ideal allocation
Flight Exemptions
USA
AAL
4/
21
/0
1
DAL
4/
14
/0
1
UCA
4/
7/
01
UAL
3/
31
/0
1
COA
3/
24
/0
1
-40
1/
6/
01
-40
4/
21
/0
1
-30
4/
14
/0
1
-30
4/
7/
01
-20
3/
31
/0
1
-20
3/
24
/0
1
-10
3/
17
/0
1
-10
3/
10
/0
1
0
3/
3/
01
0
2/
24
/0
1
10
2/
17
/0
1
10
2/
10
/0
1
20
2/
3/
01
20
1/
27
/0
1
30
1/
20
/0
1
30
1/
13
/0
1
40
1/
6/
01
40
CJC
3/
17
/0
1
TWA
3/
10
/0
1
AAL
3/
3/
01
USA
2/
24
/0
1
DAL
2/
17
/0
1
UCA
2/
10
/0
1
UAL
1/
27
/0
1
COA
1/
20
/0
1
CJC
1/
13
/0
1
TWA
Deviation RBS ideal-Opt. model
2/
3/
01
Deviation RBS ideal-RBS actual
• Minimize deviations using optimization model that incorporates
exemptions
• reduces systematic biases, e.g. USA from 11m/flt to 2m/flt, UCA
from 18m/flt to 5m/flt
Discussion
• Define “ideal” allocation
• Manage program dynamics based on models that
minimize deviation of actual slots allocated from
ideal allocation
• Provides single approach to both RBS and
compression
• Provides approach for mitigating bias due to
exemptions
• Other potential application, e.g. handling “pop-ups”
Issues
• What is an ideal (fair) allocation?
• How can an allocation be generated that is
very close to the ideal while taking into
account dynamic problem aspects?
• How can airlines exchange resources they
receive as part of their allocation?
Why Exchange Slots??
XX AAL355 4:00
Earliest time
of arrival:
4:15
AAL350 4:50
AAL235 5:10
Slot made available
by canceled or delayed
flight
Current Procedure: Compression
XX AAL355
UAL205
DAL254
USA105
Earliest time
of arrival: 4:15
4:00
4:05
4:10
4:15
AAL350 4:50
AAL235 5:10
Current Procedure: Compression
UAL205
DAL254
USA105
AAL350
Earliest time
of arrival: 4:15
4:00
4:05
4:10
4:15
AAL235 4:50
AALXXX 5:10
Inter-Airline Bartering
UAL
AAL
Mediator:
FAA
DAL
SWA
NWA
Mediated Slot Exchange
• Offer:
– slot_O: slot willing to give up
– slot_A1,…, slot_An: slots willing to accept in
return
• Each airline submits a set of offers
• Mediator determines set of offers to accept
and for each accepted offer, the returned
slot
Default Offers
earliest time
of arrival
slot_An
slot_A1
slot_O
Offer Associated with Canceled or Delayed Flights
time slot from
canceled flight
earliest time of
arrival for earliest
available flight
occupied
time slot
occupied
time slot
slot_O
slot_A1
slot_An
Mediation Problem
Input -- list of offers:
slot_A1
slot_O
slot_An
Problem: Which offers to accept
Cycle = set of mutually compatible set of exchanges
Schedule Movements Associated with Cycle
NWA
DAL
UAL
AAL
Overall Solution: find non-intersecting set of cycles –
problem can be formulated as an assignment problem
Compression-like
solutions can be found
using a bi-level
objective function (1st
level lexicographically
minimizes max
deviation between
early slots released on
later slots obtained)
Mediated bartering model suggests
many possible extensions:
• Dynamic trading (w conditional offers)
• Alternate mediator objective functions
• K-for-N trades
• Side payments
1-for-1 trades to 2-for-2 trades
• Compression  1-for-1 trading system, i.e. offers involve
giving up one slot and getting one in return (many offers
processed simultaneously)
• What about k-for-k or k-for-n offers, e.g. 2-for-2:
Trade??
Formulation of general mediator’s problem as set
partitioning problem:
Offer to trade slots 1
& 2 for 3,4 & 5
1
Set
partitioning
0/1 matrix
Right
Hand
Side
Slack variable: slot
not traded
1
1
1
1
1
Slots,
Copy 1
1
1
1
1
1
1
1
1
1
1
1
Slots,
Copy 2
Possible 2-for-2 trades:
1 up for 1 down: reduce
delay on 1
flight/increase delay on
another;
Model as reduce delay at
least d- on f1 in
exchange for increasing
delay at most d+ on f2.
2 down: reduce
delay on two
flights; handled by
2 “reduce delay”
single flight trades.
2 down: increase
delay on two
flights; not
reasonable.
Formulation of 2-for-2 trading problem as network
flow problem w side constraints:
slots
flights/slots
at least
side
constraint
at most
classes
On-Time (Flight)Performance Airline
Performance Function
• Compression Benefits
– performance improvement if compression executed
after flts with excessive delay (>2hrs) are canceled
Compression Improvement
40
Global Max.
Compression
% improvement
35
30
25
20
15
10
5
bo
s0
106
-0
bo
1
s0
115
-0
bo
1
s0
119
-0
bo
1
s0
130
-0
bo
1
s0
208
-0
bo
1
s0
214
-0
bo
1
s0
221
-0
bo
1
s0
226
-0
bo
1
s0
310
-0
bo
1
s0
313
-0
bo
1
s0
321
-0
bo
1
s0
323
-0
bo
1
s0
330
-0
bo
1
s0
408
-0
bo
1
s0
418
-0
1
0
GDP
Improvement Using 2-for-2
Trading System
• 2-for-2 Trading Model:
– proposed offers: all at-least, at-most pairs that improve
on-time performance
Trading Improvement
40
Global Max
Trading Model
30
25
20
15
10
5
01
01
-3
bo 0-0
1
s0
208
-0
bo
1
s0
214
-0
bo
1
s0
221
-0
bo
1
s0
226
-0
bo
1
s0
310
-0
bo
1
s0
313
-0
bo
1
s0
321
-0
bo
1
s0
323
-0
bo
1
s0
330
-0
bo
1
s0
408
-0
bo
1
s0
418
-0
1
01
bo
s
bo
s
01
-1
9-
01
01
-1
5-
01
-0
6-
bo
s
0
bo
s
%Improvement
35
GDP
Computational
Efficiency:
• 13sec avg.
• 67% solved by
LP relaxation
Results for Total Passenger Delay Airline
Performance Function
Max achievable
improvement:
Staircase Objective
Passenger Delays
90
80
80
70
70
% Improvement
90
60
50
40
30
60
50
40
30
20
20
10
10
0
0
0 1 01 01 01 0 1 01 01 01 0 1 01 01 01 01 0 1 01 01
2/ 0 /20 /20 /20 /20 /20 /20 /20 /20 /20 /20 /20 /20 /20 /20 /20
6
3
3
7
3
0
7
0
7
4
0
7
4
1
4
1
1/ 1/1 1/2 1/2 2/ 2/1 2/1 2/2 3/ 3/1 3/1 3/2 3/3 4/ 4/1 4/2
GDP
Staircase Objective
1/6
/2
1/1 00 1
3/2
1/2 0 01
0/2
1/2 0 01
7/2
0
2/3 01
/20
01
2/1
0/2
0
01
2/1
7/2
0
01
2/2
4/2
00
1
3/3
/2
3/1 00 1
0/2
3/1 0 01
7/2
3/2 0 01
4/2
3/3 0 01
1/2
0
4/7 01
/20
01
4/1
4/2
4/2 0 01
1/2
00
1
% Improvement
Passenger Delays
Improvement from
2-for-2 trading:
GDP
Final Thought: Options for providing airlines
ability to trade-off $$ & delay reductions
• Concept 1: Inter-airline slot trading with side
payments and slot buying & selling
• Concept 2: Auction long term leases on airport
slots with two “levels” of airport capacity
“as-available capacity”
“guaranteed capacity”