9

Capacity Allocation

Capacity allocation is the problem of determining how many seats (or hotel rooms or rental cars) to allow low-fare customers to book when there is the possibility of future high-fare demand. Capacity allocation is particularly important to passenger airlines because many airlines have based their revenue management strategy on segmenting the market between early-booking, low-fare leisure customers and later-booking, higher-fare business customers, as discussed in Chapter 8. Capacity allocation is also an issue for any revenue management company that has the opportunity to restrict early low-price bookings in order to reserve capacity for later higher-price bookings. The techniques described in this chapter are used mutatis mutandis in many industries, including rental car companies, hotels, cruise lines, freight transportation, and made-to-order manufacturing, among many others.

We begin by analyzing the two-class model in some detail. We then move on to the multiclass problem, with an emphasis on the widely used expected marginal seat revenue (EMSR) heuristics. Next we consider the dynamic multiclass problem when fare classes are nested. We then relax the independence assumption and examine how booking limits could be set when demand in different fare classes can depend on which classes are currently open. We look at a data-driven approach that does not depend on estimating parameters of a demand distribution. Finally, we see how the performance of a capacity allocation program can be measured and evaluated.

9.1 THE TWO-CLASS PROBLEM

In the two-class capacity allocation problem, a flight (or other product, such as a hotel room night) with fixed capacity serves two classes of customers: discount customers who book early and full-fare customers who book later. Discount customers each pay a fare p _d > 0, and full-fare customers each pay a higher fare p_f > p_d. In the basic two-class model, we assume that all discount booking requests occur before any full-fare passengers seek to book. We have a limited number of seats. The static two-class capacity allocation problem is to determine how many discount customers (if any) we should allow to book. Or, equivalently, how many seats (if any) we should protect for full-fare customers.

The standard approaches to the capacity allocation problem described in this section are formulated as if the goal were to maximize expected revenue—that is, incremental costs and ancillary contribution are zero. This streamlines the discussion and is consistent with the revenue management literature. But, in reality, companies will be (or should be) maximizing expected total contribution, including incremental cost and ancillary contribution, as discussed in Section 8.8. The approaches in this section can be made consistent with maximizing total contribution by substituting net contribution wherever price or fare appears in an algorithm or equation.

The goal of two-class capacity allocation is to determine a discount booking limit—the maximum number of discount bookings that will be allowed. When there are only two classes, the protection level for full-fare bookings is equal to the capacity minus the booking limit: y = C – b, where C is capacity as described in Section 8.5. It is straightforward to calculate the booking limit given the protection level and capacity, and vice versa.

9.1.1 The Decision Tree Approach

At the heart of the capacity allocation problem is the trade-off between setting the booking limit too high and setting it too low. If we set the discount booking limit too low, we will turn away discount customers but not see enough full-fare demand to fill the plane. The plane will depart with empty seats even though we turned away bookings. This is called spoilage, since the empty seats become spoiled inventory at the moment the flight departs. On the other hand, if we allow too many discount customers to book, we run the risk of turning away more profitable full-fare customers. This is called dilution, since we diluted the revenue we could have received from saving an additional seat for a high-fare booking. The challenge of capacity allocation is to balance the risks of spoilage and dilution to maximize expected revenue.

The trade-offs in the two-class problem are shown as a decision tree in Figure 9.1 for a flight with total capacity C. F_f(x) is the probability that full-fare demand is less than or equal to x, and F _d (x) is the probability that discount demand is less than or equal to x. Assume we have currently set a booking limit of b with 0 ≤ b < C. The decision we face is whether to increase the booking limit by one seat (or, equivalently, to reduce the protection level by one seat). What would be the change in expected revenue if we increase the booking limit from b to b + 1? If discount demand d_d is less than or equal to b, there will be no effect on expected revenue. (Recall that booking classes are nested, so all of the seats that are not sold to discount customers are available to full-fare customers.) In this case, the net change in expected revenue of increasing the booking limit by one seat is 0, as shown on the top branch of the tree in Figure 9.1.

Only when discount demand is greater than b—which occurs with probability F̄ _d (b) = 1 – F_d(b)—do things get interesting.¹ In that case, increasing the booking limit from b to b + 1 results in an additional discount booking. (For simplicity, throughout the chapter, we assume no cancellations or no-shows so that the additional booking will result in a paying passenger.) The net effect on revenue depends on full-fare demand. If full-fare demand is greater than C – b, which happens with probability F̄_f(C – b) = 1 – F_f (C – b), the additional discount booking will displace a full-fare passenger. This is dilution, and the resulting change in total revenue is p _d – p_f < 0. The other possibility is that discount demand is greater than b and full-fare demand is less than the protection level, C – b. In this case, we accept an additional discount passenger but do not displace a full-fare passenger. The gain is p_d. In this case, increasing the discount booking limit has reduced spoilage.

Figure 9.1 Two-class capacity allocation decision tree.

The expected change in revenue from changing the booking limit from b to b + 1 is the probability-weighted sum of the possible outcomes, or

If the term on the right-hand side of Equation 9.1 is greater than zero, then we can increase expected profitability by increasing the discount booking limit from b to b + 1. On the other hand, if the term is less than zero, increasing the discount booking limit will lead to decreased expected revenue.

The key term in Equation 9.1 is p_d – F̄_f(C – b)p_f. As long as this term is greater than zero, we should keep increasing the discount booking allocation until it becomes less than or equal to zero or b = C, whichever comes first. With a booking limit of b, there will always be at least C – b seats available for full-fare passengers. If discount demand turns out to be less than b, even more seats will be available for full-fare passengers. F̄_f(C – b) is the probability that full-fare demand will exceed the protection level. It is shown as a function of b in Figure 9.2. The term F̄_f (C – b) is small when the discount booking limit is small (that is, the protection level is large) and gets larger as we increase the booking limit (that is, as we decrease the protection level). If p_d < F̄_f(C)p_f, then we should not allocate any seats for discount passengers—we are better off saving all seats for full-fare passengers. If p_d > F̄_f(C)p_f, then we are better off allocating at least one seat for discount passengers.

This marginal analysis suggests the following simple hill-climbing algorithm for calculating the optimal booking limit b*.

Algorithm for Computing Optimal Discount Booking Limit

1. Set b = 0.

2. If b = C, set b* = C and stop. Otherwise, go to step 3.

Figure 9.2 Probability that full-fare demand will exceed the protection level as a function of booking limit for a 100-seat aircraft.

3. Calculate E[h(b)] = p_d – F̄_f (C)p_f.

4. If E[h(b)] ≤ 0 or F_d (b + 1) = 1, set b* = b and stop.

5. If E[h(b)] > 0 and F_d (b + 1) < 1, set b ← b + 1 and go to step 2.

This algorithm involves adding one seat at a time to the discount booking limit (or, equivalently, removing one seat at a time from the full-fare protection level) and continuing as long as adding one more seat increases expected revenue. However, there is a simpler way to get to the same point.

9.1.2 Littlewood’s Rule

The sequential algorithm finds the largest integer value of b* such that F̄_f (C – b) > p_d/p_f. The value of b* that meets this condition can be approximated by solving the equation

or, equivalently, F_f (y*) = 1 – p_d/p_f, where y* = C – b* is the optimal protection level for full-fare bookings. Equation 9.2 is an approximation because it is unlikely that the value for which y* holds exactly will be an integer; however, if F̄_f (y*) is a continuous distribution (say, the normal or log-normal), then we can solve 9.2 exactly and round to find a reasonable integer solution. If we are using a discrete distribution, then we set y* to the smallest value of y such that F̄_f (y*) ≤ p_d/p_f.

Condition 9.2 for the optimal two-class discount booking limit was first described in 1972 by Kenneth Littlewood, an analyst at British Overseas Airways Company (BOAC, a predecessor to British Airways), and is known as Littlewood’s rule. The quantity on the left-hand side of Equation 9.2, F̄_f (y*), is the probability that full-fare demand will exceed the protection level. Littlewood’s rule states that, to maximize expected revenue, the probability that full-fare demand will exceed the protection level should equal the fare ratio p_d/p_f. If the discount fare is 0, Littlewood’s rule states that we should set the protection so high that there is no chance that full-fare demand would exceed it. In other words, the optimal discount booking limit would be 0. This is intuitive—if discount passengers are not paying us, we should not give them any seats! As p _d increases, the optimal number of seats to protect decreases until, when p _d = p_f, it is optimal to set the discount booking limit to C. This is also intuitive—if discount passengers are paying as much as full-fare passengers, there is nothing to be gained by turning away a discount booking when there are still empty seats.

Almost always, the function F̄_f (y) will be a strictly decreasing function of the protection level y. In this case, F̄_f will be invertible and we can write Littlewood’s rule as

where refers to the inverse complementary cumulative distribution function of full-fare demand. At the point where the risks of protecting too much capacity for full-fare demand and protecting too little are exactly balanced.

Note that, according to Equation 9.3, the optimal protection level does not depend on the aircraft capacity except that it cannot be larger than the capacity. This means that we do not need to recalculate the protection level if we change capacity as long as the fares do not change. The idea is illustrated in Example 9.1.

Example 9.1

An airline has set a discount booking limit of 80 seats on a 150-seat aircraft for a certain flight departure. The corresponding protection level is 70 seats. If the airline substituted a 100-seat aircraft for that flight and neither the fares nor the full-fare demand forecast changed, then the optimal protection level would still be 70 seats. The optimal discount booking limit with the smaller aircraft would be 100 – 70 = 30 seats. If the airline decides to go even smaller and assign a 50-seat aircraft to the flight, the optimal decision would be to protect all 50 seats for full-fare passengers.

One fact you may find surprising about Littlewood’s rule is that the optimal protection level—and, hence, the optimal discount booking limit—does not depend in any way on the forecast of discount demand. The distribution of discount demand F _d does not appear in Equation 9.2. Doubling (or halving) the discount demand forecast will not change the optimal protection level. The economic trade-offs embodied in Littlewood’s rule only depend on the two fares and the distribution of expected full-fare demand.

Example 9.2

The mean full-fare demand for a flight with a 100-seat aircraft is 50 with a standard deviation of 100. For any fare ratio, the corresponding optimal booking limit is the largest value of b for which F̄_f (C – b) ≤ p_d/p_f. Table 9.1 illustrates the key calculation in the optimal two-class discount booking limit algorithm for a 100-seat flight. For a fare ratio of 0.4, the optimal booking limit is 25; for a ratio of 0.5, it is 50; and for a ratio of 0.6, it is 76. Since discount demand does not enter into Littlewood’s rule, these limits are independent of the discount demand forecast.

TABLE 9.1

The value of 1 − F_f (C − b) as a function of b when total capacity is 100 seats and the mean full-fare demand is 50 with a standard deviation of 100

Figure 9.3 Expected discount, full-fare, and total revenues as a function of booking limit.

In Example 9.2 the booking limit increases with the fare ratio, as expected. Notice that if the fare ratio is less than 0.309, we would not allow any discount passengers to book—we would be better off protecting the entire plane for full-fare passengers. On the other hand, if the fare ratio is greater than 0.691, we would open the entire flight to discount passenger bookings. In either case, the airline might want to consider revisiting its fare structure—in the first case the discount fare is probably too low, and in the second case it is probably too high relative to the full fare.

The trade-offs involved in setting the discount booking limit are shown in Figure 9.3 for a 100-seat flight with mean full-fare demand of 50 and standard deviation of 25—the same values as in Table 9.1. The discount fare is $100, and the full fare is $200, so the fare ratio is 0.5. The top curve is total expected revenue—the sum of the expected revenue from full-fare passengers and discount passengers. The dotted curve is expected discount revenue, and the difference between expected total revenue and expected discount revenue is expected full-fare revenue. As we increase the discount booking limit from zero, the expected revenue from discount passengers increases, with very little decrease in expected full-fare passenger revenue. As we continue to increase the discount booking limit, we begin to displace more and more full-fare passengers. The point at which the decrease in expected full-fare passengers exactly balances the gain from expected additional discount passengers is the optimal booking limit calculated by Littlewood’s rule.

To summarize, Littlewood’s rule determines the optimal discount booking limit in the case when discount demand books before full-fare demand. The optimal booking limit depends only on the forecast of full-fare demand, the aircraft capacity, and the fare ratio. It is not affected by the forecast of discount demand. However, the forecast of discount demand has a big impact on the sensitivity of expected revenue to the booking limit. When the forecast of discount demand is low, expected revenue is usually not very sensitive to the booking limit, within reasonable ranges. But when the forecast of discount demand is high, expected revenue becomes very sensitive to the booking limit. The lesson is that it is most critical to calculate precise booking limits when we forecast high levels of discount demand.

9.1.3 Littlewood’s Rule with Independent Normal Demands

The two-class discount booking limit algorithm will find the optimal booking limit given any distribution of full-fare demand. But there is a particularly simple way to calculate the optimal discount booking limit when full-fare demand is normally distributed.² In this case,

where Φ(x) is the standard cumulative normal distribution and μ_f and δ_f are the mean and standard deviation, respectively, of full-fare demand. Littlewood’s rule implies that we want to find the value of b such that

which means that the optimal booking limits and protection levels must satisfy

and

where Φ^–1 (x) is the inverse cumulative normal distribution.³ (Note that the solutions to 9.4 and 9.5 are unlikely to be integers, so rounding will usually be required.)

Figure 9.4 shows Φ^–1 (1 – p_d/p_f) as a function of the fare ratio p_d/p_f. From this figure and Equation 9.5, we can derive a number of important characteristics of the optimal discount booking limit. First, Φ^–1 (1 – p_d/p_f) is a decreasing function of the fare ratio. This means that b* is an increasing function of the fare ratio. Note that when p_d = p_f/2, then Φ^–1 (1/2) = 0, which implies that y* = min(μ_f,C); that is, it is optimal to set the protection level to expected full-fare demand when the fare ratio is 1/2. For p_d/p_f < 1/2, it is optimal to protect more seats for full-fare demand than we expect to receive, and for p_d/p_f > 1/2, it is optimal to protect fewer seats than expected full-fare demand. In other words, the fare ratio determines whether we should save more or fewer seats than expected demand for full-fare passengers.

Figure 9.4 Inverse cumulative normal function of 1 – p_d/p_f.

Example 9.3

A flight has a capacity of 100 seats and two fare classes. The full fare is $300, and full-fare demand is normally distributed with a mean of 70. If the discount fare is $150, the airline should protect exactly 70 seats for full-fare customers and set a booking limit of 30 for discount-fare demand. If the discount fare is $180, the airline should protect fewer than 70 seats for full-fare demand; if the discount fare is $120, the airline should protect more than 70 seats for full-fare demand. The optimal protection levels for each case can be determined from Equation 9.5.

Equation 9.5 specifies that the optimal protection level is equal to the expected full-fare demand μ_f plus the standard deviation of full-fare demand δ_f times a term. Recall that δ_f > 0 is a measure of the uncertainty in our forecast of full-fare demand. A higher value of δ_f means a flatter distribution and more uncertainty. What impact does it have on the optimal booking limit? First, notice that δ_f = 0 implies that b* = [C – μ_f]⁺. This means that if we knew full-fare demand with certainty, we would protect seats for full-fare demand unless μ_f > C, in which case we would reserve the entire capacity of the plane for full-fare passengers and set b* = 0. Because we know d_f = μ_f that when δ = 0, this policy will maximize expected revenue.

Of course, things would be too easy (and there would be no need for sophisticated revenue management) if companies knew future full-fare demand with certainty, so we need to consider the case when the standard deviation is greater than zero.⁴ From Equation 9.5, we can see that y* is a linear function of the standard deviation when full-fare demand is normally distributed and the fares are constant. The effect of the standard deviation on the optimal protection level when mean full-fare demand is 50 is shown in Figure 9.5 for different values of the fare ratio, p_d/p_f.

Figure 9.5 Optimal discount booking limit for a 100-seat flight as a function of the standard deviation of full-fare demand.

TABLE 9.2

Dependence of protection level y* on the standard deviation of full-fare demand when full-fare demand is normally distributed

The dependence of the optimal protection level on full-fare demand standard deviation and the fare ratio is summarized in Table 9.2. When the fare ratio is exactly 1/2 or the standard deviation of full-fare demand is zero, then the optimal protection level for full-fare demand is equal to mean full-fare demand. If the fare ratio is less than 1/2, the optimal protection level will be greater than μ_f, and increasing the standard deviation will increase the protection level. If the fare ratio is greater than 1/2, the optimal protection level will be less than μ_f and will fall as the standard deviation increases.

9.1.4 Relation to Newsvendor Problem

Littlewood’s rule has a close relationship to the critical fractile (or critical ratio) solution to the optimal replenishment problem for perishable goods that is studied as part of operations management. Both capacity allocation and replenishment of perishable goods are themselves special cases of a classic problem known as the newsvendor problem. The news-vendor problem well predates revenue management; it was first identified and studied as early as 1888.

The newsvendor problem considers the situation in which a purchaser needs to order a quantity of some good in the face of uncertain demand. The problem got its name from the example of a newspaper salesperson who needs to determine how many newspapers to purchase at the beginning of the day to satisfy the day’s uncertain demand. The key to this decision is that the newsvendor faces different costs if he purchases too much or too little. If he buys too many newspapers, then at the end of the day he will have unsold, worthless copies that he discards. If he buys too few, he will sell out of papers and turn away potentially profitable customers. The purchaser might also be a retailer deciding how many units of a fashion good to order, or it might be a manufacturer ordering raw materials.

The solution to the newsvendor problem can be expressed in terms of the overage cost and the underage cost of the decision. The overage cost is the cost per unit of purchasing too many items; the underage cost is the unit cost of purchasing too few. Assume that the newsvendor buys newspapers for 20 cents apiece and sells them at 25 cents. His overage cost is 20 cents per unsold paper; his underage cost is the 5-cent profit that he forgoes for each missed sale. (Note that the overage cost is an actual monetary cost, while the underage cost is an opportunity cost.) If U is the underage cost and O is the overage cost, the optimal order quantity for the newsvendor is the value of Y such that

where F(y) is the cumulative distribution on demand.

Example 9.4

When newspapers cost 20 cents and are sold for 25 cents, Equation 9.6 implies that the number of newspapers the vendor should purchase would be the smallest value of Y such that F(Y) ≥ 5/(20 + 5) = 0.2.

Finding the optimal discount booking limit in the two-class case is analogous to the newsvendor problem. The airline needs to determine how many seats to protect (i.e., “order”) to satisfy unknown full-fare demand. The airline’s unit overage cost from protecting too many seats is a displaced discount fare: O = p_d. The underage cost is the revenue from a lost full-fare booking minus the discount fare: U = p_f – p _d. Substituting into Equation 9.6 means that the airline should set the protection level such that

which is Littlewood’s rule.

9.2 CAPACITY ALLOCATION WITH MULTIPLE FARE CLASSES

Littlewood’s rule finds the optimal discount allocation in the case of two classes when the lower fare class books first and demands are independent. However, as discussed in Section 8.3, airlines are prolific price differentiators, often offering tens if not hundreds of different fares on a flight, such as special discount fares, corporate fares, and group fares in addition to the standard discount fares and full fare. An airline needs to manage the availability of all of these fares to maximize total contribution. The same holds true for any revenue management company selling multiple fare classes. More specifically, they need to set the nested booking limits within a booking control structure, as described in Section 8.5.2. This is the multiclass capacity allocation problem, and, predictably, it is more difficult to solve than the two-class model.

To analyze the multiclass model, we make the following assumptions.

• A product has n fare classes, each with an associated fare. Fare classes are numbered in descending fare order—that is, p₁ > p₂ > ⋅⋅ ⋅ > p_n. A fare class is called higher than another if it has a higher fare—class 1 is the highest class, and class n is the lowest class.

• Demand in each class is an independent random variable. We denote the demand in fare class i by d_i. Demand in class i can be described by a probability density function f_i(x) defined on integer x ≥ 0, where f_i(x) is the probability that demand for fare class i will be x. F_i(x) denotes the probability that d_i ≤ x, and F̄_i (x) denotes the probability that d_i > x.

• Demand books in increasing fare order. That is, the lowest-fare passengers (those paying p_n) book first, followed by the second-lowest-fare passengers and so on, so that the highest-fare passengers (those paying p₁) book last.

• There are no no-shows or cancellations.

• The objective function is to maximize expected revenue. (As noted before, the approaches and algorithms in this section can be modified to maximize expected total contribution by replacing price with net contribution.)

The time convention for the multiclass model is shown in Figure 9.6. During the first period, the airline sees only booking requests from the lowest-fare passengers, those paying p_n. At the end of this first booking period, the airline has accepted some number of bookings from these passengers, say, x_n ≥ 0. During the second period, passengers paying the next highest fare start to book, and so on, until the last period, in which the highest-fare passengers—those paying p₁—seek to book. Note that the indices of the fare classes decrease as the time of departure approaches. (It may help to think of a countdown to departure as a way to remember this convention.)

Figure 9.6 Booking process assumed in simple multiclass model.

The airline’s decision at the start of each booking period j is how many bookings of type j it should accept. It knows how many bookings it has already accepted—namely, Since there are no no-shows or cancellations, is the unbooked capacity remaining at the beginning of period j. The airline also knows the demand distributions for future booking periods. Given this information, the airline needs to find the maximum number of bookings from class j to accept in order to maximize expected revenue. We call this quantity the class j booking limit and denote it by b_j. In this model, the airline only needs to calculate one booking limit at the start of each period, since it will receive bookings from only one fare class during the coming period. The airline can wait until it sees how many bookings it accepts in this period before setting the booking limits for the next higher class.

9.2.1 The Decision Tree Approach

To solve the multiclass booking limit problem, we work backward. At the beginning of the final period, the airline has C₁ seats remaining. Since there are no no-shows or cancellations, it is clearly optimal for the airline to allow all remaining seats to be booked. So b₁ = C₁. Next we consider period 2—the penultimate period before departure. At the beginning of period 2, the airline has C₂ seats remaining. The problem the airline faces at the beginning of the second period is exactly the two-fare-class problem we solve in Section 9.1. Therefore, the airline can maximize revenue by applying Littlewood’s rule (Equation 9.2): The optimal booking limit is the smallest value of 0 ≤ b₂ ≤ C₂ such that F₁(C₂ – b₂) < 1 – p₂/p₁.

Things get more complicated when we move backwards one period to calculate b₃. Conceptually, the trade-off is similar to the two-class case: If we increase the booking limit in period 3, one of two things can happen. Either we receive an additional type 3 passenger booking or we do not. If we do not, the net impact on total revenue of increasing the booking limit will be zero. If we do book an additional customer in period 3, we will receive a fare of p₃, but we run the risk of displacing a later-booking customer who would pay a higher fare—either p₁ or p₂. There is no easy way to calculate either the probability that we will displace a booking or the conditional probability of which type of booking will be displaced. However, the fundamental trade-off remains the same as in the two-class case—we want to set the booking limit that balances the risks of spoilage and dilution.

The period 3 problem is illustrated in Figure 9.7, where q₂ is the probability that increasing the class 3 booking limit will displace a class 2 passenger and q₁ is the probability that it will displace a class 1 passenger. From this tree we can see that the optimal class 3 booking limit depends on the probability that an additional class 3 booking would displace a higher-fare booking and the fare of the booking that would be displaced. If we knew the displacement probabilities q₁ and q₂, it would be straightforward to roll back the decision tree to solve for the optimal b₃ (Exercise 1). Unfortunately, there is no easy way to calculate the displacement probabilities for three or more fare classes, and there is no closed-form solution for the optimal booking limits. As a result, the solution techniques for finding the optimal booking limits for three or more fare classes require the use of dynamic programming. Dynamic programming approaches to optimal multiclass capacity control are outside the scope of this book; the reader who is interested in learning about such approaches will find useful references in Section 9.8.

Figure 9.7 Capacity allocation decision tree for period 3 prior to departure.

While the techniques for finding the optimal booking limits and protection levels in the multiclass problem are not mathematically difficult, they can be computationally intensive, particularly when they need to be applied to thousands of flights in a limited period of time. For this reason, airlines, hotels, rental car companies, and their revenue management brethren typically do not calculate the optimal multiclass booking limits. Rather, they utilize a heuristic to determine good but not necessarily optimal booking limits. The most popular of these heuristics are the expected marginal seat revenue (EMSR) approaches, especially EMSR-a and EMSR-b. These are very fast and almost always find booking limits that generate expected revenue very close to the theoretical optimum.

9.2.2 Expected Marginal Seat Revenue (EMSR) Heuristics

Expected marginal seat revenue (EMSR) comes in two flavors: EMSR-a and EMSR-b. Both EMSR-a and EMSR-b were introduced by Peter Belobaba in his PhD dissertation and a series of subsequent papers (Belobaba 1987, 1989). Both are based on approximating the multiclass problem by a series of two-class problems and applying Littlewood’s rule to obtain a solution.

EMSR-a. Expected marginal seat revenue—version a (EMSR-a) is the best-known heuristic for the capacity allocation problem. It is based on the idea of calculating protection levels for the current class relative to each of the higher classes using Littlewood’s rule. These protection levels are then summed to create the protection level for the current class. For example, if we are setting a protection level for class 3, EMSR-a would calculate a protection level for class 3 against class 1 (which we denote by y₃₁) using the form of Littlewood’s rule in Equation 9.3:

and a protection level for class 3 against class 2, which we denote by y₃₂ according to

The EMSR-a protection level for class 3 is the sum of these two protection levels; that is, min(y₃₁ + y₃₂, C) or min( where the superscript a in denotes that it is a protection level calculated by EMSR-a. The booking limit for class 3 can then be written

EMSR-a can be generalized to any number of fare classes. For j ≥ 2, the EMSR-a protection level is given by

If demands are normally distributed for each fare class, the EMSR-a protection level for class j is

which is quite easily computed using standard cumulative normal distribution tables. It is easy to confirm that EMSR-a reduces to Littlewood’s rule in the case of two fare classes.

EMSR-b. Expected marginal seat revenue—version b (EMSR-b) assumes that a passenger displaced by an additional booking would be paying a fare equal to a weighted average of future fares. EMSR-b creates an artificial class with mean demand equal to the sum of the mean demands for all the future periods and a fare equal to the average expected fare from future bookings. It then uses Littlewood’s rule to calculate the booking limit of the current class j with respect to the artificial class. EMSR-b assumes that the expected fare of the displaced booking is equal to the expected fare of future demand. This is an approximation because limits will also be set on higher-fare booking, so the mean of the demand accepted in a higher booking class will generally not be equal to the mean of the unconstrained demand.

To formalize EMSR-b, we assume as before that demands in different classes are independent, with the demand in class i having a mean of μⁱ and a standard deviation of δ_i. Assume we are at the beginning of period j ≥ 2 and want to calculate the booking limit b_j. EMSR-b then proceeds as if we were solving a two-class problem. If we assume that demands for the different classes are normally distributed, then EMSR-b assumes that demand for the artificial class is normally distributed with mean demand μ, average fare p, and standard deviation δ given by

(The formulas for the mean and the standard deviation are standard for the sum of any independent random variables. See Appendix B for more details.) We can use the version of Littlewood’s rule for normal distributions in Equation 9.5 to write

as the formula for the EMSR-b protection level for classes higher than class j when demands are normally distributed. Again, it is easy to confirm that EMSR-b reduces to Littlewood’s rule in the case of two fare classes.

Comparison of EMSR heuristics. It is difficult to make comprehensive statements about the relative merits of the two EMSR heuristics. There are cases when EMSR-a gives higher booking limits than EMSR-b and cases when the opposite is true. More pertinently, there are cases when EMSR-a results in higher revenue than EMSR-b, and vice versa. Both appear to give solutions close to the optimal booking limits in most realistic cases, and both generally capture a high percentage of the optimal revenue. One set of studies has shown that EMSR-b was consistently within 0.5% of the optimal revenue, while EMSR-a led to revenues that were more than 1.5% lower than optimal in some cases (Belobaba 1992). Other studies (and much practical experience) has shown that both EMSR heuristics tend to perform well in almost all realistic cases and that neither strictly dominates the other, although EMSR-b seems to perform slightly better than EMSR-a in practice.

Guillermo Gallego and Huseyin Topaloglu (2019) report on a series of simulations to compare the performance of the two EMSR heuristics on an aircraft with four booking classes. They assumed that demands for the four classes followed independent normal distributions. The fares, mean, and standard deviations of demand along with the corresponding optimal protection levels EMSR-a protection levels and EMSR-b protection levels for the four booking classes j = 1, 2, 3, 4 are shown in Table 9.3. The performance of the two EMSR heuristics against the optimal protection levels was tested for capacities ranging from 80 seats to 160 seats using 500,000 simulation runs for each capacity. Table 9.4 shows the results. The expected revenue using the optimal booking limit is shown along with the percentage of the expected optimal booking limit achieved by the two heuristics. The heuristics performed extremely well, capturing more than 99% of the optimal revenue in each case. This is consistent with previous studies of the same sort.

TABLE 9.3

Fares, demand data, and resulting protection levels for EMSR-a and EMSR-b heuristics

SOURCE: Gallego and Topaloglu 2019. Used with permission.

TABLE 9.4

Revenue from the optimal policy and the two EMSR heuristics as a function of total capacity

SOURCE: Adapted from Gallego and Topaloglu 2019.

It is widely felt that the additional revenues from solving the optimal booking control problem do not generally justify the extensive additional computations that would be required relative to using an EMSR heuristic. As a result, EMSR-b has become the standard for calculating booking limits for a single resource.

9.2.3 Bid Pricing

We have seen that optimal nested booking limits have the property that if one fare class is open, then all higher fare classes will be open. This means that one of three conditions must hold when the allocations for a resource are optimized:

• All fare classes are open.

• All fare classes are closed.

• There is an open fare class such that all higher classes are open and all lower classes are closed.

This suggests the following rule:

Accept a single-seat booking request if its associated fare is greater than or equal to the fare in the lowest open class. Otherwise reject it.

Example 9.5

A flight departure has six fare classes. Two weeks before departure, fare classes 1, 2, and 3 are open, while classes 4, 5, and 6 are closed. The class 3 fare is $250 and the class 4 fare is $210. If the next booking request has a fare greater than or equal to $250, it will be accepted; otherwise it will be rejected.

This simple rule to control bookings is called bid pricing, and the minimum acceptable fare is called the bid price.⁵ In bid pricing, the fare of a booking request is compared to a hurdle rate (the bid price) for a product and accepted if and only if the fare exceeds the bid price. When the bid price is zero, any booking request with positive net contribution will be accepted—this is equivalent to having all fare classes open. When the bid price is set to any amount higher than the highest fare, no booking requests will be accepted—this is equivalent to having all fare classes closed. The seller can use the bid price as an intensity control, raising the bid price when he wishes to reduce the rate of sales and increase average price, and lowering the bid price when he wishes to increase the sales rate at a lower average price.

Bid pricing has an appealing simplicity. It requires only calculating and updating a single number—the bid price. It avoids the complexity involved in recalculating multiple booking limits. If bid prices are continually updated and each request is for a single unit of resource (e.g., a single airline seat or a single hotel room night) and demand for different fare classes were independent, a system under which booking requests are evaluated only against a bid price could capture at least as much revenue as the standard booking limit approaches.

The bid price criteria should remind you of the rule we established in Section 7.3 that a request for a constrained resource should be accepted only if the associated price exceeds the opportunity cost of the resource. There is a reason for this—the bid price for a resource is the opportunity cost for that resource. The decision tree approach described in Section 9.1.1 makes this explicit: we should accept a booking only if its fare exceeds the expected revenue we could realize from that unit of capacity in the future—that is, its opportunity cost. Bid pricing is based on the following equivalence.

Bid price for a resource = fare in the lowest open fare class

= opportunity cost for the resource

= lowest fare we should accept for a booking request

Bid pricing is simply an example of the rule that a unit of a constrained perishable resource should be sold only if the price received is greater than the opportunity cost.

Despite the appealing simplicity of bid pricing, most revenue management companies do not use pure bid pricing systems. Rather, they rely on the booking limits and protection levels described in Section 8.5.2. If bid pricing is so good, why is it not used more often? There are three main reasons.

• Bid prices give only marginal guidance—that is, a bid price can only tell us whether we should accept a booking request for a single seat. The bid price does not give a definitive answer to the question of whether or not we should accept a booking request for more than one seat. Booking limits enable more precise control of multiseat booking requests: for example, an airline would be able to accept a booking request for three seats in a particular class while rejecting requests for four or more seats.

• The bid price for a resource jumps upward any time a booking is accepted and decreases any time an existing booking is canceled. For bid prices to provide optimal control, they would need to be calculated at least every time a booking or cancellation takes place. This would be computationally infeasible given the volume of bookings and cancellations that an airline, rental car company, or large hotel chain needs to process. Booking limits can remain in place for a longer period of time, with the limits updated as bookings and cancellations occur according to the mechanisms described in Section 8.5.

• As described in Chapter 8, booking limits were built into the airline reservation systems from their inception. The nested booking controls described in Section 8.5 were the only way available to airlines and other revenue management companies to implement capacity allocation.

Despite these practical concerns, bid pricing is an important concept. Since the bid price on a leg approximates the opportunity cost for a resource, it is a good estimate of the additional revenue that could be achieved by acquiring an additional unit of resource. Bid prices also play an extremely important part in network revenue management, as we see in Chapter 10.

9.3 CAPACITY ALLOCATION WITH DEPENDENT DEM ANDS

The models we have considered so far assume that demand in each fare class is independent of demand in the other fare classes. Perhaps even more surprisingly, they assume that demand in each fare class is independent of whether other classes are opened or closed. This is equivalent to assuming that the fare classes perfectly segment the market (see Chapter 6). Standard capacity allocation models, such as Littlewood’s rule and the EMSR heuristics, assume no cannibalization—opening a discount class has no effect on full-fare demand. Full-fare passengers are either unwilling or unable to purchase at the discount fare, and none of the discount passengers would purchase the product at the full fare.

The assumption of fare class independence does not reflect the real world. In reality, there are no such things as full-fare customers and discount customers; there are only potential buyers searching for the alternative that best meets their needs. In fact, the assumption of independence fails even at the most basic level of airline segmentation. Some business travelers book early to take advantage of discount fares, just as some leisure travelers would be willing to pay full fare for travel but are more than happy to purchase at a lower discount fare. This means that some fraction of the customers who are refused when we close the discount fare will go on to purchase at the full fare and that the two demands are not really independent. Rather, the full-fare demand will depend on whether the discount fare class is opened or closed. When we close discount fares, we would expect more full-fare demand because some of the discount-fare customers will go ahead to purchase at full fare when the discount fare is not available.

As revenue management systems became more widely used, revenue managers—the airline personnel who monitor fare class allocations for a set of flights—noticed that closing a discount fare class would often lead to increased demand in higher classes. This phenomenon was termed buy-up or sell-up. By the same token, opening a discount fare class would often lead to decreased demand in higher classes—cannibalization. Revenue managers would close discount classes earlier than recommended by the revenue management system because they knew that they would gain benefits from buy-up.

Buy-up and cannibalization are not separate phenomena. As Bill Brunger, vice president of revenue management for Continental Airlines, put it in conversation with me, “Passengers do not come with Y-Class or M-Class stamped on their foreheads.” Rather, customers search for the best combination of fare and travel option that meets their needs. The internet has increased visibility of all airline fares and their accessibility to all customers. As a result, the difference between full fares and discount fares has grown tremendously—for some flights, the average full fare can be five times or more the average discount fare. This provides a tremendous incentive for customers to shop for lower fares.

The assumption of fare class independence was built into revenue management from the beginning. The reasons for this were twofold. First, the most pressing need facing the airlines was to quickly develop systems that enabled them to respond to the challenge of low-cost competitors and to manage the exploding number of fares in the marketplace. Rapidly implementing relatively simple approaches was more important than waiting to develop a perfect solution. The second reason was that, in many cases, the assumption of perfect segmentation was not too bad. The booking fences between discount and full-fare segments were fairly effective. Furthermore, for international airlines, regional pricing was a major part of revenue management strategy. In the 1980s, the fare paid in Japan for a ticket would often be 50% more than the same ticket purchased in Europe or the United States, and in the 1990s, one European airline estimated that 100% of its profit was due to its ability to sell tickets in certain overseas markets at fares higher than in its own market. Before the rise of the internet, this geographical discrimination was quite powerful and not subject to high levels of cannibalization. However, the internet has eroded many of the barriers among booking classes, and the need to incorporate demand dependence into revenue management has become more pressing.

9.3.1 Demand Dependence with Two Fare Classes

We can modify the marginal analysis approach of Figure 9.1 to find the optimal booking limit under imperfect segmentation with two fare classes. We assume as before that the discount fare is p _d and the full fare is p_f, with p_f>p_d. For this analysis, we use new definitions of demand:

d_d = Total discount demand,

d_f = Total full-fare demand assuming all discount bookings are accepted.

In addition, we define α as the fraction of rejected discount demand that will seek to book a full fare, with 0 ≤ α ≤ 1. The actual full-fare demand the airline sees will be a function of the discount booking limit and can be written as

d̂_f = d_f + α[d_d – b]⁺

This means that increasing the booking limit b by one seat will decrease expected full-fare demand by α if discount demand exceeds the booking limit and will have no effect on full-fare demand otherwise.

We can relate this model to the willingness-to-pay approach introduced in Chapter 3. Specifically, this model is equivalent to assuming that there are d_d customers with a willingness to pay for the discount product that is greater than p _d and are able to book early. Of these, αd_d also have a willingness to pay for the full-fare product that is greater than p_f: if the discount product is not available, they will buy the full-fare product. Finally, there are d_f customers who have a willingness to pay for the full-fare product that is greater than p_f and who are unwilling or unable to book early, so their willingness to pay for the discount product is lower than p_d. Of course, we would expect d_d, d_f, and α to change if we changed the fares p _d and p_f.

The decision tree for the two-class model with demand dependence is shown in Figure 9.8. The only difference from the basic two-class allocation model in Figure 9.1 occurs when discount demand is greater than the booking limit and full-fare demand is less than the protection level, C − b. In this case, increasing the booking limit by 1 leads to an additional discount booking, but there is a probability of α that this increased discount booking cannibalizes a future full-fare booking. The net impact on expected profitability is p _d − αp_f.

Figure 9.8 Two-class capacity allocation with demand dependence.

It is apparent that the expected marginal impact of increasing the booking limit by 1 in this case is given by

The change in expected profit will be determined by the sign of the term p_d – αp_f – (1 − α) F̄_f(C − b)p_f. If this term is greater than zero, increasing the booking limit by one will lead to increased expected revenue. If it is less than zero, increasing the booking limit will lead to decreased expected revenue. Note that if α≥p_d/p_f, the term on the right will be less than or equal to zero for all values of b. This corresponds to the case where cannibalization overwhelms demand induction. In this case, we know immediately that the optimal booking limit is b* = 0.

Assume now that p_d/p_f ≥ α. Then, from Equation 9.8 we can see that we are looking for the protection level y* that solves

Note that Equation 9.9 reduces to Littlewood’s rule when α = 0.

We can also write Equation 9.9 as

The expression is called the modified fare ratio, and Equation 9.10 is the same as Littlewood’s rule, using in place of the fare ratio p_d/p_f. Since the modified fare ratio is less than the actual fare ratio, the impact of demand dependence is to reduce the discount booking limit (equivalently, increase the full-fare protection level) from the case with no demand dependency.

When full-fare demand is normally distributed, the optimal protection level is

9.3.2 Modified EMSR Heuristics

Both EMSR-a and EMSR-b can be modified to incorporate imperfect segmentations. The modifications are based on the assumption that when a class closes, rejected demand for that class may buy up to the next highest class—but not to any higher classes. For example, if we close class 3, some class 3 demand may seek to buy in class 2 but not in class 1. We can easily derive modified versions of the EMSR heuristics under this simple assumption.

Define α_j for j = 2, 3, . . . , n as the fraction of class j customers who would purchase in the next higher class, j − 1, if class j is closed. Thus, α₃ is the fraction of class 3 customers who would “buy up” to class 2 if they find class 3 closed when they request a booking. α_j is referred to as the buy-up factor for class j. Note that there is no buy-up factor for the highest fare class. Then, for the case of normal demand distributions, EMSR-a and EMSR-b can be extended to incorporate buy-up factors as follows:

where μ, p, and δ for the modified EMSR-b algorithm are as defined in Equation 9.7.

Modified EMSR-a calculates the protection levels for class j against every higher class under the assumption that buy-up will only occur to the next highest class, j − 1, if we close j. It then subtracts the sum of all these protection levels from the remaining capacity to determine the booking limit for class j. EMSR-b assumes that buy-up will occur to the aggregate class consisting of all the higher classes.

These two modifications to the EMSR heuristics have been studied by Peter Belobaba and Lawrence Weatherford (1996), who showed that the modified EMSR heuristics provide additional revenue when buy-up is present. The modified EMSR heuristics are easy to implement, and versions of them have been used in practice. However, they have some disadvantages. They require buy-up factors to be estimated and stored for each flight. They also require redefining the demand for each fare class as the demand that would be received if the next higher class is open. In their simplest form, they do not incorporate the possibility of buy-up from class j to classes higher than j − 1.

9.3.3 Capacity Control with a Consumer Choice Model

The EMSR heuristics modified to incorporate buy-up in the previous section are somewhat unsatisfying. For one thing, they are a heuristic grafted onto another heuristic. They are not derived from a fundamental model of consumer choice. Rather, they assume that passengers do have M-Class and Y-Class stamped on their heads and that only some of the M-Class passengers will buy up to Y-Class if M-Class is closed. “Buy up” is not really a good description of the underlying phenomenon—at heart, what is happening is that consumers are faced with the decision of purchasing a ticket from among the options that they have available to them.

This section presents a more general approach to incorporating consumer choice into capacity control models. There are challenges in implementing this approach fully into revenue management systems, which we consider. However, the approach provides insights into the underlying problem and, in particular, illustrates the important concept of inefficient sets.

For this approach, we drop the assumption that bookings occur in fare order. Instead, we assume that, at any time, more than one fare class may be open. Fare classes are distinguished by various restrictions, with low-price fare classes being more restricted than higher-price fare classes. The lower-fare classes are inferior products being sold at lower prices. The decision facing the airline at each time period is which set of fare classes to open. At each time period, customers arrive and observe which fare classes the airline has made available. Each customer either purchases from one of the open fare classes or does not purchase. The question facing the airline is which set of fare classes to open at which time.

As before, we assume that time periods are indexed so that time runs from the current period t counting down to departure at time 0. There are n fare classes indexed so that the prices are ordered according to p₁ > p₂ > ⋅ ⋅⋅ > p_n > 0. There is a fixed capacity of C, and bookings are firm—there are no cancellations or no-shows. For this model, we assume that there is at most one booking request in each period. For simplicity, we assume that the probability of a booking request is the same in each period and is equal to λ with 1 ≥ λ > 0.

At each time period, the airline needs to determine what set, S(t), of booking classes to offer. There are 2ⁿ possible sets that can be offered corresponding to all possible combinations of individual booking classes being opened or closed. If all booking classes are closed, the flight is closed for booking. Let S(t) indicate the set that is open at time t, and define p_j(S(t)) as the probability that a customer arriving at time t chooses class j given that S(t) is the set of open classes, with p₀ (S(t)) representing the probability of no purchase. Obviously p_j(S(t)) > 0 only if class j is in set S(t); otherwise p_j(S(t)) = 0.

These concepts are best illustrated by an example. Assume that a flight has three booking classes, Y, M, and K, with fares $800, $500, and $450, respectively. Y fare is unrestricted, while M and K have various restrictions—say, a 14-night stay and a Saturday-night stay, respectively. There are eight possible sets that the airline could offer on this flight. Assume that customers for this flight fall into five segments—two business and three leisure. One of the business segments can accept no restrictions; the other can purchase 14 days in advance but not stay over Saturday. All of the leisure segments can purchase 14 days in advance, but Leisure Segment 1 cannot accept a Saturday-night stay. Leisure Segments 2 and 3 can both accept both restrictions, but Leisure Segment 3 is not willing to pay more than $470 for the flight. The situation is summarized in Table 9.5 along with the probability that a booking request belongs to each of the five segments. Note that a customer segment will purchase a product only if they can accept the restrictions and they are willing to pay the associated fare.

TABLE 9.5

Segments and their characteristics for the example

From the information in Table 9.5, we can define the following values:

and

Here, Q(S) is the probability that a customer will purchase one of the products in S given that the set S is on offer, and R(S) is the average revenue from an arriving request given that set S is on offer. P₀(S) is the probability of no purchase in the period. The values of Q(S) and R(S) for the example are shown in Table 9.6. We assume that each booking request purchases in the least-expensive fare class available that meets the customer’s requirements.

We now establish the following definition. A set T is said to be inefficient if there exist probabilities α(S) such that

where the summations are over all sets. Here, each α(S) is a probability, which means that each α(S) ≥ 0 and that Σα(S) = 1. There is an important special case in which a set T is inefficient if there exists a set U such that Q(T) ≥ Q(U) and R(T) ≥ R(U).

This has been a long setup, but the first payoff is the observation that inefficient sets can never be optimal. This means that they can be dropped from consideration. Table 9.7 illustrates the calculation of Q(S) and R(S) for each of the sets in the example from Tables 9.5 and 9.6. To clarify how these are calculated, consider the set {M, K}. If the airline offers this set, then every customer except those in the Business Segment 1 will purchase. Business 2 and Leisure 1 will purchase from M-Class for a total probability of P_M(S) = .4 of an M-Class purchase. Leisure 2 and Leisure 3 will both purchase from M-Class for a total probability of P_K(S) = .5. The total probability of purchase is the sum of these, so Q(S) = .9. The expected revenue is thus .4 times the M-Class fare plus .5 times the K-Class fare: R(S) = 4 × $500 + .5 × $450 = $425.

In Table 9.7, only Set 1, which includes only Y-Class; Set 5, which includes Y-Class and K-Class; and Set 7, which includes all three classes, are efficient. The remaining four sets are inefficient and should never be offered—thus, the airline should never offer only M and K classes together without Y class.

TABLE 9.6

Choice probabilities P_j(S), probability of purchase Q(S), and expected revenue R(S) for all sets corresponding to segments and probabilities in Table 9.5

TABLE 9.7

Booking class purchased by each segment for the example in Table 9.5

The intuition about efficiency is that, if a set is inefficient relative to another set—that is, Q(T) ≥ Q(S) and R(T) < R(S) for some sets T and S—then S provides more expected revenue than T and has a lower expected opportunity cost because it has a lower probability of consuming a seat. If T is inefficient against a combination of sets, then the same holds true against the policy of choosing one of the sets in the combination with probability α(S).

The second payoff is that, for two efficient sets, S₁ and S₂, Q(S₁) ≥ Q(S₂), implies that R(S₁) ≥ R(S₂) and vice versa. This means that the efficient sets can be ordered in terms of expected sale probability and expected revenue. This ordering is shown in Figure 9.9 for the extended example. The points corresponding to the three efficient sets are labeled. The lines connecting them represent an efficient frontier—combinations of expected sales and expected revenue that could be achieved by randomizing among the three efficient sets. The points for the inefficient sets fall below the efficient frontier—they are dominated by weighted combinations of the efficient sets.

Figure 9.9 also provides a key as to how choice-based capacity control could be embedded in a dynamic booking control system. When a flight is not expected to book up, it is optimal to choose a set that provides a high probability of selling a seat—in Figure 9.9, that is the set {Y, M, K}. As capacity is expected to become scarcer, we would move down the efficient frontier. Thus, the next action would be to close M-Class and offer only {Y, K}. If capacity becomes highly scarce, then we would close all of the booking classes except Y-Class. As in traditional capacity control, we are managing availability by opening and closing booking classes; the difference is that we are not closing in order of fare class.

Figure 9.9 Efficient and inefficient sets for choice-based capacity control example.

Source: Talluri and van Ryzin 2004b. Used with permission.

Note that under this approach, the probability that a booking inquiry would purchase from booking class j if set S is offered—P_j(S)—will change over time as departure approaches. For an obvious example, the probability that 10 days before departure a customer will book in a fare class that has a 14-day booking restriction is 0. However, as we have seen, the mix of business and leisure passengers also changes as departure approaches. This means that the airline needs to forecast and estimate values of Q(S) and R(S) that depend on time to departure.

9.4 A DATA-DRIVEN APPROACH TO CAPACITY CONTROL

The methods for setting booking classes described in Section 9.3 assume that we have an estimate of the distribution of demand for each booking class. Assuming that demands for booking classes follow a normal distribution, these methods require an estimate of the mean and the standard deviation of demand for each booking class. They also assume that demands are independent—early demand for discount bookings does not give us any information about later full-fare demand. In all cases, we need to choose distributions of demand with parameters derived by applying statistical estimation to historic observations. This section discusses a data-driven approach that does not make assumptions about the distributions or independence of demand and allows us to go directly from the data to booking limits without estimating the parameters of an underlying distribution.

Let us assume that we have historic observations of demand by booking class for each of T preceding departures of a flight (same flight number, same time, same day of week). As usual, we assume n booking classes with fares p₁ > p₂ > ⋅ ⋅⋅ > p_n, and we assume no cancellations or no-shows. We seek to calculate the booking limits for future flight T + 1, which we denote as b₁, b₂, ⋅⋅ ⋅, b_n. Since there are no no-shows or cancellations, we know that b₁ = C.

The classical approach to calculating (and the approach used by most airlines, hotels, etc.) is to make a probabilistic forecast of demand based on historical demand and apply an algorithm similar to those described in Sections 9.1 through 9.3. However, the data-driven approach tackles the problem by asking: What set of booking limits would have maximized revenue if we had applied them to flights 1, 2, . . . , T? Those would then be the booking limits that we would apply to flight T + 1. The logic is that if booking-class demands for flight T + 1 are being drawn from the same distributions as those for flights 1 through T, then the set of booking limits that maximizes total revenue across those flights would be good ones to apply to flight T + 1.

To formalize our statement, let be the total demand for booking class i on flight t for 1 ≤ t ≤ T with booking limits b₁, b₂, ⋅⋅ ⋅, b_n. Then, the bookings that would be realized in class i on flight t would be

In words, the number of bookings accepted in each booking class on each flight is the minimum of the demand for that booking class and the difference between the sum of the booking limits for all lower classes and the bookings accepted in those classes. Let us denote where b = (b₁, b₂, ⋅⋅ ⋅, b_n) is the vector of booking limits. The optimal data-driven booking limits can be found by solving the optimization problem

subject to b₁ = C, b ≥ 0.

In the case of two booking classes, the optimization problem in Equation 9.11 is linear and can be solved using standard linear programming approaches. In the case of multiple booking classes, the problem is not linear, but it is generally not difficult to solve given the simple constraint structure.

Example 9.6

A flight has a capacity of 100 seats and three booking classes: B-Class with a fare of $160, M-Class with a fare of $240, and Y-Class with a fare of $700. As usual, B-Class books before M-Class, which books before Y-Class. The flight has been in operation for the last 10 weeks, and the demands for each of the three fare classes for the last 10 Monday flights are shown in Table 9.8. To find the optimal booking limits for this flight, the airline solves the optimization problem in Equation 9.11 using the demands shown in Table 9.8. The results are booking limits of 39 for B, 69 for M, and 100 for Y. With these limits, the average loads per flight and revenue per flight are 39 and $6,240 for B-Class, 28.4 and $6,816 for M-Class, and 25.6 and $17,920 for Y-Class, with an average revenue of $30,976 per flight. This could be considered a forecast of the performance of the next flight.

TABLE 9.8

Booking demands by fare class for the previous 10 departures of the flight in Example 9.6

In some ways, the data-driven approach to capacity allocation is quite appealing. It does not require arbitrary assumptions about the distribution of demand for a particular booking class–flight combination or about the independence (or lack of it) in demands for flight–booking class combinations. It collapses the two steps of “forecast” and “optimize” required by classical approaches into a single “optimize” step. Although it requires observations of total demand by booking class and flight that are often not available, this is not a disadvantage relative to the forecast-and-optimize approach, because forecasting demand also typically requires estimates of historical demand (not just loads).

Despite these apparent advantages, a pure data-driven approach has not (to my knowledge) been implemented at any revenue management company in 2019. There are several likely reasons for this. The first is that most revenue management companies have implemented some flavor of the classical “forecast, then optimize” systems, which are generally working well enough that there is no financial incentive to rip them out to implement an entirely new approach. Second, forecast-then-optimize approaches have the advantage that they allow revenue managers to update forecasts to account for anticipated changes in demand. For example, a hotel owner who knows that the Super Bowl will be held in his city next year would have his revenue manager increase the demand forecasts for those dates well before the date of the game. The revenue management system would then reoptimize capacity controls given the new forecasts. It is difficult (but not impossible) to incorporate such user knowledge as overrides in a data-driven system. It is also not clear how to incorporate consumer choice into data-driven models. Addressing these issues is a topic of current research.

9.5 CAPACITY ALLOCATION IN ACTION

We have discussed several techniques for calculating booking limits. These techniques need to be used within the context of a booking control structure, as described in Section 8.5. In practice, booking limits are periodically calculated offline for a flight and transmitted to the reservation system, where they are used to control bookings. The combination of periodic recalculation of booking limits and the nested booking limits within the reservation system defines a dynamic booking control process.

Dynamic Booking Control Process

1. Calculate the initial booking limits for a flight.

2. When a booking request for class j is received, compare the number of seats requested with the current booking limit for the class.

3. If the number of seats requested exceeds the booking limit for class j, reject the request and go to step 6.

4. If the number of seats requested is within the booking limit for class j, accept the request. Depending on the capabilities of the reservation system, update booking limits using either standard nesting or theft nesting.

5. When a booking cancels, either (a) increment the booking limits for classes with positive availability by the number of seats canceled (irreversible) or (b) increment to booking limits for all classes by the number of seats canceled (reversible).

6. Periodically recalculate all booking limits based on total bookings and demand expected in each class until departure. (This recalculation is often called a reoptimization.)

This dynamic booking control process makes no assumption about the nature of the reoptimization approach being used or the frequency with which reoptimizations occur. In fact, there is considerable variation among companies in the optimization approaches used and the frequency and situations under which they are applied. There is a general belief that frequent reoptimization is important—particularly when demand is changing rapidly or departure is approaching and bookings and cancellations are being received at a high rate. Often, the trade-off is between using a more complex algorithm and reoptimizing less often versus using a simpler algorithm and reoptimizing more often. These issues are the topics of ongoing research and are by no means settled.

9.6 MEASURING CAPACITY ALLOCATION EFFECTIVENESS

As noted in Chapter 8, revenue per available seat mile (RASM) is the metric most widely used to measure the overall effectiveness of revenue management at an airline. RASM is a good high-level measure, but it does not tell the entire story. It is often not immediately clear why RASM is high or low in a particular market. Are we achieving a high RASM in a particular market relative to the competition because we have superior service? Superior marketing? Better revenue management? All of these? Or have we simply assigned too few seats to the market? RASM by itself does not address the important need to isolate and measure the effects of revenue management separately from other influences in a market. The need to understand the effects of revenue management is important because revenue management software systems are expensive, usually requiring millions of dollars of investment in software and hardware. Revenue management programs are also expensive to operate—a major airline may have a department of 50 or more people dedicated to running the revenue management system and reviewing and updating its forecasts and recommendations. How can management be convinced that this expensive and somewhat esoteric department is yielding results that justify this investment? A metric specifically targeted at measuring revenue management effectiveness is required.

One popular approach to measuring revenue management effectiveness is the revenue opportunity model originally developed by American Airlines (Smith, Leimkuhler, and Darrow 1992). The revenue opportunity model assumes we have a record of all the booking requests we received for a flight—those we accepted and those we rejected. We then measure the revenue that could be achieved from a specific flight under two extreme cases. In the base case, bookings are accepted in the order in which they are received until the capacity constraint is reached or demand is exhausted, whichever comes first. The revenue achieved in the base case is the flight’s performance without any revenue management—we can call it the “No RM Revenue.” In the perfect revenue management case, bookings are accepted in decreasing order of revenue until demand is exhausted or the capacity constraint is reached. In this case, no booking is accepted that would displace a higher-fare future booking. This represents a case in which we achieved as much revenue as possible given the demands for different fare classes. We call the revenue calculated this way the “Perfect RM Revenue.” Of course, this level of performance is not achievable because it would require perfect foresight on future demand.

It should be clear that the revenue achieved under perfect revenue management will always be greater than or equal to the revenue achieved under no revenue management. If the flight is full, the revenue achieved under any actual revenue management program will generally lie between these extremes—better than no revenue management but never better than perfect revenue management.⁶ The total revenue opportunity on a flight is the difference between the revenue achieved from perfect revenue management and the revenue achieved from no revenue management. Then the revenue opportunity metric (ROM) is the revenue actually achieved from that flight minus the revenue that would have been achieved under no revenue management expressed as a percentage of the total revenue opportunity.

Example 9.7

Senilria assigned a 100-seat aircraft to a particular route with four booking classes. The fares for the four booking classes were F = $1,000, Y = $800, M = $600, and B = $200. Using its sophisticated revenue management system, Senilria set booking limits of (32, 45, 70, 100) for the flight. Actual demand for this flight by booking class came in at F = 25, Y = 30, M = 20, and B = 50. To determine the ROM for the flight, calculate as follows:

Perfect RM revenue = 25 × $1,000 + 30 × $800 + 20 × $600 + 25 × $200 = $66,000

No RM revenue = 30 × $800 + 20 × $600 + 50 × $200 = $46,000

Realized revenue = 25 × $1,000 + 25 × $800 + 13 × $600 + 32 × $200 = $59,200

Thus, Senilria realized a ROM of ($59,200 − $46,000)/($66,000 − $46,000) = 66% on this flight departure.

Example 9.7 illustrates the calculation of ROM using a single flight departure. In practice, ROM is only meaningful when applied to a large number of flights. And even then, changes in ROM are probably more meaningful than the absolute measure itself. For example, for the case of the 90-seat flight with results shown in Table 9.4, the expected revenue that was achieved using an optimal capacity allocation algorithm was $74,003. For the 500,000 replications of this flight, the first-come, first-served revenue was $61,215 and the maximum possible revenue was $79,458. This means that the ROM achieved from using an optimal algorithm was ($74,003 − $61,215)/($79,458 − $61,215) = 70.1%. Since this result was achieved using an optimal algorithm with the same means and standard deviations that were used to generate the actual loads, it represents an upper bound to the average revenue that could be achieved in practice.

ROM has been used by airlines, hotels, and other RM companies to measure the effectiveness of their revenue management programs. American Airlines claimed that its systemwide ROM increased from 30% in 1988 to 49% in 1990 as the result of better revenue management systems and processes (Smith, Leimkuhler, and Darrow 1992). ROM has also proven useful in evaluating the performance of different forecasting and optimization algorithms as well as in measuring the performance of revenue managers. However, it can be sensitive to changes in market conditions. For example, the ROM for a flight with very low demand will always be close to 100%, since every booking will be accepted. On the other hand, a flight with high uncertainty in high-fare demand (a high standard deviation) will tend to have a lower ROM than one with the same expected high-fare demand but less uncertainty (a lower standard deviation). This means that changes in ROM for a flight or group of flights may be due to changes in the underlying structure of demand rather than changes in revenue management effectiveness.

9.7 SUMMARY

• The capacity allocation problem is how to regulate booking requests for a product consisting of a single resource over time in order to maximize revenue or contribution. For most revenue management companies, this is solved by periodically setting and updating booking limits for a nested booking control structure. The problem is typically posed assuming that bookings occur in order of increasing fare.

• At the heart of the two-class problem is the trade-off between accepting too many discount bookings, which cannibalizes future full-fare demand, and accepting too few discount bookings, which means that the plane departs with empty seats. Littlewood’s rule finds the booking limit that balances these two risks to maximize total expected contribution.

• The underlying trade-off when there are more than two fare classes is the same as in the two-class problem: accepting too many early discount bookings may cannibalize future full-fare bookings, whereas accepting too few may lead to empty seats. However, when there are more than two fare classes, there is no easy closed-form solution for finding the optimal booking limits. Rather, airlines and other revenue management companies typically rely on various heuristic approaches, of which EMSR-a and EMSR-b are the best known.

• The basic EMSR approaches to multiple-fare class booking control do not incorporate the fact that opening or closing a fare class will change the anticipated demand in other fare classes for the same product. EMSR heuristics are often modified to incorporate the phenomenon of dependent demand, also known as buy-up and sell-down.

• Incorporating a fully flexible model of consumer choice is complex because the combinations of booking classes that could be offered is 2ⁿ, where n is the number of classes. However, the number of efficient sets, which are the only ones that need to be considered, may be much smaller than the number of possible sets. Furthermore, the efficient sets can be nested in order of increasing revenue and potential demand in a way that facilitates nesting.

• An alternative to explicit optimization or heuristics is a data-driven approach in which the booking limits that would have maximized expected revenues for past flights is calculated and applied to future flights.

• Typically, the decision of whether to accept a particular booking request is based on whether there is sufficient availability for that class in the booking system. The function of the revenue management system is to periodically update the booking limits in the system based on current bookings and changes in the market.

• A common way for airlines and other revenue management companies to measure the effectiveness of their capacity allocation is by using the revenue opportunity metric, or ROM. ROM measures the revenue actually achieved as a percentage of the maximum revenue that could have been achieved if the supplier had perfect forecasts of future demand. ROM is not an absolute measure, because underlying uncertainty in demand ensures that 100% ROM can never be achieved. But it is a good relative measure of how well different flights are being managed.

Capacity allocation is the first of the three constituents of revenue management that we study. Network management, which is treated in Chapter 10, extends the ideas from this chapter to the case in which a company is selling products that consist of more than one resource. Overbooking, treated in Chapter 11, extends the idea of capacity allocation still further, to the situation in which bookings can cancel or not show.

9.8 FURTHER READING

As noted in Section 9.2, there is no closed-form solution to the multiclass booking problem. Curry 1990, Wollmer 1992, and Brumelle and McGill 1993 describe three different solution approaches utilizing dynamic programming. A comparison among these three approaches is given in Li and Oum 2002. The equivalence between Littlewood’s rule and the critical fractile approach is described in Netessine and Shumsky 2002.

The seminal paper on incorporating choice in optimal capacity allocation is Talluri and van Ryzin 2004a. The example in Section 9.3.3 was adapted from Talluri and van Ryzin 2014. A good survey of research on incorporating choice into capacity allocation is Strauss, Klein, and Steinhardt 2017, which provides many additional references to research.

9.9 EXERCISES

1. Roll back the decision tree in Figure 9.7 to determine a formula for the period 3 booking limit that would maximize expected net revenue given the displacement probabilities q₁ and q₂.

2. Granite State Airlines serves the route between New York and Portsmouth, New Hampshire, with a single-flight-daily 100-seat aircraft. The one-way fare for discount tickets is $100, and the one-way fare for full-fare tickets is $150. Discount tickets can be booked up until one week in advance, and all discount passengers book before all full-fare passengers. Over a long history of observation, the airline estimates that full-fare demand is normally distributed, with a mean of 56 passengers and a standard deviation of 23, while discount-fare demand is normally distributed, with a mean of 88 passengers and a standard deviation of 44.

a. A consultant tells the airline it can maximize expected revenue by optimizing the booking limit. What is the optimal booking limit?

b. The airline has been setting a booking limit of 44 on discount demand, to preserve 56 seats for full-fare demand. What is its expected revenue per flight under this policy? (Hint: Use a spreadsheet.)

c. What is the expected gain from the optimal booking limit over the original booking limit?

d. A low-fare competitor enters the market and Granite State Airlines sees its discount demand drop to 44 passengers per flight, with a standard deviation of 30. Full-fare demand is unchanged. What is the new optimal booking limit?

3. Granite State Airlines also serves the route between Washington, D.C. (Reagan), and Portsmouth, New Hampshire, with a single flight daily. The airline sells both discount-fare and full-fare tickets. The airline has assigned a 100-seat aircraft to the flight. Using Littlewood’s rule, the airline has determined that the optimal discount-fare booking limit for a flight departing in two weeks is 40.

a. What is the protection level for the flight?

b. The revenue manager has learned that the annual Yorkshire Terrier Fancier’s Convention will be in Portsmouth in two weeks. As a result, he increased the forecast of mean discount-fare demand by 50% over its previous value. The full-fare forecast remained the same. What are the new booking limits and protection levels for this flight?

TABLE 9.9

Booking demands by fare class for the previous 12 departures for the Senilria flight described in Exercise 4

c. Right after learning about the Yorkshire Terrier Fancier’s Convention, the revenue manager learned that, because of maintenance problems, there will also be a switch of aircraft on the flight. Instead of a 100-seat aircraft, the flight will be served by a 120-seat aircraft. What are the new booking limits and protection levels for this flight?

d. The full fare for the flight is $200, and the discount fare is $100. What is the expected full-fare demand for this flight, assuming that both discount-fare and full-fare demand follow normal distributions?

4. Senilria Airlines has started a new flight from Rome to Palermo, Sicily, once a week on Monday mornings and has operated the flight for the last 12 weeks. Senilria offers three booking classes on the flight: B-Class with a fare of €70, M-Class with a fare of €120, and Y-Class with a fare of €200. The demand for each fare class for each of the previous 12 flight departures is shown in Table 9.9.

a. Assume that Senilria has assigned a 200-seat aircraft to this flight for the initial 12 flights and for the next flight. Using the data-driven approach, what would be the recommended booking limits for each of the three classes for the 13th departure? What is the expected revenue?

b. Assume that Senilria is considering assigning a 225-seat aircraft to the Rome-to-Palermo flight for the next departure. Given a capacity of 225 seats, what are the recommended booking limits for each of the three classes for the 13th departure? What is the expected revenue? What is the additional revenue from the 25 seats of extra capacity?

NOTES

1. Here we use the notation F̄(x) to denote the complementary cumulative distribution (CCDF) associated with the cumulative distribution function F(x). It is defined by F̄(x) = 1 – F(x). More details can be found in Appendix B.

2. We use the discrete version of the normal distribution here, so some of the expressions that follow need to be treated with care. See Appendix B for details.

3. That is, if Φ(y) = x, then Φ^-1(x) = y. Some properties of the inverse normal distribution are discussed in Appendix B.

4. Airlines typically find that the standard deviation of demand ranges from 25% to 75% or more of the expected demand. This is equivalent to saying that the coefficient of variation, defined as σ/μ, ranges from 0.25 to 0.75.

5. The term “bid price” is unfortunate because it is easily confused with the idea of bidding in an auction. This is not the situation in revenue management usage—the bid price is the minimum price that a seller would accept for another unit of a resource (such as a seat on a flight). The closest concept in auction theory is the reserve price, which is the minimum amount a seller would accept for an item. However, the terminology is standard, so we use it.

6. It is possible for achieved revenue to be lower than the no-revenue-management case if too many early-booking requests were rejected in anticipation of future bookings that did not materialize.