23.3 finals.pdf

Models for Evaluating Airline Overbooking 301

Models for Evaluating Airline

Overbooking

Michael P. Schubmehl

Wesley M. Turner

Daniel M. Boylan

Harvey Mudd College

Claremont, CA

Advisor: Michael E. Moody

Introduction

We develop two models to evaluate overbooking policies.

The ﬁrst model predictstheeffectiveness of a proposedoverbookingscheme,

using the concept of expected marginal seat revenue (EMSR). This model solves

the discount seat allocation problem in the presence of overbooking factors for

each fare class and evaluates an overbooking policy stochastically.

The second model takes in historical ﬂight data and reconstructs what the

optimal seat allocation should have been. The percentage of overbooking rev-

enue obtained in practice serves as a measure of the policy’s value.

Finally, we examine the overbooking problem in light of the recent drastic

changes to airline industry and conclude that increased overbooking would

bring short-term proﬁts to most carriers. However, the long-term ill effects

that have traditionally caused airlines to shun such a policy would be even

more pronounced in a post-tragedy climate.

Literature Review

There are two major ways that airlines try to maximize revenues: over-

booking (selling more seats than available on a given ﬂight) and seat allocation

(price discrimination). These measures are believed to save major airlines as

much as half a billion dollars each year, in an industry with a typical yearly

proﬁt of about $1 billion dollars [Belobaba 1989].

The UMAP Journal 23 (3) (2002) 301–316.

Permission to make digital or hard copies of part or all of this work for personal or classroom use

is granted without fee provided that copies are not made or distributed for proﬁt or commercial

advantage and that copies bear this notice. Abstracting with credit is permitted, but copyrights

for components of this work owned by others than COMAP must be honored. To copy otherwise,

to republish, to post on servers, or to redistribute to lists requires prior permission from COMAP.

302 The UMAP Journal 23.3 (2002)

Beckman [1958] models booking and no-shows in an effort to ﬁnd an optimal

overbooking strategy. He ignores advance cancellations, assuming that all can-

cellations are no-shows [Rothstein 1985]. A method that is easy to implement

but sophisticated enough to allow for cancellations and group reservations was

developed by Taylor [1962]. Versions of this model were implemented at Iberia

Airlines [Shlifer and Vardi 1975], British Overseas Airways Corporation, and

El Al Airlines [Rothstein 1985].

None of these approaches considers multiple fare classes. Littlewood [1972]

offers a simple two-fare allocation rule: A discount fare should be sold only if

the discount fare is greater than or equal to the expected marginal return from

selling the seat at full-fare. This idea was generalized by Belobaba [1989] to in-

clude any number of fare classes and allow the integration of overbooking. We

use expected marginal seat revenue in predicting about overbooking schemes.

There is a multitude of work on the subject [McGill 1999]—according to

Weatherford and Bodily [1992], there are more than 124,416 classes of models

for variations of the yield management problem, though research has settled

into just a few of these. Several authors tried to better Belobaba’s [1987] heuristic

in the presence of three or more fare classes (for which it is demonstrably sub-

optimal) [Weatherford and Bodily 1992]; generally, these adaptive methods for

obtaining optimal booking limits for single-leg ﬂights are done by dynamic

programming [Mcgill 1999].

After deregulation in 1978, airlines were no longer required to maintain a

direct-route system to major cities. Many shifted to a hub-and-spoke system,

and network effects began to grow more important. To maximize revenue, an

airline may want to consider a passenger’s full itinerary before accepting or

denying their ticket request for a particular leg. For example, an airline might

prefer to book a discount fare rather than one at full price if the passenger is

continuing on to another destination (and thus paying an additional fare).

The ﬁrst implementations of the origin-destination control problem consid-

ered segments of ﬂights. The advantage to this was that a segment could be

blacked out to a particular fare class, lowering the overall complexity of a book-

ing scheme. Another method, virtual nesting, combines fare classes and ﬂight

schedules into distinct buckets [Mcgill 1999]. Inventory control on these buck-

ets would then give revenue-increasing results. Finally, the bid-price method

deterministically assigns a value to different seats on a ﬂight leg. The legs in

an itinerary are then summed to establish a bid-price for that itinerary; a ticket

request is accepted only if the fare exceeds the bid-price [Mcgill 1999]

The most realistic yield management problem takes into account ﬁve price

classes. The ticket demands for different fare classes are randomized and corre-

lated with one other to allow for sell-ups and the recapture of rejected customers

on later ﬂights. Passengers can no-show or cancel at any time. Group reser-

vations are treated separately from individuals—their cancellation probability

distribution is likely different. Currently, most work assumes that passengers

who pay full fare would not ﬁrst check for availability of a lower-class ticket;

a more realistic model would allow buyers of a higher-class ticket to be di-

Models for Evaluating Airline Overbooking 303

verted by a lower fare. A full accounting of network effects would consider

the relative value of what Weatherford and Bodily [1992] terms displacement—

denying a discount passenger’s ticket request to ﬂy a multileg itinerary in favor

of leaving one of the legs open to a full-fare passenger.

Unfortunately, while the algorithms for allocating seats and setting over-

booking levels are highly developed, there has been little work done on the

problem of evaluating how effective these measures actually are. Our solution

applies industry-standard methods to ﬁnd optimal booking levels, then exam-

ines the actual booking requests for a given ﬂight to determine how close to an

optimal revenue level the scheme actually comes.

Factors Affecting Overbooking Policy

General Concerns

The reason that overbooking is so important is because of multiple fare

classes. With only one fare class, it would be easier for airlines to penalize

customers for no-shows. However, while most airlines offer nonrefundable

discount tickets, they prefer not to penalize those who pay full fare, like business

travelers, because these passengers account for most of the proﬁts.

The overbooking level of a plane is dictated by the likelihood of cancellations

and of no-shows. An overbooking model compares the revenue generated by

accepting additional reservations with the costs associated with the risk of

overselling and decides whether additional sales are advisable. In addition,

the “recapture” possibility can be considered, which is the probability that a

passenger denied a ticket will simply buy a ticket for one of the airline’s other

ﬂights. Since a passenger is more valuable to the airline buying a ticket on a

ﬂight that has empty seats to ﬁll than on one that is already overbooked, a high

recapture probability reduces the optimal overbooking level [Smith et al. 1992].

No major airline overbooks at proﬁt-maximizing levels, because it could

not realistically handle the problems associated with all the overloaded ﬂights.

This gives the overbooking optimization problem some important constraints.

The total ﬂight revenue is to be maximized, subject to the conditions that only

a certain portion of ﬂights have even one passenger denied boarding (one

oversale), and that a bound is placed on the expected total number of oversales.

Dealing with even one oversale is a hassle for the airline’s staff, and they are

not equipped to handle such problems on a large scale. Additionally, some

research indicates that increased overbooking levels would most likely trigger

an “overbooking war” [Suzuki 2002], which would increase short-term proﬁts

but would probably engender enough consumer resentment that the industry

as a whole would lose business.

While the overbooking problem sets a limit for sales on a ﬂight as a whole,

proper seat allocation sets an optimal point at which to stop selling tickets

for individual fare levels. For example, a perfectly overbooked plane, loaded

304 The UMAP Journal 23.3 (2002)

exactly to capacity, could be ﬂying at far below its optimal revenue level if

too many discount tickets were sold. The more expensive tickets are not for

ﬁrst-class seats and involve no additional luxuries above the discount tickets,

apart from more lenient cancellation policies and the ability to buy the tickets

a shorter time before the ﬂight’s departure.

September 11, 2001

Since the September 11 terrorist attacks, there have been signiﬁcant changes

in the airline business. In addition to the forced cancellation of many ﬂights in

the immediate aftermath of the attacks and the extreme levels of cancellations

and no-shows by passengers after that, passenger trafﬁc has dropped sharply

in general. The huge downturn in passenger levels has led to large reductions

in service by most carriers.

In terms of the booking problem, there are fewer ﬂights for passengers

to spill over onto, which could increase the loss by an airline if it bumps a

passenger from a ﬂight. On the other hand, since passenger levels have fallen

so far, it is less likely that an airline will overﬁll any given ﬂight. The heightened

security at airports will likely increase the passenger no-show rate somewhat,

as passengers get delayed at security checkpoints. At the very least, it should

almost completely remove the problem of “go-shows,” passengers who show

up for a ﬂight but are not in the airline’s records.

On the whole, optimal booking strategies have become even more vital as

airlines have already lost billions of dollars, and some teeter on the brink of

failure. Some overbooking tactics previously dismissed as too harmful in the

long run might be worthwhile for companies in trouble. For example, an airline

near failure might increase the overbooking rate to the level that maximizes

revenue, without regard to the inconvenience and possible future resentment

of its customers.

Constructing the Model

Objectives

A scheme for evaluating overbooking policies needs to answer two ques-

tions: how well should a new overbooking method perform, and how well is a

current overbooking scheme already working? The ﬁrst is best addressed by a

simple model of an airline’s booking procedures; given some setup for allocat-

ing seats to fare classes, candidate overbooking schemes can be laid on top and

tested by simulation. This approach has the advantage that it provides insight

into why an overbooking scheme is or is not effective and helps to illuminate

the characteristics of an optimal overbooking approach.

The second question is, in some respects, a simpler one to answer. Given the

actual (over)booking limits that were imposed on each fare class, and all avail-

Models for Evaluating Airline Overbooking 305

able information on the actual requests for reservations, how much revenue

might have been gained from overbooking, compared to how much actually

was? This provides a very tangible measure of overbooking performance but

very little insight into the reasons for results.

The enormous number of factors affecting the design and evaluation of

an overbooking policy force us to make simplifying assumptions to construct

models that meet both of these goals.

Assumptions

• Fleet-wide revenues can be near-optimized one leg at a time.

Maximizing revenue involves complicated interactions between ﬂights. For

instance, a passenger purchasing a cheap ticket on a ﬂight into a major hub

might actually be worth more to the airline than a business-class passenger,

on account of connecting ﬂights. We assume that such effects can be compen-

sated for by placing passengers into fare classes based on revenue potential

rather than on the fare for any given leg. This assumption effectively reduces

the network problem to a single-leg optimization problem.

• Airlines set fares optimally.

Revenue maximization depends strongly on the prices of various classes

of tickets. To avoid getting into the economics of price competition and

supply/demand, we assume that airlines set prices optimally. This reduces

revenue maximization to setting optimal fare-class (over)booking limits.

• Historical demand data are available and applicable.

The model needs to estimate future demand for tickets on any given ﬂight.

We assume that historical data are available on the number of tickets sold

any given number of days t before a ﬂight’s departure. In some respects, this

assumption is unrealistic because of the problem of data censorship—that is,

the failure of airlines to record requests beyond the booking limit for a fare

class [Belobaba 1989]. On the other hand, statistical methods can be used

to reconstruct this information [Boeing Commercial Airline Company 1982,

7–16; Swan 1990].

• Low-fare passengers tend to book before high-fare ones.

Discount tickets are often sold under advance purchase restrictions, for the

precise reason that it enables price discrimination. Because of restrictions

like these, and because travelers who plan ahead search for cheap tickets,

low-fare passengers tend to book before high-fare ones.

Predicting Overbooking Effectiveness

Disentangling the effects of overbooking, seat allocation, pricing schemes,

and external factors on revenues of an airline is extremely complicated. To

306 The UMAP Journal 23.3 (2002)

isolate the effects of overbooking as much as possible, we want a simple, well-

understood seat allocation model that provides an easy way to incorporate

various overbooking schemes. In light of this objective, we pass up several

methods for ﬁnding optimal booking limits on single-leg ﬂights detailed in, for

example, Curry [1990] and Brumelle [1993], in favor of the simpler expected

marginal seat revenue (EMSR) method [Belobaba 1989].

EMSR was developed as an extension of the well-known rule of thumb,

popularized by Littlewood [1972], that revenues are maximized in a two-fare

system by capping sales of the lower-class ticket when the revenue from selling

an additional lower-class ticket is balanced by the expected revenue from selling

the same seat as an upper-class ticket. In the EMSR formulation, any number of

fare classes are permitted and the goal is “to determine how many seats not to

sell in the lowest fare classes and to retain for possible sale in higher fare classes

closer to departure day” [Belobaba 1989].

The only information required to calculate booking levels in the EMSR

model is a probability density function for the number of requests that will

arrive before the ﬂight departs, in each fare class and as a function of time.

For simplicity, this distribution can be assumed to be normal, with a mean and

standard deviation that change as a function of the time remaining. Thus, the

only information an airline would need is a historical average and standard

deviation of demand in each class as a function of time. Ideally, the informa-

tion would reﬂect previous instances of the particular ﬂight in question. Let

the mean and standard deviations in question be denoted by μ

(t) and σ

(t) for

each fare class i =1, 2,... ,k. Then the probability that demand is greater than

some speciﬁed level S

is given by

,t) ≡

√

2πσ

(t)



∞

(r−μ

(t))

/σ

(t)

dr.

This spill probability is the likelihood that the S

th ticket would be sold if offered

in the ith category. If we further allow f

(t) to denote the expected revenue

resulting from a sale to class i at a time t days prior to departure, we can deﬁne

EMSR

,t)=f

(t) ·

,t),

or simply the revenue for a ticket in class i times the probability that the S

seat will be sold. The problem, however, is to ﬁnd the number of tickets S

that

should be protected from the lower class j for sale to the upper class i (ignoring

other classes for the moment). The optimal value for S

satisﬁes

EMSR

,t)=f

(t), (1)

so that the expected marginal revenue from holding the S

th seat for class i is

exactly equal to (in practice, slightly greater than) the revenue from selling it

immediately to someone in the lower class j. The booking limits that should

be enforced can be derived easily from the optimal S

values by letting the

Models for Evaluating Airline Overbooking 307

booking limit B

for class j be

(t)=C − S

j+1

−



i<j

(t), (2)

that is, the capacity C of the plane, less the protection level of the class above j

from class j and less the total number of seats already reserved. Sample EMSR

curves, with booking limits calculated in this fashion, are shown in Figure 1.

EMSR ($)

10 20 30 40 50 60

100

150

200

250

b1b2

Seat Number

Figure 1. Expected marginal seat revenue (EMSR) curves for three class levels, with the high-

est-revenue class at the top. Each curve represents the revenue expected from protecting a par-

ticular seat to sell to that class. Also shown are the resulting booking limits for each of the lower

classes—that is, the levels at which sales to the lower class should stop to save seats for higher

fares.

This formulation does not account for overbooking; if we allow each fare

class i to be overbooked by some factor OV

, the optimality condition (1) be-

comes

EMSR

,t)=f

(t) ·

. (3)

This can be understood in terms of an adjustment to f

and f

; the overbooking

factors are essentially cancellation probabilities, so we use each OV

to deﬂate

the expected revenue from fare class i. Then

,t) ·

(t)

= f

(t) ·

(t)

308 The UMAP Journal 23.3 (2002)

which is equivalent to (3). Note that the use of a single overbooking factor for

the entire cabin (that is, OV

= OV ) causes the OV

and OV

in (3) to cancel.

Nonetheless, the boarding limits for each class are affected, because the capacity

of the plane C must be adjusted to account for the extra reservations, so now

∗

= C · OV

and the booking limits in (2) are adjusted upward by replacing C with C

∗

The EMSR formalism gives us the power to evaluate an overbooking scheme

theoretically by plugging its recommendations into a well-understood stable

model and evaluating them. Given the EMSR boarding limits, which can be

updated dynamically as booking progresses, and the prescribed overbooking

factors, a simulated string of requests can be handled. Since the EMSR model

involves only periodic updates to establish limits that are ﬁxed over the course

of a day or so, a set of n requests can be handled with two lookups each (booking

limit and current booking level), one subtraction, and one comparison; so all

n requests can be processed on O(n) time. An EMSR-based approach would

thus be practical in a real-world real-time airline reservations system, which

often handles as many as 5,000 requests per second. Indeed, systems derived

from EMSR have been adopted by many airlines [Mcgill 1999].

Evaluating Past Overbookings

The problem of evaluating an overbooking scheme that has already been

implemented is somewhat less well studied than the problem of theoretically

evaluating an overbooking policy. One simple approach, developed by Ameri-

can Airlines in 1992, measures the optimality of overbooking and seat allocation

separately [Smith et al. 1992]. Their overbooking evaluation process assumes

optimal seat allocation and, conversely, their seat allocation evaluation scheme

assumes optimal overbooking. Under this assumption, an overbooking scheme

is evaluated by estimating the revenue under optimal overbooking in two ways:

• If a ﬂight is fully loaded and no passenger is denied boarding, the ﬂight

is considered to be optimally overbooked and to have achieved maximum

revenue.

• If n passengers are denied boarding, the money lost due to bumping these

passengers is added back in and the n lowest fares paid by passengers for

the ﬂight are subtracted from revenue.

• On the other hand, if there are n empty seats on the plane, the n highest-fare

tickets that were requested but not sold are added to create the maximum

revenue ﬁgure.

Their seat-allocation model estimates the demand for each ﬂight by calcu-

lating a theoretical demand for each fare class and then setting the minimum

ﬂight revenue (by ﬁlling the seats lowest-class ﬁrst) and the maximum ﬂight

Models for Evaluating Airline Overbooking 309

revenue (by ﬁlling the seats highest-class ﬁrst). To estimate demand, we use

the information on the ﬂight’s sales up to the point where each class closed. By

assuming that demand is increasing for each class, we can project the number

of requests that would have occurred had the booking limits been disregarded.

Given these projected additional requests and the actual requests received

before closing, it is straightforward to compute the best- and worst-case over-

booking scenarios. The worst-case revenue R

−

is determined by using no

booking limits and taking reservations as they come, and the best-case rev-

enue R

is determined by accommodating high-fare passengers ﬁrst, giving

the leftovers to the lower classes. The difference between these two ﬁgures is

the revenue to be gained by the use of booking limits. Thus, the performance

of a booking scheme that generates revenue R is

p =

R − R

−

− R

−

· 100%, (4)

representing the percentage of the possible booking revenue actually achieved.

We select this method for evaluating booking schemes after the fact.

Analysis of the Models

Tests and Simulations

The EMSR method requires information on demand as a function of time.

Although readily available to an airline, it is not widely published in a detailed

form. Li [2001] provides enough data to construct a rough piecewise-linear

picture of demand remaining as a function of time, shown in Figure 2.

This information can be inputted into the EMSR model to produce optimal

booking limits that evolve in time. A typical situation near the beginning of

ticket sales was shown in Figure 1, while the evolution of the limits themselves

is plotted in Figure 3.

The demand information in Figure 2 can also be used to simulate requests

for reservations. By taking the difference between the demand remaining at

day t and at day (t −1) before departure, the expected demand on day t can be

determined. The actual number of requests generated on that day is then given

by a Poisson random variable with parameter λ equal to the expected number

of sales [Rothstein 1971]. The requests generated in this manner can be passed

to a request-handling simulation that looks at the most current booking limits

and then accepts or denies ticket requests based on the number of reservations

already conﬁrmed and the reservations limit. An example of this booking

process is illustrated in Figure 4.

The results of the booking process provide an ideal testbed for the revenue

opportunity model employed to evaluate overbooking performance. The sim-

ulation conducted for Figure 4 had demand values of {11, 41, 57}, for classes 1,

310 The UMAP Journal 23.3 (2002)

Expected Remaining Demand as Flight Time Approaches

Fraction of Demand Remaining

60 40 20 0

0.2

0.4

0.6

0.8

Days Until Departure

Figure 2. Demand remaining as a function of time for each of three fare classes, with the highest

fare class on top. The curves represent the fraction of tickets that have yet to be purchased. Note

that, for example, demand for high fare tickets kicks in much later than low-fare demand. ( Data

interpolated from Li [2001].)

2, and 3 respectively, before ticket sales were capped. A linear forward projec-

tion of these sales rates indicates that they would have reached {18, 49, 69}had

the classes remained open. Given fare classes {$250, $150, $100}, the minimum

revenue would be

−

= $100(69) + $150(40) + $250(0) = $12 , 900

and the maximum revenue would be

= $250(18) + $150(49) + $100(42) = $16 , 050.

The actual revenue according to the EMSR formalism was

R = $100(57) + $150(41) + $250(11) = $14, 600,

so the efﬁciency is

p =

R − R

−

− R

−

· 100% =

$14, 600 − $12, 900

$16, 050 − $12, 900

· 100% = 54%,

without the use of a complicated overbooking scheme. This is not close to the

efﬁciencies reported in Smith et al. [1992], which cluster around 92%. This rela-

tive inefﬁciency is to be expected, however, from a simpliﬁed booking scheme

given incomplete booking request data.

Models for Evaluating Airline Overbooking 311

Evolution of Booking Limits by the EMSR Method

Booking Limit

60 40 20 0

100

Days Until Departure

Figure 3. Booking limits for each class are dynamically adjusted to account for tickets already sold.

For illustrative purposes, the number of tickets already sold is replaced here with the number

of tickets that should have been sold according to expectations. In this case, the booking limits

estimated at the beginning of the process are fairly accurate and require relatively little updating.

Total Bookings by Fare Class: First Sale to Flight Time

Bookings

60 40 20 0

Days Until Departure

Figure 4. The EMSR-based booking limits are used to decide whether to accept or reject a sequence

of ticket requests. These requests follow a Poisson distribution where the parameter λ varies with

time to match the expected demand. Each fare class reaches its booking limit, as desired, so the

ﬂight is exactly full. Incorporating overbooking factors shifts the limits up accordingly.

312 The UMAP Journal 23.3 (2002)

Strengths and Weaknesses

Strengths

• Applies widely accepted, industry-standard techniques.

Although more advanced (and optimal) algorithms are available and are

used, EMSR and its descendants are still widely used in industry and can

come close to optimality. The EMSR scheme, tested as-is on a real airline,

caused revenue gains as much as 15% [Belobaba 1989].

Our method for determining the optimality of a scheme after the fact is also

based on tried and true methods developed by American Airlines [Smith et

al. 1992].

• Simplicity

Since it does not take into account as many factors as other booking models,

EMSR is easier to deal with computationally. While a simple model may not

be able to model a major airline with complete accuracy, an optimal pricing

scheme can be made using only three fare classes [Li 2001].

Weaknesses

• Neglects network effects

We treat the problem of optimizing each ﬂight as if it were an independent

problem although it is not.

• Ignores sell-ups

In considering the discount seat allocation problem, we treat the demands

for the fare classes as constants, independent of one other. This is not the

case, because of the possibility of sell-ups. If the number of tickets sold in a

lower fare class is restricted, then there is some probability that a customer

requesting a ticket in that class will buy a ticket at a more expensive fare.

This means it is possible to convert low-fare demand into high-fare demand,

which would suggest protecting a higher number of seats for high fares than

calculated by the model that we use. Sell-ups would be straightforward to

incorporate into EMSR, but doing so would require additional information

[Belobaba 1989].

• Discounts possibility of recapture

Similar to sell-ups, the recapture probability is the probability that a passen-

ger unable to buy a ticket at a certain price on a given ﬂight will buy a ticket

on a different ﬂight. Depending on the recapture probability for each fare

class, more or fewer seats might be allocated to discount fares.

Models for Evaluating Airline Overbooking 313

Recommendations on Bumping Policy

In 1999, an average of only 0.88 passengers per 10,000 boardings were in-

voluntarily bumped. Airlines are not required to keep records of the number

of voluntary bumps, so it is impossible to determine a general bump rate.

Before bumping passengers involuntarily, the airline is required to ask for

volunteers. Because there are no regulations on compensation for voluntary

bumps, this is often a cheaper and more attractive method for airlines anyway.

If too few people volunteer, the airline must pay those denied boarding 200%

of the sum of the values of the passengers’ remaining ﬂight coupons, with a

maximum of $400. This maximum is decreased to $200 if the airline arranges

for a ﬂight that will arrive less than 2 hours after the original ﬂight. The air-

line may also substitute the offer of free or reduced fare transportation in the

future, provided that the value of the offer is greater than the cash payment

otherwise required. Alternatively, the airline may simply arrange alternative

transportation if it is scheduled to arrive less than an hour after the original

ﬂight.

Auctions in which the airline offers progressively higher compensation for

passengers who give up their seats are both the cheapest and the most com-

mon practice. As long as the airline does not engage in so much overbooking

that it cannot ﬁnd suitable reroutes for passengers bumped from their original

itineraries, no alternatives to this policy need to be considered.

Conclusions

The two models presented in this paper work together to evaluate over-

booking schemes by simulating their effects in advance and by quantifying

their effects after implementation.

The expected marginal seat revenue (EMSR) model predicts overbooking

scheme effectiveness. It determines the correct levels of protection for each fare

class above the lowest—that is, how many seats should be reserved for possible

sale at later dates and higher fares. Overbooking factors can be speciﬁed sepa-

rately for each fare class, so the model effectively takes in overbooking factors

and produces booking limits that can be used to handle ticket requests.

The revenue opportunity model attempts to estimate the maximum revenue

from a ﬂight under perfect overbooking and discount allocation. This is accom-

plished by estimating the actual demand for seats, then calculating the revenue

that these seats would generate if sold to the highest-paying customers. Sim-

ple calculations produce the ideal overbooking cap and the optimal discount

allocation for the ﬂight. Thus, this model effectively represents how the airline

would sell tickets if they had perfect advance knowledge of demand.

After the September terrorist attacks and their subsequent catastrophic ef-

fects on the airline industry, heightened airport security and fearful passengers

will increase no-show and cancellation rates, seeming to dictate increasing

314 The UMAP Journal 23.3 (2002)

overbooking levels to reclaim lost proﬁts.

Airlines considering such action should be cautioned, however, that the

negative effects of increased overbooking could outweigh the beneﬁts. With

reduced airline service, ﬁnding alternative transportation for displaced passen-

gers could be more difﬁcult. The effect of denying boarding to more passen-

gers, along with the greater inconvenience of being bumped, could seriously

shake consumers’ already-diminished faith in the airline industry. With air-

lines already losing huge numbers of customers, it would be a mistake to risk

permanently losing them to alternatives like rail and auto travel by alienating

them with frequent overselling.

References

Beckman, J.M. 1958. Decision and team problems in airline reservations. Econo-

metrica 26: 134–145.

Belobaba, Peter. 1987. Airline yield management: An overview of seat inven-

tory control. Transportation Science 21: 63–73.

. 1989. Application of a probabilistic decision model to airline seat

inventory control. Operations Research 37: 183–197.

Biyalogorsky, Eyal, et al. 1999. Overselling with opportunistic cancellations.

Marketing Science 18 (4): 605–610.

Boeing Commercial Airline Company. 1982. Boeing Promotional Fare Man-

agement System: Analysis and Research Findings. Seattle, WA: Boeing,

Seattle.

Bowen, B.D., and D.E. Headley. 2000. Airline Quality Rating 2000. http:

//www.uomaha.edu/~unoai/research/aqr00/ .

Brumelle, S.L., and J.I. McGill. 1993. Airline seat allocation with multiple

nested fare classes. Operations Research 41: 127–137.

Chatwin, Richard E. 2000. Optional dynamic pricing of perishable products

with stochastic demand and a ﬁnite set of prices. European Journal of Oper-

ations Research 125: 149–174.

Curry, R.E. 1990. Optimal airline seat allocation with fare classes nested by

origins and destinations. Transportation Science 24: 193–204).

Davis, Paul. Airline ties proﬁtability yield to management. 1994. Siam News

27 (5); http://www.siam.org/siamnews/mtc/mtc694.htm .

Li, M.Z.F. 2001. Pricing non-storable perishable goods by using a purchase

restriction with an application to airline fare pricing. European Journal of

Operations Research 134: 631–647.

Models for Evaluating Airline Overbooking 315

Littlewood, K. 1972. Forecasting and control of passenger bookings. AGIFORS

Symposium Proceedings: 12.

McGill, J.I., and G.Z. and Van Ryzin. 1999. Revenue management: Research

overview and prospects. Transportation Science 33 (2): 233–256.

Rothstein, M. 1971. An airline overbooking model. Transportation Science 5:

180–192.

Rothstein, Marvin 1985. OR and the airline overbooking problem. Operations

Research 33 (2): 237–247.

Ross, Robert. 1998. Embry-Riddle experts reveal airfare secrets. http://comm.

db.erau.edu/leader/fall98/priced.html .

Shlifer, R., and Y. Vardi. 1975. An Airline Overbooking Policy. Transportation

Science 9: 101-114.

Swan. 1990. Revenue management forecasting biases. Working paper. Seattle,

WA: Boeing Commercial Aircraft.

Smith, Barry C., et al. 1992. Yield management at American Airlines. Interfaces

22 (1): 8–31.

Suzuki, Yoshinori. 2002. An empirical analysis of the optimal overbooking

policies for U.S. major airlines. Transportation Research E38: 135–149.

Taylor, C.J. 1962. The determination of passenger booking levels. AGIFORS

Symposium Proceedings, vol. 2. Fregene, Italy.

Weatherford, L.R., and S.E. Bodily. 1992. A taxonomy and research overview of

perishable-asset revenue management: Yield management, overbooking,

and pricing. Operations Research 40: 831–844.

Presentation by Richard Neal (MAA Student Activities Committee Chair) of the MAA award to

Daniel Boylan and Wesley Turner of the Harvey Mudd College team (Michael Schubmehl could

not come), after their presentation at the MAA Mathfest in Burlington, VT, in August. On the right

is Ben Fusaro, Founding Director of the MCM. Photo by Ruth Favro, Lawrence Tech University.

316 The UMAP Journal 23.3 (2002)

Letter to the CEO of a Major Airline

Airline overbooking is just one facet of a revenue management problem that

has been studied extensively in operations research literature. Airlines have

been practicing overbooking since the 1940’s, but early models of overbooking

considered only the most rudimentary cases. Most importantly, they did not

take into account the revenue maximizing potential of price discrimination—

charging different fares for identical seats. In order to maximize yield, it is

particularly critical to price discriminate between business and leisure travelers.

That is, when ﬁlling the plane, book as many full fare passengers and as few

discount fare passengers as possible.

The implementation of a method of yield management can have dramatic

effects on an airline’s revenue. American Airlines managed its seat inventory

to a $1.4 billion increase in revenue from 1989 to 1992—about 50% more than

its net proﬁt for the same period. Controlling the mix of fare products can

translate into revenue increases of $200 million to $500 million for carriers with

total revenues of $1 billion to $5 billion.

Though several decision models of airline booking have been developed

over the years, comparing one scheme to another remains a difﬁcult task. We

have taken a two-pronged approach to this problem, both simulating and mea-

suring a booking scheme’s proﬁtability.

In orderto simulate a booking scheme’s effect, we used the expected marginal

seat revenue (EMSR) model proposed by Belobaba [1989] to generate near-

optimal decisions on whether to accept or deny a ticket request in a given fare

class. The EMSR model accepts as input overbooking levels for each of the fare

classes that compose a ﬂight, so different policies can be plugged in for testing.

Our approach to measuring a current scheme’s proﬁtability is similar to one

used at American Airlines [Smith et al. 1992]. We compare the actual revenue

generated by a ﬂight with an ideal level calculated with the beneﬁt of hindsight,

as well as with a baseline level that would have been generated had no yield

management been used. By calculating the percentage of this spread earned by

a ﬂight employing a particular scheme, we are able to gauge the effectiveness

of different booking schemes.

It is our hope that these models will prove useful in evaluating your airline’s

overbooking policies. Simulations should provide insight into the properties of

an effective scheme, and measurements after the fact will help to provide perfor-

mance benchmarks. Finally, while it may be tempting to increase overbooking

levels in order to compensate for lost revenues in the post-tragedy climate, our

results indicate this will probably hurt long-term proﬁts more than they will

help.

Cordially,

Michael P. Schubmehl, Wesley M. Turner, and Daniel M. Boylan