Advances in Systems Science and Applications (2012) Vol.12 No.3 272-282 Improved Airline Seat Inventory Control Policies under Parametric Uncertainty of Customer Demand Models Nicholas A. Nechval1, Konstantin N. Nechval2 and Maris Purgailis1 1University of Latvia, EVF Research Institute, Statistics Department, Raina Blvd 19, LV-1050 Riga, Latvia 2Transport and Telecommunication Institute, Applied Mathematics Department, Lomonosov Street 1, LV-1019 Riga, Latvia Abstract Most models, which are used for solving airline seat inventory control problems, are developed in the literature under the assumptions that the parameter values of the models are known with certainty. When these models are applied to solve real-world problems, the parameters are estimated and then treated as if they were the true values. The risk associated with using estimates rather than the true parameters is called estimation risk and is often ignored. When data are limited and/or unreliable, estimation risk may be significant, and failure to incorporate it into the model design may lead to serious errors. In this paper, we consider the static and dynamic problems of airline seat inventory control under parametric uncertainty, which are invariant with respect to a certain group of transformations. Since common practice for airlines is to charge several different fares for a common pool of seats, this paper presents the policies that have been used to address the problem of when to refuse booking requests for a given fare level to save the seat for a potential request at a higher fare level. In this paper, we present the innovative technologies for constructing the static and dynamic policies of the airline seat inventory control.on the basis of the ‘unbiasedness performance index’. The idea of prediction of a future cumulative customer demand for the seats on a flight via the order statistics from the underlying distribution, introduced in the paper, allows one to use the invariant embedding technique in order to eliminate the unknown parameters from the problem and to use the previous and current sample data as completely as possible. The proposed unbiased static and dynamic policies are more efficient as compared with the policies, where the unknown parameters of the airline customer demand models are estimated and then treated as if they were the true values. An illustrative example is given. Keywords Airlines, demand, uncertainty, airline booking, optimization 1 Introduction Passenger reservations systems have evolved from low level inventory control pro- cesses to major strategic information systems. Today, airlines and other trans- portation companies view revenue management systems and related information Advances in Systems Science and Applications (2012) Vol.12 No.3 273 technologies as critical determinants of future success. Indeed, expectations of revenue gains that are possible with expanded revenue management capabilities are now driving the acquisition of new information technology. Each advance in information technology creates an opportunity for more comprehensive reserva- tions control and greater integration with other important transportation plan- ning functions. The airline seat inventory control problem lies at the heart of airline revenue management. It is common practice for airlines to sell a pool of identical seats at different prices according to different booking classes to improve revenues in a very competitive market. In other words, airlines sell the same seat at different prices according to different types of travelers (first class, business and economy) and other conditions. The question then arises whether to offer seats at a rela- tively low price at a given time with a given number of seats remaining or to wait for the possible arrival of a higher paying customer. Assigning seats in the same compartment to different fare classes of passengers in order to improve revenues is a major problem of airline seat inventory control. This problem has been con- sidered in numerous papers. For details, the reader is referred to a review of yield management, as well as perishable asset revenue management, by Weatherford et al. [1], and a review of relevant mathematical models by Belobaba [2]. This paper deals with the airline seat inventory control problem when cus- tomers for different fare levels are booked into a common seating pool in the aircraft. The following assumptions are made: (1) single-leg flight: bookings are made on the basis of a single departure and landing; no allowance is made for the possibility that bookings may be part of larger trip itineraries, (2) independent demands: the demands for different fare classes are stochastically independent, (3) low before high demands: the lowest fare reservations requests arrive first, followed by the next lowest, etc., (4) no cancellations: cancellations, no-shows and overbooking are not considered, (5) nested classes: any fare class can be booked into seats not taken by bookings in lower fare classes, (6) fare classes: the business and economy fare classes are considered. The first purpose of this paper is to present the innovative information tech- nologies for constructing the static and dynamic policies of the airline seat inven- tory control on the basis of the ‘unbiasedness performance index’. The static and dynamic policies (unbiased) are more efficient (from the point of view of airline revenue management) as compared with the policies, where the unknown param- eters of the airline customer demand models are estimated and then treated as if they were the true values. The second purpose of this paper is to introduce the idea of prediction of a future cumulative customer demand for the seats on a flight via the order s- tatistics from the underlying distribution, where only the functional form of the 274 Nicholas A. Nechval:Improved Airline Seat Inventory Control Policies under Parametric... distribution is specified, but some or all of its parameters are unspecified. This idea allows one to use the technique of invariant embedding of sample statistics in a performance index in order to eliminate the unknown parameters from the problem [3-4]. The technique represents a simple and computationally attractive statistical method based on the constructive use of the invariance principle in mathematical statistics. Unlike the Bayesian approach, an invariant embedding technique is independent of the choice of priors, i.e., subjectivity of investigator is eliminated from the problem. It allows one to find the improved invariant statistical decision rules, which have smaller risk than any of the well-known tra- ditional statistical decision rules, and to use the previous and current sample data as completely as possible. 2 State-of-the-art and Progress Beyond Airline seat inventory control is a very profitable tool in the airline industry. A major problem of airline seat inventory control is to sell the same seat at different prices according to different types of travelers (first class, business and economy) and other conditions in order to improve revenues. This problem has been considered in numerous papers. Littlewood [5] was the first to propose a solution method of the seat inventory control problem for a single leg flight with two fare classes. The idea of his scheme is to equate the marginal revenues in each of the two fare classes. He suggests closing down the low fare class when the certain revenue from selling low fare seat is exceeded by the expected revenue of selling the same seat at the higher fare. That is, low fare booking requests should be accepted as long as c2 ≥ c1Pr{Y1 > µ1}, (1) where c1 and c2 are the high and low fare levels respectively, Y1 denotes the de- mand for the high fare (or business) class,µ1 is the number of seats to protect for the high fare class and Pr{Y1 > µ1} is the probability of selling more than µ1 protected seats to high fare class customers. The smallest value of µ1 that satisfies the above condition is the number of seats to protect for the high fare class, and is known as the protection level of the high fare class customers. The concept of determining a protection level for the high fare class can also be seen as setting a booking limit, a maximum number of bookings, for the low fare class. Both concepts restrict the number of bookings for the low fare class in order to accept bookings for the high fare class. It should be remarked that there is no protection level for the low fare (or economy) class;µ2 is the booking limit, or number of seats available, for the low fare class; the low fare class is open as long as the number of bookings in this class remains less than this limit. Thus,is the booking limit, or number of seats available, for the low fare class; the low fare class is open as long as the number Advances in Systems Science and Applications (2012) Vol.12 No.3 275 of bookings in this class remains less than this limit. Thus, µ1+µ2 is the booking limit or number of seats available, for the high fare class at time. The high fare class is open as long as the number of bookings in this and low classes remain less than this limit. Richter [6] gave a marginal analysis, which proved that (1) gives an optimal allocation (assuming certain continuity conditions). Optimal policies for more than two classes have been presented independently by Curry [7], Wollmer [8], and Brumelle & McGill [9]. 3 Airline Booking Policies which are Used in Practice 3.1 Static Airline Booking Policy under Complete Information It will be noted that (1) represents the static policy of airline seat inventory control (or airline booking) under complete information. If Fθ , the probability distribution function of Y1 with the parameter θ (in general, vector), is continuous and strictly increasing, the definition (1) of µ1 is equivalent to µ1 = arg ( F̄θ(µ1) = γ ) (2) where γ = c1/c2, (3) F̄θ(τj) = 1− Fθ(τj). (4) 3.2 Static Airline Booking Policy under Parametric Uncertainty In practice, under parametric uncertainty, i.e. when the parameter θ is unknown, the performance index, F̄θ(µ1) = γ, (5) is usually used to construct the static policy given by µ1 = arg ( F̄θ̂(µ1) = γ ) , (6) where θ̂ represents the maximum likelihood estimator of θ . The performance index (5) is named as ‘maximum likelihood performance index’. The static poli- cy (6) based on (5) is named as ‘static maximum likelihood airline booking policy’. 3.3 Dynamic Airline Booking Policy under Parametric Uncertainty The static policy of airline booking is optimal as long as no change in the prob- ability distributions of the customer demand is foreseen. However, information on the actual customer demand process can reduce the uncertainty associated with the estimates of demand. Hence, repetitive use of a static policy over the booking period, based on the most recent demand and capacity information, is the general way to proceed. 276 Nicholas A. Nechval:Improved Airline Seat Inventory Control Policies under Parametric... 4 Improved Airline Booking Policies Proposed in the Paper 4.1 Static Unbiased Airline Booking Policy under Parametric Uncertainty This policy is based on the performance index, Eθ{F̄θ(µ1)} = γ, (7) which takes into account (2) and the previous data of cumulative customer de- mand Y1 for the seats on a flight. It allows one to construct the static airline booking policy given by µ (µnb) 1 = arg ( Eθ{F̄θ(µ1)} = γ ) , (8) where µ1 ≡ µ1(θ̂),θ̂ represents either the maximum likelihood estimator of θ or sufficient statistic S for θ, i.e., µ1 ≡ µ1(S) The performance index (7) is named as ‘unbiasedness performance index’.The static policy (8), which is based on (7), is named as ‘static unbiased airline booking policy’. The relative bias of the static airline booking policy is given by γ(µ1) = ∣∣Eθ{F̄θ(µ1)} − γ ∣∣ γ 100% (9) 4.2 Dynamic Airline Booking Policy under Complete Information In this section, we consider a flight for a single departure date with m predefined reading dates at which the dynamic policy is to be updated, i.e., the booking peri- od before departure is divided intom readings periods:(0, τ1], (τ1, τ2], . . . , (τm−1, τm] determined by them reading dates:τ1, τ2, . . . , τm. These reading dates are indexed in increasing order:0 < τ1 < τ2 < . . . < τm, where (τm−1, τm] denotes the reading period immediately preceding departure, and τm] is at departure. Typically, the reading periods that are closer to departure cover much shorter periods of time than those further from departure. For example, the reading period immediately preceding departure may cover 1 day whereas the reading period 1-month from departure may cover 1 week. Let us suppose that the cumulative passenger demand for the high fare class at the kth reading date (time τk, 1 ≤ k ≤ m) is Y1k representing the kth order statistic from the underlying distribution with the probability distribution func- tion Gθ(y1k), where θ is a parameter (in general, vector). In other words,Y1k represents the number of seats sold for the customers of the high fare class at the kth reading date. We assume that the cumulative passenger demands for the high and low fare classes are stochastically independent. Each booking of a seat of the high fare class generates average revenue of c1. Each booking of a seat of the low fare class generates average revenue of c2 , where c2 < c1.Let µ1k be an individual protection level for the high fare class at time τk (the kth Advances in Systems Science and Applications (2012) Vol.12 No.3 277 reading date).This many seats are protected for the high fare class from the low fare class. There is no protection level for the low fare class;µ2k is the booking limit for the low fare class at time τk; the low fare class is open as long as the number of bookings in this class remains less than this limit. Thus,µ1k + µ2k is the booking limit for the high fare class at time τk The high fare class is open as long as the number of bookings in this and low classes remain less than this limit. The maximum number of seats that may be booked by fare classes in the next at time τk prior to flight departure is the number of unsold seats µ◦ k. Under the complete information, the dynamic airline booking policy is given by µ1k = arg ( Ḡθ(µ1k|y1k) = γ ) , k = 1, 2, . . . ,m− 1, (10) where Ḡθ(µ1k|y1k) = 1−Gθ(µ1k|y1k), (11) Gθ(µ1k|y1k) represents the conditional probability distribution function of the mth order statistic Y1m . The number of unsold seats protected for the high fare class from the low fare class in the next at time τk prior to flight departure is the number of unsold seats,µ◦ 1k,which is given by µ◦ 1k = min(µ◦ k, µ1k − y1k). (12) 4.3 Dynamic Unbiased Airline Booking Policy under Parametric Uncertainty Under the parametric uncertainty, the dynamic unbiased airline booking policy is given by µunb 1k = arg ( Eθ{Ḡθ(µ1k|y1k)} = γ ) , k = 1, 2, . . . ,m− 1, (13) where µ1k ≡ µ1k(θ̂),θ̂ represents either the maximum likelihood estimator of θ or sufficient statistic S for θ, i.e.,µ1k ≡ µ1k(S).The number of unsold seats protected for the high fare class from the low fare class in the next at time τk prior to flight departure is the number of unsold seats µ◦ 1k,which is given by µ ◦(unb) 1k = min(µ◦ k, µ unb 1k − y1k). (14) 5 Mathematical Preliminaries Theorem 1 Let X1 ≤ . . . ≤ Xk be the first k ordered observations (order statis- tics) in a sample of size m from a continuous distribution with some probability density function fθ(x) and distribution function Fθ(x) where θ is a parameter (in general, vector). Then the joint probability density function of X1 ≤ . . . ≤ Xk and the lth order statistics Xl(1 ≤ k ≤ l ≤ m) is given by gθ(x1, . . . , xk, xl) = gθ(x1, . . . , xk)gθ(xl|xk), (15) 278 Nicholas A. Nechval:Improved Airline Seat Inventory Control Policies under Parametric... where gθ(x1, . . . , xk) = m! (m− k)! k∏ i=1 fθ(xi) [ 1− Fθ(xk) ]m−k , (16) gθ(xl|xk) = (m− k)! (l − k − 1)!(m− l)! [Fθ(xl)− Fθ(xk) 1− Fθ(xk) ]l−k−1[ 1− Fθ(xl)− Fθ(xk) 1− Fθ(xk) ]m−l fθ(xl) 1− Fθ(xk) = (m− k)! (l − k − 1)!(m− l)! k−l−1∑ j=0 ( l − k − 1 j ) (−1)j [ 1− Fθ(xl) 1− Fθ(xk) ]m−l+j fθ(xl) 1− Fθ(xk) = (m− k)! (l − k − 1)!(m− l)! m−l∑ j=0 ( m− l j ) (−1)j [Fθ(xl)− Fθ(xk) 1− Fθ(xk) ]l−k−1+j fθ(xl) 1− Fθ(xk) (17) represents the conditional probability density function of Xl given Xk = xk. Proof. The joint density of X1 ≤ . . . ≤ Xk and Xl is given by gθ(x1, . . . , xk, xl) = m! (l − k − 1)!(m− l)! k∏ i=1 fθ(xi) [ Fθ(xl)− Fθ(xk) ]l−k−1 fθ(xl) [ 1− fθ(xl) ]m−l =gθ(x1, . . . , xk)gθ(xl|xk). (18) It follows from (4) that gθ(xl|x1, . . . , xk) = gθ(x1, . . . , xk, xl) gθ(x1, . . . , xk) = gθ(xl|xk), (19) i.e., the conditional distribution of Xl, given Xi = xi for all i = 1, . . . , k, is the same as the conditional distribution of Xl, given only Xk = xk, which is given by (17). This ends the proof. Corollary 1.1. The conditional probability distribution function of Xl given Xk = xk is Pθ{Xl ≤ xl|Xk = xk} =1− (m− k)! (l − k − 1)!(m− l)! l−k−1∑ j=0 ( l − k − 1 j ) (−1)j m− l + 1 + j [ 1− Fθ(xl) 1− Fθ(xk) ]m−l+1+j = (m− k)! (l − k − 1)!(m− l)! m−k∑ j=0 ( m− l j )[Fθ(xl)− Fθ(xk) 1− Fθ(xk) ]l−k+j . (20) Advances in Systems Science and Applications (2012) Vol.12 No.3 279 Corollary 1.2.Let X1 ≤ . . . ≤ Xk be the first k order statistics in a sample of size m from the two-parameter Weibull distribution with the probability density function fθ(x) = δ β (x β )δ−1 exp [ −( x β )δ ] (x > 0), (21) where θ = (β, δ), β > 0 and δ > 0 are the scale and shape parameters, respective- ly. Then the conditional probability distribution function of Xl given Xk = xk is Pθ{Xl ≤ xl|Xk = xk} = 1− (m− k)! (l − k − 1)!(m− l)! l−k−1∑ j=0 ( l − k − 1 j ) (−1)j m− l + 1 + j [ exp(− xδl − xδk βδ ) ]m−l+1+j . (22) Theorem 2 If in (22) the scale parameter β is unknown, then the predictive probability distribution function of Xl based on (xk, δ) is given by Pδ {(Xl Xk )δ ≤ ( xl xk )δ ) } = 1− m! (l − k − 1)!(m− l)! × l−k−1∑ j=0 ( l − k − 1 j ) (−1)j m− l + 1 + j ( Πk−1 s=0 [(( xl xk )δ − 1 ) (m− j +1+ j) + (m− k+1+ s) ])−1 . (23) Proof.We reduce (22) to Pθ {(Xl Xk )δ ≤ ( xl xk )δ | (Xk β )δ = (xk β )δ} = 1− (m− k)! (l − k − 1)!(m− l)! l−k−1∑ j=0 ( l − k − 1 j ) × (−1)j m− l + 1 + j [ exp ( − ω[νδ − 1] )]m−l+1+j =Pδ{V δ ≤ νδ|W = ω} (24) where V = Xl/Xk is the ancillary statistic whose distribution does not depend on the parameter β. Since Xk does not depend on V ,W = (Xk/β) δ is the pivotal quantity, whose distribution is known and does not depend on the parameters β and δ, we eliminate the parameter β from the problem as Pδ{Xl ≤ xl} = ∫ ∞ 0 Pθ{Xl ≤ xl|Xk = xk}gθ(xk)dxk, (25) where gθ(xk) = m! (k − 1)!(m− k)! F k−1 θ (xk) [ 1− Fθ(xk) ]m−k fθ(xk), xk ∈ (0,∞), (26) 280 Nicholas A. Nechval:Improved Airline Seat Inventory Control Policies under Parametric... represents the probability density function of the kth order statistic Xk.Indeed, it follows from (26) that gθ(xk)dxk = m! (k − 1)!(m− k)! [ 1− exp ( − (xk β )δ)]k−1 exp ( − (xk β )δ(m−k) ) exp ( − (x β )δ) d (x β )δ = m! (k − 1)!(m− k)! [ 1− e−ω ]k−1 e−ω(m−k+1)dω = g(ω)dω. (27) It follows from (24) and (27) that Pδ{V δ ≤ νδ} = ∫ ∞ 0 Pδ{V δ ≤ νδ|W = ω}g(ω)d(ω) =1− m! (l − k − 1)!(m− l)! l−k−1∑ j=0 ( l − k − 1 j ) (−1)j m− l + 1 + j( Πk−1 s=0 [ (νδ − 1)(m− l + 1 + j) + (m− k + 1 + s) ])−1 . (28) Now (23) follows from (28). This ends the proof. Corollary 2.1.If the parameter δ = 1 , i.e., we deal with the exponential distri- bution, then the predictive probability distribution function of Xl based on xk is given by P {(Xl Xk ≤ xlxk )} =1− m! (l − k − 1)!(m− l)! × l−k−1∑ j=0 ( l − k − 1 j ) (−1)j m− l + 1 + j( Πk−1 s=0 [( xl xk − 1 ) (m− l + 1 + j) + (m− k + 1 + s) ])−1 . (29) 6 Illustrative Example of Airline Booking Policies Let X1, . . . , Xn be the random sample of the previous independent observations of the cumulative customer demand for the high fare class, which follow the exponential distribution with the probability density function (21)(δ = 1) , where the parameter β is unknown. Then the static policies of airline booking under parametric uncertainty are given as follows. Advances in Systems Science and Applications (2012) Vol.12 No.3 281 The static maximum likelihood airline booking policy follows from (6): µml 1 = ln γ−S/n, (30) where S = ∑n i=1Xi is the sufficient statistic for β,with V = S/β ∼ f(ν) = 1 Γ(n) νn−1 exp(−ν), ν ≥ 0, (31) and the relative bias, r(µml 1 ) = ∣∣Eθ{F̄θ(µ ml 1 )} − γ ∣∣ γ 100% = 1 + (1 + ln γ−1/n)−1 − γ γ 100%. (32) If, say,n = 1 and γ = 0.4, then rrb(µ ml 1 ) = 30%.Thus, in this example the static maximum likelihood airline booking policy has the relative bias equal to 30%.It follows that the protection level for customers of the high fare class will be determined incorrectly. This may lead to serious loss. The static unbiased airline booking policyfollows from (8): µunb 1 = [γ−1/n − 1]S, (33) where the relative bias r(µunb 1 ) = 0. The dynamic unbiased airline booking policyfollows from (13) and (29): µunb 1k = arg ( m! (m− k − 1)! m−k−1∑ j=0 ( m− k − 1 j ) (−1)j 1 + j ( Πk−1 s=0 [(µ1k y1k − 1 ) (1 + j) + (m− k + 1 + s) ])−1 = γ ) , k = 1, 2 . . . ,m− 1, (34) µ ◦(unb) 1k = min ( µ◦ k, µ unb 1k ,−y1k ) . (35) 7 Conclusion The methodology, which is developed in this paper for the use in the airline in- dustry under parametric uncertainty of airline customer demand models, may be found to be useful in other industries such as hotels, car rental companies, shipping companies, etc. While the details of problems considered in this project can change significantly from one industry to the next, the focus is always on making better demand decisions and not manually with guess work and intuition but rather scientifically with models and technology, all implemented with disci- plined processes and systems. 282 Nicholas A. Nechval:Improved Airline Seat Inventory Control Policies under Parametric... Acknowledgements This research was supported in part by Grant No. 06.1936, Grant No. 09.1014, and Grant No. 09.1544 from the Latvian Council of Science and the National Institute of Mathematics and Informatics of Latvia. References [1] Weatherford L.R., Bodily S.E. and Pfeifer P.E. (1993), “Modeling the cus- tomer arrival process and comparing decision rules in perishable asset rev- enue management situation”, Transportation Science, Vol.27, pp.239-251. [2] Belobaba P.P. (1987), “Airline yield management: an overview of seat in- ventory control”, Transportation Science, Vol.21, pp.66-73. [3] Nechval N.A., Berzins G., Purgailis M., Nechval K.N. (2008), “Improved estimation of state of stochastic systems via invariant embedding technique”, WSEAS Transactions on Mathematics, Vol.7, pp.141-159. [4] Nechval N.A., Nechval K.N., Purgailis M., Rozevskis U. (2011), “Improve- ment of inventory control under parametric uncertainty and constraints”, In: Dobnikar, A., Lotric, U., Ster, B. (eds.), Adaptive and Natural Computing Algorithms, LNCS, Vol.6594, Part II, pp.136-146, Springer, Heidelberg. [5] Littlewood K. (1972), “Forecasting and control of passenger bookings”, In: Proceedings of the 12th AGIFORS Symposium, pp.95-117, American Air- lines, New York. [6] I Richter H. (1982), “The differential revenue method to determine opti- mal seat allotments by fare type”, In: Proceedings of the XXII AGIFORS Symposium, pp.339-362, American Airlines, New York. [7] Curry, R.E. (1990), “Optimal airline beat allocation with fare classes nested by origins and destinations”, Transportation Science, Vol.24, pp.193-203. [8] Wollmer, R.D. (1992), “An airline seat management model for a single leg route when lower fare classes book first”, Operations Research, Vol.40, pp.26- 37. [9] Brumelle, S.L. and McGill, J.I. (1993), “Airline seat allocation with multiple nested fare classes”, Operations Research, Vol.41, pp.127-137. Corresponding author Nicholas Nechval can be contacted at:jnechval@junik.lv