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