Optimal Overbooking 283 Optimal Overbooking David arthur Sam malone Oaz nir Duke University Advisor: David Kraines Introduction We construct several models to examine the effect of overbooking policies on airline revenue and costs in light of the current state of the industry, including fewer flights, increased security, passengers' fear, and billions in lc Using a plausible average ticket price, we model the waiting-time distribu tion for flights and estimate the average cost per involuntarily bumped pas- senger For ticketholders bumped voluntarily, the interaction between the airline and ticketholders takes the form of a least-bid auction in which winners receive compensation for foregoing their flights. We discuss the precedent for this type of auction and introduce a highly similar continuous auction model that allows us to calculate a novel formula for the expected compensation required Our One-Plane Model models expected revenue as a function of overbook ing policy for a single plane. Using this framework, we examined the relation- ship between the optimal(revenue-maximizing)overbooking strategy and the arrival probability for ticketholders. We extend the model to consider multiple fare classes; doing so does not significantly alter optimal overbooking policy. Our Interactive Simulation Model takes into account estimates for average compensation costs. It simulates the interaction between 10 major U.S. airlines with a market base of 10,000 people, factoring in passenger arrival probability flight frequency, compensation for bumping, and the behavior of rival airlines Thus, we estimate optimal booking policy in a competitive environment. Simu- lations of this model with likely parameter values before and after September 11 gives robust results that corroborate the conclusions of the One-Plane Model and the compensation- cost formula The UMAP Journal 23(3)(2002)283-300. 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
Optimal Overbooking 283 Optimal Overbooking David Arthur Sam Malone Oaz Nir Duke University Durham, NC Advisor: David Kraines Introduction We construct several models to examine the effect of overbooking policies on airline revenue and costs in light of the current state of the industry, including fewer flights, increased security, passengers’ fear, and billions in losses. Using a plausible average ticket price, we model the waiting-time distribution for flights and estimate the average cost per involuntarily bumped passenger. For ticketholders bumped voluntarily, the interaction between the airline and ticketholders takes the form of a least-bid auction in which winners receive compensation for foregoing their flights. We discuss the precedent for this type of auction and introduce a highly similar continuous auction model that allows us to calculate a novel formula for the expected compensation required. Our One-Plane Model models expected revenue as a function of overbooking policy for a single plane. Using this framework, we examined the relationship between the optimal (revenue-maximizing) overbooking strategy and the arrival probability for ticketholders. We extend the model to consider multiple fare classes; doing so does not significantly alter optimal overbooking policy. Our Interactive Simulation Model takes into account estimates for average compensation costs. It simulates the interaction between 10 major U.S. airlines with a market base of 10,000 people, factoring in passenger arrival probability, flight frequency, compensation for bumping, and the behavior of rival airlines. Thus, we estimate optimal booking policy in a competitive environment. Simulations of this model with likely parameter values before and after September 11 gives robust results that corroborate the conclusions of the One-Plane Model and the compensation-cost formula. The UMAP Journal 23 (3) (2002) 283–300. 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
284 The UMAP Journal 23.3 (2002) Overall, we conclude that airlines should maintain or decrease their current levels of overbooking Terms Ticketholders: People who purchased a ticket Contenders: Ticketholders who arrive in time to board their flight. Boarded passengers: Contenders who board successfully. Bumped passengers: Contenders who are not given seating on their flight Voluntarily bumped passengers: Bumped passengers who opt out of their seating in exchange for compensation. Involuntarily bumped passengers: Bumped passengers who are denied boarding against their will Compensation costs The total value of money and other incentives given to bumped passengers Flight Capacity: The number of seats on a flight Overbooking: The practice of selling more tickets that flight capacity Waiting time: The time that a bumped passenger would have to wait for the next flight to the destination Load factor: The ratio of the number of seats filled to the capacity Assumptions and Hypotheses Flights are domestic, direct, and one-way. departure time of the next available flight to a given destination Scheduled The waiting time between flights is the amount of time until the The ticket price is $140 [Airline Transport Association 2002, independent of when the ticket is bought, except when we consider multiple fares Pre-September 11, the average probability of a ticketholder checking in for the flight (and thus becoming a contender)was 85%[Smith et al. 1992, 9 The pre-September 11 average load factor was 72%[Bureau of Transportation Statistics 2000
284 The UMAP Journal 23.3 (2002) Overall, we conclude that airlines should maintain or decrease their current levels of overbooking. Terms • Ticketholders: People who purchased a ticket. • Contenders: Ticketholders who arrive in time to board their flight. • Boarded passengers: Contenders who board successfully. • Bumped passengers: Contenders who are not given seating on their flight. • Voluntarily bumped passengers: Bumped passengers who opt out of their seating in exchange for compensation. • Involuntarily bumped passengers: Bumped passengers who are denied boarding against their will. • Compensation costs: The total value of money and other incentives given to bumped passengers. • Flight Capacity: The number of seats on a flight. • Overbooking: The practice of selling more tickets that flight capacity. • Waiting time: The time that a bumped passenger would have to wait for the next flight to the destination. • Load factor: The ratio of the number of seats filled to the capacity. Assumptions and Hypotheses • Flights are domestic, direct, and one-way. • The waiting time between flights is the amount of time until the scheduled departure time of the next available flight to a given destination. • The ticket price is $140 [Airline Transport Association 2002], independent of when the ticket is bought, except when we consider multiple fares. • Pre-September 11, the average probability of a ticketholder checking in for the flight (and thus becoming a contender) was 85% [Smith et al. 1992, 9]. • The pre-September 11 average load factor was 72% [Bureau of Transportation Statistics 2000]
Optimal Overbooking 285 Complicating Factors Each of our models attempts to take into account the current situation facing irlines The traffic Factor On average, there are fewer flights by airlines between any given locations The Security Factor ecurity in and around airports has been heightened e The fear factor Passengers are more wary of the dangers of air travel, such as possible ter rorist attacks, plane crashes, and security breaches at airports . The financial Loss factor Airlines have lost billions of dollars in revenue due to decreased demand for air travel, increased security costs and increased industry risks The Traffic Factor Because there are fewer flights, it is likely that the demand for any given flight will increase. Flights are likely to be fuller; the average waiting time between flights to a destination is likely to increase, so bumped passengers will demand higher compensation The security Factor The increase in security will likely lead to an increase in the number of ticketholders who arrive at the airport but- due to security delays- do not arrive at their departure gates in time Successful implementation of security measures may lead to an improve- ment in the public perception of the airline industry and an increase in demand for air travel The Fear Factor Increased fear of flying decreases demand for air travel, so security delays may not be as serious On the other hand, if a higher percentage of ticketholders are flying out of necessity, then the probability that a ticketholder becomes a contender may increase because of decreased cancellations and no-shows. However, fewer ticketholders are likely to agree to be bumped voluntarily at any price, so the percentage of involuntarily bumped passengers may increase
Optimal Overbooking 285 Complicating Factors Each of our models attempts to take into account the current situation facing airlines: • The Traffic Factor On average, there are fewer flights by airlines between any given locations. • The Security Factor Security in and around airports has been heightened. • The Fear Factor Passengers are more wary of the dangers of air travel, such as possible terrorist attacks, plane crashes, and security breaches at airports. • The Financial Loss Factor Airlines have lost billions of dollars in revenue due to decreased demand for air travel, increased security costs, and increased industry risks. The Traffic Factor Because there are fewer flights, it is likely that the demand for any given flight will increase. Flights are likely to be fuller; the average waiting time between flights to a destination is likely to increase, so bumped passengers will demand higher compensation. The Security Factor The increase in security will likely lead to an increase in the number of ticketholders who arrive at the airport but—due to security delays—do not arrive at their departure gates in time. Successful implementation of security measures may lead to an improvement in the public perception of the airline industry and an increase in demand for air travel. The Fear Factor Increased fear of flying decreases demand for air travel, so security delays may not be as serious. On the other hand, if a higher percentage of ticketholders are flying out of necessity, then the probability that a ticketholder becomes a contender may increase because of decreased cancellations and no-shows. However, fewer ticketholders are likely to agree to be bumped voluntarily at any price, so the percentage of involuntarily bumped passengers may increase
286 The UMAP Journal 23.3(2002) The financial loss factor Because companies may seek to increase short-term profits in the face of re- cent losses, some airlines may implement more aggressive overbooking, which could induce an overbooking war between airlines [Suzuki 2002, 148]. The likely increase in the number of bumped passengers would lead to a rise in compensation costs that would partially offset increased revenue Decreasing the number of bumped passengers would improve the airlines image and might spur demand, which would bolster future revenue One-Plane model Introduction and motivation We first consider the optimal overbooking strategy for a single flight, in- dependent of all other flights. We will see later that its results are a good approximation to the results of the full-fledged Interaction Simulation Model Development Let the plane have a capacity of C identical seats and let a ticket costT=$140 ndependent of when it is bought. Let the airline's overbooking strategy be to sell up to B tickets, if possible(B>C). We analyze this strategy in the case when all b tickets are sold We model the number of contenders for the flight with a binomial distribu tion,where a ticketholder becomes a contender with probability p. The average p for flights from the ten leading U.S. carriers 0.85 [Smith et al. 1992 The value of p for a particular flight depends on a host of factors-flight time length, destination, whether it is a holiday season--so we carry out our analysis for a range of possible p values With our binomial model, the probability of exactly i contenders among the B ticket-holders is p (1-p)B-i We assi at each bumped d passenger is pa tion(1+kT= 140(1+k), for some constant k. Translated into everyday terms, this means that a bumped passenger receives compensation equal to the ticket price T plus some additional compensation kT>0. Later, we relax the assumption that compensation cost is the same for each passenger, when we consider in voluntary vs voluntary bumping We define the compensation cost function F(i, C)to be the total comp sation the airline must pay if there are exactly i contenders for a flight with seating capacity C <C: (k+1)T(i-C)
286 The UMAP Journal 23.3 (2002) The Financial Loss Factor Because companies may seek to increase short-term profits in the face of recent losses, some airlines may implement more aggressive overbooking, which could induce an overbooking war between airlines [Suzuki 2002, 148]. The likely increase in the number of bumped passengers would lead to a rise in compensation costs that would partially offset increased revenue. Decreasing the number of bumped passengers would improve the airlines’ image and might spur demand, which would bolster future revenue. One-Plane Model Introduction and Motivation We first consider the optimal overbooking strategy for a single flight, independent of all other flights. We will see later that its results are a good approximation to the results of the full-fledged Interaction Simulation Model. Development Let the plane have a capacity ofC identical seats and let a ticket costT = $140 independent of when it is bought. Let the airline’s overbooking strategy be to sell up to B tickets, if possible (B>C). We analyze this strategy in the case when all B tickets are sold. We model the number of contenders for the flight with a binomial distribution, where a ticketholder becomes a contender with probability p. The average p for flights from the ten leading U.S. carriers is p = 0.85 [Smith et al. 1992]. The value of p for a particular flight depends on a host of factors—flight time, length, destination, whether it is a holiday season—so we carry out our analysis for a range of possible p values. With our binomial model, the probability of exactly i contenders among the B ticket-holders is B i pi (1 − p)B−i . We assume that each bumped passenger is paid compensation (1 + k)T = 140(1 + k), for some constant k. Translated into everyday terms, this means that a bumped passenger receives compensation equal to the ticket price T plus some additional compensation kT > 0. Later, we relax the assumption that compensation cost is the same for each passenger, when we consider involuntary vs. voluntary bumping. We define the compensation cost function F(i, C) to be the total compensation the airline must pay if there are exactly i contenders for a flight with seating capacity C: F(i, C) = 0, i ≤ C; (k + 1)T(i − C), i > C.
Optimal Overbooking 287 We calculate expected revenue R as a function of B R(B) p(1-p)-(BT-F(i, C)) i=1( =140B-140(k+1) p2(1-p) B-i We use a computer program to determine, for given C, p, and k, the over- booking strategy Bopt that maximizes R(B). However, it is also possible to produce a close analytic approximation, which we now derive revenue for a bumped passenger, T-(k+ as ma gnitude k times that for a boarded passenger, T. Thus, the optimal overbooking strategy is such that the distribution of contenders is in some sense"balanced with 1/(k+1)of its area corresponding to bumped passengers and the remaining k/(k+1)corresponding to boarded passengers We approximate the binomial distribution of contenders with a normal dis tribution ≈更 Bp(1-p) where is the cumulative distribution function of the standard normal dis tribution.Clearing denominators and solving the resulting quadratic in VB 1()vm一可+√(P1-D+4C 2p as an analytic approximation to Bopt For k=l, we get BoDt=c/p This analytic approximation is always within 1 of the optimal overbooking strategy for.80≤p≤90andl≤k≤3 Results and interpretation The airline should be able to obtain good approximations to p and k empir- ically. Thus, it can take our computer program, insert its data for C, T, p, and k, and obtain the optimal overbooking strategy Bopt. Figure 1 plots expected revenue R(B)vS BC=150, k=1, p=0.85, and T= 140 AtB= 177, the airline can expect revenue R(177)=$24, 200, which is than 15% in excess of the expected revenue R(150)=$21, 000 from a policy of no overbooking Operating at a less-than-optimal overbooking strategy can have serious consequences. For example, American Airlines has an annual revenue of $20 billion [AMR Corporation 2000]. An overbooking policy b outside the range of 173, 183 implies an expected loss of more than $1 billion over a 5-year period compared with the expected revenue at Bopt=177
Optimal Overbooking 287 We calculate expected revenue R as a function of B: R(B) = B i=1 B i pi (1 − p) B−i (BT − F(i, C)) = 140B − 140(k + 1) B i=C+1 B i pi (1 − p) B−i (i − C) We use a computer program to determine, for given C, p, and k, the overbooking strategy Bopt that maximizes R(B). However, it is also possible to produce a close analytic approximation, which we now derive. The revenue for a bumped passenger, T −(k+1)T = −kT, has magnitude k times that for a boarded passenger, T. Thus, the optimal overbooking strategy is such that the distribution of contenders is in some sense “balanced,” with 1/(k + 1) of its area corresponding to bumped passengers and the remaining k/(k + 1) corresponding to boarded passengers. We approximate the binomial distribution of contenders with a normal distribution: C − Bp Bp(1 − p) ≈ Φ−1 k k + 1 , where Φ is the cumulative distribution function of the standard normal distribution. Clearing denominators and solving the resulting quadratic in √ B gives B opt = −Φ−1 k k+1 p(1 − p) + Φ−1( k k+1 )2p(1 − p)+4pC 2p 2 (1) as an analytic approximation to Bopt. For k = 1, we get B opt = C/p. This analytic approximation is always within 1 of the optimal overbooking strategy for .80 ≤ p ≤ .90 and 1 ≤ k ≤ 3. Results and Interpretation The airline should be able to obtain good approximations to p and k empirically. Thus, it can take our computer program, insert its data for C, T, p, and k, and obtain the optimal overbooking strategy Bopt. Figure 1 plots expected revenue R(B) vs. B C = 150, k = 1, p = 0.85, and T = 140. At B = 177, the airline can expect revenue R(177) = $24, 200, which is more than 15% in excess of the expected revenue R(150) = $21, 000 from a policy of no overbooking. Operating at a less-than-optimal overbooking strategy can have serious consequences. For example, American Airlines has an annual revenue of $20 billion [AMR Corporation 2000]. An overbooking policy B outside the range of [173, 183] implies an expected loss of more than $1 billion over a 5-year period compared with the expected revenue at Bopt = 177.
288 The UMAP Journal 23.3(2002) Revenue vs. Tickets sold 24000 23500 23000 21000 17o 190 200 210 Figure 1. Revenue R vs overbooking strategy B for C= 150, k= l, p=0.85, and T=$140 Limitations The single-plane model fails to account for bumped passengers general dissatisfaction and propen sity to switch airlines assumes a simple constant-cost compensation function for bumped passen ignores the distinction between voluntary and involuntary bumping assumes that all tickets are identical-that is, everyone flies coach assumes that all b tickets that the airline is willing to sell are actually sold Even so, the model successfully analyzes revenue as a function of over- booking strategy plane capacity, the probability that ticket-holders become contenders, and compensation cost. Later, we develop a more complete model. The Complicating Factors First, though, we use the basic model to make preliminary predictions fo the optimal overbooking strategy in light of market changes due to the com- plicating factors post-September 11
288 The UMAP Journal 23.3 (2002) Revenue vs. Tickets Sold 21000 21500 22000 22500 23000 23500 24000 Revenue 150 160 170 180 190 200 210 Tickets (#) Figure 1. Revenue R vs. overbooking strategy B for C = 150, k = 1, p = 0.85, and T = $140. Limitations The single-plane model • fails to account for bumped passengers’ general dissatisfaction and propensity to switch airlines; • assumes a simple constant-cost compensation function for bumped passengers; • ignores the distinction between voluntary and involuntary bumping; • assumes that all tickets are identical—that is, everyone flies coach; • assumes that all B tickets that the airline is willing to sell are actually sold. Even so, the model successfully analyzes revenue as a function of overbooking strategy, plane capacity, the probability that ticket-holders become contenders, and compensation cost. Later, we develop a more complete model. The Complicating Factors First, though, we use the basic model to make preliminary predictions for the optimal overbooking strategy in light of market changes due to the complicating factors post-September 11
Optimal Overbooking 289 Of the four complicating factors, only two are directly relevant to this model the security factor and the fear factor. The primary effect of the security factor is to decrease the probability p of a ticketholder reaching the gate on time and becoming a contender. On the other hand, the primary effect of the fear factor is that a greater proportion of those who fly do so out of necessity; since such passengers are more likely to arrive for their flights than more casual flyers, the fear factor tends to increase p Figure 2 plots the optimal overbooking strategy Bopt VS. p for fixed k=1 and C= 150 Optimal Ticket sales vs. Show-up Probability Probability(p) Figure 2. Optimal overbooking strategy vs arrival probability p It is difficult to assess the precise change in p resulting from the securit and fear factors. However, airlines can determine this empirically by gathering statistics on their flights, then use our graph or computer program to determine a new optimal overbooking strategy. One-Plane model: Multifare extension Introduction and motivation Most airlines sell tickets in different fare classes(most commonly first class and coach). We extend the basic One-Plane Model to account for multiple fare classes Development For simplicity, we consider a two-fare system, with C1 first-class seats and C2 coach seats. We assume that a first-class ticket costs Ti= $280 and that
Optimal Overbooking 289 Of the four complicating factors, only two are directly relevant to this model: the security factor and the fear factor. The primary effect of the security factor is to decrease the probability p of a ticketholder reaching the gate on time and becoming a contender. On the other hand, the primary effect of the fear factor is that a greater proportion of those who fly do so out of necessity; since such passengers are more likely to arrive for their flights than more casual flyers, the fear factor tends to increase p. Figure 2 plots the optimal overbooking strategy Bopt vs. p for fixed k = 1 and C = 150. Optimal Ticket Sales vs. Show-up Probability 150 160 170 180 B_optimal 0.8 0.85 0.9 0.95 1 Probability (p) Figure 2. Optimal overbooking strategy vs. arrival probability p. It is difficult to assess the precise change in p resulting from the security and fear factors. However, airlines can determine this empirically by gathering statistics on their flights, then use our graph or computer program to determine a new optimal overbooking strategy. One-Plane Model: Multifare Extension Introduction and Motivation Most airlines sell tickets in different fare classes (most commonly first class and coach). We extend the basic One-Plane Model to account for multiple fare classes. Development For simplicity, we consider a two-fare system, with C1 first-class seats and C2 coach seats. We assume that a first-class ticket costs T1 = $280 and that a
290 The UMAP Journal 23.3(2002) coach ticket costs T2=$140. We consider an overbooking strategy of selling up to B1 first class tickets and up to B2 coach tickets, where the two types of sales are made independently of one another. We assume that a first-class ticketholder becomes a first-class contender with probability pi and that a coach ticketholder becomes a coach contender with probability p2. We use two independent binomial distributions as our model. First-class ticketholders are more likely to become contenders than coach passengers, since they have made a larger monetary investment in their tickets; that is, P1> P2. Thus, the probabilities of exactly i first-class contenders and exactly j coach contenders are BI B (1-p1) ()z(1-m We model compensation costs as constant per bumped passenger but de- pendent on fare class, with(k1+1)T1 as compensation for a bumped first-class passenger and(k2 +1)T2 for a bumped coach passenger. We define the com- pensation cost function i≤C1,j≤C F(i,j,C1,C2)= T1(k1+1)(-C1), i>C1,j≤C2 max{T2(k2+1)(0-C2)-(i-C1),0},i≤Cl,j>C2 T1(k1+1)(-C1)+12(k2+1)(-C2),i>C1,j>C2 The justification for the third case is that an excess of coach contenders lowed to spill over into any available first-class seats. On the other hand, excess first-class contenders cannot be seated in any available coach seats; this fact is reflected in the second case We model expected revenue R as a function of the overbooking strategy (B1,B2) B1\/B2 1(/(沙)(1-m1)B-r(1-p)2-3 (BIT1+ B2T2-F(i,j, C1, C2)) Results and interpretation For fixed Ci, Ti, Pi, and ki(i= 1, 2), we can find(Bl, opt, B 2, opt)for which R(B1, B2)is maximal by adapting the computer program used to solve the one-fare case For example for a plane with C1= 20 first class seats, C2= 130 coach seats, ticket costs of T1=$280 and T2=$140, and compensation constants h1= k2= l, we obtain the optimal overbooking strategies listed in Table 2 The optimal strategy involves relatively little overbooking of first-class pas sengers,since there is a much higher compensation cost. However, the total
290 The UMAP Journal 23.3 (2002) coach ticket costs T2 = $140. We consider an overbooking strategy of selling up to B1 first class tickets and up to B2 coach tickets, where the two types of sales are made independently of one another. We assume that a first-class ticketholder becomes a first-class contender with probability p1 and that a coach ticketholder becomes a coach contender with probability p2. We use two independent binomial distributions as our model. First-class ticketholders are more likely to become contenders than coach passengers, since they have made a larger monetary investment in their tickets; that is, p1 > p2. Thus, the probabilities of exactly i first-class contenders and exactly j coach contenders are B1 i pi 1(1 − p1) B1−i , B2 j pj 2(1 − p2) B2−j . We model compensation costs as constant per bumped passenger but dependent on fare class, with (k1 +1)T1 as compensation for a bumped first-class passenger and (k2 + 1)T2 for a bumped coach passenger. We define the compensation cost function: F(i,j,C1, C2) = 0, i ≤ C1, j ≤ C2; T1(k1 + 1)(i − C1), i>C1, j ≤ C2; max{T2(k2 + 1)((j − C2) − (i − C1)), 0}, i ≤ C1, j>C2; T1(k1 + 1)(i − C1) + T2(k2 + 1)(j − C2), i>C1, j>C2. The justification for the third case is that an excess of coach contenders is allowed to spill over into any available first-class seats. On the other hand, excess first-class contenders cannot be seated in any available coach seats; this fact is reflected in the second case. We model expected revenue R as a function of the overbooking strategy (B1, B2): R(B1, B2) = B1 i=1 B2 j=1 B1 i B2 j pi 1(1 − p1) B1−i pj 2(1 − p2) B2−j · (B1T1 + B2T2 − F(i,j,C1, C2)) Results and Interpretation For fixed Ci, Ti, pi, and ki (i = 1, 2), we can find (B1,opt, B2,opt) for which R(B1, B2) is maximal by adapting the computer program used to solve the one-fare case. For example, for a plane with C1 = 20 first class seats, C2 = 130 coach seats, ticket costs of T1 = $280 and T2 = $140, and compensation constants k1 = k2 = 1, we obtain the optimal overbooking strategies listed in Table 2. The optimal strategy involves relatively little overbooking of first-class passengers, since there is a much higher compensation cost. However, the total
Optimal Overbooking 291 Table 2 Two-fare optimal overbooking strategies for selected arrival probabilities 0 0.80 166 0.850.85 23 155 0900.8522 0.950.85 155 146 0.950.9021 145 number of passengers(coach plus first-class) overbooked in an optimal two-fare situation is virtually the same as the total number overbooked in the one -fare situation. The upshot is that the effect of multiple fare classes on the optimal overbooking strategy is not very significant; so, when we construct our more general model, we do not take into account multiple fares Compensation Costs The key element that separates different schemes for compensating bumped ticketholders is the degree of choice for the passenger. Airlines often hold auctions for contenders in which the lowest bids are first to be bought off of a We construct a model for involuntary bumping costs that is based on DOT regulations and takes into account the waiting time distribution for flights Then we discuss auction methods for voluntary bumping and derive novel results for expected compensation cost for a continuous auction that matches actual ticket auctions fairly well Involuntary Bumping: DOT Regulations The Department of Transportation(DOT) requires each airline to give all passengers who are bumped involuntarily a written statement describing their rights and explaining how the airline decides who gets on an overbooked flight and who does not [Department of Transportation 2002. Travelers who do not get to fly are usually entitled to an"on-the-spot payment of denied boarding compensation. The amount depends on the price of their ticket and the length of the delay Passengers bumped involuntarily for whom the airline arranges substitute transportation scheduled to get to their final destination within one hour of their original scheduled arrival time receive no compensation
Optimal Overbooking 291 Table 2. Two-fare optimal overbooking strategies for selected arrival probabilities. p1 p2 B1,opt B2,opt 0.85 0.80 23 165 0.90 0.80 22 165 0.95 0.80 20 166 0.85 0.85 23 155 0.90 0.85 22 155 0.95 0.85 20 155 0.90 0.90 22 146 0.95 0.90 21 145 number of passengers (coach plusfirst-class) overbooked in an optimal two-fare situation is virtually the same as the total number overbooked in the one-fare situation. The upshot is that the effect of multiple fare classes on the optimal overbooking strategy is not very significant; so, when we construct our more general model, we do not take into account multiple fares. Compensation Costs The key element that separates different schemes for compensating bumped ticketholders is the degree of choice for the passenger. Airlines often hold auctions for contenders in which the lowest bids are first to be bought off of a flight. We construct a model for involuntary bumping costs that is based on DOT regulations and takes into account the waiting time distribution for flights. Then we discuss auction methods for voluntary bumping and derive novel results for expected compensation cost for a continuous auction that matches actual ticket auctions fairly well. Involuntary Bumping: DOT Regulations The Department of Transportation (DOT) requires each airline to give all passengers who are bumped involuntarily a written statement describing their rights and explaining how the airline decides who gets on an overbooked flight and who does not [Department of Transportation 2002]. Travelers who do not get to fly are usually entitled to an “on-the-spot” payment of denied boarding compensation. The amount depends on the price of their ticket and the length of the delay: • Passengers bumped involuntarily for whom the airline arranges substitute transportation scheduled to get to their final destination within one hour of their original scheduled arrival time receive no compensation
292 The UMAP Journal 23.3 (2002) If the airline arranges substitute transportation scheduled to arrive at the destination between one and two hours after the original arrival time, the airline must pay bumped passengers an amount equal to their one-way fare, with a $200 maximum If the substitute transportation is scheduled to get to the destination more than two hours later, or if the airline does not make any substitute travel arrangements for the bumped passenger, the airline must pay an amount equal to the lesser of 200% of the fare price and $400 Bumped passengers always get to keep their tickets and use them on another flight. If they choose to make their own arrangements, they are entitled to an"involuntary refund"for their original ticket These conditions apply only to domestic flights and not to planes that hold 60 or fewer passe The function for the compensation cost for an involuntarily bumped pas- senger Is if0<t<1 C(,F)={min(2FF+200,1<T≤2 min(3F,F+400),i2<T, where T is waiting time and F is the fare price. We assume that all flights to a given location are direct and have the same flight duration. Thus, the waiting time between flights equals the difference in departure times, and the waiting time T is the time until the next flight to the destination departs. We assume that involuntarily bumped passengers always ask for a refund of their fare Involuntary Bumping: The Waiting Time Model To use the compensation cost function to determine the average comper nsa tion(per involuntarily bumped passenger), we would need to know the joint distribution of fare prices and waiting times. Because this information would be extremely difficult to obtain, we opt instead for practical compromises We restrict our attention to determining the expected compensation cost for the average ticket price, $140 [Airline Transport Association 20001 We specify a workable model for the distribution of waiting times that allows us to calculate this cost directly. Our model for the distribution of waiting times is the exponential distri- bution, a common distribution for waiting times. Let T be a random variable representing waiting time between flights; then
292 The UMAP Journal 23.3 (2002) • If the airline arranges substitute transportation scheduled to arrive at the destination between one and two hours after the original arrival time, the airline must pay bumped passengers an amount equal to their one-way fare, with a $200 maximum. • If the substitute transportation is scheduled to get to the destination more than two hours later, or if the airline does not make any substitute travel arrangements for the bumped passenger, the airline must pay an amount equal to the lesser of 200% of the fare price and $400. • Bumped passengers always get to keep their tickets and use them on another flight. If they choose to make their own arrangements, they are entitled to an “involuntary refund” for their original ticket. These conditions apply only to domestic flights and not to planes that hold 60 or fewer passengers. The function for the compensation cost for an involuntarily bumped passenger is C(T,F) = 0, if 0 < T ≤ 1; min (2F,F + 200), if 1 < T ≤ 2; min (3F,F + 400), if 2 < T, where T is waiting time and F is the fare price. We assume that all flights to a given location are direct and have the same flight duration. Thus, the waiting time between flights equals the difference in departure times, and the waiting time T is the time until the next flight to the destination departs. We assume that involuntarily bumped passengers always ask for a refund of their fare. Involuntary Bumping: The Waiting Time Model To use the compensation cost function to determine the average compensation (per involuntarily bumped passenger), we would need to know the joint distribution of fare prices and waiting times. Because this information would be extremely difficult to obtain, we opt instead for practical compromises: • We restrict our attention to determining the expected compensation cost for the average ticket price, $140 [Airline Transport Association 2000]. • We specify a workable model for the distribution of waiting times that allows us to calculate this cost directly. Our model for the distribution of waiting times is the exponential distribution, a common distribution for waiting times. Let T be a random variable representing waiting time between flights; then Pr(T ≤ t)=1 − e−λt