11

Overbooking

Overbooking occurs whenever a seller with constrained capacity sells more units than he has available (or believes he will have available). The reason that sellers engage in such a seemingly nefarious practice is to protect themselves against no-shows and cancellations. A cancellation is defined as a booking that a customer terminates by notifying the seller at some point prior to the service date. A no-show occurs when a buyer with a booking does not cancel but simply fails to show up.

American Airlines estimated that about 50% of its reservations resulted in either a cancellation or a no-show (Smith, Leimkuhler, and Darrow 1992). Without overbooking, many of these cancellations and all of the no-shows would result in an empty seat—even when there are other customers willing to fly. In this situation, overbooking becomes critical. Consider a flight with 100 seats that consistently faces demand much higher than 100. Assume that customers have a 13% no-show rate. If the airline never overbooks, it will, on average, leave with 13 empty seats on every flight while denying reservations to customers who want to fly. This would be an enormous waste. The airline would be in the same situation as a manufacturer who had a plant that could only run at 87% of capacity. Without the ability to overbook, not only would the airline lose potential revenue; it would be paying to purchase, maintain, and support huge amounts of useless capacity.

No-shows and cancellations are not only an airline issue; they are a feature of any service industry in which bookings can be canceled (or not honored) without penalty or where the penalty is small relative to the opportunity cost of the resource booked. Primary care medical appointments, for example, typically have a no-show rate of 15 –20% in the United States, and accordingly, most clinics overbook. And, of course, many of the usual revenue management industries such as hotels, rental cars, and freight transportation face similar issues. In all of these industries, overbooking is used as a way to improve capacity utilization in the face of cancellations and no-shows.

The literal-minded might argue that overbooking is not really part of pricing and revenue optimization because it does not directly affect price. However, overbooking is inextricably intertwined with capacity allocation: to determine how many seats to offer to different booking classes on a flight, we certainly need to know how many seats we will be offering in total. For that reason, it is generally considered to be an integral part of revenue management, and we treat it as such.

This chapter starts by giving a short history of overbooking. It then characterizes industries in which overbooking is used and introduces four different approaches to overbooking: a deterministic heuristic, risk-based policies, service-level policies, and hybrid policies. We see how booking limits can be determined under each policy in the case of a single price and an uncertain level of no-shows. We then examine a data-driven approach to overbooking similar to the data-driven approach to capacity allocation in Section 9.4. We consider dynamic overbooking in the face of cancellations and multiple fare classes. Finally, we look at some extensions to the basic problem and some alternatives to overbooking for managing cancellations and no-shows.

11.1 BACKGROUND

11.1.1 History of Overbooking

Overbooking is closely identified with the passenger airline industry (particularly by anyone who has had the experience of being denied a seat on an overbooked flight). From the earliest days of commercial aviation in the United States, airlines adopted the policy that a customer with a reservation could cancel at any time before departure without paying a penalty and that a customer who had purchased a ticket for a flight would not be penalized if she did not show up for that flight. As a result, an airline ticket was like money in that it could be used at full face value for a future flight or redeemed for cash. (This policy should be contrasted with Broadway shows, opera, and rock concerts, where unused tickets are generally not refundable.) This raised a problem for the airlines—how many passengers should they allow to book on each flight? If they limited bookings to the capacity of a flight, many fully booked flights would leave with empty seats. As mentioned, American Airlines estimated in 1990 that about 15% of the seats on sold-out flights would be empty because of no-shows and cancellations if they only booked up to capacity (Smith, Leimkuhler, and Darrow 1992).

By the 1960s, no-shows were becoming a major problem. According to Kalyan Talluri and Garrett van Ryzin, “In 1961, the Civil Aeronautics Board (CAB) reported a no-show rate of 1 out of every 10 passengers booked among the 12 leading carriers. . . . The CAB acknowledged that this situation created real economic problems for the airlines” (2004b, 131). As a result, the airlines were allowed to overbook. This was effective in increasing loads but, predictably, meant some passengers were refused boarding on a flight for which they held a ticket—so-called denied boardings (DBs). When a flight was oversold—that is, the number of passengers showing up exceeded the seats on the flight—the airline would pick customers to bump, that is, rebook on a later flight. If the flight was much later, the bumped passengers were provided with a meal; if it was the next day, they were provided with overnight accommodation. In addition, the airline paid a penalty to each bumped passenger. At one point this penalty was equal to 100% of ticket value. When a passenger is bumped against her will, it is known as an involuntary denied boarding. In 1966, the Civil Aeronautics Board estimated that the involuntary denied-boarding rate was about 7.7 per 10,000 boarded passengers.¹

Because airlines needed to overbook to remain financially viable, the practice became universal. The risk of being bumped from an oversold flight was seen by consumers as yet one more irritating aspect of flying, along with delayed flights and lost luggage. However, the airlines were reluctant to own up to overbooking. In the 1960s, flight controllers at American Airlines recognized that overbooking was critical to financial performance. They continued to overbook despite periodically reassuring senior management that they were not doing so. When denied boardings occurred, the flight controllers blamed them on “system error.”² Airline overbooking continued largely without constraints until 1972, when Ralph Nader was denied a boarding on an Allegheny Airlines flight. Nader sued and won a judgment of $25,000 based on the fact that Allegheny did not inform customers that they might be bumped against their will. Following this judgment, the Civil Aeronautics Board ruled that airlines must inform their customers that they engage in overbooking.

In the late 1970s, following a suggestion by economist Julian Simon (1968), the airlines began to experiment with a voluntary denied-boarding policy. In Simon’s vision, the airlines would conduct a sealed-bid reverse auction to find enough passengers willing to be bumped at different levels of compensation. While the airlines initially objected that such an auction would be impractical, ultimately, they adopted a variant of Simon’s scheme, in which an overbooked airline asks for volunteers to be bumped in return for compensation (usually a voucher for future travel). If enough volunteers are not found, the compensation level may be increased once or twice. If enough volunteers are still not found, the airline will choose which additional passengers to bump. The volunteers are termed voluntary denied boardings and those chosen by the airline involuntary denied boardings. This approach to overbooking has been successful, both from the point of view of the customers and from the point of view of airlines. Airline research shows that voluntary denied boardings are often happy to get bumped in return for compensation. Not only has it made customers happier; the volunteer policy has resulted in a drastic drop in the involuntary denied-boarding rate for major US airlines—from 7.7 in 10,000 passengers in 1985 to 0.13 per 10,000 in the third quarter of 2018. In fact, involuntary denied boardings have become almost extinct at some airlines—Delta managed to board over 37 million passengers in the third quarter of 2018 without a single involuntary denied boarding. On the other hand, voluntary denied boardings have increased substantially from a rate of about 20 per 10,000 in 1995 to 43.5 per 10,000 in the third quarter of 2018.

Overbooking is also practiced by hotels and rental car companies, although statistics on its prevalence are hard to come by, since, unlike the airlines, other industries are not required to report statistics on denied service. The typical hotel practice is to find accommodations for a bumped guest at a nearby property—preferably one in the same chain. Compensation such as a discount coupon for a future stay is sometimes (but not always) offered. In many cases, there is no consistent policy across a chain or group of hotels, and reimbursement policies are determined by each property manager. A rental car overbooking is usually experienced by the customer as a wait—a customer who arrives to find no car available needs to wait until a car is returned, cleaned, and refueled. In rare situations, a location may be so overbooked that there is no prospect of a car for every customer. In this case, the manager will either send booked customers to competitors or move cars from another location if possible to satisfy the additional demand. Again, compensation in the form of a discount coupon may or may not be offered, depending on the situation and company policy.

11.1.2 When Is Overbooking Applicable?

Overbooking is applicable in industries with all the following three characteristics.

• Capacity (or supply) is constrained and perishable, and bookings are accepted for use of future capacity.

• Customers are allowed to cancel or not show.

• The cost of denying service to a customer with a booking is relatively low.

It should be understood that the cost of denied service includes intangible elements, such as customer ill will and future lost business, as well as any direct compensation, as discussed in Section 11.1.3. If the total denied-service cost is sufficiently high, it is not in the seller’s interest to overbook, since the cost of denying service will overwhelm any potential revenue gain. For example, airlines would be unlikely to overbook at all if they had to pay a million dollars to every denied boarding.

The three characteristics just listed are the classic requirements for overbooking. Under these circumstances, companies overbook to hedge against the possibility of excessive cancellations or no-shows. However, there is another situation in which overbooking may come into play—when the amount of capacity that will be available is uncertain. Both hotels and rental car companies face this issue because of the risk of overstays and understays: Customers may stay longer or depart earlier than their reservations specify. If 10 customers depart early, then a hotel will have 10 additional empty rooms the next night. If it booked only to expected capacity, these rooms would go empty, even in the absence of no-shows or cancellations.

Television broadcasters also face a problem of uncertain capacity. Broadcasters in the United States sell the vast majority of their capacity for the season starting in September during the upfront market during the previous May. Each buyer is sold a schedule of slots and guaranteed a certain number of impressions (“eyeballs”) by the broadcaster. If the schedule sold delivers the guaranteed number of impressions (or more), then that is the end of the matter. But if the schedule does not deliver the guaranteed number of impressions, the broadcaster needs to supply the advertiser with additional slots until the guarantee is met—a practice known as gapping. But the broadcaster does not know in advance how many people will actually watch a particular show. A new show may be an unexpected dud or an unexpected hit. This is similar to the airline overbooking problem, with the difference that the broadcaster knows the demand he must meet but is unsure what the supply (impressions) will be.³

Cruise lines and resort hotels generally avoid overbooking. In these industries, the cost of denied service is simply too high. A couple who arrives at the dock with all their luggage for a two-week cruise is unlikely to be easily mollified when they find out they will not be able to board because the cruise is overbooked. Instead of overbooking, cruise lines and resort hotels manage the risks of cancellations and no-shows by a combination of nonrefundable deposits and higher prices.⁴ Most industries that sell nonrefundable bookings (or tickets) do not overbook. Theater tickets and tickets to sporting events are examples. In this case, the risk to the customer of purchasing a ticket is mitigated by the fact that bookings in these industries are transferable to others—unlike airline tickets.

TABLE 11.1

Overbooking in different industries

Table 11.1 shows the relative importance of overbooking in various revenue management industries. It can be argued that overbooking has had the greatest financial impact of any aspect of passenger airline revenue management. For example, American Airlines estimated that it achieved benefits of $225 million in 1990 from overbooking (Smith, Leimkuhler, and Darrow 1992)—more than from any other element of its revenue management program, including capacity allocation and network management. Overbooking is important for hotels and rental car companies, both of which face uncertain supply (due to overstays and understays) as well as no-shows and cancellations. It is also quite important for air freight, where no-shows and cancellations are commonplace.

11.1.3 The Cost of Denied Service

A key consideration in setting an overbooking limit—and indeed in whether to overbook at all—is the cost of denied service. This cost varies from industry to industry and depends on how customers who are denied service are treated. This varies from industry to industry and from company to company within an industry. A broadcaster that cannot meet the number of impressions he has guaranteed to an advertiser needs to provide additional advertising spots until he has fulfilled the guarantee. A rental car outlet that does not have a car available when a booked customer arrives must either ask the customer to wait until a car is available or provide a vehicle from a competing company.

In the passenger airline industry, the cost of denied service is called denied-boarding cost. In the United States, the treatment of overbooked passengers is regulated by the Department of Transportation. As of July 2004, the DOT requires that an airline with an overbooked flight first seek customers willing to take a later flight in return for compensation. As noted previously, airlines will typically increase the compensation level one or two times if they cannot find enough volunteers at the initial level. For these volunteers, the denied-boarding cost is simply the amount of compensation that the airline provides. If the airline cannot find enough volunteers, it will need to bump one or more passengers (i.e., take some involuntary denied boardings). In the United States, the Department of Transportation has specified minimum compensation that must be provided to each passenger who is involuntarily denied a boarding. As of July 2020, each person involuntarily denied boarding must be provided an alternative ticket to the destination plus additional compensation as follows:⁵

• If the arrival delay is less than one hour: no compensation

• If the arrival delay is between one and two hours: 200% of one-way fare, with maximum of $675

• If the arrival delay is more than two hours: 400% of one-way fare, with maximum of $1,350

These rules do not apply to charter flights, scheduled flights with planes that hold 30 or fewer passengers, when an airline has substituted a smaller plane for the one it originally planned to use, or when an aircraft needs to shed weight to meet weight and balance constraints. The rules are also minimum guidelines—the airlines are free to pay additional compensation if they so choose. Usually, the only additional compensation the airlines provide is meal vouchers if the delay is more than two hours, and a hotel voucher if the bumped passenger is accommodated on a flight that leaves the next day.

The airlines are unusual in that several governments have mandated a procedure and compensation level for bumping passengers. Companies in other industries are generally free to deal with denied-service situations as they see fit. However, denied-service cost in all cases includes one or more of four components:

• The direct cost of the compensation to the bumped passenger—this could be a certificate for future travel or a future hotel room night.

• The provision cost of meals and/or lodging provided to a bumped passenger.

• The reaccommodation cost of a customer who is denied service. For an airline, this is the cost of putting the customer on another flight to the same destination; for a hotel, it is the cost of alternative accommodation for the night.

• The ill-will cost from denying service. This may be hard to calculate but is usually an estimate of the expected lost future business from the bumped customer.⁶

Denied-service cost will vary depending on the situation. For a passenger airline, bumping a passenger from the last flight of the day will usually incur the additional cost of lodging her overnight. Reaccommodation cost for an airline depends on whether the bumped passenger is rebooked on one of its own flights or on a competing airline’s flight. Of course, the ill-will cost for a voluntary denied boarding is much less than for an involuntary denied boarding—in fact, in many cases, a volunteer has been happy to have the opportunity to take a later flight in return for a flight voucher—perhaps resulting in a goodwill benefit (although airlines do not consider such benefits in their overbooking calculations.) The relatively low cost of voluntary denied boardings has led to their proliferation—as noted above, the voluntary denied-boarding rate among US major carriers was 43.5 per 10,000 customers in the third quarter of 2018 as opposed to a total denied-boarding (all involuntary) rate of 7.7 per 10,000 customers in 1985.

11.1.4 A Model of Customer Booking

To describe and compare different approaches to overbooking, we initially use the following simple model of booking dynamics.

• A supplier plans to accept bookings for a fixed capacity, C.

• The supplier sets a booking limit b before any bookings arrive.

• The supplier continues to accept bookings as long as total bookings are less than the limit b. Once the limit is reached (if it ever is), the supplier stops accepting bookings.

• At the time of service (e.g., the departure time for a flight), customers arrive. Booked customers who arrive are called shows; those who fail to show are called no-shows.

• Each show pays a price of p.

• The supplier can accommodate up to C of the shows. If the number of shows is less than or equal to C, they are all accommodated. If the number of shows exceeds C, exactly C of the shows will be served, and the rest will be denied service. Shows that are denied service are each paid denied-service compensation of D > p.⁷

The supplier’s problem is to determine the total number of bookings to accept. We call this number the booking limit and denote it by b.

This model is rich enough to illustrate the fundamental trade-offs and algorithms used to determine the total booking limit. However, it makes three heroic assumptions that are relaxed in later sections.

• The model ignores cancellations by calculating the booking limit based entirely on no-shows. This makes the booking limit easier to calculate. Furthermore, it means that the booking limit b can be static—that is, it does not need to change over the booking period. If bookings can cancel prior to departure, then the optimal booking limit is likely to change over time as departure approaches. Section 11.7.1 addresses the calculation of dynamic booking limits.

• The model assumes that each customer will pay the same price p. However, as described in Chapter 9, airlines, hotels, and rental car companies all offer different prices for the same unit of capacity. This can significantly complicate the calculation of the optimal total booking limit. Section 11.7.2 addresses overbooking with multiple fare classes.

• The model assumes that only those customers who arrive (i.e., the shows) pay. Bookings themselves are costless. This is the historic airline, hotel, air freight, and rental car situation, in which bookings could be canceled without penalty and tickets were fully refundable. However, many of these industries are moving all or partway toward nonrefundable or partially refundable prices. Section 11.7.3 addresses the effect of nonrefundable or partially refundable prices.

11.2 APPROACHES TO OVERBOOKING

Once a company decides it is going to overbook, it needs to decide what it wants to achieve with its overbooking policy and how it is going to achieve it. Most companies follow one of four approaches:

• A simple deterministic heuristic that calculates a booking limit based only on capacity and expected no-show rate

• A risk-based policy that involves estimating the costs of denied service and weighing those costs against the potential revenue to determine the booking levels that maximize expected total revenue minus expected overbooking costs. A risk-based booking limit can either be calculated by explicit optimization or using a data-driven approach. We look at both approaches.

• A service-level policy that involves managing to a specific target—for example, targeting no more than one instance of denied service for every 5,000 shows

• A hybrid policy in which risk-based limits are calculated but constrained by service-level limits

The different policies are closely analogous to the different replenishment policies followed by different retailers. Some stores set their replenishment levels so as to ensure that stockouts do not exceed a certain frequency: a service-level policy. Others specifically trade off the cost of a potential stockout with the cost of holding more inventory to determine the replenishment level that maximizes expected profit: a risk-based policy. Just as retailers differ in their stocking policy, so do companies differ in their overbooking policies. For example, at one point, the Hertz rental car company used a risk-based policy to set total booking limits (Carroll and Grimes 1996), while National Car Rental used a service-level policy (Geraghty and Johnson 1997). Sections 11.3 –11.6 describe each of these four ways to calculate a total booking limit using the model of customer booking described in Section 11.1.4.

11.3 A DETERMINISTIC HEURISTIC

A hotel has observed that its historic show rate has averaged 85%. Furthermore, this rate has been consistent over time. A reasonable policy might be for the hotel to set its total booking limit b so that if it sells b rooms and experiences the average show rate, it will fill exactly C rooms. That is, it would set b such that C = 0.85b, or b = C/0.85.

This approach to calculating a total booking limit can be written as b = C/ρ, where C is capacity and ρ is the show rate. Despite its simplicity, the deterministic heuristic turns out to be a reasonable approximation to the optimal booking limit in many cases. It is still used to calculate overbooking limits by many companies in cases in which the cost of denied (or delayed) service is unclear (for example, medical clinics).

Example 11.1

For a hotel with 250 rooms and an expected show rate of 85%, the deterministic heuristic gives a booking limit of 250/0.85 = 294 rooms.

Note that applying this approach does not mean that the hotel will be overbooked 15% of the time or that 15% of bookings will experience an overbooking.

11.4 RISK-BASED POLICIES

The deterministic heuristic described in the previous section is certainly simple to calculate, but it obviously does not consider the relative costs of an additional customer versus denied service. Under a risk-based policy, the booking limit is set by balancing the expected cost of denied service with the potential additional contribution from more sales. The first step in calculating a risk-based booking limit is to specify the objective function.

11.4.1 The Risk-Based Objective Function

Denote the number of passengers who show up at departure by s. The number of shows is a random variable that depends on both the booking limit and the total demand for bookings. Since each show pays price p, total revenue is p × s. If shows exceed capacity, then the supplier must deny service to s – C customers. Each customer denied service results in a denied-boarding cost of D. For the moment, we assume that this denied-boarding cost is the same for each passenger, which means that denied boardings are either all voluntary or all involuntary. The total denied-boarding cost is 0 if s ≤ C and is D(s – C) if s > C. The net revenue is then

(Recall that (s – C)⁺ denotes the maximum of s – C and 0.) A company pursuing a risk-based policy wants to set its booking limit so as to maximize the expected value of net revenue as defined in Equation 11.1, where the number of shows is a random variable that depends on the booking limit, which the company can choose.

Total revenue as a function of the number of shows is plotted in Figure 11.1. Revenue increases linearly until the capacity limit is reached, at which point it begins to decrease. Two things are apparent immediately from Figure 11.1. First, the number of shows will always be less than or equal to the booking limit, so it is never optimal to set the booking limit less than the capacity. Thus, we know that the optimal booking limit b* must satisfy b* ≥ C. Second, if the price is higher than the denied-boarding cost (that is, p > D), net revenue would continue to increase even when shows exceed the booking limit. In this case, the seller should accept every booking and set b* = ∞. Since this case is not very realistic, we assume that D > p.

Figure 11.1 Net revenue as a function of shows.

Calculating the optimal risk-based booking limit is complicated by the fact that the number of shows is a function of three different factors:

• The booking limit b

• The total demand for bookings, d

• The number of bookings that ultimately show, s

We are interested in the number of bookings at departure, which we denote by b_D. Bookings at departure is the minimum of the booking limit and the demand for bookings—that is, b_D = min(d, b). The total number of shows is the number of bookings at departure minus no-shows—that is, s = b_D – x, where x denotes the number of no-shows. We denote the show rate, ρ, as the fraction of bookings at departure we anticipate will show—that is, ρ = E[s/b_D]—while the no-show rate is the fraction of bookings at departure we anticipate will not show—that is, 1 – ρ. Airline no-show rates typically range between 10% and 20% for major airlines; however, there is significant variation. In general, international and transcontinental flights have much lower no-show rates than do shorter domestic flights. Bad weather can cause no-show rates to soar to 30% or more. Resort hotels tend to experience lower no-show rates than business hotels, and cruise lines have very low no-show rates.

11.4.2 Modeling Shows

Risk-based models of overbooking all require a probabilistic representation of no-show behavior. The simplest assumption is that each booking has an identical probability, 0 < ρ ≤ 1, of showing and that show decisions are independent. Then the number of shows given n bookings follows a binomial distribution.⁸ Let g(s|b) be the probability of s shows given a booking limit of b—which also means b bookings at departure. Then

with mean E[(s|b)] = ρb and variance var[(s|b)] = ρ(1 – ρ)b. Under these assumptions, the number of no-shows x will also follow a binomial distribution with parameters 1 – ρ and b. More information on the binomial distribution can be found in Appendix B.

Figure 11.2 Distribution of shows given 120 bookings. (A) Probability density function for different show rates; (B) corresponding cumulative distribution functions.

The density function of shows is given in panel A of Figure 11.2 for n = 120 bookings and show rates of 80%, 90%, and 95%. Panel B of Figure 11.2 gives the corresponding cumulative distributions. Each cumulative distribution shows the probability that shows will be less than x, given 120 total bookings. This can be interpreted as the probability that a flight with x seats will be overbooked if it has 120 bookings at departure, given different no-show rates. Panel A shows that both the mean and the standard deviation of the number of shows depend on the show rate. The mean number of shows is the show rate times the number of bookings: 96, 108, and 114 for show rates of 80%, 90%, and 95%, respectively.

Notice that the bulk of the probability on shows for any show rate between 80% and 95% lies between 80 and 110 when there are 120 bookings at departure. Thus, for a show rate of 80%, it is almost certain (a 99.97% chance, to be exact) that the number of shows will be between 80 and 110. We can use panel B of Figure 11.2 to estimate the probability that we will not have an oversold flight if we have 120 bookings at departure for aircraft with different seating capacities. As shown, if we have 120 bookings for a flight with 100 seats, we will almost certainly have at least 1 denied boarding if our show rate is 90% or 95%. On the other hand, we will only have about an 8% chance of being oversold if the show rate is 80%. These types of relationships are critical in determining the optimal booking limit.

11.4.3 A Simple Risk-Based Booking Limit

The decision tree approach can be used to derive the conditions for an optimal total booking limit in a fashion similar to the way it is used to derive the condition for an optimal protection level in Section 9.1.1. Recall that capacity is C, the price is p, and the denied-service cost is D, with D > p. We define F (b) as the probability that bookings will be less than or equal to b, and (s|b) as the number of shows given that bookings are b.

Figure 11.3 Overbooking decision tree.

Figure 11.3 illustrates how the overbooking decision in this case can be illustrated as a decision tree in a format similar to the capacity allocation decision tree in Figure 9.1. Here, the decision is whether to increase the booking limit from b to b + 1. If the booking limit is increased but there is no additional booking, then there is no change in total revenue—this is the lowest branch on the tree. If there is an additional booking that no-shows, then there is also no change in total revenue—this is the top branch on the tree. If the booking shows, there are two possibilities: if shows given b are less than C, then the additional booking will result in an additional fare p, and if shows given b are greater than or equal to C, then the additional booking will result in a fare minus the denied-boarding cost, or p − D. Rolling back the decision tree and setting the marginal cost to zero gives the optimality condition

where b* is the optimal risk-based booking limit.

The condition in Equation 11.3 is formulated as an equality, but because the booking limit is discrete, it is unlikely that there is a value of b for which Equation 11.3 holds exactly. A way to account for the discrete nature of the booking limit is to start with the case when the booking limit is set to capacity—that is, b = C—and then sequentially increase the booking limit by increments of one seat. Assume that we increase the booking limit by one seat so that b = C + 1. Let us assume that demand is very high relative to capacity, so that we will always receive another booking when we increase the booking limit by one. If this booking does not show—which will happen with probability 1 – ρ—there is no impact on revenue at all. If the booking does show—which happens with probability ρ—there are two possibilities. The first possibility is that all C of the other bookings show, in which case we have a denied boarding with associated cost p – D. The second possibility is that at least one of the C bookings does not show, in which case we can accommodate the new booking and gain a payment of p. Note that the probability that all C of the initial bookings will show is equal to ρ^C, and thus the expected change in revenue from increasing the booking limit from C to C + 1 is

Here, ΔR(C, C + 1) denotes the expected total revenue change from changing the booking limit from C to C + 1. Overbooking by at least one seat will increase expected revenue if the term on the right side is greater than 0 or, equivalently, if

Example 11.2

An airplane has 100 seats and a historical show rate of 90% and faces very high demand for the flight. The fare is $250 and the denied-boarding cost is $500. In this case, =  ..55 and ρ^C = .9¹⁰⁰ = 0.000027. Given that condition 11.4 is satisfied, it is profitable for the airline to overbook by at least one seat. The increase in expected revenue from increasing the booking limit from C to C + 1 is ΔR(C, C + 1) = .9 × [$250 – .000027 × $500] = $224.99.

Example 11.2 illustrates the strong economic incentive for airlines and other sellers with constrained capacity to overbook. With a 90% show rate, the probability that a departure with 100 seats that is booked to capacity will leave with at least 1 empty seat is 99.997%. In this case, the denied-boarding penalty that would be required to make it unprofitable for the airline in Example 11.2 to overbook is much larger than the likely actual denied-boarding cost (see Exercise 7).

We have seen how to determine if it is profitable to overbook by at least one seat, but the question remains of how to find the optimal booking limit—the one that will maximize expected revenue. By extending the logic from before, we can write

where ΔR(b, b + 1) is the change in expected revenue from increasing the booking limit from b to b + 1, Pr{(s|b) < C } is the probability that the shows given the booking limit b are less than the capacity C, and Pr{(s|b) ≥ C } = Pr{(s|b) < C } is the probability that the shows given the booking limit b are greater than or equal to C.

We can rearrange Equation 11.5 to derive the relationship

That is, expected revenue will always increase as long as the probability that shows are less than capacity is less than the ratio of the price to the denied-boarding cost, which means that we can start by setting the booking limit equal to capacity and then sequentially increase the booking limit by one and test against condition 11.6. We stop when increasing the booking limit by another seat would lead to a booking limit that violated 11.6. This suggests the following algorithm for computing the optimal booking limit:

Simple Risk-Based Overbooking Algorithm

1. Set b = C.

2. Compute Pr{(s|b) ≥ C }.

3. If set b* = b and STOP.

4. Otherwise set b ← b + 1 and go to step 2.

This algorithm will find the booking limit b* that maximizes expected revenue. It starts by setting b = C. For the current value of b, it determines the change in revenue that would occur by increasing b by 1. The optimal booking limit is the minimum value of b for which increasing it by 1 would lead to a decrease in revenue.

The results so far can be summarized as follows: The optimal booking limit when demand is much higher than capacity is the smallest value of b for which

Example 11.3

Consider a flight with 100 seats, a fare of $120, and a denied-boarding cost of $300. Then, p/D = 0.4. Assume that the probability that each booking will show is .92. Then, Table 11.2 shows the values of Pr{s|b}, passenger revenue, expected denied boardings, expected denied-boarding costs, and expected net revenue for values of the booking limit b from 100 to 109. The optimal booking limit is b = 108, which satisfies the condition for an optimal booking limit.

The only part of the algorithm not yet discussed is the calculation of the probability Pr{(s|b) ≥ C}. For a given value of b, this is the complementary cumulative binomial function. Given a booking limit of b, Equation 11.2 gives the probability of s shows for any value of s < b. The probability that s is greater than or equal to C for some value of b ≥ C can be found by summing the individual probabilities—that is,

This can be a bit of a pain to calculate; however, standard cumulative binomial distribution tables enable the required values to be quickly accessed. Perhaps more conveniently, for sufficiently large values of b, the cumulative binomial distribution can be approximated by the cumulative normal distribution. Specifically, the binomial distribution in Equation 11.7 has mean ρb and standard deviation Under appropriate conditions, we can use the normal approximation:

TABLE 11.2

Calculating booking limits for Example 11.3

NOTE: DB = denied boarding.

This is quite convenient since it allows us to use standard normal distribution tables to estimate the probability. However, the approximation is only valid within certain bounds. A common rule of thumb is that the approximation in (11.8) is only valid if (1 – ρ)C > 9; that is, the no-show rate times the capacity is greater than 9. For a departure with 150 seats and a typical no-show rate of .1 or so, we would have (1 – ρ)C = 15, which meets the criterion. For much smaller flights (or hotels) or much higher no-show rates, the normal approximation may not be valid and tables of the binomial distribution may be needed to calculate the overbooking limit.

Like the two-class booking limit problem discussed in Section 9.1.4, the problem of setting a risk-based overbooking limit has a close relationship to the newsvendor problem. Recall that the solution to the newsvendor problem requires ordering an amount of inventory Y so that

where U is the underage cost, O is the overage cost, and U/(U + O) is the critical fractile or critical ratio. In setting a risk-based booking limit b, we are determining how many bookings to order—that is, the total number of bookings to allow. The underage cost is the opportunity cost of an empty seat—that is, p—and the overage cost is the denied-boarding fee for a show—that is, D – p. Therefore, the critical ratio is p/D. The event that triggers an overage cost is “shows exceeding capacity,” which in our simplified model is Pr{(s|b) ≥ C }. Thus, Equation 11.3 is equivalent to the risk-based model.

11.4.4 A Risk-Based Model with Demand Uncertainty*

To make the approach to overbooking more realistic, we need to consider the fact that the demand for a flight is not infinite. In this case, increasing the booking limit from b to b + 1 will only result in an additional booking if demand is greater than b and the additional booking shows. Let f(d) be the probability that booking demand is exactly equal to d. The cumulative distribution F(d) = f(1) + f(2) + . . . + f(d) is the probability that demand is less than or equal to d, and the complementary cumulative distribution function, F̄(d) = 1 – F(d) is the probability that the demand for bookings is greater than d. If we increase the booking limit from b to b + 1, the probability that we will experience an additional booking is F̄(b).

For a given booking limit, the expected number of denied boardings will be given by E[(s|b) – C]⁺, where (s|b) is the number of shows given booking limit b. Thus, the change in total expected revenue from increasing the booking limit from b to b + 1 is

We can see that ΔR(C, C + 1) = pF̄(C) – DE[(s|C + 1) – C]⁺. But E[(s|C + 1) – C]⁺ = F̄(C)ρ^{C + 1} so that ΔR(C, C + 1) = F̄(C)(p – Dρ^{C + 1}). This will be greater than zero if F̄(C) > 0 and if condition 11.6 holds. This means that, even when demand is uncertain, there is still a strong motivation to set a booking limit higher than capacity—that is, to overbook.

The optimal booking limit with demand uncertainty is the smallest value of b for which ΔR(b, b + 1) defined in Equation 11.9 is less than zero. This can be computed iteratively starting from b = C + 1 as in the previous model, and it can also be approximated numerically.

11.4.5 A Data-Driven Approach

The approaches explained in Sections 11.4.3 and 11.4.4 can be described as forecast and optimize because they both start with probabilistic forecasts of demand and shows given demand and then optimize to find the booking limit that maximizes total expected revenue from a flight, including denied-boarding costs. In the spirit of the approach to capacity allocation described in Section 9.4, we can consider a data-driven approach to overbooking. Assume that we are trying to determine the booking limit to apply to a particular flight. We assume (not unreasonably) that the same flight has been operated at the same time to the same destination with the same equipment for some time in the past. We also assume, somewhat less reasonably, the total booking demand for every historical departure of the flight—that is, how many bookings would occur if no booking limit had been applied. Finally, we assume, very unrealistically, that we know how many of the bookings would show for every possible booking limit. This is not unreasonable for booking limits less than those applied historically because the airline can observe which passengers showed and which did not. But it is unrealistic to assume that an airline would know who would show and who would not for bookings it did not accept. In short, for any booking limit b that could have been applied to flight t, we know the number of bookings that would show at departure t—denote this by s_t(b). Note that s_t(b) is a nondecreasing function of b. Assume that the airline has observations for historical departures operated on day t = 1, 2, . . . , T and it is looking to determine the booking limit for the departure scheduled for day T + 1. As before, we assume that the price for a ticket on this departure is p, the capacity is C, and the denied-boarding cost is D.

We can compute the net revenue that we would have achieved from departure t if it had capacity C and we had applied booking limit b with b ≥ C as

If we applied the same booking limit to all of the historic departures, the average net revenue would have been

Under the data-driven approach, we would choose the booking limit for departure T + 1 that maximizes R̄(b)—that is, arg max R̄(b). The idea is illustrated in Example 11.4.

Example 11.4

Senilria Airlines runs a 20-seat flight from San Francisco to San Bernardino, California, every Monday morning at 10:00 a.m. It has operated this flight for the last 10 weeks and did not apply any booking limits, which allowed it to observe the show/no-show behavior of every booking. Table 11.3 shows the order of bookings for each departure of the flight and whether each booking showed; a value of 1 indicates that the booking showed, a value of 0 indicates that the booking did not show, and a dash indicates no booking. Thus, departure 1 had 30 bookings of which 26 showed and departure 3 had 16 bookings of which 14 showed. On the basis of this history, Senilria wants to determine the booking limit that would maximize expected revenue from the next departure given a fare of $200 and a denied-boarding cost of $300.

Table 11.4 shows the number of shows that each departure would have experienced given levels of the booking limit b from 20 to 26. Booking limits above 26 do not need to be considered because at a limit of 26, every departure with at least 20 shows is full. Finally, Table 11.5 shows the net revenue that would be achieved for each flight. Based on this history, the value of b that would maximize expected revenue is b* = 23 with a corresponding expected revenue of $3,580. This can be compared with the expected revenue from not overbooking of $3,340, a gain of $240 or a 7.2% increase.

TABLE 11.3

Bookings and no-shows for Senilria Airlines flight

TABLE 11.4

Shows per historic flight for different booking limits

TABLE 11.5

Net revenue per flight and average revenue for Senilria Airlines departures in Example 11.4

While more than 10 historical observations would typically be required, Example 11.4 illustrates the strength of the data-driven approach: it enables us to go directly from the underlying data to the decision without the need to make assumptions about underlying distributions or estimating coefficients. The approach does not require independence of shows and could easily be adapted to the case of multiple-person bookings. Furthermore, it will adapt over time to changes in the marketplace.

The shortcomings of the approach are also evident. In particular, it requires information on all bookings and shows that is generally not available. An airline can fully observe which of its bookings show, but it cannot observe whether bookings it did not accept would have shown. In fact, once a departure has reached its booking limit, it is not usually possible to determine how many additional customers would have booked, much less which of those would have shown.

One way to overcome the information shortage is through experimentation. Senilria could set the booking limit to 26 for several departures to observe the corresponding pattern of shows. This has a cost—based on the information in Table 11.5, overbooking at 26 costs an average of $80 per flight relative to not overbooking at all, and it costs $320 relative to the optimal overbooking limit of 23. This is a classic trade-off between exploration and exploitation; the challenge in using a data-driven approach in this setting is to experiment periodically by setting the booking limit artificially high for some departures to observe the pattern of shows and then use that information to set the optimal booking limits for future departures. Periodic experimentation is required to ensure that the underlying pattern of demand has not changed in a way that would imply a different limit.

11.5 SERVICE-LEVEL POLICIES

In the absence of any other considerations, properly calculated risk-based booking limits maximize expected short-run profitability. From this, it would seem to follow that risk-based booking limits would be universally used. However, this is not the case. Many airlines and other overbookers do not explicitly trade off denied-boarding costs and customer revenue to set booking limits. Rather, they try to determine the highest overbooking limit that keeps denied-service incidents within management-specified levels. Reasons that a company might prefer a service-level policy over a risk-based policy include the following.

• Some components of denied-service cost, such as ill will, might be viewed as difficult or impossible to quantify. In view of this, management might consider a service-level policy to be safer than a risk-based policy.

• Risk-based booking limits can lead to wide variation in booking limits—and potential numbers of denied boardings—from flight to flight. Under a risk-based policy, an airline might set overbooking levels ranging from 10% to more than 50% of capacity for different flights departing from the same airport during the day. Instead of accepting this wide variation, the airline might be comfortable with simply setting a constant overbooking limit over all flights to smooth staffing needs and to ensure that no single flight ever experiences a massive overbooking situation.

• Corporate management may feel that a risk-based booking limit calculation is a mathematical black box that they cannot understand and do not have confidence in. On the other hand, service-level limits are easy to understand, the results are easy to measure, and they give comfort that denied-service levels will not be out of line with those experienced by competitors.

Whatever the reason (or combination of reasons), service-level policies are commonplace. Examples of companies that use (or have used) service-level policies include airlines such as American (Rothstein and Stone 1967), rental car companies such as National (Geraghty and Johnson 1997), and many hotels and resorts.

A typical service-level policy is to limit the fraction of booked customers who are denied service. For example, an airline might set a policy that the fraction of bookings that result in a denied boarding should be approximately 1 in 10,000. Recalling that (s|b) refers to shows given booking limit b and that C refers to capacity, this policy would be equivalent to setting b such that

or, equivalently, E[((s|b) – C)⁺] = 0.0001 × E[(s|b)].

An alternative service-level policy would be to specify that the number of denied-service incidents should be some specified fraction of customers served rather than of total bookings. This is the way in which airlines report denied boardings to the Department of Transportation. Under this policy, the company would set b so that

where q is the target denied-service fraction and E [min((s|b),C)]is expected boardings (accommodated customers) given a booking limit of b.

It should be noted that applying the policies implied by Equations 11.10 and 11.11 on a flight-by-flight basis (or a rental-day-by-rental-day basis) will result in conservative booking limits. That is, the fraction of denied-service incidents that will actually occur will almost certainly be less than q. This is because the booking limits calculated by Equations 11.10 and 11.11 will result in an average denied-service rate of q on flights with demand sufficiently high that the booking limit is relevant. Some flights will have such low demand that they will never sell out. Including bookings on these flights will improve the denied-service statistics at a system level.

11.6 HYBRID POLICIES

Many airlines, hotels, and rental car companies are not purists when it comes to overbooking. In many cases, they use a hybrid policy under which they calculate booking limits using both risk-based and service-level policies and use the minimum of the two limits. This allows them to gain some of the economic advantage from trading off the costs and benefits of overbooking while still ensuring that metrics such as “involuntary denied boardings per 10,000 passengers” remain within acceptable bounds—however these bounds are set.

11.7 EXTENSIONS

11.7.1 Dynamic Booking Limits

Suppliers overbook to compensate for both cancellations and no-shows. However, so far we have only considered no-shows in our calculation of booking limits. Without cancellations, a supplier can simply calculate an optimal booking limit at the beginning of the booking period and hold it constant until departure. The supplier does not need to update the booking limit or change it over time. When cancellations are factored in, the situation becomes more complex. Specifically, the optimal booking limit for a supplier who allows bookings to cancel prior to departure will change over time. In this case, the supplier needs to calculate a dynamic booking limit.

In the most general case, a supplier will face both cancellations and no-shows. This is certainly the case for airlines, hotels, and rental car companies. American Airlines has estimated that about 35% of all bookings will cancel before departure, compared to 15% of bookings at departure that will not show. While cancellation rates are typically higher than no-show rates, cancellations are less costly than no-shows since they allow the opportunity to accept a booking to fill the space freed up by the cancellation.

A common model of cancellations is to estimate a dynamic cancellation fraction r(t), where t is the number of days until departure. Assume an airline has accepted b(t) bookings at time t. Then it would expect that, on average, r(t)b(t) of those bookings will cancel, while [1 – r(t)]b(t) of them will convert to bookings at departure. With a show rate of ρ, the airline would expect that an average of ρ[1 – r (t)]b(t) of the current bookings will show. One tempting (and common) approach is to use ρ[1 – r (t)] as a dynamic show rate and to apply standard risk-based or service-based models to determine the current booking limit.

Example 11.5

An airline is using a dynamic version of the deterministic booking heuristic in Equation 11.1, in which the booking limit is set to the capacity divided by the show rate—that is, b = C/ρ, where C is the capacity and ρ is the expected show rate. The airline has an average no-show rate of 13% for a flight assigned an aircraft with 120 seats. Twenty days before departure, the expected cancellation rate for this flight is 60%. The airline therefore sets a booking limit of b = 120/[(1 – 0.6) × 0.87] = 345. Five days before departure, the expected cancellation rate is 20%, and the corresponding booking limit is b = 120/[(1 – 0.2) × 0.87] = 172.

Bookings tend to firm toward departure—the fraction of current bookings that will cancel decreases as t approaches 0. This means that r(t), the expected cancellation rate, is typically an increasing function of t. It may not, however, be a continuous function. For example, many airlines specify that certain discount tour and group bookings cannot be canceled later than 14 days prior to departure without penalty. This often leads to a booking cliff, with the number of bookings crashing dramatically on the same day as all the tours and groups simultaneously cancel their unsold allocations. The booking limit needs to adjust accordingly to reflect the fact that reservations on the books within 14 days of departure are far more likely to convert to shows than those on the books prior to that period.

A typical dynamic booking limit is shown in Figure 11.4. Here, the heavy curve shows the total booking limit at each time before departure, while the lighter line shows actual bookings. The booking limit starts out high to allow for the possibility of a high proportion of future cancellations. As the departure date of the flight approaches, the booking limit decreases as bookings become more firm. Bookings initially start out low and increase toward departure. In Figure 11.4, total bookings hit the booking limit at time A. At that point, the airline stops accepting bookings. Note that for some period, accepted bookings can actually exceed the booking limit. In Figure 11.4, a sufficient number of cancellations occur so that bookings fall below the limit at time B. At time B, the airline starts accepting bookings again, until the booking limit is reached again, at which time the flight would again be closed. In the figure, the flight closes three times and reopens twice.

Figure 11.4 Example of a dynamic booking limit.

The difference between the booking limit at departure and the capacity of the aircraft is the amount the airline has overbooked specifically to accommodate no-shows. It is where the airline would like bookings to be, considering future cancellations and no-shows (assuming the airline is following a risk-based overbooking policy). If the airline has done a good job managing bookings over time and gotten a bit lucky, it will reach this point. Of course, demand may be so low that bookings never reach the limit. Or they may reach the limit at some point, but a higher or lower cancellation rate than expected may result in bookings at departure being higher or lower than the ideal. Cancellations add yet another complication to the already dicey game of managing bookings to maximize profitability.

Figure 11.4 illustrates an important aspect of dynamic booking limits: the booking limit tends to be high early on, just when actual bookings are likely to be low. Except for flights that have extraordinary levels of early-booking demand, the total booking level is not likely to be binding when there is still a long time until departure. This means that using computational resources to calculate exact total booking limits that have little chance of being binding and to update them frequently months before departure is not necessary. However, as departure approaches, the optimal booking limit decreases and the number of bookings generally increases. This means it becomes more and more worthwhile to compute an exact booking limit as departure approaches. Typically, an airline may only update the total booking limit for a flight monthly when it is six months or more until departure. As departure approaches, the airline will increase the frequency of recalculation. Most airlines will be recalculating the total booking limit every day during the last week before departure. Similar approaches are used by hotels, rental car companies, freight carriers, and other suppliers that practice overbooking.

11.7.2 Overbooking and Capacity Allocation

The models we have studied so far have been based on the assumption of a single fare class. However, as Chapter 9 shows, the same unit of capacity can often be sold to customers from many different fare classes at different prices. If customers are booking in reverse fare order and bookings can cancel or not show, then the airline faces a combined overbooking and capacity control problem. Say we have n fare classes, with p₁ > p₂ > ⋅⋅ ⋅ > p_n with class n booking first, followed by class n – 1, and class 1 booking last. The problem faced by the airline is the same in spirit as the capacity allocation problem treated in Chapter 9—that is, the airline needs to set booking limits (or, equivalently, protection levels) for each fare class. The difference now is that these booking limits need to incorporate the fact that some of the bookings from each class are likely to cancel or not show.

The problem of finding optimal booking limits for multiple fare classes—the combined overbooking and capacity allocation problem—is extremely difficult to solve in general. It is complicated by the fact that not only are different booking classes likely to have different fares, but they are also likely to have different cancellation and no-show rates. In fact, the general problem of combining overbooking with capacity allocation is so difficult that many companies use some variant of the following heuristic.

Combined Overbooking and Capacity Allocation Heuristic

1. Compute a total booking limit for the entire plane using either the deterministic heuristic, a risk-based approach, or a service-level approach. Call this limit B. No matter what approach is used, B will be greater than or equal to capacity.

2. Use a capacity allocation approach such as EMSR-a or EMSR-b to determine protection levels. (Recall that optimal protection levels are not based on capacity.)

3. From the protection levels calculated in step 2, determine booking limits for each fare class as if the capacity were equal to B.

4. Update B and the protection levels as bookings and cancellations occur.

Example 11.6

An airline is selling three fare classes—full fare, standard coach, and discount—on a flight with 100 seats. Three weeks before departure, the airline sets a total booking limit of 115. Using EMSR-b, the airline calculates protection levels of 35 for full fare and 60 for full fare and standard coach. The airline then sets booking limits of 115 – 60 = 55 for discount bookings, 115 – 35 = 80 for standard coach, and 115 for full fare.

A question not yet addressed is how the total booking limit B should be calculated. The risk-based approaches discussed in Section 11.4 assume that the same fare will be received for each additional seat that is filled. This is the right assumption when there is a single fare. When there are multiple fares, it is not so clear what the increased revenue would be from filling an additional seat. A common heuristic is to use an estimated fare that is a weighted average of the fares, where the weights are proportional to the mean demands in each fare class. In other words, the average fare is

where μ_i is the mean demand in fare class i. Substituting p into the risk-based algorithms will enable the calculation of a booking limit.

This approach—sometimes called the pseudocapacity approach—is widely used. It has the distinct advantage of allowing the supplier to mix and match overbooking and capacity management approaches; any approach to calculating the total booking limit (e.g., risk based or service level) can be combined with any approach to calculating the booking limits for different fare classes. Research has shown that it generally provides a good solution as long as no-show rates do not vary widely among classes—however, it is by no means optimal.

An alternative to the pseudocapacity approach would be to use a data-driven approach such as that described in Section 11.4.5. In theory, this would allow us to determine a booking limit that maximizes expected revenue without making assumptions about the mix of customers that would be accepted or rejected. Note, however, that the number of decisions that need to be considered is much greater because we need to update the dynamic booking limit over time, which implies that much more experimentation would be required to understand the implications of different limits at different times. Developing hybrid approaches that enable taking advantage of experimentation but use realistic structural assumptions is a promising area of research.

11.7.3 Other Extensions

We have assumed that the denied-boarding cost is a constant. In reality, the denied-boarding cost per passenger is likely to be an increasing function of the number of oversales. Consider a flight that is oversold by 15 passengers. The airline might be able to persuade five people to volunteer to take another flight for $200 apiece. It might convince another seven volunteers for $600 apiece. It then may have to choose three more involuntary denied boardings, with an associated cost of $850 apiece (including ill-will cost). In this case, total denied-boarding cost is the piecewise linear function of the number of oversales shown in Figure 11.5.

An airline cannot know in advance exactly how many volunteers it will induce at each level of compensation for a particular flight departure. This means not only that the denied-boarding cost is not constant but also that it is a random variable. Increasing the booking limit b leads to an increase in the expected number of denied boardings E [((s|b) – C)⁺], which in turn leads to an increased expected denied-boarding cost per passenger. Instead of a constant value of denied-boarding cost D, the airline needs to calculate an expected denied-boarding cost as a function of the booking limit. Increasing denied-boarding costs tend to reduce the optimal booking limit relative to constant denied-boarding costs.

Figure 11.5 Nonlinear denied-boarding cost.

Figure 11.6 Calculating the optimal total booking limit with a no-show penalty.

We have also assumed that tickets are totally refundable and that no-show customers do not pay any penalty. This was standard practice in the airline industry for many years. However, airlines, hotels, and rental car companies are increasingly selling partially refundable bookings and charging penalties for no-shows and cancellations. A partially refundable ticket or no-show penalty changes the underlying economic trade-offs and therefore also changes the optimal booking limit. Assume the airline charges a penalty of α times the price for each no-show, where α < 1. Thus, if α = 0.25, the airline would collect $25 for a passenger who purchased a $100 ticket but did not show. The marginal impact of changing the booking limit in the case when the airline collects αp from each no-show is shown in Figure 11.6. This tree is identical to the tree in Figure 11.3, with the exception that the top branch, which represents an additional no-show from increasing the booking limit by 1, now has a payoff of αp. We can use this tree to calculate the booking limit that maximizes expected net revenue using the same approach as before (see Exercise 1).

Finally, in many industries the risk of no-shows and cancellations is counterbalanced to some extent by the possibility of walk-ups: customers without a reservation who show up just prior to departure wanting to buy a ticket.⁹ Companies sell capacity to walk-ups only if it is available after all shows are accommodated. Since walk-up customers have not made bookings, they are not entitled to payment if they are not served. Walk-ups are highly desirable customers: not only can they be used to fill seats that would otherwise go empty, but they can usually be charged high prices. Thus, hotels will often charge walk-ups the rack rate—even if the hotel is not close to being full—under the belief that a walk-up customer has a high willingness to pay since the cost of finding an alternative is relatively high.

It is easy to see that the possibility of walk-ups reduces the optimal total booking limit. If a hotel knew that it would have 10 high-paying walk-up customers arriving every day, it would set its booking limits as if it had 10 fewer rooms. Of course, like all elements of future customer demand, the number of walk-ups is uncertain at the point when the booking limit needs to be set. However, in cases where walk-ups are important, companies will forecast expected walk-up demand and incorporate its effect explicitly in calculating booking limits (see Exercise 3).

Each of these complications adds to the complexity of calculating the total booking limit. However, in any circumstances, the basic idea is the same. We want to find the booking limit such that the additional revenue we would expect from increasing the booking limit balances the additional expected denied-boarding cost we would incur.

11.8 MEASURING AND MANAGING OVERBOOKING

Prior to the deregulation of the airlines, airline management focused on load factor as the key performance indicator, both for individual flights and on a system level. The load factor of a flight is the ratio of the number of passengers on a flight (its load) to its capacity. A flight departing with 100 seats and 86 passengers has an 86% load factor. Load factor can be measured at any level, from a single flight to a market served by many flights to an entire airline. Up into the 1970s and even beyond, load factor was the main metric that airlines tracked. Marketing programs were evaluated based on changes in load factor—a program that increased load factors was successful, one that did not increase them was ineffective. Persistently low load factors on a flight were considered a signal that a smaller aircraft should be assigned to the route or that the flight should be rescheduled to a different time or even be dropped.

Unfortunately, load factor fails as a measure of overbooking policy. The booking policy that maximizes load factor is simple—accept every booking request. This may result in hundreds or thousands of denied boardings, but the planes will be full and load factors will be sky-high.

To avoid the hordes of denied boardings that would result from an unconstrained booking policy, airline management often instructed booking controllers to minimize denied boardings. This created a basic conflict: Any booking policy that increases load factor is likely to result in an increase in denied boardings, and policies that decrease denied boardings are likely to reduce load factors. As we have seen, an optimal risk-based booking policy neither maximizes load factors nor minimizes denied boardings. Rather, it finds the booking limit that best balances the risks of spoilage with the risk of denied boardings, to maximize expected net revenue. Therefore, airline overbooking policies are often evaluated on two metrics:

• Spoilage rate: the number of empty seats at departure for which a booking was denied, expressed as a fraction of total seats on the departure¹⁰

• Denied-boarding rate: the number of denied boardings, expressed as a fraction of total shows for a departure (involuntary and voluntary denied boardings are usually tracked separately)

Both the spoilage rate and the denied-boarding rate need to be measured against targets. These targets can be calculated with the same forecasts used to calculate the booking limit in the first place.

Example 11.7

An airline sets a total booking limit for a flight with a 100-seat aircraft, expected demand of 110 passengers with a standard deviation of 55, a no-show rate of 10%, and a discount fare of $200 and a full fare of $350. If we are using the optimal risk-based booking limit calculated in Section 11.4.4, we would expect a spoilage rate of about 0.06 and a denied-boarding rate of about 0.02. Of course, the spoilage and denied-boarding rates for a specific flight departure will most likely be different, but the average overall flight departures with the same characteristics should be close to 0.06 and 0.02. If the rates are significantly different, we should seek the reasons why. Are our demand or no-show forecasts consistently in error? Are booking controllers intervening too often to raise or lower the booking limits?

It should be stressed that performance needs to be evaluated against targets in both directions. For example, it might seem that a denied-boarding rate of 1% would indicate better performance than 2%. But if the lower denied-boarding rate was achieved at the cost of a higher spoilage rate, it may mean that our overbooking policy was not sufficiently aggressive and we lost profitable opportunities to fill additional seats. If the lower denied-boarding rate did not coincide with a higher spoilage rate, we still need to understand the reason why it differed from our target. It may mean that our demand and no-show forecasts need to be adjusted for future flights.

11.9 ALTERNATIVES TO OVERBOOKING

Needless to say, involuntary denied service is not popular with customers. Customers hate arriving weary at their hotel at midnight only to be told that the hotel is overbooked and they will be bused to another hotel 10 miles away. Overbooking is also unpopular with suppliers. Not only does it create unhappy customers; it is a continual source of stress for gate agents, desk clerks, or whoever needs to deliver the bad news to the customer that she is going to be denied service. Airline gate agents often feel as if the sole purpose of overbooking is to make their lives more difficult, and airline revenue managers spend a considerable amount of time explaining to them the need for overbooking and the financial benefits it brings. Furthermore, overbooking as a policy is inefficient—an airline can only find out how many of its customers are sufficiently flexible to take an alternative flight just prior to departure. If an airline knew earlier that a high fraction of its bookings were flexible, they would be more willing to overbook than if all of their bookings were inflexible.

In this environment, it is not surprising that airlines and other overbookers have actively searched for alternative ways to manage the uncertainty intrinsic in allowing customers to cancel and not show other than waiting until the last few minutes before departure. The following are some of the approaches that have been utilized or proposed:

• Standbys. A standby booking is one that is sold at a discount and gives the customer access to capacity only on a space-available basis. Customers with standby tickets arrive at the airport and are told at the gate whether they will be accommodated on their flight. If they cannot be accommodated on their flight, the airline books them at no charge on some future flight (usually also on a standby basis).

• Bumping strategy. If the fares for late-booking passengers are sufficiently high, an airline could pursue a bumping strategy—that is, if unexpected high-fare demand materializes, the airline would overbook with the idea that it can deny boardings to low-fare bookings in order to accommodate the high-fare passengers. For a bumping strategy to make sense, the revenue gain from boarding the full-fare passenger must outweigh the loss from bumping the low-fare booking, including all penalties and ill-will cost that might be incurred. Historically, airlines were reluctant to overbook with the conscious intent of bumping low-fare passengers to accommodate high-fare passengers. However, with the average full fare now equal to seven or more times the lowest discount fare on many routes, the bumping strategy may make more economic sense.

• Flexible products. A flexible product guarantees that the buyer will receive one out of a set of closely substitutable services. The seller decides the exact service close to (or at) the time of fulfillment on the basis of demand information acquired during the booking period (Gallego and Phillips 2004). An example would be purchasing a nonstop coach ticket from London to New York City on a date three weeks from today from an airline that has nonstop departures at 9:00 a.m., noon, and 5:00 p.m. The night prior to departure, the airline would contact the customer to inform her which flight she has been assigned to. Similarly, a traveler could book a room in Chicago from a large hotel chain (such as Marriott) that has multiple properties in Chicago. The night before arrival, the traveler would receive a text informing her which property she will be staying at. Typically, the flexible product would be sold at a discount to the fixed product in which the exact flight or exact property is specified.

One advantage of the flexible product is that it allows the seller to identify flexible customers prior to the date of service delivery. This enables them to better match demand to limited supply. For an airline, under standard overbooking, a customer who arrives for the noon flight cannot be offered the option of the 9:00 a.m. flight, but flexible customers on the overbooked noon flight can be shifted to the 9:00 a.m. flight. This is an advantage for both the seller and the customer over standard overbooking.

Flexible products have not been widely adopted in the airline or hotel industries. However, they are used in air freight and ocean shipping where many shippers only care about departure time and delivery time and not the itinerary taken by the cargo. They are also used by internet advertisers. The German tour operator Germanwings starts with a large set of alternatives and allows customers to pay to remove specific alternatives from the set (Gallego and Stefanescu 2012).

• Opaque products are similar to flexible products in that sellers offer customers a bundle of substitutable products (often from different sellers). Which product the customer is assigned is revealed only when she has made her purchase. Opaque selling is used in the travel industry by Hotwire and Priceline; for example, a customer can reserve a rental car from a major provider and will only learn if it is Hertz, Avis, or National after making the reservation. One rationale for companies to participate in opaque products is the desire to offer discounted products while maintaining their brand image.

• Options. A logical approach to managing the adverse effects of uncertain future events is through the use of options. It is not surprising that options have been proposed as an alternative to overbooking, although they are not widely used. Callable options for airline seats were proposed in Gallego, Phillips, and Sahin 2008. A callable option includes the option for the seller to recall the capacity at a prespecified price before the service is delivered. The callable services could either be sold at a discount or with a recall price premium to compensate the customer for the potential inconvenience of having the service recalled. For example, a customer could purchase a discount ticket for $200 with a recall option of $50. If the airline found that it had excess full-fare demand for $500 for that flight, it could call the option, in which case the customer holding the option would pay nothing but would receive a payment of $50. The benefit for the airline is that it receives a payment of $500 minus the $50 call payment, or $450 for a seat that would otherwise be sold for $200. By offering both callable options and regular seats, a seller can segment the market between flexible and inflexible customers and thereby provide a source of additional riskless revenue.

• Last-minute discounts. Historically, the price of airline bookings has tended to increase as departure approaches, as airlines seek to exploit the fact that later-booking customers tend to be less price sensitive than early-booking customers. However, increasingly airlines have been using last-minute deep discounts to sell capacity that would otherwise go unused. For example, the company Last-Minute Travel (https://www.lastminutetravel.com) specializes in selling deeply discounted capacity for flights that are nearing departure and hotel check-in dates that are only a few days in the future. To limit cannibalization, many airlines, hotels, and rental car companies only offer last-minute discounts through opaque channels. In a similar vein, classical concerts and operas often sell standing-room-only tickets at a deep discount once all seats have been sold.

• Cancellation and no-show penalties. Many airlines, hotels, and rental car companies have instituted penalties for customers who cancel or do not show. These penalties can range from 10% or less of the price all the way to 100% for a nonrefundable ticket. These penalties can significantly change the economics of overbooking. (See Exercise 1.)

Each of these approaches has drawbacks. Standby tickets usually need to be priced at extreme discounts in order to sell. Furthermore, while standbys may help reduce spoilage, they do nothing to help the situation in which the airline has accepted too many bookings and needs to deny some boardings. In fact, they make the situation worse, since both the passengers denied boarding and the standbys will be demanding seats on some future flight to the same destination.

Cancellation and no-show penalties might seem to be an obvious answer to the overbooking problem, since such penalties should decrease the number of cancellations and no-shows as well as reduce the revenue risk to airlines. However, two points need to be made. First, an airline with a cancellation penalty will still have a motivation to overbook as long as it faces a significant number of cancellations and no-shows. An airline with nonrefundable tickets may still face a combined late cancellation and no-show rate of 10% or more. In this case, the airline can still increase revenue by overbooking. Second, it is not always easy for an airline to institute cancellation or no-show penalties. Customers whose travel plans are somewhat unsure will value the ability to cancel or change their flights without penalty. Instituting a cancellation penalty may induce these customers to purchase from a competitor who does not penalize cancellations.

Flexible products, opaque products, and options appear to be attractive alternatives for managing demand to better accord with supply constraints; however, their use is currently somewhat limited save for the distribution of opaque products through suppliers such as Hotwire and Priceline.

11.10 SUMMARY

• Overbooking is the policy of selling more units of a resource than are expected to be available. It is employed as a tactic by industries in which bookings can be canceled and/or some customers book but do not show up (are no-shows), and in which the cost of denying service is not too high relative to the fare. Industries in which overbooking is common including airlines, nonresort hotels, rental cars, freight, medical clinics, and universities. It is less common or nonexistent in resort hotels and cruise lines.

• The cost of denied service consists of four elements:

• The direct cost of compensation to the customer

• The provision cost of meals or other extras

• The reaccommodation cost of providing an alternative service

• The ill-will cost from denying service

• Four general approaches to overbooking are common:

• A simple heuristic in which the capacity is adjusted by the show rate

• Risk-based approaches in which a supplier trades off the cost of additional denied-service costs with the potential of additional booking revenue to find the booking limit that maximizes expected total revenue (including expected denied-service costs). The optimal risk-based booking limit can be calculated in two ways:

• Forecast and optimize: Probabilistic forecasts of demand and shows are used within an optimization framework to determine the optimal booking limit.

• Data-driven: The optimal booking limit is based on the net revenue minus denied-service costs that would have been achieved had the booking limit been applied to similar flights in the past.

• Service-level policies in which the booking limit is set to meet a goal on the rate of denied service

• Hybrid policies in which an optimal risk-based booking limit is calculated subject to service-based limits

• The overbooking problem is further complicated by the fact that booking limits will change during the time between when a flight opens to first booking and when it departs. In general, the booking limit decreases as the flight departure date approaches because there will be fewer cancellations.

• To achieve maximum contribution, overbooking needs to be solved simultaneously with capacity allocation. One heuristic is to determine a total booking limit, including overbooking, for a flight and then use that pseudocapacity as an input to the capacity allocation approaches discussed in Chapter 9.

• Two metrics that are used to measure the effectiveness of overbooking are the spoilage rate and the denied-service (or denied-boarding) rate. Spoilage measures the seats that could have been filled but were left empty as a result of a booking limit that was too low, and denied service measures the number of passengers who showed but were denied boarding on a flight because shows exceeded available capacity.

• Because overbooking (or at least involuntary denied service) is unpopular with customers, airlines and other travel providers have experimented with alternative approaches including standbys, bumping, flexible products, opaque products, options, last-minute discounts, and penalties. Each of these has its benefits and costs relative to traditional overbooking.

11.11 FURTHER READING

The history of overbooking at American Airlines is told in Rothstein 1985. A review of the literature is given in McGill and van Ryzin 1999. Key early research papers in airline overbooking include Robinson 1995 and Chatwin 1998. Papers that discuss integrating capacity control and overbooking include Subramanian, Stidham, and Lautenbacher 1999; Feng and Xiao 2001; and Karaesmen and van Ryzin 2004. Models for overbooking in medical clinics can be found in Muthuraman and Lawley 2008 and Zacharias and Pinedo 2014.

A good overview and discussion of alternatives to overbooking, such as flexible products, opaque products, standby, and so on, can be found in Gallego and Stefanescu 2012 and the references therein.

11.12 EXERCISES

1. Solve the decision tree in Figure 11.6 to determine a formula for the total booking limit that maximizes expected net revenue when there is a no-show penalty of αp. Does the no-show penalty generally result in higher or lower booking limits than the case when tickets are entirely refundable?

2. A flight has 100 seats and a passenger fare of $130. The number of no-shows is independent of total bookings and is given by a normal distribution with a mean of 22 and a standard deviation of 15. The denied-boarding cost is $260 per denied boarding. Use a table of cumulative normal distribution values or the NORMINV function of Excel to determine the optimal booking limit in this case. Recall that the booking limit needs to be an integer.

3. Capacity, fare, denied-boarding cost, and the no-show distribution are the same as in Exercise 2. However, there is now a 0.6 probability that there will be a walk-up customer for the flight. Assuming there is a seat available on the flight after shows are accommodated, the airline will charge the walk-up customer $200. What is the optimal booking limit for this flight?

4. A flight has 100 seats and a passenger fare of $130. The denied-boarding cost is $390 per denied boarding, and the no-show rate is 0.16. Demand for this flight is extremely high; in fact, for any booking limit b < 200, bookings will always hit the booking limit. What is the optimal total booking limit in this case? What is the corresponding expected net revenue? How much does the airline gain from overbooking in this case?

5. A low-cost airline sells only nonrefundable tickets. Customers pay in full at the time of booking. If they cancel or miss their flight for any reason, no portion of the price is refunded, and they cannot board another flight without buying a new ticket. Despite this policy, the airline still experiences a no-show rate of 5%. That is, if it sells 100 tickets on a 100-seat aircraft, it will, on average, depart with 5 empty seats. Should this airline overbook? If so, what kind of policy should it adopt? If it should not overbook, why?

6. A rental car company will have 100 cars available for rent on a particular day. It expects that demand for that day will be very high, so demand is certain to be higher than 300 bookings. If it expects a 15% no-show rate, what booking level should it set if it wants to ensure that the probability that a booking will be denied service is 0.0002? (You can use the normal approximation to the binomial described in Appendix B to estimate your answer.)

7. In Example 11.2, what is the minimum value of the overbooking penalty D that would be required for the expected revenue change from overbooking by one seat to be less than 0?

NOTES

1. The figures for voluntary and involuntary denied boardings here and elsewhere in this chapter are from various editions of the Air Travel Consumer Report, published by the US Department of Transportation Office of Aviation Enforcement and Proceedings, available at https://www.transportation.gov/individuals/aviation-consumer-protection/air-travel-consumer-reports.

2. The story of “system error” is from Rothstein 1985, which provides a history of overbooking at American Airlines.

3. For more background on the television advertising market, see Phillips and Young 2012.

4. In addition, many cruise lines sell trip insurance, which will refund the price of the cruise to the buyer in case she needs to cancel.

5. For the latest DOT rules on treatment of involuntary denied boardings, see US Department of Transportation 2020.

6. In certain circumstances, the ill-will cost can be much higher. In April 2017, when United Airlines could not find enough volunteers on an oversold flight from Chicago to Louisville, Kentucky, security personnel forcibly removed a struggling passenger, Dr. David Dao, who hit his head on an armrest while he was being removed and was bleeding profusely as he was dragged out of the plane. The event was filmed by other passengers on their cell phones and immediately went viral, creating an enormous backlash toward United. United Airlines later settled with Dao for a reported $140 million (Economy 2019).

7. This booking model assumes that all shows buy a ticket. Those who are denied service pay the price p but receive denied-service compensation of D. The net denied-service cost to the supplier for each denied service is then p – D. The case in which those who are denied service do not buy a ticket but pay a fee of f can be represented in this model by setting D = p + f.

8. The assumption that no-shows are independent is often unrealistic—many bookings are for multiple individuals (e.g., a family traveling together), who tend to show or no-show together. Also, events like bad weather or extremely heavy traffic may drive large numbers of no-shows. However, a number of studies (starting with Thompson 1961) have shown that a binomial distribution is reasonable, assuming that very large groups are treated separately. Background on the binomial distribution is given in Appendix B.

9. Walk-ups are also known as go-shows in the passenger airlines and as walk-ins in the rental car and hotel industries.

10. It is important to note that only the seats on a flight for which a booking was denied were spoiled. Seats for which there was no booking request are not considered spoiled. A flight with five denied booking requests that left with seven empty seats had five spoiled seats. On the other hand, a flight with three denied booking requests that left with one empty seat had one spoiled seat.