《数学建模》美赛优秀论文：02B ACE is High.pdf_大学文库

ACE is High 339 ACE is High Anthony C Pecorella Elizabeth a perez Crystal T. Taylor Wake Forest University Winston Fig5-Salem, Nc Advisor: Edward e. allen Introduction We design a model that allows an airline to substitute its own values for ticket prices, no-show rates and fees, compensation for bumped passengers and capacities to determine its optimal overbooking level Our model is based on an equation that combines the two cases involved in overbooking: The first sums all cases in which the airline doesn't fill all seats with passengers, and the second sums all cases in which there is an over- flow of passengers due to overbooking. The model includes the possibility of upgrading passengers from coach to first-class when there is overflow in coach Furthermore, we use a binomial distribution of the probabilities of bumping booking percenta oly the airlines with useful information pertaining to customer relations We apply our model with different values of the parameters to determine of byusing our model, an individual airline can find an optimal overbooking timal overbooking levels in different situations level that maximizes its revenue. an joint optimal overbooking strategy for all airlines is to agree to allow bumped passengers to fly at a discounted fare on a Analysis of the Problem From January to September 2001, 0. 187% of pa bumped from flights due to overbooking. This seems like an inconsequential percentage, but it actually amounts to 731, 449 people. Additionally, 4.4% of those bumped, The UMAP Journal 339-349. @Copyright 2002 by COMAP, Inc. All rights reserved ermission to make digital or hard copies of part or all of this work for personal or classroom m use is granted without fee provided that copies are not made or distributed for profit or commercial dvantage 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

ACE is High 339 ACE is High Anthony C. Pecorella Elizabeth A. Perez Crystal T. Taylor Wake Forest University WinstonFig5-Salem, NC Advisor: Edward E. Allen Introduction We design a model that allows an airline to substitute its own values for ticket prices, no-show rates and fees, compensation for bumped passengers, and capacities to determine its optimal overbooking level. Our model is based on an equation that combines the two cases involved in overbooking: The first sums all cases in which the airline doesn’t fill all seats with passengers, and the second sums all cases in which there is an over- flow of passengers due to overbooking. The model includes the possibility of upgrading passengers from coach to first-class when there is overflow in coach. Furthermore, we use a binomial distribution of the probabilities of bumping passengers, given different overbooking percentages, to supply the airlines with useful information pertaining to customer relations. We apply our model with different values of the parameters to determine optimal overbooking levels in different situations. By using our model, an individual airline can find an optimal overbooking level that maximizes its revenue. An joint optimal overbooking strategy for all airlines is to agree to allow bumped passengers to fly at a discounted fare on a different airline. Analysis of the Problem From January to September 2001, 0.187% of passengers were bumped from flights due to overbooking. This seems like an inconsequential percentage, but it actually amounts to 731,449 people. Additionally, 4.4% of those bumped, The UMAP Journal 339–349. 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

340 The UMAP Journal 23.3 (2002) or 32,452 people, were denied their flights involuntarily [U.S. Department of Transportation 2002]. Since 10% to 15% of passengers who reserve a seat don’t show up, airlines have little chance to fill their planes if they book only as many passengers as seats available. Overbooking by American Airlines helped save the airline $1.4 billion between 1989 and 1992. We examine a fictional company to determine an optimal overbooking strategy that maximizes revenue. The goal is a model to increase revenue while maintaining favorable customer relations. Our main model, the Expected Gain Model, provides a clear formula for what percentage of the seats to overbook. Based on sample no-show rates, ticket prices, and seat numbers, our Expected Gain Model shows that a 16% overbooking rate is the most effective choice. Our other model, the Binomial Distribution Model, calculates, for various overbooking levels. the probability that a passenger will be bumped. Assumptions • There is no overbooking infirst class (to maintain good relations with wealthy and influential passengers). • Anyone bumped (voluntarily or involuntarily) is compensated with refund of ticket price plus an additional 100% of the ticket price. • There are only two flight classes, coach and first-class. • The fare is constant regardless of how far in advance the ticket is purchased. Overbooked passengers are given seats on a first-come-first-served basis, as is often the case. Therefore, ticket prices will average out for both those bumped and those seated. • Each passenger’s likelihood of showing up is independent of every other passenger. • First-class ticketholders have unrestricted tickets, which allow a full refund in case of no-show; coach passengers have restricted tickets, which allow only a 75% refund in case of no-show. • There are no walk-ons. • There are no flight delays or cancellations. • The marginal cost of adding a passenger to the plane is negligible

0 .0000% 1 0.0000% 2 0.0000% 3 0.0000% 4 0.0000% 5 0.0000% 6 0.0000% 7 0.0000% 8 0.0000% 9 0.0000% 100.0000% 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 First Class 101 105 106 107 108 109 110 111 112 113 114 115 116 8 5.0000% 8 7.0000% 8 9.0000% 9 1.0000% 9 3.0000% 9 5.0000% 9 7.0000% 9 9.0000% 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 First Class 101 105 106 107 108 109 110 342 The UMAP Journal 23.3 (2002) Binomial Distribution Model We create ACE Airlines, a fictional firm, to understand better how to handle overbooking. We examine binomial distributions of ticket sales, so we call this the Binomial Distribution Model. ACE features planes with 20 first-class seats and 100 coach seats. The noshow rate is 10% for coach and 20% for first-class. Figure 1 compares various overbooking levels with the chance that there will be enough available seats in first-class to accommodate the overflow. The functions are y = 100+ x j=0 C j (0.9)j (0.1)C−j (coach), y = 20 −x j=0 C j (0.8)j (0.2)20−j (first class), where C reservations are made for coach and 20 are always made for first class. Figure 1. Probability of enough seats vs. overbooking level. The graph on the right is a close-up of the upper left corner of the one on the left. Where the first-class line passes below the various overbooking lines indicates the probability at which we must start bumping passengers. This simplistic model doesn’t account for ticket prices, no-show fees, or refunds to bumped passengers and doesn’t specifically deal with revenue either. Thus, it can act as a good reference for verifying the customer-relations aspect of any solution but can’t give a good solution on its own. To be sure that ACE is receiving the most revenue it can, we must create a more in-depth model. ACE coach fare is $200. We refund $150 on no-show coach tickets, thus gaining $50 on each. To keep good customer relations, when we are forced to bump a passenger from a flight, we refund the ticket price with an additional bonus of 100% of the ticket price (thus, we suffer a $200 loss). We define prob(x, y, r) as the binomial probability of y independent events happening in x trials, with a probability r of each event happening: prob(x, y, r) = x y ry(1 − r) x−y.

344 The UMAP Journal 23.3 (2002) into first-class openings. The first part of the previous formula, Mi can still be used, since it deals with the cases in which the coach section isnt filled anyway Since ACe will not overbook first-class, ACE should always book it fully. Thus, fare for first-class is unimportant when considering how to maximize revenue. We further assume that aCe sells only unrestricted first-class tickets(there is no penalty to first-class no-shows) The second part of the equation needs only a minor modification to adjust for seats made available by first-class no-shows. ACE still gets $200 for each of the 100 passengers who show up and gets $50 for each of the(a-j)no- shows. The difference now is that instead of simply multiplying by -$200 for each passenger over 100, we check for first-class openings and multiply -$200 by just the number who end up bumped. Those upgraded to first-class still pay coach fare(thus, more than 100 coach passengers can pay that $200). This function, Pi(y), with y 100 the number of overflow coach passengers, gives the expected net revenue expected for that much overflow. Similarly, P2(y) gives the expected net revenue when ACe can seat all of the overflow. Thus, the new version of the second part of the formula reads M2(x) prob(x,3,0.9)[20010950(x-j)+P(-100)+P2(-100) The form of the Pi functions is similar to the two parts of the model alread discussed. The probability of there being few enough first-class passengers is multiplied by $200(coach fare) times the number of extra coach passengers who can be seated (-100) Recall that the show rate for first-class is 0.8 P (20,k,0.8)(200) k=0 The other case is when ace can t seat all of the coach overflow. This time we multiply by the loss of revenue from the coach spillover y, $200 for each of the y-(20-k)bumped customers, offset by $200 for each of the(20-k) passengers upgraded to first-class. The result is P1(y) prob20,k,0.8)[(-200(-(20-k)+20020-k) At this point, we have all of the pieces of the expected gain model. We plot the equation M= M1+ M2 in Figure 3 and find the maximum for 100 The ideal overbooking level lies at 115 or 116 reservations, with a negligible Applying the model We implemented our modelin a computer program in which the parameters can be varied including seating capacities, ticket price, and no-show fees

344 The UMAP Journal 23.3 (2002) into first-class openings. The first part of the previous formula, M1 can still be used, since it deals with the cases in which the coach section isn’t filled anyway. Since ACE will not overbook first-class, ACE should always book it fully. Thus, fare for first-class is unimportant when considering how to maximize revenue. We further assume that ACE sells only unrestricted first-class tickets (there is no penalty to first-class no-shows). The second part of the equation needs only a minor modification to adjust for seats made available by first-class no-shows. ACE still gets $200 for each of the 100 passengers who show up and gets $50 for each of the (x − j) noshows. The difference now is that instead of simply multiplying by −$200 for each passenger over 100, we check for first-class openings and multiply −$200 by just the number who end up bumped. Those upgraded to first-class still pay coach fare (thus, more than 100 coach passengers can pay that $200). This function, P1(y), with y = j − 100 the number of overflow coach passengers, gives the expected net revenue expected for that much overflow. Similarly, P2(y) gives the expected net revenue when ACE can seat all of the overflow. Thus, the new version of the second part of the formula reads: M2(x) = x j=101 prob(x,j, 0.9) 200(100)+50(x − j)+ P1(j − 100)+ P2(j − 100) . The form of the Pi functions is similar to the two parts of the model already discussed. The probability of there being few enough first-class passengers is multiplied by $200 (coach fare) times the number of extra coach passengers who can be seated (j − 100). Recall that the show rate for first-class is 0.8: P2(y) = 20 −y k=0 prob(20,k, 0.8)(200)y. The other case is when ACE can’t seat all of the coach overflow. This time, we multiply by the loss of revenue from the coach spillover y, $200 for each of the y − (20 − k) bumped customers, offset by $200 for each of the (20 − k) passengers upgraded to first-class. The result is P1(y) = 20 k=21−y prob(20,k, 0.8) (−200) (y − (20 − k) + 200(20 − k) At this point, we have all of the pieces of the expected gain model. We plot the equation M = M1 + M2 in Figure 3 and find the maximum for x ≥ 100. The ideal overbooking level lies at 115 or 116 reservations, with a negligible difference in profit ($0.07) between them. Applying the Model We implemented our model in a computer program in which the parameters can be varied, including seating capacities, ticket price, and no-show fees

ACE is High 345 Expected Gain Model 20780 Revenue($)20740 20720 131411111 Coach Reservations Mad Figure 3. Expected Gain Model: Revenue M vS number of coach reservations. In the case of our example, the optimum is very broad around 116. When de ciding optimal overbooking levels, the airlines must balance revenue is against the chance of bumping. If ACE books 113 passengers instead the revenue de creases by $105 per flight but the probability of no bumping rises to 73% from 53%. Similarly, if it books 114 passengers, it loses $35 per flight but there is a 67% probability that no one will be bumped Fewer Flights The decrease in air traffic by 20% since September 11 means fewer flights Due to more-detailed security checks, it is necessary for planes to have longer turnaround times between flights. Adding 15 extra minutes at each turnaround would cause an airline such as Southwest to need almost 100 additional planes to maintain its previous air traffic flow. Therefore, there are fewer flights How does this circumstance affect our model? Federal regulations donot require compensating a bumped passenger sched uled to reach the destination within an hour of the original arrival time. Butnow the probability of accomplishing that is much smaller than before September 11th, we do not consider it likely and do not include it in the model Can bumped passengers be put onto a later flight to arrive within two hours of their original scheduled time? If this happens, federal regulations require an airline to compensate them for a ticket, essentially flying them for free. There is no loss or gain from this transaction, which is certainly more desirable than paying every bumped passenger $200 on top of refunding ticket price If people are put onto later flights, ACe Pays fewer passengers an extra $200. However, our Expected Gain Model attempts to maximize the number of people on the flight. Thus, the probability of a passenger being able to take a later flight is very low and the optimal overbooking level changes negligibly For example, disregarding first class, our Expected Gain Model shows only a 7% chance of a coach seat available on the next flight. We conclude that the

ACE is High 345 Figure 3. Expected Gain Model: Revenue M vs. number of coach reservations. In the case of our example, the optimum is very broad around 116. When deciding optimal overbooking levels, the airlines must balance revenue is against the chance of bumping. If ACE books 113 passengers instead, the revenue decreases by $105 per flight but the probability of no bumping rises to 73% from 53%. Similarly, if it books 114 passengers, it loses $35 per flight but there is a 67% probability that no one will be bumped. Fewer Flights The decrease in air traffic by 20% since September 11 means fewer flights. Due to more-detailed security checks, it is necessary for planes to have longer turnaround times between flights. Adding 15 extra minutes at each turnaround would cause an airline such as Southwest to need almost 100 additional planes to maintain its previous air traffic flow. Therefore, there are fewer flights. How does this circumstance affect our model? Federal regulations do not require compensating a bumped passenger scheduled to reach the destination within an hour of the original arrival time. But now the probability of accomplishing that is much smaller than before September 11th; we do not consider it likely and do not include it in the model. Can bumped passengers be put onto a later flight to arrive within two hours of their original scheduled time? If this happens, federal regulations require an airline to compensate them for a ticket, essentially flying them for free. There is no loss or gain from this transaction, which is certainly more desirable than paying every bumped passenger $200 on top of refunding ticket price. If people are put onto later flights, ACE pays fewer passengers an extra $200. However, our Expected Gain Model attempts to maximize the number of people on the flight. Thus, the probability of a passenger being able to take a later flight is very low and the optimal overbooking level changes negligibly. For example, disregarding first class, our Expected Gain Model shows only a 7% chance of a coach seat available on the next flight. We conclude that the

346 The UMAP Journal 23.3 (2002) Expected Gain Model is just as effective and much simpler if we disregard the possibility of bumped passengers obtaining a seat on a later flight, so we assume that all bumped passengers are compensated with a refund of their ticket price and $200 Heightened Security and Passengers'Fear Demand for flying is down, even though airlines have devoted much of their revenue to providing security. The additional security, while well justified causes problems for airlines and their passengers I CE Airlines is concerned about passengers who miss their flights because of the extensive security checks. This, along with passenger's fear, can cause a change in the no-show rate which the airlines must consider in their overbook ing strategies. Passengers may reserve a flight but then decide that in light of events they are too frightened to get on the plane. Because these factors create higher no-show rates, a higher overbooking rate may become optimal. In our expected gain model with increased no-show rates of 20% and 30% for coach and first-class, the optimal overbooking level jumps to around 130 or 135 seats Dealing with Bumped Passengers While most ways that airlines have dealt with bumping passengers are subtle and good business practice, some border on the absurd. For exa& x until 1978, United Airlines trained employees to bump people less likely complain: the elderly and armed services personnel-two groups that perhaps instead should have priority in seating There is a strategy other than the current compensations that could be op- timal for airlines to use, but it depends on cooperation. If ACE could convince other airlines that they all should give bumped passengers discount tickets usable on any of the airlines) to bumped passengers then each airline would lose less money from compensating bumped passengers. This would create a mutually profitable situation for all airlines involved: The airline accepting bumped passengers would fill seats that would otherwise be empty; the airline bumping the passengers would cut the amount of compensation to the price of a discounted ticket Suppose that the amount of compensation is decreased by one -half. The optimal level of overbooking rises, as does revenue; but we cannot be sure that every bumped passenger can be acea on another ight

346 The UMAP Journal 23.3 (2002) Expected Gain Model is just as effective and much simpler if we disregard the possibility of bumped passengers obtaining a seat on a later flight, so we assume that all bumped passengers are compensated with a refund of their ticket price and $200. Heightened Security and Passengers’ Fear Demand forflying is down, even though airlines have devoted much of their revenue to providing security. The additional security, while well justified, causes problems for airlines and their passengers. ACE Airlines is concerned about passengers who miss their flights because of the extensive security checks. This, along with passenger’s fear, can cause a change in the no-show rate, which the airlines must consider in their overbooking strategies. Passengers may reserve a flight but then decide that in light of events they are too frightened to get on the plane. Because these factors create higher no-show rates, a higher overbooking rate may become optimal. In our expected gain model with increased no-show rates of 20% and 30% for coach and first-class, the optimal overbooking level jumps to around 130 or 135 seats. Dealing with Bumped Passengers While most ways that airlines have dealt with bumping passengers are subtle and good business practice, some border on the absurd. For example, until 1978, United Airlines trained employees to bump people less likely to complain: the elderly and armed services personnel—two groups that perhaps instead should have priority in seating! There is a strategy other than the current compensations that could be optimal for airlines to use, but it depends on cooperation. If ACE could convince other airlines that they all should give bumped passengers discount tickets (usable on any of the airlines) to bumped passengers, then each airline would lose less money from compensating bumped passengers. This would create a mutually profitable situation for all airlines involved: The airline accepting bumped passengers would fill seats that would otherwise be empty; the airline bumping the passengers would cut the amount of compensation to the price of a discounted ticket. Suppose that the amount of compensation is decreased by one-half. The optimal level of overbooking rises, as does revenue; but we cannot be sure that every bumped passenger can be placed on another flight

ACE is High 347 Strengths and Weaknesses of the Model Strengths • Our model involves only basic combinatorics and elementary statistics. • Because it is parametrized, the model can continue to be used as rates, seating capacities, and compensation amounts change. • The model considers more than one class. • An airline can attempt to find the balance between maximizing revenue and pleasing customers, depending on how much risk the airline chooses to take. Weaknesses • We do not consider business class; including it would have risked the model being too complicated. Business class should not have a large effect on revenue maximization, because no-show rates are lower and business people are more concerned with reaching their destination on time than surrendering their seats for compensation. • Our model does not take into consideration how multiple flights affect each other. If putting passengers onto later flights were an option, revenue would increase slightly but doing so would also further complicate optimal overbooking levels on other flights. • Because ACE is not bumping passengers to later flights, bumped passengers are left out in the cold with no flight and just a little bit of extra money—a resolution that does not provide positive customer relations. • We allow no overbooking in first class. If ACE is willing to take the risk of downgrading or bumpingfirst-class passengers, then revenue could increase slightly by overbooking first-class seats. • In reality, anyone can buy a restricted or unrestricted ticket in either class. Therefore, a more complicated model would include the possibility of some coach no-shows receiving full-refund and some first-class no-shows paying a no-show fee. • Our binomial distribution for showing up assumes independence among passengers. However, many people fly and show up in groups. References Airline Passengers to pay security fee next month. 2002. USA Today (3 January 2002). http://www.usatoday.com/news/washdc/jan02/2002-01-03- airlinesecurity.htm