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