Probabilistically optimized Airline Overbooking Strategies 317 Probabilistically optimized airline Overbooking strategies, or Anyone Willing to Take a later Flight? Kevin z leder Saverio E. Spagniole Stefan m. wild University of Colorado Boulder, Co Advisor: Anne M. Dougherty Introduction We develop a series of mathematical models to investigate relationships between overbooking strategies and revenue Our first models are static, in the sense that passenger behavior is pre- dominantly time-independent; we use a binomial random variable to model consumer behavior. We construct an auction-style model for passenger com pensation. Our second set of models is more dynamic, employing Poisson processes for continuous time-dependence on ticket purchasing /cancelling information Finally, we consider the effects of the post-September 11 market on the in dustry. We consider a particular company and flight: Frontier Airlines Flight 502. Applying the models to revenue optimization leads to an optimal book ing limit of 15% over flight capacity and potentially nets Frontier Airlines an additional $2.7 million/year on Flight 502, given sufficient ticket demand Frontier Airlines: Company Overview Frontier Airlines, a discount airline and the second largest airline operating out of Denver International Airport(DIA), serves 25 cities in 18 states. Frontie offers two flights daily from DIA to LaGuardia Airport in New York. We focus on Flight 502 The UMAP Journal 317-338. Copyright 2002 by COMAP, Inc. All rights 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 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
Probabilistically Optimized Airline Overbooking Strategies 317 Probabilistically Optimized Airline Overbooking Strategies, or “Anyone Willing to Take a Later Flight?!” Kevin Z. Leder Saverio E. Spagniole Stefan M. Wild University of Colorado Boulder, CO Advisor: Anne M. Dougherty Introduction We develop a series of mathematical models to investigate relationships between overbooking strategies and revenue. Our first models are static, in the sense that passenger behavior is predominantly time-independent; we use a binomial random variable to model consumer behavior. We construct an auction-style model for passenger compensation. Our second set of models is more dynamic, employing Poisson processes for continuous time-dependence on ticket purchasing/cancelling information. Finally, we consider the effects of the post-September 11 market on the industry. We consider a particular company and flight: Frontier Airlines Flight 502. Applying the models to revenue optimization leads to an optimal booking limit of 15% over flight capacity and potentially nets Frontier Airlines an additional $2.7 million/year on Flight 502, given sufficient ticket demand. Frontier Airlines: Company Overview Frontier Airlines, a discount airline and the second largest airline operating out of Denver International Airport (DIA), serves 25 cities in 18 states. Frontier offers two flights daily from DIA to LaGuardia Airport in New York. We focus on Flight 502. The UMAP Journal 317–338. 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
318 The UMAP Journal 23.3 (2002) Technical Considerations and details We discuss regulations for handling bumped passengers, airplane specifi cations, and financial interests Overbooking Regulations When overbooking results in overflow, the department of Transportation (DOT)requires airlines to ask for volunteers willing to be bumped in exchange for compensation. However, the dot does not specify how much compen- sation the airlines must give to volunteers; in other words, negotiations and auctions may be held at the gate until the flight's departure. A passenger who is bumped involuntarily is entitled to the following compensation If the airline arranges substitute transportation such that the passenger will reach his/her destination within one hour of the original flight's arrival time, there is no obligatory compensation If the airline arranges substitute transportation such that the passenger will reach his/her destination between one and two hours after the original flights arrival time, the airline must pay the passenger an amount equal to the one-way fare for flight to the final destination If the substitute transportation is scheduled to arrive any later than two hours after the original flight's arrival time, or if the airline does not make any substitute travel arrangements, the airline must pay an amount equal te twice the cost of the fare to the final destination Aircraft Information Frontier offers only one class of service to all passengers. Thus, we base our overbooking models on single-class aircraft Financial Considerations Airline booking considerations are frequently based on the break-even load factor, a percentage of airplane seat capacity thatmust be filled to acquire neither loss or profit on a particular flight. The break-even load-factor for Flight 502 in 57.8% Assumptions We need concern ourselves only with the sale of restricted tickets. Fron- tiers are nonrefundable, save for the ability to transfer to another Frontier flight for $60 [ Frontier 2001]. Restricted tickets t all but percentage of all tickets, and many ticket brokers, such as Priceline. com, sell only restricted tickets
318 The UMAP Journal 23.3 (2002) Technical Considerations and Details We discuss regulations for handling bumped passengers, airplane specifi- cations, and financial interests. Overbooking Regulations When overbooking results in overflow, the Department of Transportation (DOT) requires airlines to ask for volunteers willing to be bumped in exchange for compensation. However, the DOT does not specify how much compensation the airlines must give to volunteers; in other words, negotiations and auctions may be held at the gate until the flight’s departure. A passenger who is bumped involuntarily is entitled to the following compensation: • If the airline arranges substitute transportation such that the passenger will reach his/her destination within one hour of the original flight’s arrival time, there is no obligatory compensation. • If the airline arranges substitute transportation such that the passenger will reach his/her destination between one and two hours after the original flight’s arrival time, the airline must pay the passenger an amount equal to the one-way fare for flight to the final destination. • If the substitute transportation is scheduled to arrive any later than two hours after the original flight’s arrival time, or if the airline does not make any substitute travel arrangements, the airline must pay an amount equal to twice the cost of the fare to the final destination. Aircraft Information Frontier offers only one class of service to all passengers. Thus, we base our overbooking models on single-class aircraft. Financial Considerations Airline booking considerations are frequently based on the break-even loadfactor, a percentage of airplane seat capacity that must be filled to acquire neither loss or profit on a particular flight. The break-even load-factor for Flight 502 in 2001 was 57.8%. Assumptions • We need concern ourselves only with the sale of restricted tickets. Frontier’s are nonrefundable, save for the ability to transfer to another Frontier flight for $60 [Frontier 2001]. Restricted tickets represent all but a very small percentage of all tickets, and many ticket brokers, such as Priceline.com, sell only restricted tickets
Probabilistically optimized Airline Overbooking Strategies 319 Ticketholders who dont show up at the gate spend $60 to transfer to an- other Bumped passengers from morning Flight 502 are placed, at the latest, 4 h 35 min later on Frontier's afternoon Flight 513 to the same destinatio Frontier Airlines first attempts to place bumped passengers on othe lines flights to the same destination. If it cant do so, Frontier bumps other passengers from the later Frontier flight to make room for the originally umD P The annual effects/costs associated with bumping involuntary passengers is negligible in comparison to the annual effects/costs of bumping volun- tary passengers. According to statistics provided by the department of Transportation, 4% of all airline passengers are bumped voluntarily, while only 1.06 passengers in 10,000 are bumped involuntarily. With a maximum delay for bumped passengers of 4 h 35 min, the average annual cost te Frontier of bumping involuntary passengers is on the order of $100,000- negligible compared to costs of bumping voluntary passengers The static model Our first model for optimizing revenues is static, in the sense that passenger behavior is predominantly time-independent: All passengers(save no-shows arrive at the departure gate independently. This model does not account for when passengers purchase their tickets. This system may be modeled by the folle Introduce a binomial random variable for the number of passengers who show up for the flight Define a total profit function dependent upon this random variable apply this function to various consumer behavior patterns Compute(for each behavioral pattern) an optimal number of passengers to A Binomial random Variable Approach We let the binomial random variable x be the number of ticketholders who arrive at the gate after B tickets have been sold; thus, X N Binomial(B, p) Numerous airlines consistently report that approximately 12% of all booked rs do not show up to the gate(d [Lufthansa 2000, so we take Pri at the gate)= Pr(x=il p2(1-p)
Probabilistically Optimized Airline Overbooking Strategies 319 • Ticketholders who don’t show up at the gate spend $60 to transfer to another flight. • Bumped passengers from morning Flight 502 are placed, at the latest,4h 35 min later on Frontier’s afternoon Flight 513 to the same destination. Frontier Airlines first attempts to place bumped passengers on other airlines’ flights to the same destination. If it can’t do so, Frontier bumps other passengers from the later Frontier flight to make room for the originally bumped passengers. • The annual effects/costs associated with bumping involuntary passengers is negligible in comparison to the annual effects/costs of bumping voluntary passengers. According to statistics provided by the Department of Transportation, 4% of all airline passengers are bumped voluntarily, while only 1.06 passengers in 10,000 are bumped involuntarily. With a maximum delay for bumped passengers of 4 h 35 min, the average annual cost to Frontier of bumping involuntary passengers is on the order of $100,000— negligible compared to costs of bumping voluntary passengers. The Static Model Our first model for optimizing revenues is static, in the sense that passenger behavior is predominantly time-independent: All passengers (save no-shows) arrive at the departure gate independently. This model does not account for when passengers purchase their tickets. This system may be modeled by the following steps: • Introduce a binomial random variable for the number of passengers who show up for the flight. • Define a total profit function dependent upon this random variable. • Apply this function to various consumer behavior patterns. • Compute (for each behavioral pattern) an optimal number of passengers to overbook. A Binomial Random Variable Approach We let the binomial random variable X be the number of ticketholders who arrive at the gate after B tickets have been sold; thus, X ∼ Binomial(B,p). Numerous airlines consistently report that approximately 12% of all booked passengers do not show up to the gate (due to cancellations and no-shows) [Lufthansa 2000], so we take p = .88. Pr{i passengers arrive at the gate} = Pr{X = i} = B i pi (1 − p) B−i .
320 The UMAP Journal 23.3(2002) Modeling revenue We define the following per-flight total profit function and subsequently present a detailed explanation Tp(X)=(B-X)R+ Airfare x X-Costelight X≤C Airfare-CostAdd X(X-Cs CC, where R= transfer fee for no-shows and cancellations b= total number of passengers booked Airfare= a constant CostElight=total operating cost of flying the plane CostAdd= cost to place one passenger on the flight Bump= the Bump function(to be defined) Cs =number of passengers required to break even on the flight C a the full capacity of the plane(number of seats) For Airfare, we use the average cost of restricted-ticket fare over a one-week period in 2002: $316. CostFlight is based on the break-even load-factor of 57.8% for Flight 502, we take CostFlight=$24, 648 [Frontier Airlines 2001]. The average cost associated with placing one passenger on the plane is CostAdd N $16. The break-even occupancy is determined from the break-even load-factor; since Flight 502 uses an Airbus A319 with 134 seats, we take C= 134 and Cs=78 The Bump function We consider various overbooking strategies, the last three of which translate irectly into various Bump functions No Overbooking Bump Threshold Model We assign a"Bump Threshold"(BT)to each flight, a probability of having to bump one or more customers from a flight given B and p: Pr(X >flight capacity)< BT
320 The UMAP Journal 23.3 (2002) Modeling Revenue We define the following per-flight total profit function and subsequently present a detailed explanation. Tp(X) =(B − X)R + Airfare × X − CostFlight, X ≤ C¯$; Airfare-CostAdd × (X − C¯$), C¯$ C, where R = transfer fee for no-shows and cancellations, B = total number of passengers booked, Airfare = a constant CostFlight = total operating cost of flying the plane CostAdd = cost to place one passenger on the flight Bump = the Bump function (to be defined) C¯$ = number of passengers required to break even on the flight C = the full capacity of the plane (number of seats) For Airfare, we use the average cost of restricted-ticket fare over a one-week period in 2002: $316. CostFlight is based on the break-even load-factor of 57.8%; for Flight 502, we take CostFlight = $24,648 [Frontier Airlines 2001]. The average cost associated with placing one passenger on the plane is CostAdd ≈ $16. The break-even occupancy is determined from the break-even load-factor; since Flight 502 uses an Airbus A319 with 134 seats, we take C = 134 and C¯$ = 78. The Bump Function We consider various overbooking strategies, the last three of which translate directly into various Bump functions. • No Overbooking • Bump Threshold Model We assign a “Bump Threshold” (BT) to each flight, a probability of having to bump one or more customers from a flight given B and p: Pr{X > flight capacity} < BT
Probabilistically optimized Airline Overbooking Strategies 321 We take bT= 5%of flight capacity. The probability that more than N ticket- holders arrive at the gate, given B tickets sold, is P{x>N}=1-P{≤N}=1-∑(2)(1-p) This simplistic model is independent of revenue and produces(through simpleiteration) an optimal number of ticket sales(B)forexpecting bumping to occur on less than 5% of flights e Linear Compensation Plan This plan assumes that there is a fixed cost asso- ciated with bumping a passenger, the same for each passenger. The related p function is (X-C)=Bs×(X-C) where(X-C)is the number of bumped passengers and Bs is the cost of handling each Nonlinear Compensation Plan Steeper penalties must be considered, since there is a chain reaction of expenses incurred when bumping passengers from one flight causes future bumps on later flights. Here we assume that the Bump function is exponential. Assuming that flight vouchers are still adequate compensation at an average cost of 2* Airfare+$100=$732 when there are 20 bumped passengers, we apply the cost equation L (X-C)=Bs(X-C)e where Bs is the ompensation constant and r=r(Bs)is the exponential rate, chosen to fit the curve to the points(0, 316) and(20, 732 Time-Dependent Compensation Plan(Auction) The primary shortcoming of the nonlinear compensation plan is that it does not deal with flights with too few voluntarily bumped passengers, where the airline must increase its compensation offering. We now approximate the costs of an auction-type This plan assumes that the airline knows the number of no-shows and can- cellations one-half hour prior to departure. The following auction system is employed. At 30 min before departure, the airline offers flight vouchers to volunteers willing to be bumped equivalent in cost to the original airfare This offer stands for 15 min, at which time the offer increases exponentially up to the equivalent of $948 by departure time. We chose this number as twice the original airfare(which is the maximum obligatory compensatio for involuntary passengers if they are forced to wait more than 2 h), plus one more airfare costin the hope that treating the customers so favorably will result in future business from the same customers. These specifications
Probabilistically Optimized Airline Overbooking Strategies 321 We take BT = 5% of flight capacity. The probability that more than N ticketholders arrive at the gate, given B tickets sold, is Pr{X>N} = 1 − Pr{X ≤ N} = 1 − N i=1 B i pi (1 − p) B−i . This simplistic model is independent of revenue and produces (through simple iteration) an optimal number of ticket sales (B) for expecting bumping to occur on less than 5% of flights. • Linear Compensation Plan This plan assumes that there is a fixed cost associated with bumping a passenger, the same for each passenger. The related Bump function is Bump(X − C) = B$ × (X − C), where (X − C) is the number of bumped passengers and B$ is the cost of handling each. • Nonlinear Compensation Plan Steeper penalties must be considered, since there is a chain reaction of expenses incurred when bumping passengers from one flight causes future bumps on later flights. Here we assume that the Bump function is exponential. Assuming that flight vouchers are still adequate compensation at an average cost of 2 ∗Airfare+$100 = $732 when there are 20 bumped passengers, we apply the cost equation BumpNL(X − C) = B$(X − C)er(X−C) , where B$ is the ompensation constant and r = r(B$) is the exponential rate, chosen to fit the curve to the points (0, 316) and (20, 732). • Time-Dependent Compensation Plan (Auction) The primary shortcoming of the nonlinear compensation plan is that it does not deal with flights with too few voluntarily bumped passengers, where the airline must increase its compensation offering. We now approximate the costs of an auction-type compensation plan. This plan assumes that the airline knows the number of no-shows and cancellations one-half hour prior to departure. The following auction system is employed. At 30 min before departure, the airline offers flight vouchers to volunteers willing to be bumped, equivalent in cost to the original airfare. This offer stands for 15 min, at which time the offer increases exponentially up to the equivalent of $948 by departure time. We chose this number as twice the original airfare (which is the maximum obligatory compensation for involuntary passengers if they are forced to wait more than 2 h), plus one more airfare costin the hope that treating the customers so favorably will result in future business from the same customers. These specifications
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
Probabilistically optimized Airline Overbooking Strategies 325 Bump Threshold model Using a 0.05 bump threshold, we compute an optimal number of passengers to book on Flight 502. Given the Airbus A319 capacity of 134 passengers and a passenger arrival probability of p= 88, the optimal number of tickets to sell to guarantee that bumping occurs less than 5% of the time is B=145, or 107% of flight capacity Linear Compensation plan Table 1 shows th rofit for various linear bump functions Table 1 Linear bump functions compared Bump cost Optimal #f Expected profit Per passenger to book per flig 316 $17817 400 151 $16799 800 151 $16,692 150 16601 1000 $16526 If Frontier were to compensate bumped passengers less than the cost of airfare, bumping passengers would always cost less than revenue gained from ticket sales. Thus, assuming it could sell as many tickets as it wanted, Frontier would realize an unbounded profit on each flight! Obviously, the linear com- pensation plan is not realistic in this regime, and we must wait for subsequent models to see increased real-world applicability. These results agree with the result of using a simple bump threshold above and indicate an average profit of approximately $17,000. In comparison with using no overbooking strategy at all, Frontier gains additional profit of $4,000 per flight! The actual dynamics of the problem may be seen in Figure 4, where compet- ng effects form an optimal number of tickets to sell(B)when Frontier assumes a sizeable enough compensation average. We can also see the unbounded profit available in the unrealistic regime Nonlinear Compensation Plan Numerical results for the more realistic nonlinear model paint a more rea- sonable picture Table 2 recommends booking limmits similar to(though slightly higher than) previous models. The dynamics may be seen in the Figure 5
Probabilistically Optimized Airline Overbooking Strategies 325 Bump Threshold Model Using a 0.05 bump threshold, we compute an optimal number of passengers to book on Flight 502. Given the Airbus A319 capacity of 134 passengers and a passenger arrival probability of p = .88, the optimal number of tickets to sell to guarantee that bumping occurs less than 5% of the time is B = 145, or 107% of flight capacity. Linear Compensation Plan Table 1 shows the expected profit for various linear bump functions. Table 1. Linear bump functions compared. Bump cost Optimal # Expected profit per passenger to book per flight 200 ∞ ∞ 316 162 $17,817 400 156 $17,394 500 153 $17,121 600 152 $16,940 700 151 $16,799 800 151 $16,692 900 150 $16,601 1000 150 $16,526 If Frontier were to compensate bumped passengers less than the cost of airfare, bumping passengers would always cost less than revenue gained from ticket sales. Thus, assuming it could sell as many tickets as it wanted, Frontier would realize an unbounded profit on each flight! Obviously, the linear compensation plan is not realistic in this regime, and we must wait for subsequent models to see increased real-world applicability. These results agree with the result of using a simple bump threshold above and indicate an average profit of approximately $17,000. In comparison with using no overbooking strategy at all, Frontier gains additional profit of $4,000 per flight! The actual dynamics of the problem may be seen in Figure 4, where competing effects form an optimal number of tickets to sell (B) when Frontier assumes a sizeable enough compensation average. We can also see the unbounded profit available in the unrealistic regime. Nonlinear Compensation Plan Numerical results for the more realistic nonlinear model paint a more reasonable picture. Table 2 recommends booking limmits similar to (though slightly higher than) previous models. The dynamics may be seen in the Figure 5
326 The UMAP Journal 23.3 (2002) t Figure 4. Per-flight profit vs. booking limit(B)for different bump costs(Linear Compensation Table 2 Nonlinear bump functions compared timal number Profit $18700 100c01000-c)(X-C) $18240 200e000(X-)(X-C) $17722 316e0042(X-0)(X-C) 154 $17363 All nonlinear bump functions that we investigated result in a maximum realizable profit, as expected Time-Dependent Compensation Plan The histogram of 1,000 runs using the time-dependent compensation plan in Figure 6 shows that the optimal booking limit is most frequently B= 154 Figure 7 is a graph of expected total profit versus the optimal booking limit for 15 trials, displaying the randomness due to the Chebyshev draws at higher values of B. If B is too low, then all models have the same profit behavior, because the randomness from the overbooking scheme is not introduced un- til customers are bumped. This graph also shows that regardless of random
326 The UMAP Journal 23.3 (2002) 135 140 145 150 155 160 165 170 175 180 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2 x 104 Booking Limit (B) Profit ($) B$ =200 B$ =316 B$ =500 Figure 4. Per-flight profit vs. booking limit (B) for different bump costs (Linear Compensation Plan) Table 2. Nonlinear bump functions compared. Bump function Optimal number Profit to book per flight 50e0.134(X−C)(X − C) 160 $18,700 100e0.100(X−C)(X − C) 158 $18,240 200e0.065(X−C)(X − C) 156 $17,722 316e0.042(X−C)(X − C) 154 $17,363 All nonlinear bump functions that we investigated result in a maximum realizable profit, as expected. Time-Dependent Compensation Plan The histogram of 1,000 runs using the time-dependent compensation plan in Figure 6 shows that the optimal booking limit is most frequently B = 154. Figure 7 is a graph of expected total profit versus the optimal booking limit for 15 trials, displaying the randomness due to the Chebyshev draws at higher values of B. If B is too low, then all models have the same profit behavior, because the randomness from the overbooking scheme is not introduced until customers are bumped. This graph also shows that regardless of random