10
When every product offered by a supplier uses only a single resource, the supplier can maximize total profitability by maximizing the profitability of each resource independently. For example, a Broadway show can maximize total revenue over a season by setting prices and availabilities that maximize revenue independently for each performance.1 However, a seller that sells products that use multiple resources—such as an airline selling tickets on connecting flights or a hotel selling multiple-night stays—faces a much more complex problem. The seller can no longer maximize total contribution by maximizing contribution from each resource independently. Rather, he needs to consider the interactions among the various products he sells and their effect on his ability to sell other products. This is the challenge of network management—the topic of this chapter.
Chapter 9 describes the techniques used to maximize expected profitability for a single resource. This is all that is needed by airlines such as EasyJet that only allow single-leg bookings.2 These airlines—like the Broadway show—can maximize total profitability by maximizing the profitability of each resource independently. However, this approach will not maximize system profitability for airlines that offer passengers the opportunity to buy tickets for two or more connecting flight legs. Hotels and rental car companies also sell multiple-resource products, since hotel guests can stay for more than one night and rental car customers can rent for more than a day. Network management is applicable to any company controlling a set of constrained and perishable resources and selling products that consist of combinations of those resources.
Section 10.1 introduces the network management problem and the types of industries in which it applies. The section also demonstrates why the problem is complex and why a simple and intuitive greedy heuristic does not work. The subsequent sections present various solution approaches to the network management problem. One intuitive approach is linear programming. However, linear programming is a computationally intensive procedure that can only be run on a periodic basis. In the interim, most airlines use some version of virtual nesting to manage booking requests. We examine virtual nesting and the concept of net leg fare (sometimes called net local fare), which is a consistent way to rank (and hence nest) network booking requests. Section 10.4 shows how bid pricing can be used in network management, and Section 10.5 discusses some of the issues involved in implementing network management.
10.1 WHEN IS NETWORK MANAGEMENT APPLICABLE?
Network management is important in any revenue management industry that sells products consisting of more than one resource. As shown in Table 8.7, there are some revenue management industries, such as cruise lines and event ticketing, in which network management does not play a major role.3 By contrast, in the industries shown in Table 10.1, managing products that consist of combinations of resources is a critically important aspect of revenue management.
Network management is very important to business hotels, rental car companies, and multiunit housing—and indeed to any company that rents out capacity for periods of varying duration. Network management is also important to airlines that offer connecting service. This can be seen from Figure 10.1, which shows the distribution of passengers by fare class and total fare paid on a flight from San Francisco to Chicago. There are three fare classes on this flight: full fare (Y), discount (M), and deep discount (B). In general, Y-Class passengers tend to pay more than M-Class passengers, who tend to pay more than B-Class passengers. However, fare class is not a perfect proxy for revenue. Some B-Class passengers pay more than $400 and some Y-Class passengers pay less than $250. Managing this flight based on fare class alone will not maximize revenue. If this airline closes B-Class, it will still be accepting Y-Class (and M-Class) passengers who are paying less than $250 while rejecting B-Class passengers willing to pay more than $400 for a seat. Furthermore, managing by fare class does not allow the airline to take advantage of the spread of fares within each class. If capacity on this flight were constrained, the airline might want to accept only passengers paying more than, say, $200.
TABLE 10.1
Examples of multi-resource products from various revenue management industries
Figure 10.1 Distribution of total fares by fare class on an example flight.
Consider an airline that has San Francisco and Chicago as hubs. This means that the San Francisco–to-Chicago flight carries passengers traveling from many origins to many destinations. Only a small fraction of the passengers are actually flying from San Francisco to Chicago; the majority are connecting in either San Francisco or Chicago (or both). For example, the highest fares on the flight (those with total fare over $3,000) might be flying from Tokyo to Chicago via San Francisco or from San Francisco to Paris via Chicago. Other passengers might be flying from San Francisco to Chicago to Grand Rapids or from Fresno to San Francisco to Chicago, and so on. Each origin-destination combination can be purchased in different fare classes, adding even more complexity. The fare for an M-Class Tokyo-to-Chicago passenger is likely to be higher than a Y-Class San Francisco–to-Chicago passenger. Yet leg-based capacity allocation would not allow the airline to accept the M-Class Tokyo-to-Chicago passenger while rejecting the Y-Class San Francisco–to-Chicago passenger. The goal of network management is to improve revenue by managing the mix of products as well as the mix of fare classes being sold for each product.
Airlines have estimated that network management adds 0.5% to 1% of additional revenue on top of the revenue gains from optimal capacity allocation and overbooking. This may not sound like much, but for a carrier such as British Airways with revenue of about 13 billion British pounds ($16 billion) in 2018, it represents $80 million to $160 million in additional operating profit. Network management is even more critical for hotels and rental car companies. In these industries, managing the mix of bookings by length of stay (or length of rental) provides more leverage than managing by fare class alone. For a hotel, it is usually more important not to accept short-stay bookings that displace future longer-stay booking requests than it is to worry about the rate mix of any individual booking length. For this reason, unlike the airlines, the first successful hotel (and rental car) revenue management systems included network management capabilities.
10.1.1 Types of Network
In the 1960s, major airlines in the United States began to establish hub-and-spoke networks as a way to better leverage their operations. Figure 10.2 shows a hub-and-spoke network with 2 hubs and 13 spoke cities. Each spoke city is connected to one or more of the hubs. Arrivals and departures at the hubs are timed so that passengers arriving from cities to the west of the hub can connect to cities to the east, and vice versa. The hub-and-spoke network allows an airline to offer a large number of products with a relatively small number of flights. With 20 eastbound flights into a hub connecting with 20 westbound flights, an airline can offer 440 products (all possible connections plus the direct flights in and out of the hub) with only 40 total flights. While hub-and-spoke airlines offer some direct flights between spoke cities, the vast majority of their traffic touches at least one hub—as either an origin, a destination, or a connecting point. Airlines operating hub-and-spoke networks include the majority of global carriers including American, Delta, United, Air France, British Airways, and Singapore Airlines, among many others. During the 1980s, most large airlines organized their operations around the hub-and-spoke model and saw their connecting traffic soar. In the United States, about 35% of passengers travel on connecting flights (Berry and Jia 2010). While rushing to make a connection may not be popular with passengers, the efficiency of hub-and-spoke networks means that they are here to stay.
Figure 10.2 Example of a hub-and-spoke network. Nodes A and B are hubs; the other nodes are spoke cities.
The resources for a hotel are room nights, and its products are combinations of arrival date and length of stay. A hotel essentially runs a linear network in which each room night connects to the preceding night and to the following night. Such a network is shown in Figure 10.3. Passenger railway networks are also linear; for example, Amtrak’s California Zephyr starts at Emeryville, California, and terminates in Chicago, making 33 intermediate stops along the way. A passenger boarding the Zephyr at Emeryville can get off at any one of 34 stops (the 33 intermediate stops plus Chicago); a passenger boarding at the second stop (Martinez, California) can get off at any one of 33 stops; and so on. Each of the 34 legs is a resource, and each combination of origin and destination is a product. The typical passenger railroad has a linear network similar to the hotels and rental car companies, but with the length of the network equal to the number of legs being offered.
Figure 10.3 A linear network, typical of hotels, passenger rail, and rental car companies.
Each product in a network has one or more associated fare classes. The network management problem is to determine which booking requests to accept for every possible combination of product and fare class at every time. We use the term origin-destination fare class (or ODF) for a product–fare class combination.4 While ODF is an airline term, we use it to refer to a combination of product and fare class in any industry. Thus, for a hotel, a four-night rack-rate5 booking arriving June 13 is a different ODF than a three-night discount booking arriving on June 14. The goal of network management is to manage and update the availability of all ODFs over time to maximize expected contribution.
The number of products being offered by a hotel or rental car company can be very large—much larger, in fact, than the number of rooms in the hotel. A hotel accepting reservations for customers arriving for the next 365 days with stays from 1 up to 15 days in length is offering 15 × 365 = 5,475 different products. In fact, the number of products can be even larger, since each room type corresponds to a different product dimension. A particular hotel might have four different types of room (for example, standard, deluxe, deluxe view, and suite), for which it can charge different rates. Since a customer can book any one of these room types for any arrival date and length of stay, the number of products being offered by the hotel is actually 4 × 15 × 365 = 21,900. In other words, a hotel may well be offering 100 times more products than it has rooms! On the other hand, cruise lines typically offer only one or two options for embarkation and disembarkation per sailing. The different products on a particular sailing are determined by the different cabin types, for example, upper-deck outside versus lower-deck inside.
10.1.2 A Greedy Heuristic for Network Management—and Why It Fails
Consider a 100-room hotel facing the unconstrained demand pattern for some future week shown in Figure 10.4. (Unconstrained demand is the total number of room nights the hotel could sell if it accepted every booking request.) The pattern shown in Figure 10.4 is typical of a midtown business hotel—demand is low on the weekend and peaks during the middle of the week. In this example, unconstrained demand exceeds capacity on Wednesday. This means that the hotel will need to reject some bookings or it will be oversold on Wednesday (ignoring no-shows and cancellations). The network management problem faced by the hotel is to decide which bookings to accept and which to reject considering both room rate and length of stay in order to maximize expected contribution margin.
Figure 10.4 Typical unconstrained occupancy pattern for a midtown business hotel.
Let us say that the hotel offers two rates: a rack rate of $200 per night and a discount rate of $150 per night. The hotel manager might look at the demand pattern in Figure 10.4 and conclude (correctly) that the hotel’s constrained resource is Wednesday night capacity. The manager might reason that the best way to maximize operating profit is to limit the number of discount-rate customers booking any product that includes Wednesday night to protect availability for rack-rate customers. In other words, the hotel might manage bookings based strictly on fare class. This approach might improve revenue relative to a first-come, first-served policy, but it has an obvious drawback. Rack-rate customers arriving Wednesday for a one-night stay pay $200. But discount-rate customers arriving Tuesday for a three-night stay pay $450. If the hotel limits discount bookings to save room for full-fare bookings, it runs the risk of turning down a $450 customer to save room for a $200 customer—a prime revenue management sin. Clearly a more sophisticated approach is required if the hotel is to maximize expected revenue.
When there is only a single constrained resource, the manager could arrange all of the ODFs that use the constrained resource by total rate paid and solve the multiclass problem using EMSR or a similar heuristic.6 This would mean that the lowest class on Wednesday would be one-night discount customers paying $150, the next highest class would be one-night rack customers paying $200, followed by two-night discount stays for either Tuesday–Wednesday or Wednesday–Thursday paying $300, followed by two-night rack customers paying $400, and so on. By establishing classes in this fashion and setting the appropriate booking limits, the hotel would maximize expected operating contribution as long as unconstrained demand exceeded capacity only on Wednesday night.
Sorting all the ODFs on each leg in fare order and setting availabilities based on total fare is called the greedy heuristic for network revenue management. The greedy heuristic is optimal if there is only a single constrained resource (that is, only a single bottleneck). It works perfectly in the hotel example if unconstrained demand for hotel rooms exceeds capacity only on Wednesday night. However, the greedy heuristic breaks down quickly when more than one resource is constrained. This would be the case for the hotel if unconstrained demand exceeded 100 rooms on both Wednesday and Thursday nights. In this case, it is no longer optimal for the hotel to order fare classes strictly by total revenue. The hotel should accept a two-night Wednesday–Thursday discount booking paying $300 if it believes that Thursday is not going to sell out. But if it believes that Thursday is going to sell out, it may be better off rejecting the $300 two-night booking in favor of waiting for two $200 one-night rack-rate bookings for Wednesday night and Thursday night.
The implication is that when multiple resources are constrained, the right ordering of ODFs on a leg can depend on the fares and demands for all the other ODFs as well as the capacities of all the other resources in the network. In fact, as we accept bookings over time and update our forecasts of future demand, the ordering of ODFs on each leg may change as well: there is no stable optimal ordering of ODFs when multiple resources in a network can be constrained.
The failure of the greedy heuristic can be illustrated with the simple network shown in Figure 10.5, where an airline offers two flights—Flight 1 from San Francisco (SFO) to Denver (DEN) and Flight 2 from Denver (DEN) to St. Louis (STL)—that have been scheduled so that passengers can connect from Flight 1 to Flight 2 at Denver. For simplicity, let us assume that the airline offers a single fare for each product and that the San Francisco–to-Denver fare is $200, the Denver-to–St. Louis fare is $160, and the San Francisco–to–St. Louis fare is $300. The airline has exactly one seat left on each of the two flights and has a customer who is willing to pay $300 for a ticket from San Francisco to St. Louis. Should the airline let her book? Or should the airline reject the booking in the hopes of booking local passengers on both legs? Let p1 be the probability that the airline will receive at least one future booking request for Flight 1 and p2 be the probability that the airline will receive at least one future request for Flight 2. Then the expected value of refusing the connecting customer and letting only the local customers book is $200p1 + $160p2. If this amount is greater than $300, then the airline is better off refusing the connecting customer and relying on local traffic to fill the last seats. If, on the other hand, $200p1 + $160p2 < $300, then the airline should go ahead and allow the connecting passenger to book.
Figure 10.5 A simple hub-and-spoke network.
The probabilities p1 and p2 are the airline’s forecasts of future local demand on the two flights. Whether or not the airline should accept the through passenger depends on these forecasts. This can be generalized to a full network: There is no unambiguous answer to the question of whether an airline should prefer connecting traffic to local traffic on a given leg. The right answer depends on the forecasts of future demand for all ODFs. Ultimately, when many resources are constrained, we need to optimize over the entire network to determine which bookings we prefer on any leg in the network.
10.2 A LINEAR PROGRAMMING APPROACH
Linear programming (LP) is a natural approach to allocating scarce resources to competing product demands. In fact, if we take the gigantic leap of assuming that future demands are known with certainty, linear programming provides an exact solution to the network management problem. Since uncertainty is a key element of revenue management decision making, a solution derived while ignoring uncertainty is not wholly satisfactory. However, the linear programming formulation of the network management problem is worth studying for three reasons. First, it solves the capacity allocation component of network management and provides insight into the nature of the optimal solution. Second, the solution to the network management linear program provides a good starting point for a fully optimal solution. In many hotels and airlines, linear programming is used to determine an initial solution, which is then adjusted to account for the uncertainty in future demand. Finally, the linear program generates marginal values of capacity as a by-product. These marginal values approximate the opportunity costs of the capacity and can serve as an estimate of network bid prices, which is discussed in Section 10.4.
To formulate the network management problem as a linear program, assume we know the future demand for every ODF with certainty. Furthermore, assume that this demand will not be influenced by which ODFs we open and close (in other words, we have independent demands on each flight and among flight legs). We have m resources and n ODFs utilizing combinations of those resources with n ≥ m. We use the subscript i to index resources and the subscript j to index ODFs. Each resource i has a constrained capacity Ci > 0. Each ODF has a known demand dj > 0 and a net contribution margin pj > 0. Let xj ≥ 0 be the amount of ODF j we will allow to book (our allocation). Then the deterministic network management problem is to find the values of xj for j = 1, 2, . . . , n that maximize total net contribution subject to the constrained capacities of the resources.
To complete the formulation, we need to represent which resources are used to produce each ODF. To do this, we define the incidence variable aij as follows:
To illustrate the use of the incidence variables, consider the simple flight network shown in Figure 10.5. There are two resources in this network: (1) Flight 1 from San Francisco to Denver and (2) Flight 2 from Denver to St. Louis. With three products and two fare classes, the airline is offering six ODFs:
1. San Francisco to Denver full fare
2. San Francisco to Denver discount
3. Denver to St. Louis full fare
4. Denver to St. Louis discount
5. San Francisco to St. Louis full fare
6. San Francisco to St. Louis discount
Using this numbering, a11 = 1 because the San Francisco–to-Denver full-fare ODF uses flight 1, while a13 = 0 because the Denver-to–St. Louis full-fare ODF does not utilize Flight 1. The values of all the incidence variables for this simple example are shown in Table 10.2.
It is instructive to compare the hub-and-spoke network in Table 10.2 with the pattern of incidence variables for a linear network. Consider a hotel that offers one-night, two-night, and three-night products only. The resources for the hotel are the room nights, and the products are combinations of arrival night and length of stay. Table 10.3 shows the values of the incidence variables (aij) for three different lengths of stay and a week of resources. In theory, the network management problem for a hotel stretches out indefinitely into the future. In practice, a hotel will only accept bookings for some limited period into the future (often a year), limiting the number of resources and products that need to be managed. Furthermore, in theory a hotel offers an infinite number of products, since customers can book any length of stay. In practice, lengths of stay longer than 14 nights are extremely rare at most hotels, and hotels usually manage them as a single product.
TABLE 10.2
Values of the incidence variables (aij) for the two-flight example
TABLE 10.3
Values of the incidence variables (aij) for a hotel
NOTE: Numbers under the arrival day indicate length of stay in days.
10.2.1 The Deterministic Network Linear Program
We can now formulate the deterministic network management problem as a linear program:
subject to
The variables x1, x2, . . . , xn are the total seats allocated to each ODF. The objective function 10.2 stipulates that the goal is to accept the demand that maximizes total net contribution. There is one constraint of the form of (10.3) for each resource. These constraints ensure that the airline can physically accommodate all the demand that it accepts. The demand constraints in (10.4) stipulate that sales of each ODF are limited by demand for that ODF. Finally, (10.5) ensures that all allocations are greater than or equal to zero.
Example 10.1
An airline is operating the two-flight airline network in Figure 10.5 and offering a full fare and a discount fare for each of the three itineraries. There are six ODFs using two resources, and the ODF-resource mapping is as shown in Table 10.2. The airline has assigned a 100-seat aircraft on Flight 1 from San Francisco to Denver and a 120-seat aircraft on Flight 2 from Denver to St. Louis; demands and fares are as shown in Table 10.4. Notice that the unconstrained demand is 160 on the San Francisco–to-Denver flight and 170 on the Denver-to–St. Louis flight. Since these demands exceed the flight capacities for the two flights, we will need to turn some passengers away. The linear program for this example is
which can be solved easily using Excel’s SOLVER or any other LP program.
TABLE 10.4
Two-flight network management example fares and demands
TABLE 10.5
Two-flight network management example solution
The optimal allocations for Example 10.1 and the total net contribution are shown in Table 10.5. Note that in this case, we took all of the full-fare passengers for each product. We also took some (but not all) of the local discount traffic in both markets and none of the San Francisco–to–St. Louis discount through traffic. At first glance, it might seem surprising that we did not take any of the San Francisco–to–St. Louis discount traffic, since those passengers were paying the second-highest fare in the system—more than any of the local full-fare passengers and much more than any of the local discount passengers. But the reason we rejected them is obvious when we look at the total network: The sum of the fares paid by the local passengers was greater than the San Francisco–to–St. Louis discount fare. Given our demand forecasts, we gain more contribution for the system by rejecting the discount through passengers in favor of local demand.
10.2.2 Structure of the Optimal Solution
Notice that in the optimal solution shown in Table 10.5, ODFs fall into three categories:
1. ODFs for which we did not accept any bookings (San Francisco to St. Louis discount)
2. ODFs for which we accepted some but not all of the demand (Denver to St. Louis discount and San Francisco to Denver discount)
3. ODFs for which we accepted all of the demand (all of the full-fare ODFs)
In the optimal solution to the deterministic network management problem there will be, at most, one fare class for each product for which we accept some but not all demand.7 All of the other fare classes for that product will be all or nothing: we will either accept all of their demand or none of it. Acceptance of fare classes for a product proceeds in fare order:
For each product there is a set of fare classes (possibly empty) for which we accept all of the demand and a set of fare classes (possibly empty) for which we accept none of the demand. The fares for the fully accepted classes are all higher than the fares for those classes for which we accept none of the demand. Finally, there may be one class for which we accept only some of the demand. This class will have a fare higher than the fares of the rejected classes but lower than the fully accepted classes.
Example 10.2
An airline operates on the flight network shown in Figure 10.5 with the same total demand by product as in Example 10.1, but with five classes per product, with the fares and ODF demands shown in the fourth and fifth columns of Table 10.6. This airline is offering 15 ODFs. The optimal allocations are shown in the corresponding column of Table 10.6. For the San Francisco–to–St. Louis product, it is optimal to accept all passengers who pay more than $200 and reject those who pay less. The airline should accept exactly 7 of those paying exactly $200, out of a total demand of 10. Similarly, for the Denver-to–St. Louis product, the airline should accept everybody paying more than $75 and reject everybody paying less than $75 while accepting 13 out of 30 passengers willing to pay exactly $75. For the San Francisco–to-Denver product, the airline should accept everyone paying more than $130 and reject all requests whose associated fares are lower than $100.
Example 10.2 shows that we never want to be accepting bookings for a lower fare class when we are rejecting them for a higher fare class for the same product. For the example in Table 10.6, there is no combination of demands, capacities, or fares for which it would be optimal to accept San Francisco–to–St. Louis $170 bookings while rejecting San Francisco–to-Denver $180 bookings. On the other hand, it is optimal in the example to reject $190 San Francisco–to–St. Louis bookings that use the San Francisco–to-Denver leg while accepting $130 San Francisco–to-Denver bookings. In network management, fare classes should be nested by product but not by resource.8
TABLE 10.6
Expanded network solution
10.2.3 Strengths and Weaknesses of the Linear Programming Approach
Efficient linear programming solution packages, such as CPLEX, have made the linear programming formulation solvable, even for many large airlines. To account for uncertainty, expected demand is often used in the demand constraints (10.4), and various adjustments are made to account for overbooking and for the dynamic nature of bookings and cancellations. On the other hand, working with a large linear program is often cumbersome and produces a large number of outputs (the ODF allocations) that can be difficult to interpret and implement. A large hub-and-spoke airline may have many ODFs with very low levels of demand. For example, a major hub-and-spoke airline offers connecting service between many small cities that have very small demand—say, Portland, Maine, to Chicago and San Francisco to Santa Barbara, California. This may be a perfectly valid set of connections and therefore a product that the airline wants to offer, but the expected demand for this product would likely be fewer than one passenger per day and the expected demand per fare class for this product would be even smaller. Many hub-and-spoke airlines offer thousands of such ODFs with very low levels of demand—less than one expected booking per month in many cases. But these ODFs still need to be managed, and linear programming would require calculating and maintaining a booking limit for each of them. This is a tremendous amount of computational and implementation overhead to manage a large number of ODFs that collectively may only represent a small fraction of total demand and revenue.
There are other issues with linear programming as a network revenue management approach. One is that it is not immediately clear how to incorporate demand uncertainty. One obvious approach is to replace the deterministic demands for each ODF, dj, with the mean demand for that ODF, μj. But analogy with the single-leg case will show that this will not provide an optimal solution: maximizing revenue based on expected demand does not maximize expected revenue.
Finally, the astute reader will notice that the network linear program has been formulated in terms of calculating allotments for different ODFs. As Section 9.4 shows, the allotment approach breaks down when bookings do not arrive in strict fare order. This is an even more pressing issue with network management than with leg-based management—it is extremely unrealistic to expect that passengers booking on different ODFs would oblige us by booking in strict order of value to the airline. In fact, passengers flying high-fare, multileg itineraries often book earlier than those flying lower-fare, single-leg itineraries. In theory at least, we could deal with the dynamics of network management by rerunning the linear program each time a booking is accepted or a cancellation takes place. However, the size and complexity of the corresponding linear program render this approach impractical. What we really need is a way to extend the concept of nesting to booking requests that utilize multiple legs. The most common way to do this in many travel-related industries is by virtual nesting, which is discussed in the next section.
10.3 VIRTUAL NESTING*
Virtual nesting is rather technical and specific to airlines and a number of other travel-related industries, and this section can be skipped by readers without a particular interest in travel-related industries.
Virtual nesting was the earliest approach to network management. It was first applied by American Airlines (Smith, Leimkuhler, and Darrow 1992), and variations on the basic idea are in use at many airlines today. Virtual nesting was developed to allow an airline to apply the preexisting, leg-based control structures in its reservation system to the network management problem with minimal changes. As the name implies, it allows ODFs to be nested. Because it is extremely flexible and can be implemented relatively easily, some variation of virtual nesting is used by practically every airline that has implemented network management.
The first step in airline virtual nesting is to define a set of buckets on each flight leg. Each bucket represents a range of fare values. The second step is to map each ODF into a bucket on each of its legs based on an estimate of the ODF’s value to the airline. The process of mapping ODFs into buckets on legs is called indexing. At the end of the indexing process, each bucket contains ODFs of similar value. (For the moment, we will defer the question of how we might calculate the value of an ODF.) We will use the convention that the lowest-numbered bucket on each leg contains the highest-value ODFs. The buckets are nested so that bucket 1 has access to the entire capacity of the leg, bucket 2 has access to all the inventory except that protected for bucket 1, and the lowest-value bucket has access only to its own allocation. Each bucket has a booking limit and a protection level that is updated every time a booking is accepted or a cancellation occurs. This means we can apply all of the mechanics for leg-based revenue management to buckets.
Example 10.3
An airline operating the simple network shown in Figure 10.5 offers a Y-Class fare and an M-Class fare for each product. This is a total of six ODFs. The airline has established three buckets on each leg. Then one possible indexing is illustrated in Figure 10.6. In this case, the airline maps SFO-STL Y-Class passengers into bucket 1 on Flight 1 but into bucket 2 on Flight 2. This means that the SFO-STL Y passengers will have access to the entire capacity of Flight 1, but they only have access to the bucket 2 allocation of Flight 2, which is less than the capacity of the plane.
A schematic diagram of a virtual nesting system is shown in Figure 10.7. The reservation system now has an additional function that maps booking requests to buckets as they arrive. Once a booking has been mapped to buckets on each leg, the reservation system checks availability of the appropriate bucket on each leg to determine whether the booking should be accepted. This function is closely analogous to the booking control function when booking requests are managed one leg at a time, as described in Section 8.5. In fact, most network management systems utilize the fare class booking structures within the reservation systems as their buckets. The function of the revenue management system in a virtual nesting approach is both to maintain and communicate the latest indexing and to calculate and update booking limits for each bucket on each leg.
Figure 10.6 Example mappings of ODFs for a two-flight network.
Figure 10.7 Schematic view of a virtual nesting architecture for network management.
10.3.1 Virtual Nesting Booking Control
The management of bookings under virtual nesting proceeds in a fashion closely analogous to single-leg booking control.
Virtual Nesting Booking Control
1. Initialization
a. Establish an indexing that maps every ODF into a bucket on each leg in the ODF.
b. For each leg bucket, estimate the mean and standard deviation of total forecasted demand.
c. Using the mean and standard deviation of demand by bucket, average contribution by bucket, and leg capacity, use EMSR or a similar approach to determine booking limits and protection levels for each bucket on each leg.
2. Operation
a. When a booking request for an ODF is received, check each leg in the ODF. If there is sufficient capacity in the corresponding bucket on each leg, accept the request. Otherwise reject it.
b. If the booking is accepted, reduce bucket availabilities on all legs in the booked ODF.
c. When cancellations occur, increase bucket availabilities for each leg in the canceled ODF.
3. Reoptimization
a. Periodically reforecast demand for each ODF and update expected bucket demand by leg.
b. Periodically rerun EMSR or other algorithm to recalculate nested booking limits for each bucket based on the new forecasts and capacity remaining on each leg.
Note that virtual nesting could be described as leg-based revenue management plus indexing. The connection to leg-based revenue management is a strength—it allows airlines to use the well-established (and hard-to-change) nested fare class structures within their reservation systems.
Another strength of virtual nesting is its flexibility. As an example, simply mapping all ODFs from the same fare class into the same bucket on each leg (i.e., mapping all M-Class bookings into an M-Class bucket on each leg and all Y-Class bookings into a higher Y-Class bucket) will give the same results as managing each leg independently. More usefully, an airline can use virtual nesting to provide preferential availability to an ODF simply by mapping it to higher buckets on its constituent legs. This can be useful, for example, if the airline is running a marketing campaign and wants to ensure that sufficient availability will be maintained for certain discount fares—even if it may not be optimal to do so from a revenue maximization point of view.
10.3.2 Indexing
Virtual nesting can be described as booking control plus indexing. We have seen how booking control works within virtual nesting. This leaves the question of how ODFs should be mapped to their constituent legs—in other words, how they should be indexed. Both the indexing scheme chosen and the frequency with which it is updated strongly influence not only the additional revenue that will be achieved but also the complexity of the revenue management system. The remainder of this chapter is devoted primarily to describing different indexing approaches and discussing the implications of each.
One immediate thought might be to map an ODF into buckets on each leg based on its total fares; that is, we would map the ODFs with the highest total fare into the highest bucket, those with slightly lower total fare into the second bucket, and so on for every leg. This is equivalent to the greedy heuristic for network management, and, as discussed in Section 10.1.2, the greedy heuristic fails when multiple resources in a network are constrained because it ignores opportunity cost in determining how an ODF should be bucketed on one of its legs. Specifically, an ODF with a high total fare but a high opportunity cost on its other legs should potentially be bucketed below an ODF with lower total fare but no opportunity cost on its other legs. This type of bucketing can never be achieved by the greedy heuristic.
The failure of the greedy heuristic suggests that we need a way of indexing ODFs that includes their opportunity costs. As it turns out, the best way to value an ODF for bucketing on a resource is on the basis of its total fare minus the opportunity cost (if any) on other resources it uses. This quantity, known as the net leg fare, is defined as follows:
The net leg fare for ODF i on leg k is equal to the total fare for ODF i minus the sum of opportunity costs on all resources other than k (if any) in ODF i.
The term net leg fare (also called net local fare) is a bit unfortunate because of its airline connotation. The same calculation holds for hotels, where the resources are room nights, and for rental car companies, where the resources are rental days.
Example 10.4
A hotel has estimated that the opportunity cost for a room on Tuesday night, January 23, is $80 and the opportunity cost for Wednesday night, January 24, is $105. The hotel receives a booking request for two nights, arriving January 23 and departing January 25, with an associated total rate of $220. The net leg fare associated with that booking request is $220 − $105 = $115 for the night of January 23 and $220 − $80 = $140 for the night of January 24.
Note that the net leg fare is calculated by subtracting the opportunity cost on other resources from the total fare. It is a local measure of the incremental contribution of one more booking in the ODF to system profitability, including the opportunity that would be forgone from other legs (if any) in the ODF. Only if the fare associated with the ODF exceeds the opportunity cost for all of the resources it uses should it be accepted. For this reason, it is the right value to use to map products into buckets on each leg.
Example 10.5
Consider the three-city network shown in Figure 10.5. Assume that the opportunity cost on Flight 1 (SFO-DEN) is $250 and on the Flight 2 (DEN-STL) leg is $800. Each leg has three buckets, defined as follows:9
• Bucket 1: Net leg fares $1,000
• Bucket 2: $600 ≤ Net leg fares < $1,000
• Bucket 3: Net leg fares < $600
TABLE 10.7
Net leg fares (NLF) and buckets for six ODFs in the network from Figure 10.5
NOTE: The opportunity cost on Flight 1 is $250, and the opportunity cost on Flight 2 is $800.
Table 10.7 shows how six different ODFs would be mapped into buckets in this case. Note that SFO-STL M-Class passengers are mapped into the highest bucket on Flight 2 but the lowest bucket on Flight 1. This means that on Flight 1 we will be protecting seats for local M-Class passengers from the SFO-STL M-Class passengers; but on Flight 2 the situation is reversed.
10.3.3 Static Virtual Nesting
We are most of the way to a practical approach for network management. We can calculate the net leg fare for each ODF on each of its legs based on its total fare minus the opportunity cost on other legs. This provides an indexing scheme that allows us to map the ODF into a bucket on each leg. If each of the buckets has sufficient availability, we accept the booking; otherwise we reject it. The remaining piece of the puzzle is how to calculate and update the opportunity cost for each leg. It is this calculation that differentiates virtual nesting approaches.
One obvious way to estimate the future opportunity cost for a product is to base it on past experience. This is, in essence, equivalent to forecasting opportunity cost.
Example 10.6
A Tuesday 2:00 flight from San Francisco to Dallas had opportunity costs of $180, $130, $190, $205, and $95 at departure. One way to estimate the opportunity cost for next Tuesday’s flight would be to average the past five opportunity costs; that is, the estimate of next Tuesday’s opportunity cost would be ($180 + $130 + $190 + $205 + $95)/5 = $160.
The method of using historic opportunity costs to map ODFs into buckets is called static virtual nesting. With static virtual nesting, an airline (or other revenue management company) estimates an opportunity cost for each resource based on the sales history of that resource.10 If the resource rarely sells out (e.g., a Tuesday night in a midtown hotel in Detroit), the opportunity cost will be small. If, on the other hand, the resource sells out with regularity, its opportunity cost will be much higher.
Example 10.7
Flight leg 135 has historically sold out 30% of the time, and its average opportunity cost when it sold out is $750. An estimate of the expected future opportunity cost for this leg would be 0.3 × $750 = $225.
There are other approaches to static virtual nesting, but they all have one thing in common: indexing is based entirely on past experience. This means that the indexing for a particular leg will not change during the booking period for a flight. In static virtual nesting, an airline might recalculate its indexing on a monthly or quarterly basis. In the interim, ODFs would always be mapped into the same buckets on each leg.11 For our two-leg airline, the mapping in Table 10.7 would be used for all departures of Flights 1 and 2 within this period. However, this mapping is based on the expectation that Flight 2 is likely to sell out and therefore is assigned a high displacement cost. While this may be true on average, it is unlikely to be true for every departure. For example, we may be almost certain that a particular departure of Flight 2 will not sell out. This means that the expected opportunity cost for this departure of Flight 2 would be close to 0. But by using the mapping in Table 10.7, the airline is mapping connecting passengers into buckets that are too low for this departure.
Another shortcoming of static virtual nesting is implicit in the name: since it is static, it does not respond to changes in the course of the booking process. An airline’s initial forecast of the opportunity cost for a leg might change considerably between first booking and departure. (As we have seen, there is a correspondence between opportunity cost and the boundary between open and closed classes. The assumption that a leg’s opportunity cost does not change between first booking and departure is equivalent to assuming that no buckets will open or close during the time that the flight is open for booking.) For the two-flight example, we could certainly have the situation where an unanticipated surge in bookings (possibly a large group) resulted in Flight 1’s actually closing to future bookings while Flight 2 remained open in bucket 1 but closed in buckets 2 and 3. Using the mapping in Table 10.7, the only ODFs that fall in bucket 1 on Flight 2 are SFO-STL through passengers. But under static virtual nesting, these booking requests will be rejected on Flight 1—which is closed in all buckets. So the system is effectively closed to all bookings, even though there are seats available on Flight 2 that could be profitably filled with local passengers.
It seems apparent that virtual nesting could be improved if we could update opportunity costs more often based on bookings and cancellations as they occur as well as on changing expectations of total demand for a flight. It turns out that, if we update opportunity costs often enough, they can almost serve as the only controls we need for network management. This is the idea behind bid pricing. Section 9.2.3 shows how bid pricing applies to a single leg. We see next how it can be applied to a network.
10.4 NETWORK BID PRICING
Section 9.2.3 describes how we should accept a booking request for a single resource only if the fare associated with the request exceeds the bid price for that resource. Perhaps not surprisingly, there is an equivalent condition for products consisting of multiple resources: we should only accept a multiple-resource booking if the fare exceeds the sum of the bid prices for the constituent resources. This condition can be written as follows:
Accept a booking for a product (ODF) only if the product’s price is greater than the sum of the bid prices on the constituent resources.
The idea behind network bid pricing is to use this condition as the basis of the revenue management system. In an airline bid-pricing system, the revenue management system calculates a bid price for each leg (we see later how this is done) at each time before departure. When a booking request is received, its fare is compared to the sum of the bid prices for its constituent legs. If the fare for the request is greater than or equal to the sum of the bid prices, the request is accepted; otherwise, it is rejected. That is all there is to bid pricing, at least from a booking control point of view.
In the extreme, this approach would allow us to dispense with the need for any sophisticated booking control structures and to manage bookings on bid price alone. However, we also need to allow for the fact that not all booking requests will be for a single seat. The easiest way to manage multiseat bookings is to keep track of the remaining unbooked seats on each leg and to use that number as a total booking limit.12 Without no-shows and cancellations, the total booking limit would be equal to the unbooked capacity. If we anticipate no-shows and cancellations, the total booking limit could be calculated using one of the overbooking techniques described in Chapter 11. Managing bookings in this fashion is called network bid price control.
Network Bid Price Control
1. Calculate an initial bid price and a total booking limit for each leg.
2. When a booking request is received, calculate the product bid price as the sum of the bid prices for all the legs in the product and the product availability as the minimum of the total booking limits on all the legs used by the product.
3. If the fare for the booking exceeds the product bid price and the number of seats requested is less than the product availability, accept the request and go to step 4. Otherwise reject the request and go to step 2.
4. Decrease the total booking limit on each resource within the product by the number of seats in the booking and go to step 2.
5. When a booking cancels, increment the total booking limits for all flights in the booking.
6. Periodically reoptimize all flight booking limits and all bid prices.
Example 10.8
Consider the solution to Example 10.2 shown in Table 10.6. If we define $75 as the bid price for the Denver-to–St. Louis leg and $125 as the bid price for the San Francisco–to-Denver leg, we will see that we have established a set of bid prices consistent with the optimal solution to the network management problem. The bid prices provide the optimal thresholds between the fare classes we want to accept for each product and those we want to reject. For the example, these thresholds are $75 and $125 for the two single-leg products, plus $75 + $125 = $200 for the San Francisco–to–St. Louis through product. By using the bid prices for the two legs plus a total booking limit for each leg in the dynamic bid price control structure, we could achieve a result very close to the optimal network solution in Table 10.6. And we have done so much more economically, by using just four total controls—two bid prices plus two booking limits—instead of the 15 allocations in Table 10.6.
Network bid price control is a remarkably simple approach to revenue management. It requires only two controls per leg—a bid price and a total booking limit. However, real-world considerations complicate the picture substantially. First, we have not yet considered how bid prices can be calculated. Furthermore, bid prices need to be updated continuously over time. If calculating optimal network bid prices is time consuming or complex (as it is), the airline will require an interim control scheme to handle bookings between reoptimizations. In addition, network bid price controls require additional controls if multiple-seat booking requests are to be handled correctly. Finally, any network management approach for airlines needs to be implemented in conjunction with the existing reservation system and distribution system infrastructure, and most existing reservation and distribution systems are not designed to easily enable pure bid price management.
The system shown in Figure 10.8 is known as an availability processor architecture. It is an implementation of a pure bid-pricing approach to network management. Booking requests arrive at an online processor known as the availability processor. The availability processor calculates the fare associated with each request and compares it to the current bid price for the requested product. If the fare is less than the bid price, the request is rejected. If the fare is greater than the bid price for the requested product, the booking is accepted and communicated to the reservation system.
Figure 10.8 Schematic view of an availability processor architecture for network management.
10.4.1 Bid Prices and Opportunity Costs
Section 9.2.3 notes that the bid price for a resource was equal to the opportunity cost for that resource and could be calculated as the fare of the lowest open fare class. Not surprisingly, network bid prices are also related to the opportunity costs of the resources in the network. We can extend this observation to a network by noting that the following six quantities are (approximately) equivalent.
• Bid price: the minimum price we should accept for a customer on a leg
• Opportunity cost: the revenue we would gain from an additional seat on a leg
• Displacement cost: the revenue we would lose if we had one seat less on a leg
• Marginal value of the capacity constraint in the network linear program
• Boundary between the highest closed and lowest open fare classes in a single-leg problem
• Closed bucket boundary: boundary between the highest closed and lowest open buckets on a leg in a virtual nest
To be sure, these six quantities will not always be exactly equal. For example, the revenue gained from an additional seat on a leg will not necessarily be exactly the same as the revenue lost from removing a seat. The marginal value of the capacity constraint in the deterministic network linear program will not generally equal the values obtained by approaches that explicitly incorporate uncertainty. However, the near equivalence among these quantities supplies ideas for how bid prices can be calculated as well as providing insights into why bid pricing works.
10.4.2 Calculating Bid Prices*
So far, we have not considered how bid prices might be calculated for a large network. You may not be surprised to find out that calculating bid prices can be quite complex—so much so that developing faster and more accurate bid-pricing algorithms is a very active area of research. While understanding the details of bid price calculation is not critical, we will briefly look at two commonly used approaches. This section is somewhat technical and can be skimmed or skipped.
Calculating bid prices by linear programming. Section 10.2 shows how the deterministic network management problem can be formulated as a linear program, where the outputs of the linear program are allotments for all the ODFs in the network. The value of the objective function at the optimal solution is the maximum revenue the company could achieve from its fixed stock of capacity. One way to calculate the bid price on a leg is to solve the network linear program twice: the first time with the actual capacities and the second time with the capacity of the leg reduced by one seat. The difference in the total contribution between the two runs would be the displacement cost on the leg, which, as we have seen, is an estimate of the bid price on the leg.
Of course, this would be a cumbersome way to estimate bid prices, since it requires solving a large linear program twice for each leg in the network. Fortunately, this is not necessary. Deterministic displacement costs for all the legs in the network can be more practically estimated using linear programming in two different ways by using the marginal values associated with the capacity constraints as bid prices.
A key to calculating bid prices is to understand their relationship to the dual variables of the underlying optimization problem. Consider the linear program specified in Equations 10.2–10.5. Associated with each constraint is a dual variable that corresponds to the improvement in the objective function associated with an incremental relaxation of the corresponding constraint. Thus, for the linear program in Equations 10.2–10.5, there are two sets of dual variables:
• λi is the dual variable associated with the constraints in Equation 10.3: 
This constraint guarantees that the number of accepted bookings for products that use a resource do not exceed the capacity of that resource.
• μj is the dual variable associated with the constraints in Equation 10.4: xj≤dj. These constraints guarantee that the number of accepted bookings for a product do not exceed the demand for that product.
These values can be computed directly by solving the dual of the deterministic linear program, which is
subject to
This problem can be solved directly using a standard linear programming approach, in which case λi is the bid price associated with resource i.
Calculating bid prices by sequential estimation. The method of sequential estimation is based on the observation that the bid price on a leg should be equal to its closed bucket boundary in a virtual nest, where the closed bucket boundary is defined as the boundary between the lowest open bucket and the highest closed bucket on the leg. It should be clear that the closed bucket boundary should approximate the bid price on a leg. After all, we will accept a local booking for a single seat only if its fare exceeds the closed bucket boundary, which is the definition of bid price. Furthermore, we will accept a multileg booking request for a single seat only if its net leg fare is greater than the closed bucket boundary on each leg in the ODF. You can confirm that this is the same as ensuring that its total net fare exceeds the sum of the closed bucket boundaries.
This means we can calculate bid prices for a network by finding a set of closed bucket boundaries that is consistent across the network. The challenge arises because the closed bucket boundary (bid price) on any leg depends on the closed bucket boundaries on all other legs via the net leg fares of multileg ODFs. If we change the bid price on a leg, we will change the net leg fares for multileg ODFs on all connecting legs. This will in turn change the buckets into which those ODFs are mapped on the other legs. When we reoptimize availabilities on those legs, the new mapping may well change the bid prices on those legs, which will change the ODF mappings on the original leg. A consistent set of bid prices is one in which the closed bucket boundaries on all legs are locally optimal given the closed bucket boundaries on all other legs.
Sequential estimation calculates bid prices by starting with an initial estimate of all bid prices and then updating the bid price on each leg until the bucket boundaries are consistent across the entire network. To see how this works, assume we have a network consisting of two legs. We initially map all the ODFs into buckets by assuming that each leg has a bid price of 0 (recall that this is equivalent to the greedy heuristic). Given this indexing, we can estimate the total demand by bucket on each leg. Then, for leg 1, we can use EMSR to calculate the bucket allocations on leg 1 given the current indexing. Once we have calculated the allocations on leg 1, we can reestimate the bid price on leg 1 as its closed bucket boundary. Given this new estimate of the leg 1 bid price, we can recalculate the net leg fares on leg 2 and rebucket all of the ODFs on leg 2 accordingly. We can then apply EMSR on leg 2, determine its closed bucket boundary, and use that as the new bid price for leg 2. Given this new leg 2 bid price, we can rebucket the ODFs on leg 1 and continue. Under the right conditions, this procedure will converge to a situation where the mappings and allocations on each leg are consistent with each other.
We can extend this approach to a full network as follows.
Sequential Estimation Algorithm to Calculate Bid Prices
1. Establish a set of buckets on all legs, and calculate probabilistic demand forecasts for all buckets. Set all leg bid prices to 0.
2. Loop over all legs, k = 1, 2, . . . , N.
3. For the current leg k and every ODF i that includes leg k, calculate the net leg fare as the fare for ODF i minus the sum of the current bid prices for all other legs in the ODF.
4. Map all the ODFs on the current leg into buckets based on their net leg fares for the ODFs. Once this is complete, use EMSR to determine allocations by bucket.
5. If all buckets are open, set the new bid price for leg k to 0. If all buckets are closed, set the new bid price for leg k to the highest bucket boundary. Otherwise, set the new bid price to the boundary between the lowest open bucket and the highest closed bucket.
6. Continue to the next leg until all legs have had new bid prices calculated.
7. When all leg bid prices have been recalculated, check the change between the new bid price and the old bid price on each leg. If the two bid prices are sufficiently close for all legs, stop—the current set of bid prices is optimal.
8. Otherwise go to step 2.
This sequential estimation algorithm generally converges to a set of consistent bucket boundaries across a network. When bookings are accepted or forecasts change, the sequential estimation algorithm can be restarted using the previous set of bid prices.
10.4.3 Dynamic Virtual Nesting*
Dynamic virtual nesting is the marriage of bid pricing and virtual nesting. It combines the conceptual elegance and intuitiveness of bid pricing with the practical orientation of virtual nesting. Under dynamic virtual nesting, new bid prices are frequently recalculated for all legs in the network based on current bookings and forecasts of future demands. The recalculation of bid prices could be purely periodic (e.g., nightly or weekly), it could be event driven (e.g., recalculated whenever a flight closes), or it could be ordered by a revenue analyst. In most cases, all of these can trigger a recalculation. Every time new resource bid prices are calculated, new net leg fares are calculated for each leg in the network. These net leg fares are used to define a new indexing. This indexing is put in place until the next recalculation of bid prices.
The strength of dynamic virtual nesting is that it updates bid prices to reflect the current situation on each leg—both current bookings and expected future demand—while utilizing virtual nesting to take advantage of leg-based control structures. Of course, an important determinant of the effectiveness of the approach is how often bid prices are recalculated. If bid prices are not recalculated very often, then dynamic virtual nesting may not be much of an improvement over static virtual nesting. If bid prices are continually updated (say, every second), then dynamic virtual nesting will approximate real-time network bid price control for single-seat bookings.
The first dynamic virtual nesting revenue management system was implemented in 1989 by Hertz rental car company and Decision Focus Incorporated (Carroll and Grimes 1996). The first airline dynamic virtual nesting system was developed jointly by Decision Focus Incorporated and the Scandinavian Airlines System in 1992. Since then, the approach has been widely applied across many revenue management industries.
10.4.4 Strengths and Weaknesses of Bid Pricing
Bid prices are more than tools to manage bookings. They are also useful pieces of information in themselves. As opportunity costs, they specify the value of an additional unit for each resource in the network. If a flight leg has a bid price of $250, this indicates that the airline could realize (approximately) $250 in additional revenue from adding another seat to that flight. Since the bid prices are marginal signals, this logic cannot be extended to determine the effect of adding more than one seat: A bid price of $250 on a flight leg does not mean that an airline could expect to gain $2,500 from adding 10 seats.13 However, even with this limitation, the bid prices can provide useful input into capacity decisions. A flight leg that consistently has a high opportunity cost at departure would be an excellent candidate to be considered for assignment to a larger aircraft, while a flight leg that consistently departs with a bid price of 0 is an excellent candidate to be considered for downsizing. A rental car company with the option to move its cars around should consider moving cars from locations with consistently low bid prices to those with consistently high bid prices.
Example 10.9
The Rent-a-Lemon rental car company rents cars at both the San Francisco airport and the San Jose airport. The two airports are 40 miles apart, and it costs $10 per car to “hike” cars from one airport to the other. For a date two weeks in the future, the bid price at the San Francisco airport is $73 and the bid price at the San Jose airport is $22. The expected net gain from moving a car from San Jose to San Francisco would be $73 − $22 − $10 = $41.
Bid pricing is particularly well suited to hotel applications where there is one bid price for each room type for each future night. The product bid price is the sum of the bid prices for the nights stayed. Hotel and rental car bid prices can be conveniently displayed using a calendar, as shown in Figure 10.9. The calendar shows the bid prices (labeled b) and the forecast unconstrained occupancies (labeled d) for a hotel as they might be displayed by a revenue management system for a future month. A customer who wants to rent a room for the nights of March 23, 24, and 25 would need to pay at least the sum of the bid prices for these nights ($199.93 + $178.25 + $122.20 = $500.38) to be allowed to book. On the other hand, a customer who wants to rent for March 12, 13, and 14 would be allowed to book if he were paying more than $42.34 + $32.34 + $54.37 = $129.05. The lower product bid price reflects lower anticipated demand during the second period than the first. The dark-shaded dates are those with a bid price greater than $150, those with medium shading have a bid price between $100 and $150, and those with no shading have a bid price less than $100. The pattern shown in Figure 10.9 is typical of a metropolitan business hotel with a midweek peak.
Bid pricing is an appealing and intuitive approach to network revenue management. However, a word of caution is in order. The product bid price is the minimum price we should accept for a product given remaining capacity and anticipated future demand by fare class. It does not tell us how we should actually be pricing the product. A hotel manager looking at the bid price calendar in Figure 10.9 should not make the mistake of thinking that he should set the rack rate on Wednesday, March 16, to $122.47. In this sense, the term bid price is unfortunate since, as we have seen, the bid price is better regarded as an opportunity cost. In the extreme case, a bid price of zero for a product tells us nothing about how we should price the product. Bid price control is a mechanism for ensuring that we do not accept any business whose margin does not exceed its opportunity cost—it does not tell us whether we are priced correctly in the market.
Figure 10.9 Bid price calendar.
10.5 NETWORK MANAGEMENT IN ACTION
The first step taken by most airlines in revenue management was to use the approaches described in Chapter 9 to maximize expected revenue on each flight leg independently. In most cases, this approach provided tremendous benefits from not managing bookings at all—that is, allowing customers to book on a first-come, first-served basis. However, hub-and-spoke airlines quickly realized that this approach was not capturing the full potential revenue from their systems.
Because of the need to work within existing reservation systems, the airlines generally adopted network management by instituting increasingly sophisticated forms of virtual nesting, often following the progression implied in Table 10.8. The first step was usually some form of ad hoc virtual nesting, under which a few high-value ODFs were mapped into higher buckets than their fare classes would imply. At some point, most hub-and-spoke airlines instituted some form of static virtual nesting, under which all ODFs would be mapped into buckets on each leg. These mappings would be updated quarterly or monthly based on forecasts of future demand and opportunity cost. Finally, many airlines worked to make these mappings dynamic—that is, updated frequently for each flight based on bookings and cancellations.
TABLE 10.8
Approaches to virtual nesting
The transition from leg-based revenue management to network management at the airlines involved more than just new software; the focus of revenue managers also needed to change. Under leg-based capacity control, flight controllers were responsible for monitoring forecasts and fare class allocations for some set of flights. For example, a flight controller for Delta Airlines might be responsible for all flights between the Atlanta hub and cities in Florida. As the name implies, flight controllers by and large took a flight-centric view of the world, looking to maximize return from their portfolio of flights. When there was a significant amount of connecting traffic, this flight-based approach could not maximize total system return.
Network management required a realignment of responsibilities. Now, there is no individual forecast for, say, M-Class bookings on a particular Atlanta-to-Orlando flight. Rather, the Atlanta-to-Orlando flight has 20 or so buckets. Each of those buckets can contain demand from hundreds of different ODFs. Thus, one bucket might include Detroit-Atlanta-Orlando Y-Class demand, Atlanta-Orlando B-Class demand, Denver-Atlanta-Orlando Y-Class demand, and so on. Furthermore, depending on demand dynamics, the mapping of ODFs to buckets might change weekly or even daily on the same flight. In essence, it is virtually impossible for a controller to manage forecasts and bucket availabilities on a flight basis. Instead, under network management the focus of the revenue management organization needs to shift from flights (or resources) to products. Instead of a flight controller focused on Atlanta-to-Florida flights, there might be a market manager focused on destination-Florida markets. The focus of this market manager would be on understanding the market from all domestic origins to Florida. She would be expected to ensure that all inbound forecasts to Florida incorporate the latest market intelligence. For example, each year she would be expected to know the academic schedule for colleges in the Northeast to ensure that the Fort Lauderdale destination forecasts included spring break demand.
Unlike the airlines, hotels and rental car companies incorporated network management into their revenue management systems right from the start. This was not due to superior technical sophistication on their part but simply to the fact that capacity allocation on a single-resource basis did not work. In fact, early experiments adapting existing leg-based airline revenue management systems to work for hotels were disastrous. The first successful hotel revenue management systems, such as those for Marriott and Hyatt, and the first successful rental car systems, such as those built for Hertz and National, all incorporate length-of-stay or length-of-rental control.
Network management is on the cutting edge of pricing and revenue optimization practice. Existing systems and approaches are a compromise between what is theoretically correct and what is practical. The need to work with preexisting reservation systems and to respond quickly to market changes means that the use of heuristics, ad hoc solutions, and good-enough algorithms are commonplace. Research into better algorithms and approaches to network revenue management continues. A topic of particular research interest is incorporating consumer choice into network management.
Finally, it should be noted that the success of discount airlines means that the traditional hub-and-spoke airlines are being forced to move from a capacity control environment to a dynamic pricing environment. In this environment, the key decision is not which fare classes should be open or closed at any time, but what prices should be on offer for each product. This requires somewhat new approaches, but the basic idea that capacity should never be sold for a fare lower than its opportunity cost is still valid.
10.6 SUMMARY
• Network management is an issue for any revenue management company that sells products consisting of a combination of two or more of the resources it controls. Examples include airlines that offer connecting services, hotels renting rooms for multiple nights, and passenger trains offering tickets that include multiple legs. Network revenue management is important for hub-and-spoke airlines, hotels, rental car companies, passenger trains, and freight transportation providers. It is generally not important for cruise lines, event ticketing, and point-to-point airlines.
• A key challenge in network management is the size and complexity of the problem. A large hub-and-spoke network may have millions of product–fare class combinations it needs to manage for future departures. The size and complexity of the problem is a major consideration in implementing solutions.
• Ordering all ODFs by total fare and setting capacity limits on that basis is called the greedy heuristic for network management. It does not work well when more than one resource is constrained and is not used in practice.
• Linear programming can be used to determine the optimal allocation of products to buckets when demand is deterministic. In real-world applications, linear programming formulations need to be modified to account for demand uncertainty.
• Most real-world network management systems use some form of virtual nesting. Under virtual nesting, a set of buckets (analogous to fare classes) is established for each resource. When a request for an ODF is received, it is mapped into buckets on each constituent resource using a predetermined indexing scheme. If each of these buckets has sufficient availability, the request is accepted; otherwise it is rejected. Different ways of defining and updating the indexing will lead to different virtual nesting approaches.
• Pure bid price control is based on establishing and updating a bid price for each resource. The bid price for a resource is the minimum fare that would be accepted for selling a unit of that resource. It is equivalent to the opportunity cost for a resource. A booking request for an ODF is accepted only if its associated fare is greater than the sum of the bid prices on all constituent resources and there is sufficient remaining capacity in each resource to accommodate the request.
• While pure bid price control is conceptually appealing, it is not widely used in practice since it would require very frequent reoptimization to be robust. Furthermore, it requires extensive (and expensive) modification of the reservation systems on which most revenue management companies rely.
• Dynamic virtual nesting is a combination of bid pricing with virtual nesting. Bid prices are recalculated frequently during the booking period for a product. The new bid prices are then used to define a new indexing, at which point bucket availabilities also need to be updated.
• Network management was incorporated into the revenue management programs for hotels and rental car companies from the beginning. Most airlines, on the other hand, initially managed capacity on a leg-by-leg basis and then introduced network management, often by way of increasingly sophisticated and dynamic virtual nesting approaches. The transition from leg-based management to network management required organizational and business process changes as well as software system changes.
10.7 FURTHER READING
For those who want to go deeper into different network revenue management algorithms, two good sources are Talluri and van Ryzin 2014 and Gallego and Topaloglu 2019, chaps. 2, 7.
The relationship between the opportunity cost of capacity on a flight and the bid price is noted in Simpson 1989 and Phillips 1994. The relationship between the dual variables of a linear program and the opportunity costs of the associated constraints and the derivation of the dual linear program are discussed in most textbooks on linear programming, such as Luenberger and Ye 2008.
Regarding individual companies that implemented network revenue management systems, Marriott’s experience is discussed in Robert Cross’s book Revenue Management (1997). Hertz’s system is described in Carroll and Grimes 1996 and National’s in Geraghty and Johnson 1997.
10.8 EXERCISES
1. How many products can Amtrak offer on the California Zephyr, assuming a single fare class? (Remember that every combination of possible boarding and deboarding stations defines a different product.)
2. Consider an airline with a single hub in the Midwest. Ten flights arrive from cities in the West at the hub every day and connect with nine flights departing for cities in the East. How many products can the airline offer, assuming a single fare class? (Hint: Do not forget the nonstop products.)
3. The airline offering the flights and fares shown in Table 10.4 decides to raise the San Francisco–to–St. Louis discount fare from $170 to $225. It estimates that discount demand at this new fare will be 20. Given that all other fares and demands remain the same, what is the new optimal set of allocations and total revenue for the network?
4. In Example 10.1, determine which bookings would be accepted using the greedy heuristic and the corresponding system revenue. What was the percentage improvement in revenue from optimizing the network?
5. CU Airlines operates two flights, one from New York to Phoenix and another one from Phoenix to San Francisco. It sells a full fare and a discount fare for each leg, and a single fare for the combined leg from New York to San Francisco. The airline has assigned a 120-seat aircraft for the first flight and a 100-seat aircraft for the second flight. The demand for each fare is assumed to be random and normally distributed. The fares and demands for these flights are shown in the following table.
a. Formulate the problem as a deterministic network linear program using the means. What is the optimal allocation and revenue?
b. To incorporate the uncertainty of demands, the chief science officer wants you to use virtual nests for each leg. For each flight, you will have three buckets—one for each ODF. The average contribution to each flight from the NYC-SFO fare is distributed proportionally according to the discount fares for each flight. How would you set the buckets for each flight? Use EMSR-b to calculate the protection levels for each bucket on each flight. How do the protection levels compare to the allocation you obtained in part a?
NOTES
1. This is not strictly true. The theater might still be able to gain additional revenue by considering the possibility of diversion from, say, weekend performances to weeknights in its pricing, as described in Section 7.6.4.
2. Customers can book individual flight legs on EasyJet that they can treat as connecting flights (e.g., they can book a flight from London to Rome and a flight three hours after the Rome arrival to Athens if they wish), but this is different from booking a connecting flight from London to Athens via Rome, since EasyJet cannot manage availability for such customers based on true origin and destination. As discussed in this chapter, the economics of offering connecting flights are so compelling that a number of airlines such as Southwest and Ryanair that initially allowed only single-flight bookings have since begun to offer connecting services.
3. This does not mean that network revenue management never plays a role in these industries. For example, cruises may have multiple stops that allow passengers to board and depart at different ports. And baseball teams may offer package deals for groups of games. In both cases, the seller is offering a product using different resources, and network management may come into play.
4. This is standard terminology. However, it can be misleading, since the real unit being managed is itinerary fare class, not origin-destination fare class. An M-Class passenger traveling from San Francisco to Denver on Flight 18 at 8 a.m. is in a different ODF than an M-Class passenger traveling from San Francisco to Denver on Flight 21 at 9 a.m., even though they share the same origin, destination, and fare class.
5. The highest nightly rate offered by a hotel is called the rack rate.
6. Recall that heuristic refers to an approach to an optimization problem that generates a solution that is not guaranteed to be optimal.
7. This requires that all of the fare classes for a product have different fares.
8. As with single-leg capacity allocation, this property holds true when demands are uncertain and independent but may not hold with dependent demands.
9. In Example 10.5, we assume for simplicity that the buckets on each leg are the same, but this does not need to be true in general.
10. Static virtual nesting is sometimes called displacement-adjusted virtual nesting, or DAVN.
11. The exception is when an ODF fare changes: in this case, the airline would recalculate the net leg fares for that ODF based on the new fare and update the indexing scheme accordingly.
12. Note that multiunit bookings are much more of an issue for airlines than for many other revenue management companies. The vast majority of car rental bookings and hotel bookings are for a single car and a single room, respectively, and the issue of managing multiunit bookings is accordingly much less important in these industries.
13. In general, additional revenue is a concave function of additional capacity—that is, the additional revenue from adding n seats will be less than n times the bid price for n > 1.