Transcript Analysis of Auction Approaches to Airport Slot Allocation

Evaluation of an Auction Mechanism
for Allocating Airport Arrival Slots
Eric J. Cholankeril
William Hall
John-Paul Clarke
June 5, 2003
Agenda



Motivation
Background on Auctions, Airline Recovery
Three Methods of Slot Allocation






Collaborative Decision Making
Global Optimization
The Auction Mechanism
Model of the Airline Recovery Problem
Results
Summary and Future Work
Motivation



Problem: While on-time rates have
improved, total passenger delay has
increased.
Inefficient use of airport resources during
Ground Delay Programs (GDPs)
A high fraction of flight cancellations is
unreported (~36%), so unused slots aren’t
being redistributed to other airlines
Motivation

Why aren’t airlines releasing unused slots?



Current slot allocation method may not provide
enough direct incentive for airlines to report
cancellations.
Airline may fear a loss in market share if its slots
are redistributed to another airline.
Airlines may be guarding against revisions to the
Ground Delay Program (GDP)
Motivation



Hypothesis: An auction could reduce
overall passenger delay by allocating
arrival slots more efficiently.
An auction provides direct monetary
incentive for airlines to give up
unneeded slots.
Objective: Test this hypothesis.
Vickrey Auction




Sealed bid, second price auction
Highest bidder wins
However, winner pays only the amount
of the second highest bid
This type of auction ensures that
bidders bid their true valuations
Previously Suggested Auctions
for Arrival Slot Allocation



Combinatorial Auction (Rassenti) –
Airlines can bid on packages of slots
Multi-Object Auction (Milner) – Airlines
report value of each possible flight/slot
combination, then FAA solves large
assignment problem
Groves Mechanism (Hall) – Impose a fee
on an airline, equal to the lost value
caused to the other airlines
Auction Design Considerations



Package bidding is complex to implement
(n slots => 2n packages!)
Individual bidding may not capture true
value of slot; since flights often arrive and
depart in banks, slots may be more
valuable when packaged together.
Charging airlines a fee to land is politically
infeasible, especially if the fee seems
unrelated to the bid values
The Airline Recovery Problem





How do airlines reroute their aircraft and
delay or cancel flights in response to a GDP?
Sub-problems: fleet assignment, aircraft
rerouting, crew scheduling, gate assignment,
slot allocation, passenger rerouting
Set-packing model (Clarke)
Aircraft selection heuristic (Rosenberger)
Goal in this thesis: simple airline recovery
model, quick to solve for a real-time auction
Goal: Evaluate Auction
as Allocation Method
Slot Allocation Methods to Compare
Auction
Arrival slots are initially assigned to airlines
according to original schedule of flights.
Then each slot is put up for auction, in the order
of the original schedule.
Collaborative Unused slots are reported and redistributed by
Decision
the FAA. An airline that gives up a slot receives
Making
priority for slots that are subsequently freed.
(CDM)
Global
All flights and slots belong to one airline.
Optimization Airline computes optimal flight-slot assignment.
Collaborative Decision Making
 Current Slot Allocation Method
 Goal: Increase usage of airport resources
 Implemented 1998
Three Steps:
1.
Initial slot assignment through Ration By
Schedule (RBS)
2.
Substitution and Cancellation
3.
Compression (at regular intervals)
CDM: Ration-By-Schedule (RBS)


Given a reduced arrival capacity, the
FAA issues a Ground Delay Program
(GDP) that maintains the original
scheduled order of flights.
For example, if the arrival capacity is 20
arrivals per hour, arrival slots are
spaced every three minutes and
assigned to the airlines according to the
original schedule.
CDM: Substitution/Cancellation



Slot is assigned to airline, rather than to a
particular flight
Substitution: Airline is free to reassign its
flights to the slots it owns, after the initial
RBS assignment. Simulate this by solving
airline recovery problem.
Cancellation: Airlines may decide to
release unused slots back to the FAA.
CDM: Compression



At regular intervals, any released slots
are redistributed or “compressed.”
If airline A releases one of its slots back
to the FAA, and the slot is reassigned to
a flight for airline B, A receives priority
for the slot that is freed as a result.
Provides some incentive for airlines to
release unused slots
Global Optimization



Goal: determine upper bound on amount of delay
that can be reduced through allocating slots
efficiently
Simulate by assigning all flights and slots to one
large airline. Airline computes optimal flight-slot
assignment by solving the airline recovery problem
Note: It is possible to exploit other efficiencies, e.g.
by constructing routes composed of flights from
different airlines. However, we are only concerned
with efficiencies that result from allocating slots.
Auction Mechanism
Sealed-bid, sequential Vickrey
auction without package bidding
•
Assign arrival slots to airlines using Ration By
Schedule.
Auction off each slot in order of the original
schedule.
1.
2.

3.
How do airlines determine sell and bid amounts?
Auction winner pays RBS slot owner for right
to slot
Slot Valuation


How does an airline decide how much to
bid on a particular slot S1, where S is the
set of slots it owns?
Bid the marginal value of the slot!
1.
2.
3.

Assign flights to S U S1
Assign flights to S \ {S1}
Subtract valuations
How to assign flights? Solve airline
recovery problem
Determining the Sell Price




In the auction, the RBS owner can set a
reservation price, or minimum sell price.
Slot is not sold unless the amount paid is
at least the reservation price.
How to determine sell price? Marginal
value of the slot.
Airline can decide not to sell the slot at all
by setting the reservation price very high.
Alternative Airline Behaviors

“Cautious Airline”



With some probability p, the airline sets its
reservation price to infinity in the auction.
In CDM, the airline refuses to release the
slot with probability p.
“Predictive Airline”

The airline bids relative to a predicted final
slot allocation, instead of bidding the
marginal value of the slot.
Model of the Airline Recovery
Problem

Minimize minutes of passenger delay
CvXv  dfKf
vV
f F
for assigned routes
for cancelled flights
•Cv = passenger delay due to assigning route v
•Xv = 1 if route v is assigned, 1 otherwise
•df = passenger delay due to cancelling flight f
•Kf = 1 if flight f is cancelled, 0 otherwise
Airline Recovery Constraints



Each aircraft is assigned to exactly one route.
Each flight is either cancelled or flown on one
route.
Each slot is assigned to at most one flight.
How to Generate Routes?


First, generate “unslotted” route alternatives for
each aircraft. Then, pair GDP arrivals with slots
within each route to generate “slotted” routes,
and calculate the resulting delay.
Constraints satisfied:



Each flight arriving at the GDP airport is assigned to
some slot.
Flight arrival times equal designated slot times.
Flow balance is maintained: aircraft must arrive at and
take off from the same airport.
Generating Unslotted Routes
with a GDP at LAX



Each aircraft must be assigned to its originating
flight (1,6), and some terminating flight (5 or 11)
Possible A routes: (1,2,3,4,5), (1,2,9,10,11),
(1,2,11)
Possible B routes: (6,7,8,9,10,11), (6,7,4,5), (6,5),
(6,7,8,11)
Reducing Route Possibilities
Using Subroutes
What happens if A is
assigned (1,2,3,4,5)
and B is assigned
(6,7,8,11)? 9 and 10
are cancelled, but
neither depart from
nor arrive at LAX!
-> Combine flights
that neither depart
from nor arrive at
GDP airport into
“subroutes”

A: (1,2,3,4,5), (1,2,9,10,11)


NOT (1,2,11)
B: (6,7,8,9,10,11), (6,7,4,5),
(6,5)

NOT (6,7,8,11)
“Slotting” Routes


Idea: Generate all possible pairings of arrival
slots to GDP arrival flights
To calculate Df, minutes flight f is delayed:


If f is a GDP arrival,
Df = (slot time – f’s original arrival time)
Otherwise, Df = delay implied by previous flights
in the route
Calculating Passenger Delay

What is “passenger delay”?


To calculate Cv, passenger delay for assigning route v:



Sum of delays to individual passengers in arriving at their final
destinations
For terminating passengers, use delay of flight
For connecting passengers, determine which passengers miss their
connections, and calculate their delays if they were to be rerouted
onto later connecting flights.
To calculate Df, passenger delay due to cancelling flight f:


Calculate delays for passengers if they were to be rerouted onto later
flights
Impose cancellation delay cutoff of 6 hours
Implementation





Simulated on actual flight data from March 1998
(Airline Service Quality Performance database for
10 biggest airlines, OAG database for local and
international airlines)
Passenger itinerary data stochastically generated
using itinerary probabilities calculated from ticket
samples (DB1B Market database, Bureau of
Transportation)
Average passenger load factor for Q1 1998: 70%
Minimum turnaround time assumed: 25 minutes
GDP at BOS, default arrival rate = 60/hr
Results: Reducible Passenger
Delay Captured

Reducible Passenger Delay
= Global Opt. Delay – CDM Delay
Reduced Airport
Arrival Rate,
Reduction Period
Avg. Percentage of
Reducible Delay
Captured By Auction
St.Dev.
0 arrivals/hr, 2 hrs
74.51%
9.54%
10 arrivals/hr, 2 hrs
69.48%
11.78%
20 arrivals/hr, 2 hrs
22.42%
21.37%
0 arrivals/hr, 1 hr
56.64%
33.29%
20 arrivals/hr, 3 hrs
36.25%
18.77%
More reducible delay captured in longer, more severe GDPs
Results: Absolute Reduction in
Passenger Delay


Reduced Airport
Arrival Rate,
Reduction Period
Avg. Percent Delay
Reduction
St. Dev.
0 arrivals/hr, 2 hrs
6.84%
4.30%
10 arrivals/hr, 2 hrs
28.80%
10.86%
20 arrivals/hr, 2 hrs
8.83%
10.2%
0 arrivals/hr, 1 hr
5.93%
4.63%
20 arrivals/hr, 3 hrs
20.48%
12.27%
Large variation in percentage of delay reduced
However, the delay reduction is statistically
different from zero in each case
Results: Varying One Airline’s
“Cautiousness”
Effect of Increasing One Airline's Caution Level on Its Net Delay in the Auction
Change in Passenger Minutes of Delay Minus Auction
Income, from p=0
150
100
50
0
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
-50
-100
-150
-200
Probability p of Withholding a Slot
It is unclear whether a single airline benefits from being more cautious.
Results display a high degree of randomness.
Results: Varying Number of
Cautious Airlines
Effect of Increasing Number of Cautious Airlines on Overall Passenger Delay in the Auction
25000
CO
Increase in Total Passenger Minutes of Delay,
from Zero Cautious Airlines
20000
HQ
15000
10000
QK
AC
5000
NW
C
9L
UA
DL
US
W9
AA
OH
6
8
HP
0
0
2
4
10
12
14
-5000
Num ber of Cautious Airlines (With Caution Level 0.3)
Increasing the number of cautious airlines seems to increase total delay.
16
Results: Varying Number of
“Predictive” Airlines
Effect of Increasing Number of Predictive Airlines on Overall Passenger Delay in the Auction
80000
US
CO
Increase in Total Passenger Minutes of Delay,
from Zero Predictive Airlines
60000
HP
HQ
W9
40000
AA
20000
NW
C
OH
QK
AC
9L
0
0
-20000
2
4
6
8
10
12
14
16
DL
UA
-40000
Num ber of Predictive Airlines
Increasing the number of predictive airlines seems to increase total delay,
but results also display a great deal of randomness.
Optimization Running Time



Time to “slot” routes, generate route delays, and
solve IP
For most airlines, under a second
For Business Express, with 23 disrupted aircraft
and 1809 possible route alternatives, under 4
seconds
Optimization Model is fast enough for a real-time
auction, but requires much more memory for
extended GDPs with many route possibilities
Summary





Use auction to allocate arrival slots more
efficiently
Assign slots to airlines according to the original
schedule, then allow airlines to bid on slots
Compared passenger delay for auction method,
CDM, and global optimization
For scenarios tested: Up to 75% of reducible
passenger delay was captured
At least 5-7% of overall passenger delay was
reduced in all scenarios
Ideas for Future Research



Simulate other auction mechanisms,
e.g. combinatorial auction
Simulate effect of revising the GDP
Future work on airline recovery problem



Route generation requires a lot of memory, esp. for
extended GDPs
More accurate passenger rerouting model needed
Add in constraints on gate assignment, crew
scheduling, etc.