Bumping for Dollars: The Airline Overbooking Problem 351 Bumping for dollars: The airline Overbooking problem John D. Bowman Corey r houmard Adam S Dickey Wake Forest University Winston -Salem. NC Advisor: Frederick H. Cher Introduction We construct a model that expresses the expected revenue for a flight in terms of the number of reservations, the capacity of the plane, the price of a ticket, the value of a voucher, and the probability of a person showing up for the flight. When values are supplied for every variable but the first, the function can be maximized to yield an optimal booking that maximizes expected revenue We apply the model to three situations: a single flight, two flights in a chain of flights, and multiple flights in a chain of flights. We conclude that fewer flights will increase the value of the penalty or voucher and thus decrease the optimal number of reservations. Heightened security also lowers the optimal number of reservations. An increase in passengers'fear decreases the prob ability that a person will show up for a flight and thus increases the optimal number of reservations. Finally, the loss of billions of dollar in revenue has no effect on the optimal value of reservations We model the probability of a given number of people showing up as a binomial distribution. We express the average expected revenue of a flight in terms of the number of bookings made Starting with the Single-Flight case, we derive a model and revenue function for a flight unaffected by previous flights. From this situation, we expand the model to the Two-Flight case, in which the earlier flight affects the number of people who show up for the later flight. We generalize the model even further to the number of people showing up depending on many previous flights The UMAP Journal 351-365. Copyright 2002 by COMAP, Inc. All rights rmission 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 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
Bumping for Dollars: The Airline Overbooking Problem 351 Bumping for Dollars: The Airline Overbooking Problem John D. Bowman Corey R. Houmard Adam S. Dickey Wake Forest University Winston-Salem, NC Advisor: Frederick H. Chen Introduction We construct a model that expresses the expected revenue for a flight in terms of the number of reservations, the capacity of the plane, the price of a ticket, the value of a voucher, and the probability of a person showing up for the flight. When values are supplied for every variable but the first, the function can be maximized to yield an optimal booking that maximizes expected revenue. We apply the model to three situations: a single flight, two flights in a chain of flights, and multiple flights in a chain of flights. We conclude that fewer flights will increase the value of the penalty or voucher and thus decrease the optimal number of reservations. Heightened security also lowers the optimal number of reservations. An increase in passengers’ fear decreases the probability that a person will show up for a flight and thus increases the optimal number of reservations. Finally, the loss of billions of dollar in revenue has no effect on the optimal value of reservations. We model the probability of a given number of people showing up as a binomial distribution. We express the average expected revenue of a flight in terms of the number of bookings made. Starting with the Single-Flight case, we derive a model and revenue function for a flight unaffected by previous flights. From this situation, we expand the model to the Two-Flight case, in which the earlier flight affects the number of people who show up for the later flight. We generalize the model even further to the number of people showing up depending on many previous flights. The UMAP Journal 351–365. 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
352 The UMAP Journal 23.3 (2002) The model In each of the three situations modeled, we derive two formulas. The first P(k), describes the probability that k people show up for a flight. The second, Revenue(b, c, r, a, p), describes the expected revenue for a flight as a function f the number of reservations. We verified these theoretical equations by a Monte-Carlo simulation For the Single-Flight Model: P(k)=(1)5(1-py n-k Revenue(b,c, T,a, p)=2 P(k)[rmin(k, c)-z max(k-c,O) For the Two-Flight Model: P(k)=B(k)1 P1()+∑P(k-)P(c+) Revenue2(b,c,r,, P)=2 P(k)[rmin(ki, c))-z max(k-c,O) For the n-Flight Model b+(n-1)(b-c) P()=P()1-∑P2=(0) (n-1)(b-c) P(h-j)Pn-1(c+j +(n-1)(b-c) Revenuen(b,c,r,a,p)=2 Pn(k)[rmin(k, c)-2max(k-c, 0) k=0 The variables are b=number of reservations(or bookings)per flight c= plane capacit r= price of a ticket r= value of a voucher p= probability that a booked passenger shows up for a flight Given p, c, r, and the method finds the b that maximizes revenue
352 The UMAP Journal 23.3 (2002) The Model In each of the three situations modeled, we derive two formulas. The first, P(k), describes the probability that k people show up for a flight. The second, Revenue(b, c, r, x, p), describes the expected revenue for a flight as a function of the number of reservations. We verified these theoretical equations by a Monte-Carlo simulation. For the Single-Flight Model: P(k) = n k pk(1 − p) n−k, Revenue(b, c, r, x, p) = c+( b−c) k=0 P(k) r min(k,c) − x max(k − c, 0) . For the Two-Flight Model: P2(k) = P1(k) 1 − b i=c+1 P1(i) + b−c j=1 P1(k − j)P1(c + j), Revenue2(b, c, r, x, p) = c+2( b−c) k=0 P(k) r min(k,c) − x max(k − c, 0) . For the n-Flight Model: Pn(k) = P1(k) 1 − b+(n− 1)(b−c) i=c+1 Pn−1(i) + (n− 1)(b−c) j=1 P1(k − j)Pn−1(c + j), Revenuen(b, c, r, x, p) = b+(n− 1)(b−c) k=0 Pn(k) r min(k,c) − x max(k − c, 0) . The variables are: • b = number of reservations (or bookings) per flight c = plane capacity r = price of a ticket x = value of a voucher p = probability that a booked passenger shows up for a flight Given p, c, r, and x, the method finds the b that maximizes revenue.
Bumping for Dollars: The Airline Overbooking Problem 353 Derivation of the Single-Flight Model The binomial distribution applies to calculating the probability that a num- ber of passengers shows up for a flight The probability involves repeated events(each trial calculates the probability of one person showing up) with only two possible outcomes(either the person is a show or no-show) We assume that peoples actions do not influence one another; each persons hance of showing up is independent of another persons chance. This is not true in reality, as people often travel in groups; but this a necessary and plification We assume that the probability of a person arriving remains constant for We use the binomial distribution to calculate expected revenue. Airlines overbook their flights, knowing that some people will not take the flight. Given a certain overbooking strategy b(i. e. the maximum number of reservations taken for a particular flight, with b>c, the capacity of the plane), the expected revenue Is Revenue(b,r,P)=>P(k)r min(k,c) The function is incomplete, however, because it does not penalize the air- line for the consequences of overbooking. The airline usually provides bumped ued, gers with either an airline ticket voucher or a cash reimbursement, val- at per bumped person c+(b-c) Revenue(b,r,P)=2 P(k)(rmin(k, c)- max(k-C, O) k=0 When k s c, the c term is zero; when k>c, the airlines is penalized for having to bun eople The booking decision b and the capacity c of the plane are fixed before the model begins. This model considers just one flight in a complex network of lights; it does not allow for the possibility that passengers are bumped from a previous flight, since it assumes that the only passengers are those who made a reservation for this particular flight. The model also applies to just one flight: If the number of passengers who show up is greater than the capacity of the plane, those bumped passengers receive a voucher and -with a wave of the magic wand of assumption-disappear. Finally, regardless of the flight's destination Hawai or Death Valley), we assume that there is enough demand to fill the predetermined number of bookings Since p is constant throughout our model, the revenue function is really dependent only on the number of bookings, the capacity of the plane, the cost f a ticket, and the cost of the penalty
Bumping for Dollars: The Airline Overbooking Problem 353 Derivation of the Single-Flight Model The binomial distribution applies to calculating the probability that a number of passengers shows up for a flight: • The probability involves repeated events (each trial calculates the probability of one person showing up) with only two possible outcomes (either the person is a show or no-show). • We assume that people’s actions do not influence one another; each person’s chance of showing up is independent of another person’s chance. This is not true in reality, as people often travel in groups; but this a necessary and appropriate simplification. • We assume that the probability of a person arriving remains constant for each person. We use the binomial distribution to calculate expected revenue. Airlines overbook their flights, knowing that some people will not take the flight. Given a certain overbooking strategy b (i.e., the maximum number of reservations taken for a particular flight, with b>c, the capacity of the plane), the expected revenue is Revenue(b, r, p) = b k=0 P(k)r min(k,c). The function is incomplete, however, because it does not penalize the airline for the consequences of overbooking. The airline usually provides bumped passengers with either an airline ticket voucher or a cash reimbursement, valued at x per bumped person: Revenue(b, r, p) = c+( b−c) k=0 P(k) [r min(k,c) − x max(k − c, 0)] . When k ≤ c, the x term is zero; when k>c, the airlines is penalized for having to bump people. The booking decision b and the capacity c of the plane are fixed before the model begins. This model considers just one flight in a complex network of flights; it does not allow for the possibility that passengers are bumped from a previous flight, since it assumes that the only passengers are those who made a reservation for this particular flight. The model also applies to just one flight: If the number of passengers who show up is greater than the capacity of the plane, those bumped passengers receive a voucher and—with a wave of the magic wand of assumption—disappear. Finally, regardless of the flight’s destination (Hawaii or Death Valley), we assume that there is enough demand to fill the predetermined number of bookings. Since p is constant throughout our model, the Revenue function is really dependent only on the number of bookings, the capacity of the plane, the cost of a ticket, and the cost of the penalty
354 The UMAP Journal 23.3(2002) Application of the Single-Flight Model We set p=0.9. Since b must be an integer, the revenue function is not continuous. Thus, the analytic method of maximizing of the function(namely, differentiating and setting the derivative equal to zero) cannot be applied. In- stead we use maple 6 After setting values for the probability, plane capacity, and ticket and voucher values we evaluate the function at b= c, then increment b until a maximum for Revenue is found We used three plane capacities: 10, 30, and 100. The values of the ticket price r, the voucher a, and the arrival probability p are held constant at $300, 300, and 0.9 for the examples in Table 1 Table 1 Results for the Single-Flight Model. Capacity Optimal overbooking Revenue Bump probability 31% 8,598 111 $29,250 4% sengers. The model is further weakened in light of the post-September 1lissues proposed by the problem. Among the four issues-fewer flights, heightened se- curity, passengers' fear, and losses--this model can account only for increased passenger fear(indicated by a change in probability that a passenger shows up). Clearly this Single-Flight Model is not a proper solution to the airline- overbooking problem Derivation of the Two-Flight Model The Two-Flight Model begins with updating both the probability and rev- enue functions. Unlike the Single-Flight Model, the new functions reflect the possibility that passengers bumped from one flight fill seats on the next. By this assumption, the probability function for the second flight, P2(k), changes, be- cause k may now also be expressed as a combination of people ticketed for the second flight and bumped passengers from the first flight. Since the revenue
354 The UMAP Journal 23.3 (2002) Application of the Single-Flight Model We set p = 0.9. Since b must be an integer, the revenue function is not continuous. Thus, the analytic method of maximizing of the function (namely, differentiating and setting the derivative equal to zero) cannot be applied. Instead, we use Maple 6. After setting values for the probability, plane capacity, and ticket and voucher values, we evaluate the function at b = c, then increment b until a maximum for Revenue is found. We used three plane capacities: 10, 30, and 100. The values of the ticket price r, the voucher x, and the arrival probability p are held constant at $300, $300, and 0.9 for the examples in Table 1. Table 1. Results for the Single-Flight Model. Capacity Optimal overbooking Revenue Bump probability 10 11 $2,782 31% 30 33 $8,598 35% 100 111 $29,250 44% The probabilities of bumping are larger than the industry frequency of about 20%. Worse, the model ignores all the problems created by these bumped passengers. The model is further weakened in light of the post-September 11 issues proposed by the problem. Among the four issues—fewerflights, heightened security, passengers’ fear, and losses—this model can account only for increased passenger fear (indicated by a change in probability that a passenger shows up). Clearly this Single-Flight Model is not a proper solution to the airlineoverbooking problem. Derivation of the Two-Flight Model The Two-Flight Model begins with updating both the probability and revenue functions. Unlike the Single-Flight Model, the new functions reflect the possibility that passengers bumped from one flight fill seats on the next. By this assumption, the probability function for the second flight, P2(k), changes, because k may now also be expressed as a combination of people ticketed for the second flight and bumped passengers from the first flight. Since the revenue
Bumping for Dollars: The Airline Overbooking Problem 355 function depends on the probability function, it too must change P2(k)=Pr(k people show up for flight 2) Pr(h regular passengers arrive) Pr(no one bumped from flight 1) Pr(k-1 passengers arrive) Pr(1 passenger bumped)+ Pr(k-j arrive) Pr( bumped)+ Pr(k-(b-c) arrive) Pr(b-c bumped P1()1-∑P1(|+∑(-)P1(+) i=k+1 A maximum of b-c people can be bumped from flight 1, since at most b people show up for it and we assume that no passengers are carried over from any previous flight. The probability that 1 passenger is bumped from flight 1 is exactly the probability that c+ I people are present for it. Thus we have Pr( passengers bumped)=P(c+j). As long as b, p, and c remain never changes; it is independent of the number of bumped passengers foe the same, the probability that new(prebooked, nonbumped)passengers arrive a previous flight. (We assume that there is no way for a passenger to know how many people have been bumped onto his or her flight from a previous one. )Thus, Pr(k-j regular passengers arrive) will always be computed by Pi(h-j), our original probability function for the Single-Flight Mode n the second summation of P2(k), the term k-j could be negative for small k. If so, we define the probability of a negative number of people showing up from a previous flight to be 0 (empty seats on a flight cannot be filled by passengers from later flights We now express the second revenue function in terms of the second proba- bility function c+2(b-c) Revenue(b, c,r, r, p) P(k)[rmin(k, c-a max(k-c,O)] passenger bumped from one flight is automatically booked on the next flight and seated before regular passengers, so as to have almost no chance of being bumped again. For the second flight, we assume that the number of eople who show up is affected only by that flight and the previous flight, and that there is enough demand to fill the predetermined number of bookings The summation now has c+2(b-c)as it maximum value. The second flight must not only account for b passengers but must also account for the number of people possibly bumped from the first flight Application of the Two-Flight Model By introducing a second flight, we more accurately model the situation. The optimal overbooking strategy and maximum revenue should either remain the
Bumping for Dollars: The Airline Overbooking Problem 355 function depends on the probability function, it too must change. P2(k) = Pr(k people show up for flight 2) = Pr(k regular passengers arrive)Pr(no one bumped from flight 1) + Pr(k − 1 passengers arrive)Pr(1 passenger bumped) + ··· + Pr(k − j arrive)Pr(j bumped) + ··· + Pr(k − (b − c) arrive)Pr(b − c bumped) = P1(k) 1 − b i=k+1 P1(i) + b−c j=1 P1(k − j)P1(c + j). A maximum of b − c people can be bumped from flight 1, since at most b people show up for it and we assume that no passengers are carried over from any previous flight. The probability that 1 passenger is bumped from flight 1 is exactly the probability that c + 1 people are present for it. Thus we have Pr(j passengers bumped) = P1(c + j). As long as b, p, and c remain the same, the probability that new (prebooked, nonbumped) passengers arrive never changes; it is independent of the number of bumped passengers from a previous flight. (We assume that there is no way for a passenger to know how many people have been bumped onto his or her flight from a previous one.) Thus, Pr(k − j regular passengers arrive) will always be computed by P1(k − j), our original probability function for the Single-Flight Model. In the second summation of P2(k), the term k−j could be negative for small k. If so, we define the probability of a negative number of people showing up from a previous flight to be 0 (empty seats on a flight cannot be filled by passengers from later flights!). We now express the second revenue function in terms of the second probability function: Revenue2(b, c, r, x, p) = c+2( b−c) k=0 P(k) r min(k,c − x max(k − c, 0) . A passenger bumped from one flight is automatically booked on the next flight and seated before regular passengers, so as to have almost no chance of being bumped again. For the second flight, we assume that the number of people who show up is affected only by that flight and the previous flight, and that there is enough demand to fill the predetermined number of bookings. The summation now has c+2(b−c) as it maximum value. The second flight must not only account for b passengers but must also account for the number of people possibly bumped from the first flight. Application of the Two-Flight Model By introducing a second flight, we more accurately model the situation. The optimal overbooking strategy and maximum revenue should either remain the
356 The UMAP Journal 23.3 (2002) same or slightly decrease Using the revenue function for the Two-Flight Model, we now calculate maximum revenue and the associated overbooking strategy for the same plane capacities as for the Single-Flight Model. Again, the values of the ticket price r, the voucher and the arrival probability p are held constant at 300, 300, and 0.9. The results are in Table 2 Table 2 Results for the Two-Flight Model. Capacity Optimal overbooking Revenue Bump probability 11 $2745 34% 8,551 29,107 57% M, In each case, the optimal booking strategy is the same as the Single-Flight lel, but the maximum revenues is lower, and bump probability is higher Since both flights are overbooked, the probability that someone is bumped should only increase. The n-Flight Model We generalize to n flights. We allow each flight to be influenced by th 1)flights before it. We still assume that a passenger bumped from one flight is given preferential seating on the next. However, giving seats to bumped passengers who are already at the airport decreases the number of seats for pre- booked passengers. The n-flight model allows this domino effect of bumping to ripple through n-1 successive flights. As n gets large, our model becomes a better and better approximation of the real case in which every flight is affected by many previous flights. Our probability function becomes recursive P()=P()1 Pn-1() (n-1)(b-c) ∑P(k-j)Pn-1(c+j Revenue(b,c,r, a,P)=2 Pn(k)[rmin(k, c)-z max(k-c, O) For the first summation, zero people show up from the previous fligh meaning that there are enough seats for everyone on that flight and anyone bumped from a previous flight. If the total possible number of people who can show up to the current flight is b+(n-1)(b-c)(as is explained in a moment)
356 The UMAP Journal 23.3 (2002) same or slightly decrease. Using the Revenue function for the Two-Flight Model, we now calculate maximum revenue and the associated overbooking strategy for the same plane capacities as for the Single-Flight Model. Again, the values of the ticket price r, the voucher x, and the arrival probability p are held constant at 300, 300, and 0.9. The results are in Table 2. Table 2. Results for the Two-Flight Model. Capacity Optimal overbooking Revenue Bump probability 10 11 $2,745 34% 30 33 $8,551 42% 100 111 $29,107 57% In each case, the optimal booking strategy is the same as the Single-Flight Model, but the maximum revenues is lower, and bump probability is higher. Since both flights are overbooked, the probability that someone is bumped should only increase. The n-Flight Model We generalize to n flights. We allow each flight to be influenced by the (n − 1) flights before it. We still assume that a passenger bumped from one flight is given preferential seating on the next. However, giving seats to bumped passengers who are already at the airport decreases the number of seats for prebooked passengers. The n-flight model allows this domino effect of bumping to ripple through n−1 successive flights. As n gets large, our model becomes a better and better approximation of the real case, in which every flight is affected by many previous flights. Our probability function becomes recursive: Pn(k) = P1(k) 1 − b+(n− 1)(b−c) i=c+1 Pn−1(i) + (n− 1)(b−c) j=1 P1(k − j)Pn−1(c + j), Revenuen(b, c, r, x, p) = b+(n− 1)(b−c) k=0 Pn(k) r min(k,c) − x max(k − c, 0) . For the first summation, zero people show up from the previous flight, meaning that there are enough seats for everyone on that flight and anyone bumped from a previous flight. If the total possible number of people who can show up to the current flight is b + (n − 1)(b − c) (as is explained in a moment)
Bumping for Dollars: The Airline Overbooking Problem 357 then the total number of people who can show up for the previous flight must be b+(n-2)(b-c), which we use as the upper limit of the summation For the second summation, we use(n-1)(b-c)instead of(b-c), since now there can be at most(n-1)(b-c) passengers bumped from flight n-1. This upper bound for bumped passengers can be proved by mathematicalinduction [EDITOR'S NOTE: We omit the authors proof. The revenue function for the 2-flight model can also be extended to n flights in a straightforward way. Note that at most n(b-c) people can be bumped from the nth flight. We have (n-1)(b-c) Revenue(b) Pn(k)[rmin(k, c)-cmax(k-c,O) k=0 We now consider booking strategies to optimize revenue. Computation of the n-Flight Model The recursive method We can create documents in Maple to compute the probability and revenue functions. To compute Revenue(b), we must evaluate Pn(k) a total of b+(n 1)(b-c)times. In turn, Pn()must evaluate Pn-1(k)at total of (2n-1)(b-c) times, Pn-1(k )must evaluate Pn-2(k)a total of [2(n-1)-1(b-c)=(2n 3)(b-c)times, and so on. Thus, without even accounting for all the evaluations of Pi(k)in each iteration, we make b+(m-1)(b-c)](2n-1)(b-c)(2n-3)(b-c)…[2n-(2k+1)(b-c)…(1)(b-c) ={b+(m-1)(b-c) function calls. With b= 105 and c= 100, Revenue2(k)requires 1650 function calls, Revenue3(k)requires 86, 250 calls, and Revenues(k )requires more than 6.3 million function calls. The computation time is proportional to the number of function calls: Revenue(105 )takes less than 1 s, Revenue3(105) takes 13 s, and Revenuea (105) takes 483 Of course, this is a very inefficient method. A more efficient method would be to store all probability values in an array, beginning with the or Pi(k) and working upwards to Pn(k). However, Maple makes array manipulation difficult. Instead, we turn to another method [EDITOR'S NOTE: Mathematica(and perhaps Maple too) provides an easy-to-use capability computation of such probabilities via dynamic programming. For an example of its use, see Farmer Klaus and the mouse, by PaulJ. Campbell, The UMAP Journal 23(2)(2002)121-134
Bumping for Dollars: The Airline Overbooking Problem 357 then the total number of people who can show up for the previous flight must be b + (n − 2)(b − c), which we use as the upper limit of the summation. For the second summation, we use (n−1)(b−c)instead of(b−c), since now there can be at most (n − 1)(b − c) passengers bumped from flight n − 1. This upper bound for bumped passengers can be proved by mathematical induction. [EDITOR’S NOTE: We omit the authors’ proof.] The revenue function for the 2-flight model can also be extended to n flights in a straightforward way. Note that at most n(b − c) people can be bumped from the nth flight. We have: Revenuen(b) = b+(n− 1)(b−c) k=0 Pn(k) r min(k,c) − c max(k − c, 0) . We now consider booking strategies to optimize revenue. Computation of the n-Flight Model The Recursive Method We can create documents in Maple to compute the probability and revenue functions. To compute Revenuen(b), we must evaluate Pn(k) a total of b +(n − 1)(b − c) times. In turn, Pn(k) must evaluate Pn−1(k) at total of (2n − 1)(b − c) times, Pn−1(k) must evaluate Pn−2(k) a total of [2(n − 1) − 1](b − c) = (2n − 3)(b−c)times, and so on. Thus, without even accounting for all the evaluations of P1(k) in each iteration, we make [b+(n−1)(b−c)](2n−1)(b−c)(2n−3)(b−c)··· [2n−(2k+1)](b−c)···(1)(b−c) = [b + (n − 1)(b − c) (2n − 1)! 2(n − 1)! (b − c) n−1 function calls. With b = 105 and c = 100, Revenue2(k) requires 1650 function calls, Revenue3(k) requires 86,250 calls, and Revenue4(k) requires more than 6.3 million function calls. The computation time is proportional to the number of function calls: Revenue2(105) takes less than 1 s, Revenue3(105) takes 13 s, and Revenue4(105) takes 483 s. Of course, this is a very inefficient method. A more efficient method would be to store all probability values in an array, beginning with the values for P1(k) and working upwards to Pn(k). However, Maple makes array manipulation difficult. Instead, we turn to another method. [EDITOR’S NOTE: Mathematica (and perhaps Maple too) provides an easy-to-use capability for computation of such probabilities via dynamic programming. For an example of its use, see “Farmer Klaus and the Mouse,” by Paul J. Campbell, The UMAP Journal 23 (2) (2002) 121–134
358 The UMAP Journal 23.3(2002) Monte carlo simulation We develop a Monte Carlo computer simulation coded in Pascal that runs the n-flight model numerous times and determines the average revenue for a large number of trials. Instead of obtaining precise probabilities using the functions developed above, we flip a(electronic)weighted coin to determin whether each individual passenger shows up for the flight. We tell the program how many trials to run, give it values for n, P, c, r, and x and tell it the largest value of b to check. The program begins with b= c. It flips numerous weighted coins to determine how many passengers show up for the first flight. It bumps any excess passengers to the second flight and flips coins again to see how many prebooked passengers arrive. The excess is bumped to the third flight and the process continues until the nth flight Revenue is evaluated by adding an amount equal to the ticket price for each passenger who flies and deducting a penalty for each passenger who is bumped. The program iterates for successive values of b until it reaches the preassigned upper bound The output includes, for each b value, the mean revenue over all trials and the corresponding percentage standard error. Percentage standard error was usually less than 2% and often less than 1% Optimization strategies for the n-Flight Model We will never earn more than the ticket price(r) times the number of se (c), so the gain from overbooking is limited--but the possible costs are not. At some point, the costs of overbooking outweigh the benefits; there should be a unique maximum for revenue. To find the maximum revenue, we evaluate the revenue function at different booking values, beginning with b=c, until we find a b with Revenue(b-1)< Revenue(b)and Revenue(b+1)<Revenue(b). This will be our bo The obvious booking strategy is to book every flight with bopt passengers While this method maximizes flight revenue, it yields a high percentage of flights with bumped passengers. For a plane with 100 seats, the maximum revenue occurs at b= 108, with 34% of flights bumping passengers. Because our model does not account for changes in demand due to the airlines behav ior, this might not be the truly optimal value of b in the long run. Bumping large numbers of passengers will drive customers away; decreased demand will depress the price that we can charge and we reduce revenue in the long demand, allow us to raise prices, and increase revenue. Thus, our modelon o term. Similarly, an especially low percentage of bumped flights may increase accounts for short-term effects, not long-term ones Moving away from maximum revenue lowers expected revenue by a small amount but decreases the bump probability by a large amount. For example, if we are at the optimal b= 108 with a capacity of 100, with ticket price and pnce penalty both $1, the expected revenue is $4, 806 with bump probability of 33% 81??? If we move down just 1 to b= 107, our revenue is $4, 791 the bump probability
358 The UMAP Journal 23.3 (2002) Monte Carlo Simulation We develop a Monte Carlo computer simulation coded in Pascal that runs the n-flight model numerous times and determines the average revenue for a large number of trials. Instead of obtaining precise probabilities using the functions developed above, we flip a (electronic) weighted coin to determine whether each individual passenger shows up for the flight. We tell the program how many trials to run, give it values for n, p, c, r, and x and tell it the largest value of b to check. The program begins with b = c. It flips numerous weighted coins to determine how many passengers show up for the first flight. It bumps any excess passengers to the second flight and flips coins again to see how many prebooked passengers arrive. The excess is bumped to the third flight and the process continues until the nth flight. Revenue is evaluated by adding an amount equal to the ticket price for each passenger who flies and deducting a penalty for each passenger who is bumped. The program iterates for successive values of b until it reaches the preassigned upper bound. The output includes, for each b value, the mean revenue over all trials and the corresponding percentage standard error. Percentage standard error was usually less than 2% and often less than 1%. Optimization Strategies for the n-Flight Model We will never earn more than the ticket price (r) times the number of seats (c), so the gain from overbooking is limited—but the possible costs are not. At some point, the costs of overbooking outweigh the benefits; there should be a unique maximum for revenue. To find the maximum revenue, we evaluate the revenue function at different booking values, beginning with b = c, until we find a b with Revenue(b − 1) < Revenue(b) and Revenue(b + 1) < Revenue(b). This will be our bopt. The obvious booking strategy is to book every flight with bopt passengers. While this method maximizes flight revenue, it yields a high percentage of flights with bumped passengers. For a plane with 100 seats, the maximum revenue occurs at b = 108, with 34% of flights bumping passengers. Because our model does not account for changes in demand due to the airlines’ behavior, this might not be the truly optimal value of b in the long run. Bumping large numbers of passengers will drive customers away; decreased demand will depress the price that we can charge and we reduce revenue in the long term. Similarly, an especially low percentage of bumped flights may increase demand, allow us to raise prices, and increase revenue. Thus, our model only accounts for short-term effects, not long-term ones. Moving away from maximum revenue lowers expected revenue by a small amount but decreases the bump probability by a large amount. For example, if we are at the optimal b = 108 with a capacity of 100, with ticket price and price = penalty both $1,, the expected revenue is $4,806 with bump probability of 33%. $1??? If we move down just 1 to b = 107, our revenue is $4,791 the bump probability
Bumping for Dollars: The Airline Overbooking Problem 359 Table 3 Results of simulation: for each number for bookings, 100 trials with 50 flights per trial Bookings Revenue Bump Delta(%Bump) Delta(%Rev) D(Bmp/D(Rev) 4539 0.02% 0.02% 0.84% 102 0.04% 0.02% 1.09% 0.02 $4,6310.04% 0.58% 092% 0.63 0.97% 2.86% 0.97% $4,758 8.52% 12.50% 076% 1645 21.02% 12.64% 0.68% 18.64 109 $4,80055.76% 1704% -0.15% -115.28 We adopt as a criterion to compare two values of b the ratio of the relative change in the bump probability and the relative change in revenue
Bumping for Dollars: The Airline Overbooking Problem 359 drops to 21%. Table 3. Results of simulation: for each number for bookings, 100 trials with 50 flights per trial. Bookings Revenue % Bump Delta(%Bump) Delta(%Rev) D(Bmp/D(Rev) 100 $4,501 0.00% 0.00% 0.02% 0.00 101 $4,539 0.02% 0.02% 0.84% 0.02 102 $4,589 0.04% 0.02% 1.09% 0.02 103 $4,631 0.04% 0.58% 0.92% 0.63 104 $4,677 0.62% 2.24% 0.97% 2.30 105 $4,722 2.86% 5.66% 0.97% 5.82 106 $4,758 8.52% 12.50% 0.76% 16.45 107 $4,791 21.02% 12.64% 0.68% 18.64 108 $4,807 33.66% 22.10% 0.34% 65.67 109 $4,800 55.76% 17.04% −0.15% −115.28 We adopt as a criterion to compare two values of b the ratio of the relative change in the bump probability and the relative change in revenue:
360 The UMAP Journal 23.3(2002) △R R △(%Bump) △ Revenue△(% Revenue) The process goes: A maximum revenue is found, along with its high bump probability. The optimizer now considers a lower value of b and looks at the ratio of the change in the bump probability to the change in revenue. If this ratio is above a certain value k, the optimizer accepts the lower b. The optimizer continues to do this until the ratio is no longer greater than the constant. In Table 3, with k= 20, the new optimum b would be 107, because the ratio 18.64 is not greater than k= 20 Table 4 shows three different optimization values for different plane ities Table 4 Optimal bookings using different criteria(p=0. 9, r=l, a=1). For each number for bookings, 100 trials with 50 flights per trial Maximum revenue k=20 b Rev Bump(%) b Rev Pump(%) b Rev Bump(%) 1010 0 10 450 0 10 30321390 311385 301350 1001094810 1074790 1044670 0.7 1501637270 1617220 1577070 0.3 2002199740 215 0713690 30313610 29913450 Application of the n-Flight Model The problem specifically mentions four issues to be addressed by our model fewer flights, heightened security, passengers'fear, and revenue losses Why are airlines offering fewer flights? If the airlines had kept offering the same number of flights, the question of an optimal overbooking strategy would be moot, because the planes would not fill. The huge drop in demand has reduced supply but could also result in slashed prices. Since the value of the compensation involuntarily bumped ticketholders is tied to the ticket price ( though with a ceiling), changes in ticket prices should affect the optimum booking level little if at all However, the fewer flights, the longer people who are denied boarding must wait for the next flight; being denied boarding is less convenient. Since compensation is usually offered in a kind of auction to induce voluntary relin quishing of seats, the airline will have to offer more. Therefore, longer delays
360 The UMAP Journal 23.3 (2002) ∆Pbump Pbump ∆Revenue Revenue = ∆(%Bump) ∆(%Revenue) . The process goes: A maximum revenue is found, along with its high bump probability. The optimizer now considers a lower value of b and looks at the ratio of the change in the bump probability to the change in revenue. If this ratio is above a certain value k, the optimizer accepts the lower b. The optimizer continues to do this until the ratio is no longer greater than the constant. In Table 3, with k = 20, the new optimum b would be 107, because the ratio 18.64 is not greater than k = 20. Table 4 shows three different optimization values for different plane capacities. Table 4. Optimal bookings using different criteria (p = 0.9, r = 1, x = 1). For each number for bookings, 100 trials with 50 flights per trial. c Maximum revenue k = 20 k = 1 b Rev Pbump(%) b Rev Pbump(%) b Rev Pbump(%) 10 10 450 0 10 450 0 10 450 0 30 32 1390 45 31 1385 12 30 1350 0 50 54 2360 50 53 2360 25 51 2290 0.8 100 109 4810 50 107 4790 19 104 4670 0.7 150 163 7270 37 161 7220 14 157 7070 0.3 200 219 9740 47 215 9660 9 211 9490 0.4 280 307 13690 46 303 13610 13 299 13450 1.3 Application of the n-Flight Model The problem specifically mentions four issues to be addressed by our model: fewer flights, heightened security, passengers’ fear, and revenue losses. Why are airlines offering fewer flights? If the airlines had kept offering the same number of flights, the question of an optimal overbooking strategy would be moot, because the planes would not fill. The huge drop in demand has reduced supply but could also result in slashed prices. Since the value of the compensation involuntarily bumped ticketholders is tied to the ticket price (though with a ceiling), changes in ticket prices should affect the optimum booking level little if at all. However, the fewer flights, the longer people who are denied boarding must wait for the next flight; being denied boarding is less convenient. Since compensation is usually offered in a kind of auction to induce voluntary relinquishing of seats, the airline will have to offer more. Therefore, longer delays