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 C<X≤C; Airfare-CostAdd X(X-Cs)-Bump(X-C,X>C, 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¯$ < X ≤ C; Airfare-CostAdd × (X − C¯$) − Bump(X − C), X>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