300 The UMAP Journal 23.3 (2002) Memorandum Attn: Don Carty, CEO American Airlines From: MCM Team 180 Subject: Overbooking Policy Assessment Results We completed the preliminary assessment of overbooking policies that you requested. There is a great deal of money at stake here, both from ticket sales and also from compensation that must be given to bumped passengers. Moreover, if too many passengers are bumped, there will be a loss of good will and many egular customers could be lost to rival airlines. In fact, we found that the profit difference for American Airlines between a good policy and a bad policy could easily be on the order of $1 billion a year. Using a combination of mathematical models and computersimulation,we considered a wide variety of possible strategies that could be tried to confront this problem. We naturally considered different levels of overbooking, but we also looked at different ways in which airlines could compensate bumped passengers. In terms of the second question, we find that the current scheme of auctioning off compensations for tickets, combined with certain calculated forced bumpings, is still ideal, regardless of changes to the market state Although we were forced to work without much recent data, we were also able to achieve reliable and consistent results for the optimal overbooking rate In particular, we found that prior to september 11, american airlines stood to maximize profits by selling approximately 1.171 times as many tickets as seats available We next considered how this number would likely be affected by the current state of the market. In particular, we focused on four consequences of the events on September 11: all airlines are offering fewer flights, there is heightened security in and around airports, passengers are afraid to fly, and the industry has already lost billions of dollars. Analyzing each of these in turn, we found that they did indeed have a significant effect on the market. In particular, American Airlines should lower its overbooking rate to 1.094 tickets per available seat In conclusion we found that there is indeed a tremendous need to re- evaluate the current overbooking policy. According to our current data, we believe that the rate should be dropped significantly. It would be valuable, however, to supplement our calculations with some of the confidential data that American Airlines has access to but that we do not
300 The UMAP Journal 23.3 (2002) Memorandum Attn: Don Carty, CEO American Airlines From: MCM Team 180 Subject: Overbooking Policy Assessment Results We completed the preliminary assessment of overbooking policies that you requested. There is a great deal of money at stake here, both from ticket sales and also from compensation that must be given to bumped passengers. Moreover, if too many passengers are bumped, there will be a loss of good will and many regular customers could be lost to rival airlines. In fact, we found that the profit difference for American Airlines between a good policy and a bad policy could easily be on the order of $1 billion a year. Using a combination of mathematical models and computer simulations, we considered a wide variety of possible strategies that could be tried to confront this problem. We naturally considered different levels of overbooking, but we also looked at different ways in which airlines could compensate bumped passengers. In terms of the second question, we find that the current scheme of auctioning off compensations for tickets, combined with certain calculated forced bumpings, is still ideal, regardless of changes to the market state. Although we were forced to work without much recent data, we were also able to achieve reliable and consistent results for the optimal overbooking rate. In particular, we found that prior to September 11, American Airlines stood to maximize profits by selling approximately 1.171 times as many tickets as seats available. We next considered how this number would likely be affected by the current state of the market. In particular, we focused on four consequences of the events on September 11: all airlines are offering fewer flights, there is heightened security in and around airports, passengers are afraid tofly, and the industry has already lost billions of dollars. Analyzing each of these in turn, we found that they did indeed have a significant effect on the market. In particular, American Airlines should lower its overbooking rate to 1.094 tickets per available seat. In conclusion, we found that there is indeed a tremendous need to reevaluate the current overbooking policy. According to our current data, we believe that the rate should be dropped significantly. It would be valuable, however, to supplement our calculations with some of the confidential data that American Airlines has access to, but that we do not
Models for Evaluating Airline Overbooking 301 Models for Evaluating airline Overbooking Michael P. Schubmehl Wesley m. Turner Daniel M. Boylan Harvey Mudd College Claremont, CA Advisor: Michael E mood Introduction We develop two models to evaluate overbooking policies. The first model predicts the effectiveness of a proposed overbooking scheme, using the concept of expected marginal seat revenue(EMSr). This model solves the discount seat allocation problem in the presence of overbooking factors for each fare class and evaluates an overbooking policy stochastically The second model takes in historical flight data and reconstructs what the optimal seat allocation should have been. The percentage of overbooking rev- enue obtained in practice serves as a measure of the policy s value Finally, we examine the overbooking problem in light of the recent drastic changes to airline industry and conclude that increased overbooking would bring short-term profits to most carriers. However, the long-term ill effects that have traditionally caused airlines to shun such a policy would be even more pronounced in a post-tragedy climate Literature review There are two major ways that airlines try to maximize revenues: over- booking(selling more seats than available on a given flight) and seat allocation (price discrimination). These measures are believed to save major airlines as much as half a billion dollars each year, in an industry with a typical yearly profit of about $1 billion dollars [Belobaba 1989] The LIMAP Journal23(3)(2002)301-316. Copyright 2002 by COMAP, Inc. All rights reservec Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice. Abstracting with credit is permitted, but copyrights for components of this work owned by others than COMAP must be honored To copy otherwise, to republish, to post on servers, or to redistribute to lists ermission from comap
Models for Evaluating Airline Overbooking 301 Models for Evaluating Airline Overbooking Michael P. Schubmehl Wesley M. Turner Daniel M. Boylan Harvey Mudd College Claremont, CA Advisor: Michael E. Moody Introduction We develop two models to evaluate overbooking policies. The first model predicts the effectiveness of a proposed overbooking scheme, using the concept of expected marginal seat revenue (EMSR). This model solves the discount seat allocation problem in the presence of overbooking factors for each fare class and evaluates an overbooking policy stochastically. The second model takes in historical flight data and reconstructs what the optimal seat allocation should have been. The percentage of overbooking revenue obtained in practice serves as a measure of the policy’s value. Finally, we examine the overbooking problem in light of the recent drastic changes to airline industry and conclude that increased overbooking would bring short-term profits to most carriers. However, the long-term ill effects that have traditionally caused airlines to shun such a policy would be even more pronounced in a post-tragedy climate. Literature Review There are two major ways that airlines try to maximize revenues: overbooking (selling more seats than available on a given flight) and seat allocation (price discrimination). These measures are believed to save major airlines as much as half a billion dollars each year, in an industry with a typical yearly profit of about $1 billion dollars [Belobaba 1989]. The UMAP Journal 23 (3) (2002) 301–316. c Copyright 2002 by COMAP, Inc. All rights reserved. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice. Abstracting with credit is permitted, but copyrights for components of this work owned by others than COMAP must be honored. To copy otherwise, to republish, to post on servers, or to redistribute to lists requires prior permission from COMAP
302 The UMAP Journal 23.3(2002) Beckman [1958]models booking and no-shows in an effort to find an optin overbooking strategy. He ignores advance cancellations, assuming that cancellations are no-shows [Rothstein 1985]. A method that easy to implement but sophisticated enough to allow for cancellations and group reservations was developed by Taylor [1962]. Versions of this model were implemented at Iberia Airlines [Shlifer and Vardi 19751, British Overseas Airways Corporation, and El Al Airlines Rothstein 1985 None of these approaches considers multiple fare classes. Littlewood [1972 offers a simple two-fare allocation rule: A discount fare should be sold only if the discount fare is greater than or equal to the expected marginal return from selling the seat at full-fare. This idea was generalized by Belobaba [1989] to in clude any number of fare classes and allow the integration of overbooking. We use expected marginal seat revenue in predicting about overbooking schemes There is a multitude of work on the subject [McGill 1999 Weatherford and Bodily [1992], there are more than 124, 416 classes of models for variations of the yield management problem, though research has settled into just a few of these. Several authors tried to better Belobaba's [1987]heuristic in the presence of three or more fare classes(for which it is demonstrably sub optimal)[Weatherford and Bodily 1992]; generally, these adaptive methods for obtaining optimal booking limits for single-leg flights are done by dynamic programming [Mcgill 1999] After deregulation in 1978, airlines were no longer required to maintain direct-route system to major cities. Many shifted to a hub-and-spoke system, and network effects began to grow more important. To maximize revenue, an ne may want to consider a passenger's full itinerary before accepting or denying their ticket request for a particular leg. For example, an airline might prefer to book a discount fare rather than one at full price if the passenger is continuing on to another destination (and thus paying an additional fare) he first implementations of the origin-destination control problem consi ered segments of flights. The advantage to this was that a segment could be blacked out to a particular fare class, lowering the overall complexity of a book ing scheme. Another method, virtual nesting, combines fare classes and flig schedules into distinct buckets [Mcgill 1999]. Inventory control on these buck ets would then give revenue-increasing results. Finally, the bid-price method deterministically assigns a value to different seats on a flight leg. The legs in request is accepted or \y if the fare exceeds the bid-price [Mcgill 190- a tick an itinerary are then summed to establish a bid-price for that itinerary; a ticket The most realistic yield management problem takes into account five price classes. The ticket demands for different fare classes are randomized and corre- lated with one other to allow for sell-ups and the recapture of rejected customers on later flights. Passengers can no-show or cancel at any time. Group reser vations are treated separately from individuals--their cancellation probability distribution is likely different. Currently, most work assumes that passengers who pay full fare would not first check for availability of a lower-class ticket a more realistic model would allow buyers of a higher-class ticket to be d
302 The UMAP Journal 23.3 (2002) Beckman [1958] models booking and no-shows in an effort tofind an optimal overbooking strategy. He ignores advance cancellations, assuming that all cancellations are no-shows [Rothstein 1985]. A method that easy to implement but sophisticated enough to allow for cancellations and group reservations was developed by Taylor [1962]. Versions of this model were implemented at Iberia Airlines [Shlifer and Vardi 1975], British Overseas Airways Corporation, and El Al Airlines [Rothstein 1985]. None of these approaches considers multiple fare classes. Littlewood [1972] offers a simple two-fare allocation rule: A discount fare should be sold only if the discount fare is greater than or equal to the expected marginal return from selling the seat at full-fare. This idea was generalized by Belobaba [1989] to include any number of fare classes and allow the integration of overbooking. We use expected marginal seat revenue in predicting about overbooking schemes. There is a multitude of work on the subject [McGill 1999]—according to Weatherford and Bodily [1992], there are more than 124,416 classes of models for variations of the yield management problem, though research has settled into just a few of these. Several authors tried to better Belobaba’s [1987] heuristic in the presence of three or more fare classes (for which it is demonstrably suboptimal) [Weatherford and Bodily 1992]; generally, these adaptive methods for obtaining optimal booking limits for single-leg flights are done by dynamic programming [Mcgill 1999]. After deregulation in 1978, airlines were no longer required to maintain a direct-route system to major cities. Many shifted to a hub-and-spoke system, and network effects began to grow more important. To maximize revenue, an airline may want to consider a passenger’s full itinerary before accepting or denying their ticket request for a particular leg. For example, an airline might prefer to book a discount fare rather than one at full price if the passenger is continuing on to another destination (and thus paying an additional fare). The first implementations of the origin-destination control problem considered segments of flights. The advantage to this was that a segment could be blacked out to a particular fare class, lowering the overall complexity of a booking scheme. Another method, virtual nesting, combines fare classes and flight schedules into distinct buckets [Mcgill 1999]. Inventory control on these buckets would then give revenue-increasing results. Finally, the bid-price method deterministically assigns a value to different seats on a flight leg. The legs in an itinerary are then summed to establish a bid-price for that itinerary; a ticket request is accepted only if the fare exceeds the bid-price [Mcgill 1999] The most realistic yield management problem takes into account five price classes. The ticket demands for different fare classes are randomized and correlated with one other to allow for sell-ups and the recapture of rejected customers on later flights. Passengers can no-show or cancel at any time. Group reservations are treated separately from individuals—their cancellation probability distribution is likely different. Currently, most work assumes that passengers who pay full fare would not first check for availability of a lower-class ticket; a more realistic model would allow buyers of a higher-class ticket to be di-
Models for Evaluating Airline Overbooking 303 verted by a lower fare A full accounting of network effects would consider the relative value of what Weatherford and Bodily [1992] terms displacement denying a discount passenger's ticket request to fly a multilegitinerary in favor of leaving one of the legs open to a full-fare passenger Unfortunately, while the algorithms for allocating seats and setting over- booking levels are highly developed, there has been little work done on the problem of evaluating how effective these measures actually are. Our solutio applies industry-standard methods to find optimal booking levels, then exam ines the actual booking requests for a given flight to determine how close to an optimal revenue level the scheme actually comes Factors Affecting Overbooking Policy General Concerns The reason that overbooking is so important is because of multiple fare classes. With only one fare class, it would be easier for airlines to penalize customers for no-shows. However while most airlines offer nonrefundable discount tickets, they prefernot to penalize those who pay full fare, like business travelers because these passengers account for most of the profi The overbooking level of a plane is dictated by the likelihood of cancellations and of no-shows. An overbooking model compares the revenue generated b accepting additional reservations with the costs associated with the risk of overselling and decides whether additional sales are advisable. In addition the"recapture" possibility can be considered, which is the probability that passenger denied a ticket will simply buy a ticket for one of the airline s other flights. Since a passenger is more valuable to the airline buying a ticket on a flight that has empty seats to fill than on one that is already overbooked, a high recapture probability reduces the optimal overbooking level [Smith et al. 1992 No major airline overbooks at profit-maximizing levels, because it could not realistically handle the problems associated with all the overloaded flights This gives the overbooking optimization problem some important constraints The total flight revenue is to be maximized, subject to the conditions that only a certain portion of flights have even one passenger denied boarding(one oversale), and that a bound is placed on the expected total number of oversales Dealing with even one oversale is a hassle for the airlines staff, and they are not equipped to handle such problems on a large scale. Additionally, some research indicates that increased overbooking levels would most likely trigger an"overbooking war"[Suzuki 2002], which would increase short-term profits but would probably engender enough consumer resentment that the industry as a whole would lose business While the overbooking problem sets a limit for sales on a flight as a whole, proper seat allocation sets an optimal point at which to stop selling tickets for individual fare levels. For example, a perfectly overbooked plane, loaded
Models for Evaluating Airline Overbooking 303 verted by a lower fare. A full accounting of network effects would consider the relative value of what Weatherford and Bodily [1992] terms displacement— denying a discount passenger’s ticket request to fly a multileg itinerary in favor of leaving one of the legs open to a full-fare passenger. Unfortunately, while the algorithms for allocating seats and setting overbooking levels are highly developed, there has been little work done on the problem of evaluating how effective these measures actually are. Our solution applies industry-standard methods to find optimal booking levels, then examines the actual booking requests for a given flight to determine how close to an optimal revenue level the scheme actually comes. Factors Affecting Overbooking Policy General Concerns The reason that overbooking is so important is because of multiple fare classes. With only one fare class, it would be easier for airlines to penalize customers for no-shows. However, while most airlines offer nonrefundable discount tickets, they prefer not to penalize those who pay full fare, like business travelers, because these passengers account for most of the profits. The overbooking level of a plane is dictated by the likelihood of cancellations and of no-shows. An overbooking model compares the revenue generated by accepting additional reservations with the costs associated with the risk of overselling and decides whether additional sales are advisable. In addition, the “recapture” possibility can be considered, which is the probability that a passenger denied a ticket will simply buy a ticket for one of the airline’s other flights. Since a passenger is more valuable to the airline buying a ticket on a flight that has empty seats to fill than on one that is already overbooked, a high recapture probability reduces the optimal overbooking level [Smith et al. 1992]. No major airline overbooks at profit-maximizing levels, because it could not realistically handle the problems associated with all the overloaded flights. This gives the overbooking optimization problem some important constraints. The total flight revenue is to be maximized, subject to the conditions that only a certain portion of flights have even one passenger denied boarding (one oversale), and that a bound is placed on the expected total number of oversales. Dealing with even one oversale is a hassle for the airline’s staff, and they are not equipped to handle such problems on a large scale. Additionally, some research indicates that increased overbooking levels would most likely trigger an “overbooking war” [Suzuki 2002], which would increase short-term profits but would probably engender enough consumer resentment that the industry as a whole would lose business. While the overbooking problem sets a limit for sales on a flight as a whole, proper seat allocation sets an optimal point at which to stop selling tickets for individual fare levels. For example, a perfectly overbooked plane, loaded
304 The UMAP Journal 23.3 (2002) exactly to capacity, could be flying at far below its optimal revenue level if too many discount tickets were sold. The more expensive tickets are not for first-class seats and involve no additional luxuries above the discount tickets apart from more lenient cancellation policies and the ability to buy the tickets a shorter time before the flight's departure September 11, 2001 Since the September 11 terrorist attacks, there have been significant changes in the airline business. In addition to the forced cancellation of many flights in the immediate aftermath of the attacks and the extreme levels of cancellations and no-shows by passengers after that, passenger traffic has dropped sharply in general. The huge downturn in passenger levels has led to large reductions in service by most carriers In terms of the booking problem, there are fewer flights for passengers to spill over onto, which could increase the loss by an airline if it bumps passenger from a flight. On the other hand, since passenger levels have fallen so far, it is less likely that an airline will overfill any given flight. The heightened security at airports will likely increase the passenger no-show rate somewhat, as passengers get delayed at security checkpoints. At the very least, it should up for a flight but are not in the airline's record ows, passengers who show lmost completely remove the problem of go-s On the whole, optimal booking strategies have become even more vital as airlines have already lost billions of dollars, and some teeter on the brink of failure. Some overbooking tactics previously dismissed as too harmful in the long run might be worthwhile for companies in trouble. For example, an airline near failure might increase the overbooking rate to the level that maximizes revenue, without regard to the inconvenience and possible future resentment of its customers Constructing the model Objectives A scheme for evaluating overbooking policies needs to answer two ques- tions: how well should a new overbooking method perform, and how well is a current overbooking scheme already working? The first is best addressed by a simple model of an airline' s booking procedures; given some setup for allocat g seats to fare classes, candidate overbooking schemes can be laid on top and tested by simulation. This approach has the advantage that it provides insight into why an overbooking scheme is or is not effective and helps to illuminate the characteristics of an optimal overbooking approach The second question is, in some respects, a simpler one to answer. Given the actual (over)booking limits that were imposed on each fare class and all avail
304 The UMAP Journal 23.3 (2002) exactly to capacity, could be flying at far below its optimal revenue level if too many discount tickets were sold. The more expensive tickets are not for first-class seats and involve no additional luxuries above the discount tickets, apart from more lenient cancellation policies and the ability to buy the tickets a shorter time before the flight’s departure. September 11, 2001 Since the September 11 terrorist attacks, there have been significant changes in the airline business. In addition to the forced cancellation of many flights in the immediate aftermath of the attacks and the extreme levels of cancellations and no-shows by passengers after that, passenger traffic has dropped sharply in general. The huge downturn in passenger levels has led to large reductions in service by most carriers. In terms of the booking problem, there are fewer flights for passengers to spill over onto, which could increase the loss by an airline if it bumps a passenger from a flight. On the other hand, since passenger levels have fallen so far, it is less likely that an airline will overfill any given flight. The heightened security at airports will likely increase the passenger no-show rate somewhat, as passengers get delayed at security checkpoints. At the very least, it should almost completely remove the problem of “go-shows,” passengers who show up for a flight but are not in the airline’s records. On the whole, optimal booking strategies have become even more vital as airlines have already lost billions of dollars, and some teeter on the brink of failure. Some overbooking tactics previously dismissed as too harmful in the long run might be worthwhile for companies in trouble. For example, an airline near failure might increase the overbooking rate to the level that maximizes revenue, without regard to the inconvenience and possible future resentment of its customers. Constructing the Model Objectives A scheme for evaluating overbooking policies needs to answer two questions: how well should a new overbooking method perform, and how well is a current overbooking scheme already working? The first is best addressed by a simple model of an airline’s booking procedures; given some setup for allocating seats to fare classes, candidate overbooking schemes can be laid on top and tested by simulation. This approach has the advantage that it provides insight into why an overbooking scheme is or is not effective and helps to illuminate the characteristics of an optimal overbooking approach. The second question is, in some respects, a simpler one to answer. Given the actual (over)booking limits that were imposed on each fare class, and all avail-
Models for Evaluating Airline Overbooking 305 able information on the actual requests for reservations how much revenue might have been gained from overbooking, compared to how much actually was? This provides a very tangible measure of overbooking performance but very little insight into the reasons for results. The enormous number of factors affecting the design and evaluation of an overbooking policy force us to make simplifying assumptions to construct models that meet both of these goals Assumptions Fleet-wide revenues can be near-optimized one leg at a time Maximizing revenue involves complicated interactions between flights. For instance, a passenger purchasing a cheap ticket on a flight into a major hub might actually be worth more to the airline than a business-class passenger, on account of connecting flights. We assume that such effects can be compen- sated for by placing passengers into fare classes based on revenue potential rather than on the fare for any given leg. This assumption effectively reduces the network problem to a single-leg optimization problem Airlines set fares optimally Revenue maximization depends strongly on the prices of various classes of tickets. To avoid getting into the economics of price competition and revenue maximization to sermng optimal fare-class(over)booking limits es supply/demand, we assume that airlines set prices optimally. This redu Historical demand data are available and applicable The model needs to estimate future demand for tickets on any given flight We assume that historical data are available on the number of tickets sold any given number of days t before a flights departure. In some respects, this assumption is unrealistic because of the problem of data censorship-that is the failure of airlines to record requests beyond the booking limit for a fare class [ Belobaba 1989. On the other hand, statistical methods can be used to reconstruct this information [Boeing Commercial Airline Company 1982, 7-16;Swan1990] Low-fare passengers tend to book before high-fare ones. Discount tickets are often sold under advance purchase restrictions, for the precise reason that it enables price discrimination. Because of restrictions like these, and because travelers who plan ahead search for cheap tickets, low-fare passengers tend to book before high-fare ones Predicting Overbooking effectiveness Disentangling the effects of overbooking, seat allocation, pricing schemes, and external factors on revenues of an airline is extremely complicated To
Models for Evaluating Airline Overbooking 305 able information on the actual requests for reservations, how much revenue might have been gained from overbooking, compared to how much actually was? This provides a very tangible measure of overbooking performance but very little insight into the reasons for results. The enormous number of factors affecting the design and evaluation of an overbooking policy force us to make simplifying assumptions to construct models that meet both of these goals. Assumptions • Fleet-wide revenues can be near-optimized one leg at a time. Maximizing revenue involves complicated interactions between flights. For instance, a passenger purchasing a cheap ticket on a flight into a major hub might actually be worth more to the airline than a business-class passenger, on account of connecting flights. We assume that such effects can be compensated for by placing passengers into fare classes based on revenue potential rather than on the fare for any given leg. This assumption effectively reduces the network problem to a single-leg optimization problem. • Airlines set fares optimally. Revenue maximization depends strongly on the prices of various classes of tickets. To avoid getting into the economics of price competition and supply/demand, we assume that airlines set prices optimally. This reduces revenue maximization to setting optimal fare-class (over)booking limits. • Historical demand data are available and applicable. The model needs to estimate future demand for tickets on any given flight. We assume that historical data are available on the number of tickets sold any given number of days t before a flight’s departure. In some respects, this assumption is unrealistic because of the problem of data censorship—that is, the failure of airlines to record requests beyond the booking limit for a fare class [Belobaba 1989]. On the other hand, statistical methods can be used to reconstruct this information [Boeing Commercial Airline Company 1982, 7–16; Swan 1990]. • Low-fare passengers tend to book before high-fare ones. Discount tickets are often sold under advance purchase restrictions, for the precise reason that it enables price discrimination. Because of restrictions like these, and because travelers who plan ahead search for cheap tickets, low-fare passengers tend to book before high-fare ones. Predicting Overbooking Effectiveness Disentangling the effects of overbooking, seat allocation, pricing schemes, and external factors on revenues of an airline is extremely complicated. To
306 The UMAP Journal 23.3 (2002) isolate the effects of overbooking as much as possible, we want a simple, well- understood seat allocation model that provides an easy way to incorporate various overbooking schemes. In light of this objective, we pass up several methods for finding optimal booking limits on single-leg flights detailed in, for example, Curry [1990] and Brumelle [1993], in favor of the simpler expected marginal seat revenue(EMsr)method [Belobaba 1989] EMSR was developed as an extension of the well-known rule of thumb, popularized by Littlewood [1972], that revenues are maximized in a two-fare system by capping sales of the lower-class ticket when the revenue from selling an additional lower-class ticket is balanced by the expected revenue from selling the same seat as an upper-class ticket. In the emsr formulation any number of fare classes are permitted and the goal is"to determine how many seats not to sell in the lowest fare classes and to retain for possible sale in higher fare classes closer to departure day"[ Belobaba 1989 The only information required to calculate booking levels in the EMSR model is a probability density function for the number of requests that will arrive before the flight departs, in each fare class and as a function of time For simplicity, this distribution can be assumed to be normal, with a mean and standard deviation that change as a function of the time remaining. Thus, the only information an airline would need is a historical average and standard deviation of demand in each class as a function of time. Ideally, the informa tion would reflect previous instances of the particular flight in question. Let the mean and standard deviations in question be denoted by ui(t)and oi(t)for each fare class i= 1, 2,...,k. Then the probability that demand is greater than some specified level Si is given by Pi(Si, t) (r-Hi(t))"/oi(t).dr 2丌o;(t)Js This spill probability is the likelihood that the Si th ticket would be sold if offered in the ith category. If we further allow fi(t) to denote the expected revenue resulting from a sale to class i at a time t days prior to departure, we can define EMSRi (Si, t)=fi(t). Pi(Si, t), ply the revenue for a ticket in class i times the probability that the Si th seat will be sold. The problem, however, is to find the number of tickets S; that should be protected from the lower class j for sale to the upper class i(ignoring other classes for the moment). The optimal value for S; satisfies EMSR(S;, t)=f,(t), so that the expected marginal revenue from holding the S; th seat for class i is exactly equal to(in practice, slightly greater than) the revenue from selling it immediately to someone in the lower class j. The booking limits that should be enforced can be derived easily from the optimal S; values by letting the
306 The UMAP Journal 23.3 (2002) isolate the effects of overbooking as much as possible, we want a simple, wellunderstood seat allocation model that provides an easy way to incorporate various overbooking schemes. In light of this objective, we pass up several methods for finding optimal booking limits on single-leg flights detailed in, for example, Curry [1990] and Brumelle [1993], in favor of the simpler expected marginal seat revenue (EMSR) method [Belobaba 1989]. EMSR was developed as an extension of the well-known rule of thumb, popularized by Littlewood [1972], that revenues are maximized in a two-fare system by capping sales of the lower-class ticket when the revenue from selling an additional lower-class ticket is balanced by the expected revenue from selling the same seat as an upper-class ticket. In the EMSR formulation, any number of fare classes are permitted and the goal is “to determine how many seats not to sell in the lowest fare classes and to retain for possible sale in higher fare classes closer to departure day” [Belobaba 1989]. The only information required to calculate booking levels in the EMSR model is a probability density function for the number of requests that will arrive before the flight departs, in each fare class and as a function of time. For simplicity, this distribution can be assumed to be normal, with a mean and standard deviation that change as a function of the time remaining. Thus, the only information an airline would need is a historical average and standard deviation of demand in each class as a function of time. Ideally, the information would reflect previous instances of the particular flight in question. Let the mean and standard deviations in question be denoted by µi(t) and σi(t) for each fare class i = 1, 2,... ,k. Then the probability that demand is greater than some specified level Si is given by P¯i(Si, t) ≡ 1 √2π σi(t) ∞ Si e(r−µi(t))2/σi(t)2 dr. This spill probability is the likelihood that the Sith ticket would be sold if offered in the ith category. If we further allow fi(t) to denote the expected revenue resulting from a sale to class i at a time t days prior to departure, we can define EMSRi(Si, t) = fi(t) · P¯i(Si, t), or simply the revenue for a ticket in class i times the probability that the Sith seat will be sold. The problem, however, is to find the number of tickets Si j that should be protected from the lower class j for sale to the upper class i (ignoring other classes for the moment). The optimal value for Si j satisfies EMSRi(Si j , t) = fj (t), (1) so that the expected marginal revenue from holding the Si j th seat for class i is exactly equal to (in practice, slightly greater than) the revenue from selling it immediately to someone in the lower class j. The booking limits that should be enforced can be derived easily from the optimal Si j values by letting the
Models for Evaluating Airline Overbooking 307 booking limit B, for class j be B(t)=C-+-∑b() that is, the capacity C of the plane, less the protection level of the class above from class i and less the total number of seats already reserved Sample emsr curves,with booking limits calculated in this fashion, are shown in Figure 1 250 150 5 eat number Figure 1. Expected marginal seat revenue(EMSr) curves for three class levels, with the est-revenue class at the top. Each curve represents the revenue expected from protecting ticular seat to sell to that class. Also shown are the resulting booking limits for each of the lasses-that is, the levels at which sales to the lower class should stop to save seats for higher This formulation does not account for overbooking; if we allow each fare class i to be overbooked by some factor OVi, the optimality condition(1)be comes OV EMSR(S;, t)=f,(t) OV This can be understood in terms of an adjustment to fi and fi; the overbooking factors are essentially cancellation probabilities, so we use each Ovi to deflate the expected revenue from fare class i. Then Pi(S, t) fi(t) f()
Models for Evaluating Airline Overbooking 307 booking limit Bj for class j be Bj (t) = C − Sj+1 j − i<j bi(t), (2) that is, the capacity C of the plane, less the protection level of the class above j from class j and less the total number of seats already reserved. Sample EMSR curves, with booking limits calculated in this fashion, are shown in Figure 1. EMSR ($) 10 20 30 40 50 60 0 50 100 150 200 250 b2 b1 Seat Number Figure 1. Expected marginal seat revenue (EMSR) curves for three class levels, with the highest-revenue class at the top. Each curve represents the revenue expected from protecting a particular seat to sell to that class. Also shown are the resulting booking limits for each of the lower classes—that is, the levels at which sales to the lower class should stop to save seats for higher fares. This formulation does not account for overbooking; if we allow each fare class i to be overbooked by some factor OVi, the optimality condition (1) becomes EMSRi(Si j , t) = fj (t) · OVi OVj . (3) This can be understood in terms of an adjustment to fi and fj ; the overbooking factors are essentially cancellation probabilities, so we use each OVi to deflate the expected revenue from fare class i. Then P¯i(Si j , t) · fi(t) OVi = fj (t) · fj (t) OVj ,
308 The UMAP Journal 23.3(2002) which is equivalent to(3). Note that the use of a single overbooking factor for the entire cabin(that is, OVi=Ov) causes the ovi and ovi in(3)to cancel Nonetheless, the boarding limits for each class are affected, because the capacity of the plane c must be adjusted to account for the extra reservations, so now and the booking limits in(2)are adjusted upward by replacing C with C# The EMSR formalism gives us the power to evaluate an overbooking scheme theoretically by plugging its recommendations into a well-understood stable model and evaluating them. Given the emsr boarding limits, which can be updated dynamically as booking progresses, and the prescribed overbooking factors, a simulated string of requests can be handled. Since the EMSR model involves only periodic updates to establish limits that are fixed over the cours of a day or so, a set of n requests can be handled with two lookups each(booking limit and current booking level), one subtraction, and one comparison; so n requests can be processed on o(n) time. An EMSR-based approach would thus be practical in a real-world real-time airline reservations system, which often handles as many as 5,000 requests per second. Indeed, systems derived from EMsr have been adopted by many airlines [Mcgill 1999I Evaluating Past Overbookings The problem of evaluating an overbooking scheme that has already been implemented is somewhat less well studied than the problem of theoretically evaluating an overbooking policy. One simple approach, developed by Ameri- can Airlines in 1992, measures the optimality of overbooking and seat allocation separately [Smith et al. 1992]. Their overbooking evaluation process assumes optimal seat allocation and, conversely, their seat allocation evaluation scheme assumes optimal overbooking. Under this assumption, an overbooking scheme is evaluated by estimating the revenue under optimal overbooking in two ways If a flight is fully loaded and no passenger is denied boarding, the flight is considered to be optimally overbooked and to have achieved maximum If n passengers are denied boarding, the money lost due to bumping these passengers is added back in and the n lowest fares paid by passengers for the flight are subtracted from revenue On the other hand, if there are n empty seats on the plane the n highest-fare tickets that were requested but not sold are added to create the maximum revenue figure Their seat-allocation model estimates the demand for each flight by calcu lating a theoretical demand for each fare class and then setting the minimum flight revenue(by filling the seats lowest-class first)and the maximum flight
308 The UMAP Journal 23.3 (2002) which is equivalent to (3). Note that the use of a single overbooking factor for the entire cabin (that is, OVi = OV ) causes the OVi and OVj in (3) to cancel. Nonetheless, the boarding limits for each class are affected, because the capacity of the plane C must be adjusted to account for the extra reservations, so now C∗ = C · OV and the booking limits in (2) are adjusted upward by replacing C with C∗. The EMSR formalism gives us the power to evaluate an overbooking scheme theoretically by plugging its recommendations into a well-understood stable model and evaluating them. Given the EMSR boarding limits, which can be updated dynamically as booking progresses, and the prescribed overbooking factors, a simulated string of requests can be handled. Since the EMSR model involves only periodic updates to establish limits that are fixed over the course of a day or so, a set of n requests can be handled with two lookups each (booking limit and current booking level), one subtraction, and one comparison; so all n requests can be processed on O(n) time. An EMSR-based approach would thus be practical in a real-world real-time airline reservations system, which often handles as many as 5,000 requests per second. Indeed, systems derived from EMSR have been adopted by many airlines [Mcgill 1999]. Evaluating Past Overbookings The problem of evaluating an overbooking scheme that has already been implemented is somewhat less well studied than the problem of theoretically evaluating an overbooking policy. One simple approach, developed by American Airlines in 1992, measures the optimality of overbooking and seat allocation separately [Smith et al. 1992]. Their overbooking evaluation process assumes optimal seat allocation and, conversely, their seat allocation evaluation scheme assumes optimal overbooking. Under this assumption, an overbooking scheme is evaluated by estimating the revenue under optimal overbooking in two ways: • If a flight is fully loaded and no passenger is denied boarding, the flight is considered to be optimally overbooked and to have achieved maximum revenue. • If n passengers are denied boarding, the money lost due to bumping these passengers is added back in and the n lowest fares paid by passengers for the flight are subtracted from revenue. • On the other hand, if there are n empty seats on the plane, the n highest-fare tickets that were requested but not sold are added to create the maximum revenue figure. Their seat-allocation model estimates the demand for each flight by calculating a theoretical demand for each fare class and then setting the minimum flight revenue (by filling the seats lowest-class first) and the maximum flight
Models for Evaluating Airline Overbooking 309 revenue(by filling the seats highest-class first). To estimate demand, we the information on the flight's sales up to the point where each class closed assuming that demand is increasing for each class, we can project the number of requests that would have occurred had the booking limits been disregarded Given these projected additional requests and the actual requests received before closing, it is straightforward to compute the best-and worst-case over- booking scenarios. The worst-case revenue R- is determined by using no booking limits and taking reservations as they come, and the best-case rev- enue R+ is determined by accommodating high-fare passengers first, giving the leftovers to the lower classes. The difference between these two figures is the revenue to be gained by the use of booking limits. Thus, the performance of a booking scheme that generates revenue R is R-R 00% R1-R representing the percentage of the possible booking revenue actually achieved We select this method for evaluating booking schemes after the fact Analysis of the models Tests and simulations The EMSr method requires information on demand as a function of time Although readily available to an airline, it is not widely published in a detailed form. Li [2001] provides enough data to construct a rough piecewise-linear picture of demand remaining as a function of time, shown in Figure 2 This information can be inputted into the emsr model to produce optimal booking limits that evolve in time. A typical situation near the beginning of ticket sales was shown in Figure 1, while the evolution of the limits themselves is plotted in Figure 3 The demand information in Figure 2 can also be used to simulate requests for reservations. By taking the difference between the demand remaining at day t and at day(t-1) before departure, the expected demand on day t can be determined. The actual number of requests generated on that day is then given by a Poisson random variable with parameter A equal to the expected number of sales [Rothstein 1971]. The requests generated in this manner can be passed to a request-handling simulation that looks at the most current booking limits and then accepts or denies ticket requests based on the number of reservations already confirmed and the reservations limit. An example of this booking process is illustrated in Figure 4 The results of the booking process provide an ideal testbed for the revenue opportunity model employed to evaluate overbooking performance. The sim- ulation conducted for Figure 4 had demand values of (11, 41, 57), for classes 1
Models for Evaluating Airline Overbooking 309 revenue (by filling the seats highest-class first). To estimate demand, we use the information on the flight’s sales up to the point where each class closed. By assuming that demand is increasing for each class, we can project the number of requests that would have occurred had the booking limits been disregarded. Given these projected additional requests and the actual requests received before closing, it is straightforward to compute the best- and worst-case overbooking scenarios. The worst-case revenue R− is determined by using no booking limits and taking reservations as they come, and the best-case revenue R+ is determined by accommodating high-fare passengers first, giving the leftovers to the lower classes. The difference between these two figures is the revenue to be gained by the use of booking limits. Thus, the performance of a booking scheme that generates revenue R is p = R − R− R+ − R− · 100%, (4) representing the percentage of the possible booking revenue actually achieved. We select this method for evaluating booking schemes after the fact. Analysis of the Models Tests and Simulations The EMSR method requires information on demand as a function of time. Although readily available to an airline, it is not widely published in a detailed form. Li [2001] provides enough data to construct a rough piecewise-linear picture of demand remaining as a function of time, shown in Figure 2. This information can be inputted into the EMSR model to produce optimal booking limits that evolve in time. A typical situation near the beginning of ticket sales was shown in Figure 1, while the evolution of the limits themselves is plotted in Figure 3. The demand information in Figure 2 can also be used to simulate requests for reservations. By taking the difference between the demand remaining at day t and at day (t − 1) before departure, the expected demand on day t can be determined. The actual number of requests generated on that day is then given by a Poisson random variable with parameter λ equal to the expected number of sales [Rothstein 1971]. The requests generated in this manner can be passed to a request-handling simulation that looks at the most current booking limits and then accepts or denies ticket requests based on the number of reservations already confirmed and the reservations limit. An example of this booking process is illustrated in Figure 4. The results of the booking process provide an ideal testbed for the revenue opportunity model employed to evaluate overbooking performance. The simulation conducted for Figure 4 had demand values of {11, 41, 57}, for classes 1