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-