overbooking became integrated into RM systems (and
before RM systems were even required). Notable early
published works include those of Simon (1968) and
Vickrey (1972), as well as articles by Rothstein (1971,
1985). Rothstein’s 1985 article is a survey of previous
OR literature dealing with the airline overbooking
problem, and includes a discussion of the customer
service impacts of inaccurate overbooking and the
role of government in regulating denied boarding
penalties.
Statistical overbooking models typically represent
no-show rates as Gaussian random variables. The
objective is to find the maximum authorized number
of bookings (or “AU”) that will keep denied boardings
below some airline-specified target level with
a desired level of confidence. These models provide
airline managers with flexibility in determining their
own overbooking policy, for example, by increasing
denied boarding tolerance or reducing statistical
confidence.
An extension of the statistical overbooking approach
is the cost-based overbooking model, which
explicitly accounts for the actual costs associated with
denied boardings and with empty seats (“spoilage”).
The objective is to find the optimal overbooking level
that minimizes the total combined costs of denied
boardings and spoilage by performing a search over a
reasonable range of AU values. The cost-based overbooking
model is the current state of the practice
at many airlines. However, this approach represents
a static formulation of the overbooking problem, in
that the dynamics of passenger bookings, cancellations,
and no-shows are not explicitly accounted for
in determining an overbooking level.
The OR literature contains many additional works
on the airline overbooking problem, some of which
propose dynamic programming (DP) formulations.
Rothstein’s (1968) Ph.D. thesis was the first to
describe such a DP approach, while Alstrup et al.
(1986) extended the DP formulation to a two-class,
joint overbooking and fare class mix problem. More
recently, Chatwin (1996) as well as Feng and Xiao
(2001) have proposed DP-based approaches that allow
for the incorporation of time-dependent no-show
and cancellation rates associated with multiple fare
classes. In practice, few airlines have implemented
such complex DP formulations because of the difficulties
of providing adequate and accurate inputs in the
form of booking and cancellation rates by the timeperiod
before departure.
The economic motivation for airline overbooking
is substantial. In the United States, domestic airline
no-show rates average 15%–25% of final predeparture
bookings. Given that most airlines struggle to attain a
5% operating margin (revenues over costs), the loss of
15%–25% of potential revenues on fully booked flights
(which would occur without overbooking) can represent
a major negative impact on profits. As part of
a revenue management system, effective overbooking
has been shown to generate as much revenue gain as
optimal fare class seat allocation, described below.
3.3. Fare Class Mix
The second major technique of airline revenue
management is the determination of the revenuemaximizing
mix of seats available to each booking
(fare) class on each future flight-leg departure. Virtually
all airline RM systems were developed with
the capability to optimize fare class mix as their primary
objective. As introduced earlier, RM systems
forecast the expected demand for each fare class on
each future flight-leg departure by applying statistical
models to historical booking data for the same
fare class on previous departures of the same flight.
The forecasting of expected booking demands for
future flight departures has been addressed in many
OR papers, including Littlewood (1972), L’Heureux
(1986), Lee (1990), and Curry (1994).
These demand forecasts are then used as inputs to a
seat allocation optimization model, which determines
booking limits to be applied to each of the booking
classes on the flight departure in question. The vast
majority of airline reservations systems now have
inventory structures based on serial nesting of booking
classes, as shown in Figure 3. Seats are not “allocated”
to partitioned classes, but are instead “protected” for
higher fare classes and nested booking limits are applied
to the lower fare classes. All available seats in the
shared inventory are made available to the highest
booking class, in the (unlikely) event that the entire
capacity of the aircraft can be filled with demand for
the highest-priced fare product. This ensures that the