OR Spectrum 29:85–103 (2007) DOI 10.1007/s00291-005-0017-0
REGULAR A RT ICLE
Y. B. Xiao . J. Chen . Y. Chen
On a semi-dynamic pricing and seat inventory allocation problem
Published online: 11 January 2006 © Springer-Verlag 2006
Abstract Motivated by the practice of airlines, this paper considers the following problem. Tickets are offered at a limited number of predetermined price levels, and the price is only allowed to change monotonically. Management needs to determine the number of seats to be sold at each discount fare with an objective of maximizing the revenue. Such a semi-dynamic pricing and seat allocation approach improves the static pricing approach, as it allows a certain degree of pricing flexibility, but it compromises the potential revenue maximization of the dynamic pricing approach. Therefore, a natural question is what is the magnitude of the revenue loss by such a semi-dynamic approach? The primary objective of this paper is to gain insights into this question. Based on structural results, numerical experiments show that the semi-dynamic pricing approach generates near-optimal revenue. Keywords Revenue management . Seat inventory allocation . Pricing 1 Introduction It’s common for the airlines to sell a pool of identical seats (i.e., seats in the same cabin) at different prices so as to improve revenue in a very competitive market. The amount paid by passengers may depend on when the ticket is purchased. For
Comments by two anonymous referees are appreciated. This research was partially supported by the National Science Foundation of China (NSFC) under Project No. 70321001 and 70329001, and the Research Grants Council of Hong Kong (SAR) under Project No. 2150393. Y. B. Xiao . J. Chen Research Center for Contemporary Management, Tsinghua University, Beijing, 100084, China E-mail:
[email protected];
[email protected] Y. Chen (*) The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong, China E-mail:
[email protected]
86
Y. B. Xiao et al.
example, if the passengers book tickets earlier, it’s possible that they will get a deeper discount. Under the practice of price discrimination, the airlines usually impose different levels of restrictions (e.g., requiring the passenger to book 7- or 21days in advance, prohibiting the passenger to cancel the ticket, etc.) on the identical seats which are sold at different prices. By designing the right combinations of fares and restrictions, the airlines can segment the market effectively and attract pricesensitive passengers while retaining the price-insensitive ones. In the revenue management literature, it is widely recognized that an airline should apply a “nested” fare structure. The optimal decision of which combination of fares to offer depends on the current seat inventory level (i.e., the number of seats that are left unsold) and the remaining time before departure. However, implementing such optimal or pure dynamic controls requires the airline booking system to continuously monitor the booking status and make decisions with respect to whether to close the lowest fare class which is on offering. Consequently, such optimal-control approaches are deemed computationally too expensive to implement with the current computing facilities used by airlines. This is because of the following three reasons. (1) We observe that, the scientific approaches that are applied in most revenue management systems (e.g., the PROS system) are NOT the optimal ones; for example, the sub-optimal EMSR approach is widely used in the airline booking systems. (2) If the pure dynamic approaches are applied, the computation burden would be prohibitive. Imagine an airline operating two flights in the same route each day and begins selling tickets only one month (30 days) in advance. Then the booking system has to monitor the booking status of the 60(=2×30) flights continuously and runs dynamic programming every time when a request arrives. As each request has to be answered within a second or less, the airline would need several computers just for this single route. Therefore, the airline has to seek for simple and less time-consuming approaches. (3) As Zhao and Zheng (2000) point out, there are administrative costs associated with pure dynamic approaches, which again makes the theoretically optimal approaches difficult to implement. Therefore, in this paper, we try to propose a practical method by which the airline makes only a limited number of decisions. Let’s take a look at a prevailing practice by Chinese airlines. In China, most passengers always buy the tickets at the lowest available fare; only a small fraction of “business travellers” would buy at a higher fare even when a lower fare exists, because they are highly restriction-sensitive and/or their future travel schedules are highly uncertain (thus, it’s likely that they may have to cancel the tickets or change to other flights). However, observing that the tickets are almost always available at later times but higher fares, those business travellers have little incentive to buy their tickets earlier. (Only exceptions are a few peak seasons, during which the tickets are normally sold out much earlier.) Furthermore, a lower fare ticket with certain restrictions can always be “upgraded” to a ticket with these restrictions being removed. For example, one can change the flight by paying a penalty, or cancel the ticket with some refund (which is regulated by the government to protect all buyers). Hence in the actual booking operations, the airline always quotes the currently lowest available fare to the ticket buyer and lets the buyer make the purchasing decision based on such a fare level. Under such an environment, even the airline is willing to sell the tickets at higher fares, the “effective” fare that determines the demand rate is the current lowest available fare, because demand rate for the higher fare classes is very limited. This phenomenon is also noted by Boyd and Kallesen
On a semi-dynamic pricing and seat inventory allocation problem
87
(2004) for the US market where the changing business environment (such as the rise of Internet and discount carriers) is making ticket price an ever important consideration in passenger purchasing behavior. Boyd and Kallesen call such a demand pattern a priceable model of demand, under which most of passengers are primarily concerned with price. Motivated by the above observations, this paper presents a model as follows. (1) Tickets are offered at a limited number of predetermined price levels; (2) price is only allowed to change monotonically, i.e., the airline uses the markup policy; and (3) there is only one passenger type whose demand depends only on the current ticket price. Management needs to determine the number of seats to be sold at each discount fare with the objective of maximizing the total revenue. The seat allocation decision is made at each decision epoch. When the ticket selling begins, the airline allocates the number of seats for the deepest discount fare. Once these seats have been sold out, the second decision epoch occurs, and the airline chooses a higher discount fare and allocates the number of seats for this new fare. Such intermittent pricing and seat allocation decisions continue till all the unsold seats have been allocated to all of the remaining fare levels, or the departure time approaches. Assumptions (1) and (2) essentially capture the practice of Chinese airlines, while Assumption (3) represents a simplification of reality. However, we believe that in the Chinese airlines market, such a simplification will not cause serious impact on our analysis, because as mentioned earlier, the number of restriction-sensitive passengers is normally very limited. Therefore, the model presented in this paper originates from the practice of airlines and differs from the existing models on airline revenue management and perishable product pricing. Our intermittent pricing and seat allocation approach improves the static pricing approach, as it allows a certain degree of pricing flexibility, but it compromises the potential revenue maximization of the dynamic pricing approach. Therefore, a natural question is what is the magnitude of the revenue loss by such a semi-dynamic approach? The objective of this paper is to gain insights into this question. Based on structural results, numerical experiments show that the proposed approach generates near-optimal revenue. The rest of the paper is organized as follows. In Section 2, we provide a brief survey of the related literature and compare our model with the existing models. After presenting the dynamic seat inventory allocation model for the case of multiple fare levels in Section 3, we focus on the optimal allocation decision when there are only two fare levels and a single price change in Section 4. The numerical results are presented in Section 5, where we compare the results generated by our semidynamic seat inventory control model with those of the pure dynamic methods. The summary conclusions of this study will be presented in Section 6. 2 Related literature We classify the existing models for the seat inventory control problems into two classes: static and dynamic models. The models that assume sequential offerings of fare-classes, consider the total demand for each fare-class, and try to find the (near) optimal booking limits (or protection levels, equivalently) for each fare-class are
88
Y. B. Xiao et al.
called static seat inventory control models. Littlewood (1972) was the first to propose a solution method for the seat inventory control problem for a single-leg flight with two fare classes. Pfeifer (1989) and Brumelle et al. (1990) generalize Littlewood’s model to allow flexible customers. Belobaba (1987) extends Littlewood’s rule to multiple nested fare classes and introduces the term expected marginal seat revenue (EMSR) for the general approach. His method is known as the EMSRa method and produces nested protection levels. The EMSRa method, however, does not yield optimal booking limits when more than two fare classes are considered. Optimal policies for more than two classes have been addressed in Curry (1990), Brumelle and McGill (1993), Wollmer (1992), Robinson (1995), and Van Ryzin and McGill (2000). Dynamic solution methods, on the other hand, do not determine a booking control policy at the start of the booking period as the static solution methods do. Instead, they monitor the state of the booking process over time and decide on acceptance of a particular booking request when it arrives. It has been noted in the literature that the multi-class inventory-control problem can be interpreted as a class of the dynamic pricing problem of perishable products in which a discrete price set is given (e.g., see Bitran and Caldentey 2003). Lee and Hersh (1993) consider a discrete-time dynamic programming model, where demand for each fare class is modelled by a non-homogeneous Poisson process. Subramanian et al. (1999) extend the model of Lee and Hersh to incorporate cancellations, no-shows, and thus overbooking. Liang (1999) and Van Slyke and Young (2000) consider the continuous-time versions of Lee and Hersh. Feng and Gallego (1995) address the problem of deciding the optimal timing of a single price change from a given initial price to either a given lower or higher second price and obtain an optimal threshold control policy. Our model is most relevant to the dynamic markup mechanism of Feng and Xiao (2000a). They study the dynamic price change in a setting that the price is allowed to change monotonically; whereas in another work, Feng and Xiao (2000b) allow the price to change reversibly. A recent paper by Talluri and Van Ryzin (2004a) presents a general choice model of consumer behavior and controls the subset of fare products to offer at each point in time to maximize the revenue. Interested readers are referred to McGill and Van Ryzin (1999) and Talluri and Van Ryzin (2004b) for an in-depth survey of revenue management problems with multifare-classes. The problem studied in this paper is a compromise of static and dynamic models. The differences with the static models are as follows: (1) we model the demand as a continuous arrival process, which comprises all the passengers who are willing to pay at different fares, instead of assuming that low-fare passengers (i.e., the passengers that are willing to pay at a low fare) always arrive before the high-fare ones; (2) the seat allocation decisions are made dynamically during the sales horizon, that is, decision occurs right after the switch-over of the price and depends on current seat inventory level and the time left-to-go. On the other hand, our model also differs from the existing dynamic models in the following two ways: (1) most dynamic models determine the “fare set” to be opened, whereas ours decides on the single effective fare; and (2) the existing dynamic models monitor the booking status constantly and make decisions based on the combination of inventory level
On a semi-dynamic pricing and seat inventory allocation problem
89
and time left-to-go, our model simplifies this decision process and only makes finite decisions (theoretically the dynamic models make infinite decisions). In summary, our model is largely motivated by the practice of airlines and combines the merits of both static and dynamic controls. The model has the following three distinctive features. First, it makes finite decisions. Each seat allocation decision is made right after the price switches to the next higher fare, and the number of decision times is less than the number of feasible fares (i.e., if there are k fare levels, then k−1 decision times at the most). Second, the decisions are also dynamic. Like the existing dynamic seat inventory control models, each seat allocation decision of our model also depends on the seat inventory level and the remaining time at the decision epoch (note that the next decision epoch is stochastic because of the random arrival of demand). Based on the above two features, we therefore call our model a “dynamic seat inventory allocation” or “semi-dynamic seat inventory control” (SDSIC) problem. Lastly, our model does not allow the lower fare to be offered again once the price switches to a higher fare; i.e., we don’t allow reversible price changes. As Kimes (2002) shows, if the ticket price changes reversibly, perceived unfairness of passengers will increase and hence the airline’s long-run profit will be affected. Moreover, right after the specified number of tickets are sold out at a certain price (say, pi), the airline is also not allowed to keep selling at pi for another few tickets. Because it may be seen as a kind of “cheat” from the point of passengers. By publicizing the number of seats to be sold at the current fare, the airline tries to influence the passenger behavior—waiting can only lose the current low price. 3 The dynamic allocation model Here is a formal description of the basic model. Let C be the number of seats on a scheduled flight, which can be sold at k different fares. The sales horizon is [0,T], where T is the departure time. Denote the set of feasible prices by P={p1,p2, ⋯, pk}, with p1 > p2 > ⋯ pk, that is, p1 is the full fare and the other k−1 fares are of different discount levels. We express the demand as a rate that depends only on the current price p through a function λ(p). For example, if the arrival rate of (potential) passengers is λ0, and each passenger has an i.i.d. stochastic reservation price whose pdf and cdf are f( p) and F(p), respectively—only those passengers whose reservation price is above the current price will buy the ticket—then the expected demand rate at price p is λ0F (p)=λ0(1−F( p)). We therefore assume that at each price level pi (i=1,2,⋯, k), demand is a homogeneous Poisson process with a constant intensity λi=λ0(1−F(pi)). It’s apparent that λ1<λ2 <λk. Each passenger demand is assumed to be of unit size. We don’t consider any passenger cancellations or no-shows, thus the airline doesn’t implement overbooking. The notion ri=piλi represents the expected revenue rate at pi. We assume r(p) is decreasing in p for p∈P, i.e., r1
90
Y. B. Xiao et al.
used demand functions satisfy the above assumption, including the linear, exponential, and power demand functions, with parameters constraints. Define the Poisson process {Ni(t):t≥ 0} whose arrival rate is λi, i=1,2, ⋯, k and let Sx(i)=inf{t:Ni(t)=x} be the xth arrival epoch when the demand rate is λi. Therefore S0(i)≡0 when x=0; and for x≥ 1, we denote the cdf and pdf of Sx(i) as Gx(i)(t ) and gx(i)(t) respectively, which are both continuous and differentiable in time t. We have 1 i t n o X e ½i t j ; GðxiÞ ðt Þ ¼ Pr SxðiÞ t ¼ PrfNi ðt Þ xg ¼ j! j¼x
(1)
and hence, gxðiÞ ðt Þ ¼
ð iÞ h i dGx ðt Þ ei t ½i t x1 ðiÞ ¼ i ¼ i Gx1 ðt Þ GðxiÞ ðt Þ : dt ðx 1Þ!
(2)
The seat allocation decision is the result of balancing between the demand and the seat inventory supply. According to our ticket selling pattern, even when the number of seats to be sold in each fare class is determined, the time point at which the airline switches the price to the next higher fare is still stochastic because of the random arrival pattern of passengers. One of the characteristics of our semidynamic seat inventory control is that each decision is still determined by the booking state, (t,d)—where t is the price switch time point and d is the seat inventory level—at the price switch time point. We denote Ri(t,d) as the maximal expected revenue over the interval (t,T ], given that the price switches to pi at t and the seat inventory level at t is d. At such point t, the airline determines the number of seats (xi) to be sold at pi, which is constrained by the number of available seats (recall that we don’t consider passenger cancellations or no-shows). The dynamic seat allocation process is depicted in Fig. 1. Note that the next ð iÞ decision epoch, t þ Sxi , depends on the realization of demand under current price (pi). Here we have the following two possibilities. ðiÞ
(1) If t þ Sxi > T ; which means that the xi tickets priced at pi are not sold out before the departure time, then the expected revenue within (t,T] is n o (3) pi E Ni ðT t ÞSxðiiÞ > T t ¼ pi E fNi ðT t ÞjNi ðT t Þ < xi g;
decision epoch
price switch epoch, the next decision epoch pi-1
pi t + S x(i)i
t
departure time
S x(i)i = inf{t : N i (t) = xi } Fig. 1 The dynamic seat allocation process
T
On a semi-dynamic pricing and seat inventory allocation problem
91
ðiÞ
(2) If t þ Sxi T ; which means that the xi tickets are sold out and the price ðiÞ switches to pi-1 at t þ Sxi ; then the expected revenue iwithin (t,T] consists ðiÞ
of two parts: the revenue that is collected in t; t þ Sxi ; which equals pixi, i ðiÞ and the revenue that will be collected in t þ Sxi ; T ; which equals Ri1 ð iÞ t þ Sxi ; d xi : Hence the total expected revenue is n o pi xi þ E Ri1 t þ SxðiiÞ ; d xi SxðiiÞ T t :
(4)
Conditioning on the next price switch epoch, from the dynamic programming point of view, we have the following recursive formulation: Z 1 pi E fNi ðT t ÞjNi ðT t Þ < xi ggxðii Þ ðsÞds Ri ðt; d Þ ¼ max 0xi d T t (5) Z T t o ð iÞ þ ½pi xi þ Ri1 ðt þ s; d xi Þgxi ðsÞds ;
f
0
where 2≤ i≤ k, t
The recursive formulae suggest a dynamic process for solving the optimal seat allocation decision and the expected revenue function; i.e., xi* and Ri (t, d) can be determined when all Rj (t, d), j=i−1,⋯1, become available. Because the number of fare levels used by the airlines, k, is usually quite small (we observe that, the Chinese airlines usually offer two to three fares for the tickets of a flight. The simulation results of many researches also show that increasing the number of fare classes only has a rather minor revenue improvement, and they suggest that it is suitable to have three to five fare classes; e.g., Lin et al. 2003). Hence, we only need a moderate computational effort to find the optimal seat allocation decision. This is another advantage of our model over the pure-dynamic policy and the policy of Feng and Xiao (2000a). However, the recursive formula 5 is still difficult to analyze, thus below, we will take a closer look at the special case of k=2. We intend to uncover the structural properties of the optimal decision, based on which a heuristic method is devised for the general multiple-fare-level case.
92
Y. B. Xiao et al.
4 The optimal allocation decision with two fare levels Because there is at the most one price change when there are two fare levels, the airline’s decision is to determine the number of seats to be sold at the discount fare (p2) at the beginning of the sales horizon. Right after the specified number of tickets are sold out, the ticket price will switch to the full fare (p1). 4.1 The revenue formulation Denote the number of seats to be sold at the discount fare as x, 0≤x≤C. Thus the remaining (C−x) seats will be sold at the full fare. If the optimal decision is to set x=0, it will mean that all the tickets should be sold at the full-fare (p1); on the other hand, if it’s optimal to set x=C, it will mean that all the tickets should be sold at the discount-fare (p2). For notational simplicity, Sx(2)=inf {t: N2 (t)=x} is abbreviated as Sx, the pdf and cdf of Sx, gx(2) (t) and Gx(2) (t), are also abbreviated as gx (t) and Gx (t), respectively. From Eqs. 5 and 6, the total expected revenue (denoted as R(x)) for selling C tickets in [0, T], given that x tickets are provided at the discount fare, is as follows: RT Rð xÞ ¼ 0 ½p2 x þ p1 EfminðC x; N1 ðT t ÞÞggx ðt Þdt R þp2 1 T E fN2 ðT ÞjN2 ðT Þ < xggx ðt Þdt ! R T ðC xÞPrfN1 ðT sÞ C x þ 1g (7) ¼ p1 0 gx ðsÞds þ1 ðT sÞPrfN1 ðT sÞ C x 1g þp2 ½x PrfN2 ðT Þ x þ 1g þ 2 T PrfN2 ðT Þ x 1g :
(7)
It is almost trivial that as the number of seats allocated to the discount fare-class, x, increases, the revenue from selling tickets at p2 also increase; and the revenue from selling tickets at p1 decreases. The decrease of the latter revenue is due to the reduction of both seat inventory and remaining time. The airline seeks to find an optimal allocation decision, x*, so as to maximize R(x). 4.2 Structural properties For analytical purposes, we split the total revenue into two parts: R2 (x), the discount-fare revenue and R1 (x), the full-fare revenue. Let ΔR1 (x):=R1 (x+1)−R1 (x), ΔR2 (x):=R2 (x+1)−R2 (x) be the marginal discount-fare and full-fare revenue, respectively. For further characterization of expected revenue function R(x), we first present the following two lemmas. Lemma 1 The discount-fare revenue, R2 (x), is increasing in x, but its marginal expected revenue, ΔR2 (x) is decreasing in x; i.e., R2 (x) is an increasing concave function of x.
On a semi-dynamic pricing and seat inventory allocation problem
93
Proof From Eq. 7 we have, R2 ð xÞ ¼ p2 ½ðx þ 1Þ PrfN2 ðT Þ x þ 2g þ 2 T PrfN2 ðT Þ xg p2 ½x PrfN2 ðT Þ x þ 1g þ 2 T PrfN2 ðT Þ x 1g
(8)
¼ p2 PrfN2 ðT Þ x þ 1g > 0; and hence, R2 ðx þ 1Þ R2 ð xÞ ¼ p2 PrfN2 ðT Þ x þ 2g p2 PrfN2 ðT Þ x þ 1g (9) ¼ p2 PrfN2 ðT Þ ¼ x þ 1g < 0: Therefore, R2 (x) is increasing and concave in x. Lemma 2 The full-fare revenue, R1(x), is decreasing in x. Proof First we define the following function that is continuous in s∈[0, T]: M ðsÞ:¼ ðC xÞ Pr fN1 ðT sÞ C x þ 1g
(10)
þ 1 ðT sÞPrfN1 ðT sÞ C x 1g: Taking the first derivative with respect to s, we have dM ðsÞ ¼ 1 PrfN1 ðT sÞ C x 1g; ds Hence transforming R1(x) by parts, we have RT R1 ð xÞ ¼ p1 0 M ðsÞdGx ðsÞ RT ¼ p1 M ðsÞGx ðsÞT0 p1 0 Gx ðsÞdM ðsÞ RT ¼ p1 1 0 Gx ðsÞ PrfN1 ðT sÞ C x 1gds:
(11)
(12)
Taking difference with respect to x yields R1 ð xÞ ¼ R1 ðx þ 1Þ R1 ð xÞ R T ¼ p1 12 Gxþ1 ðT Þ p1 1 12 0 PrfN1 ðT sÞC xggxþ1 ðsÞds:
(13)
Therefore we have ΔR1 (x)<0, because both blocks on the right-hand side are negative; i.e., R1 (x) is strictly decreasing in x. Theorem 3 The expected revenue, R(x), is strictly concave in x; i.e., for ∀x, x=0, 1⋯C−2, Rðx þ 2Þ Rðx þ 1Þ < Rðx þ 1Þ Rð xÞ:
(14)
94
Y. B. Xiao et al.
Proof Taking difference with respect to x on both sides of Eq. 13, we have R1 ðx þ 1Þ R1 ð xÞ
1 1 2 PrfN2 ðT Þ ¼ x þ 1g p1 1 2 2 Z T PrfN1 ðT sÞ ¼ C x 1ggxþ2 ðsÞds:
¼ p1
(15)
0
Combining Eq. 9 with Eq. 15, it follows that Rðx þ 2Þ 2Rðx þ 1Þ þ Rð xÞ ¼ R1 ðx þ 1Þ R1 ð xÞ þ R2 ðx þ 1Þ R2 ð xÞ 1 1 2 ¼ p2 þ p1 PrfN2 ðT Þ ¼ x þ 1g p1 1 2 2 Z T PrfN1 ðT sÞ ¼ C x 1ggxþ2 ðsÞds: 0
Because p1λ1
Z T 1 PrfN1 ðT sÞ < C xggxþ1 ðsÞds; þ p2 p1 2 0 which can be interpreted as follows. There are two possible impacts that increasing one unit of discount ticket (from x to x+1) will have on the increment of revenue: (1) When Sx+1≤T and N1 (T−Sx+1)≥C−x, the increment of the discount ticket will incur a revenue decrease, because if it is provided at the full-fare, all the remaining (C−x) tickets will be sold out at the full-fare. Therefore the airline incurs a revenue loss of p1−p2. (2) When Sx+1≤T and N1 (T−Sx+1)
On a semi-dynamic pricing and seat inventory allocation problem
95
revenue increment of the airline is −(p1−p2)λ1/λ2+p2(1−λ1/λ2)=p2−p1λ1/λ2. From the above analysis, ΔR(x) can be re-expressed as Rð xÞ ¼ ð p1 p2 Þ PrfSxþ1 T ; N1 ðT Sxþ1 Þ C xg
(17)
1 PrfSxþ1 T ; N1 ðT Sxþ1 Þ < C xg: þ p2 p1 2 Therefore from the incremental point of view, the airline should balance the trade off between the revenue improvement and revenue loss of increasing one unit of discount ticket. Only when the combined marginal expected revenue is above zero, to increase one unit of discount ticket is appropriate. The optimal allocation decision, x*, satisfies R(x*)>R(x*−1), and R(x*)≥R(x*+1). Remark 1 From Eq. 17 we see that if p1λ1≥ p2λ2, then R(x+1)
CN. Specifically, the lower bound, C0, and upper bound, CN are defined as follows: C0 ¼ maxfC jRð0Þ < 0g; CN ¼ minfC jRðC 1Þ 0g:
(18)
96
Y. B. Xiao et al.
4.2.2 Impact of the potential demand rate In our model, the effective arrival rate of demand is determined by two parts: the potential passenger arrival rate (λ0) and the passengers’ choice behavior (characterized by F ðpi Þ ). Now we focus on the impact of λ0 and for briefness, denote λ1:=a1λ0 and λ2:=a2λ0, where a2>a1. λ0 reflects the seasonal factor in our real life: in the mid-seasons of travel (the National Holidays and the Christmas Holidays, for example), the demand reaches the peak and thus λ0 is high; whereas λ0 is low during the off-seasons because the demand is quite scare. To uncover the relationship between λ0 and the optimal allocation decision, x*, we define τC−x=inf {t:N1(t)=C−x} as the (C−x)th arrival epoch of Poisson process {N1(t)}. Hence Eq. 17 is transformed as: p1 ð2 −1 Þ p2 2 p1 1 PrfSxþ1 þ Cx T g Rð xÞ ¼ Gxþ1 ðT Þ : (19) 2 p1 ð2 1 Þ PrfSxþ1 T g First we have the following Theorem 5. Theorem 5 For 0 ≤x≤ C−1, define Ψ (t):=Pr{Sx+1+τC−x ≤ t}/Pr{Sx+1 ≤ T}, t∈[0, T], then Ψ(t) is an increasing function of λ0. Proof First we prove the following stronger result: (Sx+1+τC−x)|Sx+1≤T is stochastically decreasing in λ0. Consider two scenarios, whose potential passenger b e0 ; b0 > e0 . Denote the corresponding Sx+1 and τC−x as arrival rates are 0 and Sxþ1 b0 and Cx b0 ; Sxþ1 e0 and Cx e0 ; respectively. Denote the pdf of as b f (t) and e f (t), and Cx e0 Sxþ1 e0 T Cx b0 Sxþ1 b0 T respectively. Because Sx+1 is independent of τC−x, hence, Cx1 0 t b !Cx b a1 b a1 b0 t =ðC x 1Þ! b f ðt Þ a1 0 e a1 b 0 e 0 t 0 ¼ : ¼e e 0 t a e0 e Cx1 =ðC x 1Þ! f ðt Þ a1 e0 ea1 e 1 0t b t Þ=e b e We know f ðt Þ is that that f ð decreasing in t (note 0 > 0 ), therefore ð Cx b0 jSxþ1 b0 T Þ Cx b0 jSxþ1 b0 T ; i.e., (τC−x∣Sx+1≤T) is LR
decreasing in λ0 in likelihood ratio ordering. b0 jSxþ1 b0 T ) and Now we consider the first term, denote the pdf of (S xþ1 gðt Þ and b gðt Þ; respectively: Sxþ1 e0 jSxþ1 e0 T are b x b a2 b0 ea2 0 t a2 b0 t =x! n o ; b gðt Þ ¼ Pr Sxþ1 b0 T x e a2 e0 ea2 0 t a2 e0 t =x! e gðt Þ ¼
: Pr Sxþ1 e0 T
On a semi-dynamic pricing and seat inventory allocation problem
97
Hence,
Pr Sxþ1 e0 T b gðt Þ a2 b 0 e 0 t n o e ¼ e gðt Þ Pr Sxþ1 b0 T
b0 e0
!xþ1 :
We know that b gðt Þ=e gðt Þ is alsodecreasing b0 > e0 ). Therefore, int (because e e b b Sxþ1 0 jSxþ1 0 T Sxþ1 0 jSxþ1 0 T , i.e., (Sx+1∣Sx+1≤T) is LR
decreasing in λ0 in likelihood ratio ordering. So we conclude that (Sx+1+τC−x)∣Sx+1≤ T is decreasing in λ0 in likelihood ratio ordering (see Ross 1996). That is, for ∀t∈[0,T], the following inequality holds:
Pr Sxþ1 e0 þ Cx e0 tjSxþ1 e0 T n o Pr Sxþ1 b0 þ Cx b0 tjSxþ1 b0 T ; which means that Ψ(t) is increasing in λ0. Now we define the following critical arrival rates of λ0: PrfSiþ1 þ Ci T g p2 a2 p1 a1 ðiÞ 0 ¼ 0 ; ¼ p1 ða2 a1 Þ PrfSiþ1 T g where i=0,1,⋯C−1. That is, ΔR(i)=0 when λ0=λ0(i). First we know that λ0(i) is in a decreasing order of i, which is stated as the following Lemma 6. Lemma 6 λ0(i)is decreasing in i; that is, λ0(C−1)≤λ0(C−2)≤⋯≤λ0(0). Proof For convenience, we denote φ(x,λ0):=Pr{Sx+1+τC−x≤T}/Pr{Sx+1≤T}. Suppose on the contrary that for 0≤iλ0(0), then ΔR(0)≤0 holds, the optimal decision is to sell all the tickets at the full fare, i.e., x*=0; (2) if λ0∈[λ0(i),λ0(i−1)), i=1,2...C−1, then ΔR(i)≤0 and ΔR(i−1)>0, the optimal decision is to set x*=i; and (3) if λ0<λ0(C−1), then ΔR(C−1) >0 holds, the optimal decision is to sell all the tickets at the discount fare, i.e., x*=C. Proposition 7 characterizes the balancing between the seat inventory supply and passengers demand by optimal seat allocation in another way. Given the seat capacity of the airplane assigned to the flight, the more plenteous of the demand,
98
Y. B. Xiao et al.
the more seats should be reserved for later sale at a higher fare; and the scarcer of the demand, the more seats should be sold at the lower fare. This, again, is consistent with our intuition: during the peak-seasons of travel, the airline seat supply falls short of demand even if the airline offers no discount at all; however, during the off-seasons of travel, supply exceeds demand even if the airline offers a large discount. In China, during off-seasons such as during March to April, and Mid-October to Mid-December, passengers are usually able to buy tickets at a price as low as 20∼30% of the full fare. 4.3 A heuristic solution for the multiple-fare-level case Although we cannot find a closed-form formulation for the optimal seat allocation decision (i.e., we cannot find x* by simply letting ΔR(x)=0) when there are two fare levels because the decision variable x is only allowed to take integral values; however, as mentioned in the previous subsection, x* is quite easy to find, and we only need a rather minor computational effort. Hence it is natural to think of a heuristic solution for the seat allocation decision when there are multiple (more than two) fare levels. That is, we transform the multiple-fare-level problem into a two-fare-level problem, and find the seat allocation decision for the current lowest available fare level as follows. Suppose at the decision point (t,d)—where d is the seat inventory level and t the time point, the current lowest available fare is pi(i≥2), and the number of seats to be allocated to the ith fare level, xi, must be determined. We approximate the future (i−1) fare levels (fare level 1, 2⋯, i−1) into a single fare level, whose unit revenue, e pi1 ; and corresponding arrival rate, ei1 are as follows: e pi1 :¼
i1 X j¼1
=
pj ði 1Þ; and ei1 :¼
i1 X j¼1
p j j
=
i1 X
pj :
j¼1
pi1 Þ Now, we face a two-fare-level problem, whose unit revenue vector is ð pi ; e and arrival rate vector is i ; ei1 : It’s apparent that the previous assumptions (1) pi < e pi1 ; (2) i > ei1 ; and (3) i pi > ei1e pi1 are all satisfied here. We can use its optimal allocation decision, exi , which is easy to obtain, to approximate xi*. 5 Numerical experiments and analysis Revenue aside, compared with a dynamic seat inventory control strategy, the semidynamic strategy that makes finite decisions is more desirable because it is simple and convenient. The semi-dynamic seat inventory control is almost free of the extra administrative costs associated with dynamic seat inventory controls. Therefore, a natural question is that of when a semi-dynamic control strategy should be used and what the magnitude of the revenue gain will be. In this section, we report the results of numerical experiments that are designed to develop some intuition with regard to these questions. We use the following two dynamic strategies as benchmarks to measure the performance of our semi-dynamic seat inventory control: (1) a pure dynamic seat
On a semi-dynamic pricing and seat inventory allocation problem
99
inventory control policy that allows the airline to dynamically switch between prices (abbreviated as “DP”) during the sales horizon, based on the current seat inventory level and remaining time (it is well documented, e.g., see Talluri and Van Ryzin 2004a); and (2) Feng and Xiao’s (2000a) markup policy (abbreviated as “FX”) that allows the airline to dynamically determine when to switch to the next higher fare but does not allow reversible price changes (readers may refer to Feng and Xiao (2000a) for more details). Denote the optimal revenues by implementing the DP and FX approaches as RDP and RFX, respectively. It’s obvious that in terms of revenue maximization, the DP method is better than the FX method, which in turn is better than our dynamic allocation method, because from DP to FX, and to SDSIC, more restrictions regarding the price changes are imposed. In the following numerical experiments, we first investigate the optimal decisions and revenues when there are two fare levels. The base parameters are: T=1, C=100, p1=1, p2=0.8, λ0=160, λ1=0.5λ0, and λ2=0.8λ0. Except where explicitly indicated, we alter the value(s) of only one parameter at a time. First, we study the impact of the seat capacity supply. Let the seat capacity, C, change from 70 to 140, and the expected revenues under three strategies are reported in Table 1. The optimal allocation decision, x*, and the relative revenue loss of our semi-dynamic approach, SDSIC, in contrast with the DP and FX approaches, are also listed. It’s seen that when the seat capacity is low (say C=70), the optimal action is to sell all the tickets at the full fare (i.e., x*=0) because the demand is relative plenteous (the average demand will be 80); on the other hand, when the seat capacity is high (say C=140), almost all the tickets should be sold at the discount fare because the demand is relative scarce. This is consistent with the analysis in Proposition 4. Moreover, as Table 1 shows, as the seat capacity increases, the optimal unit revenue (revenue-per-seat) strictly decreases, which is intuitive. As Table 1 shows, the revenue loss of implementing the SDSIC strategy is rather minor compared with the DP method (the largest loss is 2.67%). The relative gap becomes almost negligible when the capacity is very large or very small. Moreover, the relative revenue loss as compared with the FX method is much smaller (the largest loss is 1.08%), and the trend is basically the same: the revenue loss approaches zero when C is very large or very small. This phenomenon can be explained as follows. When the seat capacity is (relatively) small (large), the Table 1 Numerical comparisons with different seat capacities C
70 80 90 100 110 120 130 140
SDSIC
DP
FX
x*
R(x*)
Rev./seat
Rev.
Rev. loss (%)
Rev.
Rev. loss (%)
0 0 26 53 80 106 124 137
69.49 76.51 81.32 86.14 90.96 95.78 99.84 101.80
0.99 0.96 0.90 0.86 0.83 0.80 0.77 0.73
69.64 77.72 83.55 88.34 92.99 97.30 100.44 101.93
−0.22 −1.57 −2.67 −2.50 −2.18 −1.56 −0.60 −0.12
69.54 76.62 81.67 86.78 91.95 96.83 100.38 101.90
−0.07 −0.14 −0.42 −0.73 −1.07 −1.08 −0.53 −0.10
100
Y. B. Xiao et al.
dynamic methods (DP and FX) offer tickets at the full (low) fare in most times, calling to set x*=0 (x*≈C) in the semi-dynamic control. Hence the revenue loss is negligible. Next we fix the seat capacity at C=100 and change the value of λ0, the arrival rate of the potential passengers. The results are summarized in Table 2. As can be seen, while λ0 increases, fewer seats are allocated to the discount fare, and the optimal expected revenue increases. This is consistent with Proposition 7. The minimal and maximal threshold value of λ0 in this experiment are λ0(C−1)=74.4 and λ0(0)=198.4. Again, the revenue loss of SDSIC is rather minor (the largest losses are 2.60% and 1.19%, respectively). Intuitively, the impact of potential demand rates is opposite to that of the seat capacity: when λ0 is (relatively) small (large), the dynamic methods offer tickets at the discount (full) fare in most times. The fare level is another important factor. Clearly, pi (i=1,2) determines the corresponding effective demand rate and therefore affects the optimal seat allocation decision and the expected revenue. In the next group of experiments, the full fare, p1, is fixed at 1.20 and p2 ranges from 0.60 to 1.15, with an increment of 0.05. We use an exponential demand function (λi=ae−bpi), where a=480, and b=1.8. The expected revenues under different strategies are summarized in Table 3. It is found that x* increases as the discount fare increases (x* also increases as the full fare increases when we fix p2). This is because the increase of p2 (or p1) will reduce the corresponding demand rate, hence the supply will exceed demand if the seat allocation decision remains unchanged; the only way to make seat supply and demand be balanced again is to “shift” some seats from the full-fare class to the discount-fare class (hence “increase” some demand), therefore the optimal allocation decision, x*, increases. It should be noted from Table 3 that for a given full-fare, the optimal revenue, R (x*), does not always increase as the discount fare increases. For example, the increase of p2 from 0.90 to 1.10 brings a revenue loss of 13.21%. This reflects Table 2 Numerical comparisons with different potential demand rates λ0
100 110 120 130 140 150 160 170 180 190 200 210 220 230 240
SDSIC
DP
FX
x*
R(x*)
Rev.
Rev. loss (%)
Rev.
Rev. loss (%)
99 98 96 91 80 66 53 39 26 12 0 0 0 0 0
63.97 70.06 75.18 78.68 81.22 83.67 86.14 88.62 91.11 93.61 96.11 98.06 99.16 99.68 99.90
63.97 70.13 75.53 79.71 82.90 85.67 88.34 90.99 93.51 95.74 97.51 98.73 99.43 99.78 99.93
−0.01 −0.09 −0.46 −1.29 −2.04 −2.34 −2.50 −2.60 −2.56 −2.23 −1.43 −0.67 −0.28 −0.10 −0.03
63.97 70.12 75.49 79.43 82.20 84.51 86.78 89.09 91.46 93.85 96.27 98.20 99.26 99.74 99.92
−0.01 −0.08 −0.41 −0.94 −1.19 −0.99 −0.73 −0.53 −0.38 −0.26 −0.16 −0.15 −0.10 −0.06 −0.03
On a semi-dynamic pricing and seat inventory allocation problem
101
Table 3 Numerical comparisons with different discount fares p2
0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95 1.00 1.05 1.10 1.15
SDSIC
DP
FX
x*
R(x*)
Rev.
Rev. loss (%)
Rev.
Rev. loss
61 66 70 76 84 92 96 98 98 99 99 99
77.02 78.42 79.82 81.22 82.61 83.89 84.00 82.18 79.31 76.14 72.90 69.65
79.03 80.46 81.84 83.18 84.38 85.03 84.36 82.24 79.31 76.14 72.90 69.65
−2.55 −2.54 −2.48 −2.36 −2.10 −1.34 −0.43 −0.07 −0.01 −0.00 −0.00 −0.00
77.24 78.73 80.26 81.87 83.48 84.59 84.23 82.22 79.31 76.14 72.90 69.65
−0.29 −0.40 −0.56 −0.79 −1.04 −0.82 −0.28 −0.05 −0.00 −0.00 −0.00 −0.00
another managerial insight that the fare levels have a significant impact on the revenue performance. Therefore, in the practice, the combination of fare levels affects the revenue performance in a fairly significant way. Finally, the expected revenue under the semi-dynamic approach with more than two fare levels are investigated. We consider the case of 5 fare levels (i.e., k=5), where the feasible price set is P={1.00,0.95,0.90,0.80,0.75}. We use the commonly-used demand functions, and the results corresponding to the exponential arrival rates (i.e., i ¼ 0 aebpi are reported in Table 4. For the sake of comparison, we choose the demand function parameters such that the demand rates are Table 4 Numerical comparisons with five fare levels λ0
100 110 120 130 140 150 160 170 180 190 200 210 220 230 240
SDSIC
DP
FX
Heuristic
Revenue
Rev.
Rev. loss (%)
Rev.
Rev. loss (%)
Rev.
Rev. loss (%)
67.02 72.14 75.85 78.95 81.87 84.61 87.32 89.91 92.18 94.22 96.20 98.06 99.16 99.68 99.90
67.10 72.54 76.74 80.23 83.37 86.33 89.07 91.60 93.92 95.99 97.64 98.79 99.46 99.79 99.93
−0.12 −0.56 −1.15 −1.60 −1.79 −1.99 −1.97 −1.84 −1.85 −1.84 −1.47 −0.73 −0.30 −0.11 −0.03
67.07 72.39 76.33 79.56 82.55 85.21 87.87 90.50 92.70 94.73 96.52 98.06 99.16 99.68 99.90
−0.08 −0.34 −0.62 −0.76 −0.81 −0.71 −0.62 −0.65 −0.56 −0.54 −0.32 −0.00 −0.00 −0.00 −0.00
67.01 72.08 75.75 78.78 81.57 84.32 87.10 89.70 92.17 94.12 96.18 98.06 99.16 99.68 99.90
−0.02 −0.08 −0.13 −0.22 −0.37 −0.34 −0.25 −0.24 −0.01 −0.10 −0.02 −0.00 −0.00 −0.00 −0.00
102
Y. B. Xiao et al.
the same as those in Tables 1 and 2 when there are only two fare levels; i.e., a=5.24, b=2.35. We can see that the revenue loss of the SDSIC approach (in comparison with DP and FX) is again rather small. Note that the result for the SDSIC approach is based on an exact computational procedure. The performance of the heuristic approach proposed in §4.3 is also reported in Table 4. It’s seen that the approximation only results in a negligible loss as compared with the exact SDSIC method. Numerical examples of other demand functions (including the power and linear arrival rates) obtain the similar results and hence are not reported here. In summary, the above numerical experiments demonstrate that the proposed semi-dynamic seat inventory control, SDSIC, is fairly effective—it provides a good approximation to the “optimal policy” (the DP method) that adjusts the price continuously and reversely: all the revenue loss is within 3%. The heuristic solution for the case of more than 2 fare levels is also a good approximation method, which is much easier to implement than the exact SDSIC computational procedure. 6 Concluding remarks In this paper we study a semi-dynamic seat inventory control model in which the ticket price is only allowed to switch over time in an increasing order. Based on the arrival and choice (between buy and not-buy) behavior of passengers, we emphasis on the optimal seat allocation decision when there are only two fare levels. A heuristic solution is proposed for the multiple-fare-level case. The numerical examples show that the proposed model is a good approximation to that which allows dynamic and reverse price changes, and the heuristic method generally performs well. Two extensions are worth further considering. First, it is more realistic to assume that the passenger arrival rate, λ0, is non-homogeneous, and the distribution of their reservation price, f (p), can change over time. Second, in reality, cancellation and no-show may be present in the booking process, and it is thus natural to extend the current model to embrace overbooking. References Belobaba PP (1987) Air travel demand and airline seat inventory management. PhD thesis, Flight Transportation Laboratory, Massachusetts Institute of Technology, Cambridge, MA Bitran GR, Caldentey R (2003) An overview of pricing models for revenue management. Manuf Serv Oper Manag 5(3):203–229 Boyd EA, Kallesen R (2004) The science of revenue management when passenger purchase the lowest available fare. J Rev Pricing Manag 3(2):171–177 Brumelle SL, McGill JI (1993) Airline seat allocation with multiple nested fare classes. Oper Res 41(1):127–137 Brumelle SL, McGill JI, Oum TH, Sawaki K, Tretheway MW (1990) Allocation of airline seats between stochastically dependent demands. Transp Sci 24:183–192 Curry RE (1990) Optimum airline seat allocation with fare classes nested by origins and destinations. Transp Sci 24:193–204 Feng YY, Gallego G (1995) Optimal starting times for end-of-season sales and optimal stopping times for promotional fares. Manage Sci 41:1371–1391 Feng YY, Xiao BC (2000a) Optimal policies of yield management with multiple predetermined prices. Oper Res 48(2):332–343
On a semi-dynamic pricing and seat inventory allocation problem
103
Feng YY, Xiao BC (2000b) A continuous-time yield management model with multiple prices and reversible price changes. Manage Sci 46(5):644–657 Kimes SE (2002) Perceived fairness of yield management. Cornell Hotel Restaur Adm Q 43(1): 21–30 Lee TC, Hersh M (1993) A model for dynamic airline seat inventory control with multiple seat bookings. Transp Sci 27:252–265 Liang Y (1999) Solution to the continuous time dynamic yield management model. Transp Sci 33:117–123 Lin GY, Lu YD, Yao DD (2003) The stochastic knapsack revisited: structure, switch-over policies and dynamic pricing. Working Paper, IEOR Department, Columbia University, New York, NY Littlewood K (1972) Forecasting and control of passenger bookings. AGIFORS 12th Annual Symposium Proceedings, pp 95–128 McGill JI, Van Ryzin GJ (1999) Revenue management: research overview and prospects. Transp Sci 33(2):233–256 Pfeifer PE (1989) The airline discount fare allocation problem. Decis Sci 20:149–157 Robinson LW (1995) Optimal and approximate control policies for airline booking with sequential nonmonotonic fare classes. Oper Res 43(2):252–263 Ross SM (1996) Stochastic processes. 2nd ed. Wiley, New York Subramanian J, Stidham S, Lautenbacher CJ (1999) Airline yield management with overbooking, cancellations, and no-shows. Transp Sci 33(2):147–167 Talluri KT, Van Ryzin GJ (2004a) Revenue management under a general discrete choice model of consumer behavior. Manage Sci 50(1):15–33 Talluri KT, Van Ryzin GJ (2004b) The theory and practice of revenue management. Kluwer, New York Van Slyke R, Young Y (2000) Finite horizon stochastic knapsacks with applications to yield management. Oper Res 48:155–172 Van Ryzin GJ, McGill JI (2000) Revenue management without forecasting or optimization: an adaptive algorithm for determining airline seat protection levels. Manage Sci 46(6):760–775 Wollmer RD (1992) An airline seat management model for a single leg route when lower fare classes book first. Oper Res 40(1):26–37 Zhao W, Zheng YS (2000) Optimal dynamic pricing for perishable assets with nonhomogeneous demand. Manage Sci 46(3):375–388
