322 The UMAP Journal 23.3 (2002) are enough to determine the corresponding time-dependent Compensation function, plotted in Figure 1 Compensation(t) 0<t<15min; 105.33e007324t,15min<t<30min. 品合Eo Time since gate agent made first offer 1. Auction offering(compensation) Consideration of passenger behavior suggests that we use a Chebyshev weighting distribution for this effort(shown in Figure 2). A significant num ber of passengers will take flight vouchers as soon as they become available We simulate this random variable, which has probability density function f(s)= ∈[-1,1 and cumulative distribution function n2 where n is a dummy variable. Inverting the cumulative distribution function results in a method for generating random variables with the Chebyshev distribution [Ross 1990 F-()=sin T(U-2)
322 The UMAP Journal 23.3 (2002) are enough to determine the corresponding time-dependent Compensation function,plotted in Figure 1. Compensation(t) = 316, 0 ≤ t ≤ 15 min; 105.33e0.07324 t , 15 min < t ≤ 30 min. 0 5 10 15 20 25 30 300 400 500 600 700 800 900 1000 Time since gate agent made first offer Offer made by gate agent Figure 1. Auction offering (compensation) Consideration of passenger behavior suggests that we use a Chebyshev weighting distribution for this effort (shown in Figure 2). A significant number of passengers will take flight vouchers as soon as they become available. We simulate this random variable, which has probability density function f(s) = 1 π √1 − s2 , s ∈ [−1, 1], and cumulative distribution function F(τ ) = τ −1 1 π 1 − η2 dη = 1 2 + sin−1(τ ), where η is a dummy variable. Inverting the cumulative distribution function results in a method for generating random variables with the Chebyshev distribution [Ross 1990]: F −1(τ ) = sin π(U − 1 2 )
Probabilistically optimized Airline Overbooking Strategies 32 ime before departure vs Probability of Voluntary Bump Time Figure 2. Chebyshev weighting function for offer acceptance where U is a random uniform variable on 0, 1 With a linear transformation from the Chebyshev domain [-1, 1] to the time interval [0, 30 via t= 15T+15, we find a random variable t that takes on values from 0 to 30 according to the density function f(s). Figure 3 shows the results of using this process to generate 100,000 time values. We use this random variable to assign times for compensation offer acceptance under the auction plan The total costofbumping(X-C) passengers is >ial Compensation(ti) Optimizing Overbooking Strategies Our goal is to maximize the expected value of the total profit function, ETP(X)J given the variability of the bump function and the probabilistic passenger arrival model There are competing dynamic effects at work in the total profit function Ticket sales are desirable, but there is a point at which the cost of bumping becomes too great. Also, the variability of the number of passengers who show ffects the dynamics. The expected value of the tota E()=∑7o(6) n2(1-)B-
Probabilistically Optimized Airline Overbooking Strategies 323 0 5 10 15 20 25 30 0 1 2 3 4 5 6 Time Probability at t Time before departure vs. Probability of Voluntary Bump Figure 2. Chebyshev weighting function for offer acceptance where U is a random uniform variable on [0, 1]. With a linear transformation from the Chebyshev domain [−1, 1] to the time interval [0, 30] via t = 15τ + 15, we find a random variable t that takes on values from 0 to 30 according to the density function f(s). Figure 3 shows the results of using this process to generate 100,000 time values. We use this random variable to assign times for compensation offer acceptance under the auction plan. The total cost of bumping(X−C)passengers isX−C i=1 Compensation(ti). Optimizing Overbooking Strategies Our goal is to maximize the expected value of the total profit function, E[TP (X)], given the variability of the bump function and the probabilistic passenger arrival model. There are competing dynamic effects at work in the total profit function. Ticket sales are desirable, but there is a point at which the cost of bumping becomes too great. Also, the variability of the number of passengers who show up affects the dynamics. The expected value of the total profit function is E[TP (X)] = B i=1 TP (i) B i pi (1 − p) B−i .
324 The UMAP Journal 23.3 (2002) Figure 3 Histogram of 100,000 draws from the Chebyshev distribution. We optimize the revenue by finding the most appropriate booking limit(B) for any bump function. Solving such a problem analytically is unrealistic;any solution would require the inversion of a sum of factorial functions. Therefore we turn to computation for our results. We wrote and tested MatLAB programs that solve for b over a range of trivial bump functions Results of static Model analysis No Overbooking If Frontier Airlines does not overbook its flights, it suffers a significant cost in terms of loss of opportunity. If the number of people that booked (B)equals plane capacity(C), the expected value of X (number of passengers who arrive at the gate)is pB=pC=.88 x 134 N 118 passengers. Assuming(as in the total profit function)that each passenger beyond the 78th is worth $300 in profit, the expected profit is nearly (134-118)×$60+$300×(118 812960 per flight. This is only an estimate, since a smaller or larger proportion than 57. 8% of ticket-holding passengers may arrive at the gate. The profit is sizeable but there are still (on average)16 empty seats The approximate lost opportu- 00×16=$4,800!Thus, not ov ng way with only 63% of its potential profitabilit
324 The UMAP Journal 23.3 (2002) 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 0.2 0.4 0.6 0.8 1 1.2 1.4 Time (minutes) Frequency Figure 3. Histogram of 100,000 draws from the Chebyshev distribution. We optimize the revenue by finding the most appropriate booking limit (B) for any bump function. Solving such a problem analytically is unrealistic; any solution would require the inversion of a sum of factorial functions. Therefore, we turn to computation for our results. We wrote and tested MatLAB programs that solve for B over a range of trivial bump Functions. Results of Static Model Analysis No Overbooking If Frontier Airlines does not overbook its flights, it suffers a significant cost in terms of loss of opportunity. If the number of people that booked (B) equals plane capacity (C), the expected value of X (number of passengers who arrive at the gate) is pB = pC = .88×134 ≈ 118 passengers. Assuming (as in the total profit function) that each passenger beyond the 78th is worth $300 in profit, the expected profit is nearly (134 − 118) × $60 + $300 × (118 − 78) = $12,960 per flight.This is only an estimate, since a smaller or larger proportion than 57.8% of ticket-holding passengers may arrive at the gate. The profit is sizeable but there are still (on average) 16 empty seats! The approximate lost opportunity cost is $300 × 16 = $4,800! Thus, not overbooking sends Flight 502 on its way with only 63% of its potential profitability