AIRLINE YIELD — A DYNAMIC MANAGEMENT S E A T ALLOCATION M O D E L By X i a o Sun M . E n g . X i a n Jiaotong University A T H E S I S S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F T H E REQUIREMENTS FOR T H E DEGREE OF MASTER O F SCIENCE in T H E F A C U L T Y O F G R A D U A T E STUDIES F A C U L T Y O F C O M M E R C E A N D BUSINESS ADMINISTRATION We accept this thesis as conforming to the required standard T H E U N I V E R S I T Y O F BRITISH C O L U M B I A J u l y 1992 © X i a o Sun, 1992 In presenting this thesis i n partial fulfilment of the requirements for an advanced degree at the University of B r i t i s h C o l u m b i a , I agree that the L i b r a r y shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of m y department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without m y written permission. Faculty of Commerce and Business A d m i n i s t r a t i o n T h e U n i v e r s i t y of B r i t i s h C o l u m b i a 2075 Wesbrook Place Vancouver, C a n a d a V 6 T 1W5 Date: Abstract Suppose an airplane has a seat capacity of C, we have time T left before the airplane w i l l take off, the fare structure is given, and the arrival process of booking requests is stochastic, we want to know if there is an o p t i m a l policy to control booking process i n order to m a x i m i z e total expected revenue from this particular airplane. We formulate the problem as a continuous time M a r k o v decision problem. Under certain conditions the existence and some of the properties of an o p t i m a l policy are shown. In the case where the arrival process is a nonhomogenous Poisson it is shown that the o p t i m a l policy has a very simple structure and that an e-optimal policy can be easily computed. It is also shown that i n general 'Littlewood-type' formula, even being used continuously overtime, does not protect enough seats for full fare passengers and results i n less total revenue. 11 Table of Contents Abstract ii Acknowledgement iv 1 Introduction 1 2 Fomulation 6 2.1 Assumptions 6 2.2 M a r k o v Decision Process 7 2.3 T h e Revenue Function 8 2.4 The F u n c t i o n a l E q u a t i o n 10 2.5 Some Properties of an O p t i m a l P o l i c y 13 3 4 Nonhomogenous Poisson Process 16 3.1 Further Assumptions 16 3.2 T h e Solution of the Functional E q u a t i o n 17 3.3 A n Algorithm 21 3.4 Incremental Revenue and the O p t i m a l P o l i c y 27 3.5 T h e Proof of the Convergence 33 3.6 Littlewood's F o r m u l a vs. O p t i m a l i t y 36 T h e Directions of Further Research Bibliography 43 44 m Acknowledgement I ' m very grateful to Professor Shelby L . Brumelle for his v i t a l l y important supervision. I thank Professor Tae H . O u m and Professor M a r t i n L . P u t e r m a n for serving on m y supervisory committee. I also thank Professor Derek R . A t k i n s for his encouragement. IV Chapter 1 Introduction T h e deregulation of N o r t h A m e r i c a n Airlines allows airlines to practice price competition. O n the one hand, this helps to stimulate the demand for air travelling because of the resulting proliferation of discount fare booking classes; from managerial point of view it's beneficial to sell those otherwise empty seats at a discount fare. O n the other hand, the deregulation challenges airlines w i t h a significant operational problem — the problem of determining an o p t i m a l booking policy: a booking policy which allocates o p t i m a l l y the seats of a particular airplane among the various fare classes. In other words, on the one h a n d , we have the freedom to segment market through price differentiation. O n the other hand, we want to control the booking process by selling the right seats to the right passengers at the right prices and time to m a x i m i z e t o t a l revenue(Smith et a l . 1992). P r i o r work on this problem falls into one of two categories and correspondingly, there are two distinct approaches to the problem. F i r s t , those work which attemp network optim a l l y , the corresponding approach incorporates some or a l l complications, for example, multiple-flight itineraries, cancellations, overbookings, etc., v i a network flow and mathem a t i c a l programming(Mayer 1976; Glover et a l . 1982; W o l l m e r 1986; D r o r , Trudeau and Ladany 1988). Second, those work which studies the problem i n isolated settings, the corresponding approach is based on some restrictive assumptions (Rothstein 1971; L i t t l e wood 1972; B h a t i a and Parekh 1973; Richter 1982; A l s t r u p et a l . 1986; Belobaba 1987; 1 Chapter 1. Introduction 2 C u r r y 1990; W o l l m e r 1990a 1990b; B r u m e l l e and M c G i l l 1991). T h i s latter approach is the approach of this work. It seems there are problems for the first approach to fully take into consideration the stochastical nature of the problem to achieve global o p t i m i z a t i o n ; while the second approach may not produce globally o p t i m a l solution it does produce easily implemantable solutions which are o p t i m a l under the assumptions they are based. Those works which fall into the second category used either explicitly or i m p l i c i t l y some or a l l of the following assumptions: 1. single flight leg: Bookings are made on the basis of a single departure and landing. 2. independent demand: T h e demands for the different fare classes are m u t u a l l y independent . 3. low fare booking first: T h e lowest fare reservations requests arrive first, followed by the next lowest, etc. 4. no cancellations: Cancellations, 'no-show' and overbooking are not considered. 5. limited information: T h e decision to close a class is based only on the number of current bookings. 6. nested classes: A n y fare class can be booked into seats not taken by bookings i n lower fare classes. W h i l e assumption 6 is a common practice i n airline reservation system today, assumptions 1 through 5 are restrictive. These sometimes overly restrictive assumptions serve the purpose of m a k i n g the problem tractable. Chapter 1. Introduction 3 In 1972, L i t t l e w o o d considered the case where two classes of fares are offered. He proposed that an airline should continue to reduce the protection level for class 1 (full fare) seats as long as the fare for class 2 (discount) seats satisfy (1.1) P2>PlP[X > ], 1 Pl where pi denotes the fare or average revenue from the z'th fare class, P[.] denotes probability, X\ is full fare demand, and pi is the full fare protection level, the number of seats protected for the full fare passengers. T h e intiution here is clear—accept the immediate return from selling an additional discount seat as long as the discount revenue equals or exceeds the expected full fare revenue from the seat. I n 1982, Richter gave a marginal analysis which proved that (1.1) gives an o p t i m a l allocation. Wollmer( 1990b), Curry(1990), and Brumelle(1991) extended Littlewood's formula to multiple fare case. In Brumelle's terms, under the A s s u m p t i o n 1 through 6 listed above the o p t i m a l protection levels p\,p , • • -, can be obtained by finding the solutions to the 2 following system of equations P2 = p = 3 P[X >p*] Pl 1 piP[X! > * nx +x > P 1 1 *] 2 P 2 (1.2) P k + 1 = p P[Xi>pinx 1 1 + x >p* n---nx 2 2 1 + x + --- + 2 x >pi]. k where p*,i = 1 , 2 , . . . , is the o p t i m a l protection level, the o p t i m a l number of seats protected, for fare class 1 through i. Xi,i = 1 , 2 , . . . , is the demands of iih class booking requests. Note that the first of these equations is just Littlewood's formula expressed as an equation. W e w i l l call (1.2) Littlewood's type formula. Those works which fall into second category have another thing i n common: they consider Chapter 1. Introduction 4 aggregate demands. In m a n y cases, this is equivalent to eliminating time dimension from the problem. In practice, airlines realize that the Assumptions on which Littlewood's formula is based do not always hold, especially the assumption that low fare demand occurs before high fare demand. To compensate for the consequence of the failure of this assumption, airlines use Littlewood's formula repeatedly during a booking period. However, Littlewood's formula, even being used continuously over a booking period, does not protect enough seats for higher fare passengers, and results i n less total expected revenue. Intuitively, the assumption that low fare books first is equivalent to closing discount fare booking permanently when full fare booking begins. So Littlewood's formula 'makes sure' to accept enough discount fare passengers before closing the discount fare class, and i n doing so it leaves too few seats to full fare passengers. This thesis shows that a model which takes the time remaining u n t i l departure and which allows fare classes to reopen after being closed is computationally feasible. In comparison to Littlewood's formula, our model results considerable improvement i n revenue per flight. T h i s work resembles the work of Rothstein(1971) and A l s t r u p et al.(1986) i n the sense that the problem is formulated as a nonhomogenous M a r k o v i a n sequential decision process. Rothstein considered one class of passengers and A l s t r u p considered two classes of passengers. O u r model accomodates finite number of classes of passengers without conceptual or computational difficulty. B o t h Rothstein and A l s t r u p discretized time dimension on daily basis; hence to actually compute an o p t i m a l policy they aggregate booking requests on daily basis as well. The discretization is practical but from the Chapter 1. Introduction 5 viewpoint of modelling the problem it is somewhat arbitrary. We treat time as a cont i n u u m and prove the existence of an o p t i m a l policy v i a Contraction and Monotonicity A s s u m p t i o n . Further, i n the case that the arrival processes are nonhomogenous Poisson we w i l l show that an o p t i m a l policy has a very simple structure and that an e-optimal policy can be found by solving a system of differential equations. T h e existence of an e-optimal policy guarantees us a practical way to approach o p t i m a l at any prespecified degree of precision. Chapter 2 Fomulation 2.1 Assumptions We w i l l make the following assumptions: • A s s u m p t i o n 1: single flight leg. B o o k i n g requests are begun to be accepted on the basis of a single departure and landing. • A s s u m p t i o n 2: arrival process. T h e arrival process is a semi-Markov process which does not depend on any booking policy. • A s s u m p t i o n 3: no cancellations, no overbookings. Cancellations, 'no-shows' and overbookings are not considered. A s s u m p t i o n 2 means that given a predetermined booking policy the state the system w i l l enter next depends on its past only through the current state of the system. We w i l l elaborate on this i n the next section. W h i l e A s s u m p t i o n 1 and A s s u m p t i o n 3 serve the purpose of simplifying the problem; A s s u m p t i o n 2 serves a double purpose: it make the problem tractable and i n many practical cases it is true; it contains nonhomogenous Poisson process as a special case. Suppose we have m classes of booking requests and let the fare of i t h class be 1 , 2 , . . . , m , without loss of generality we assume that p\ > p2 > ... > 6 p. m i = Chapter 2.2 2. Fomulation M a r k o v Decision Process T h e control of booking process can be formulated as a M a r k o v decision process. Arrival (TJ, <j>i), Process: T h e arrival process can be described by a sequence of random vectors i = 1 , 2 , . . . ; where T,- denotes the time of the i t h booking request and (f>i the fare class. Suppose the seat inventory is £*; when the ith booking request arrives, then system state can be described by random vector u>i = (ai, r,-, </>;), i = 1 , 2 , . . . . State Space: Suppose booking requests are begun to be accepted time T before departure and airplane has a seat capacity of C. Let i n i t i a l state be UJ = (o:o, To, <j>a) = ( C , T , 0), 0 fare class 0 generates no revenue and is introduced only as a device to start the process; then LOi,i = 1 , 2 , . . . , w i l l take value from S defined as the following. Chapter 2. Fomulation 8 action 1 means to accept a booking request at a certain state and action 0 reject i t . T h e restriction of ir(s) = 0 for a l l s = (0,t,f) is because of A s s u m p t i o n 3. If the current state is s = (n, t, / ) , then the next state w i l l be s' = (n — 7r(n, t, / ) , r ' , <f>'); where given s, (r',<//) has the d i s t r i b u t i o n of (2.3) independent of IT. Transition Probability: Let Ps,a( ') is the probability distribution when the system is i n state s, a policy 7r is used, s and the system w i l l transition into state s' next. G i v e n 7r, (2.4) is identical w i t h (2.3). T h e system starts off at the i n i t i a l state s = ( C , T, 0). I n any state s = (n,t,f), 0 an action a G {0,1} is taken, as a joint result of s a n d a two things happen: when Chapter 2. 9 Fomulation 2. the system moves to a new state s' according to probability distribution P , (s'). s a then the above evolution starts a l l over again begining from state s'. M o r e specifically, if we accept a booking request, i.e. take action 1, we get revenue pf and the seat inventory w i l l be reduced by one; if we reject a booking request, i.e. take action 0, we don't get any revenue and the seat inventory remains unchanged. So we have T h e revenue function of the system can be defined as T h i s is just the summation of revenues we get i n the booking process of a particular plane. Define Chapter 2. Fomulation 10 is the expected revenue w i t h current state s = ( n , t , / ) , i.e. the state v-n-(s) — v (n,t,f) v that there are n empty seats and t t i m e before departure, a booking request of class / just arrived, and a policy IT is followed. Lemma 1 0 < v (n,t,f) n < np\ V(n,t,f)£S. T h i s is t r i v i a l l y true because we cannot sell more than a l l the seats we have and pi is the highest revenue a seat can generate; and if we don't sell we w i l l not get any revenue. T h e significance of L e m m a 1 is that it implies that v (s) is well defined for a l l s £ S. n O u r objective is to find a policy 7r* which maps S onto D and generates v*(s ) = sup 0 v„(s ), 0 the m a x i m a l expected revenue where so is fixed at ( C , T, 0). 2.4 T h e Functional E q u a t i o n Suppose 7T*, an o p t i m a l policy, exists i n the sense that v*(n,t,f) where v (n,t,f), v (n,t,f) = v^(n,tj) = sup v (n,t,f) (2.7) v 0,1,...,C n = 0 < t < T f = 1,2,...,m € S, is defined by (2.6). v*(n,t,f) is the expected revenue when the system is at state s = (n, i , / ) and an o p t i m a l policy is followed. L e m m a 2 v*(n,t,f) type f. is nondecreasing in seat inventory n for each fixed time t and fare Chapter 2. Fomulation 11 proof: W e need to show that v*(n + k,t,f) for each k > 0. Suppose ir* is > v*(n,t,f) an o p t i m a l policy and 7r° is the policy defined by 7r*(m — k, t, / ) for m > k; 0 otherwise. Then v*(n + k,t,f) > v o(n + k,tj) v = v*(n,tj). L e m m a 2 simply says that under an o p t i m a l policy we can expect a larger revenue if we have more seats — a very important fact to get a simple structured o p t i m a l policy i n our context. Let v(s) = v(n,t,f) be the solution to the following functional equation v(s) = m a x {r(s,a)+ s = s' --- (n — a, q, k) s,s' e f v{s') dP (s')} Sya (2.8) J ae{0,l} (n,t,f) S In order to reveal the relationship between v(s) and v*(s) we introduce some terminology. Let B be the collection of a l l bounded funtions from S to reals, and define a metric d on B as = sup I u(s) — v(s) I ses u G B v e B d(u, v) T h e space B is complete i n this metric. Define h(s, a, v) = r(s, a) + J v(s') dP ^(s'). s (2.9) Chapter 2. Fomulation 12 We w i l l assume h(s,a,v) satisfies 'Contraction A s s u m p t i o n ' i n the sense that for some constant c such that 0 < c < 1, we have To satisfy the Contraction A s s u m p t i o n it is sufficient to have (2.13) has a unique solution v(s) if Contraction A s s u m p t i o n is met. asserts that if Monotonicity Assumption is met as well, then Further Denardo Chapter 2. Formulation 13 where v* is defined by (2.7) and v is the solution to (2.13). Denardo has also shown that Contraction A s s u m p t i o n requirement can be relaxed to 'N-stage Contraction A s s u m p t i o n ' to gurantee (2.14) to hold. In our context 'N-stage Contraction A s s u m p t i o n ' means that there is positive probability that the Nth booking request w i l l be the last one before the plane w i l l take off. A^ can be very large as long as it's finite. T h i s makes sense i n reality because we cannot have infinite number of booking requests. Because of (2.14), we can find v*(s) by finding v(s) or vice versa; and because of the simplicity of the action set Z), if we can find u(s),for some s G S" we can easily figure out the corresponding value of the o p t i m a l policy 2.5 w(s). Some Properties of an O p t i m a l Policy T h e functional equation (2.8) can be w r i t t e n out fully as the following v(n,t,f) = Ek=i So H", ?, k)dP[(n, q, k) \ (n, t, / ) ; 0]; max < { Pf + ET=iSov(n-l,q,k)dP[(n-l,q,k)\(n,tjy,l) v(d,t,f) = 0 *>(M>/) = v(0,0,f) = n = 0 < f = (2.15) J (2.16) (2.17) P f (2.18) 0 1,2,...,C t<T l,2,...,m Chapter 2. Fomulation 14 Define v•°(n,t,f) = v \n,t,f) = (2.19) v(n, k)dP[(n,q,k)\(n,t,fy,0]; qi Pf + Y, / fc=i v{n-l,q,k)dP[{n-\,q,k) \ {n,t,f);\\ (2.20) where v°(n, t, f) is the expected revenue if the class / booking request is not accepted and follow an o p t i m a l policy after t; v (n, t, f) is the expected revenue if the class / booking 1 request is accepted and follow an o p t i m a l policy after t. L e t ' s enhance A s s u m p t i o n 2 by the following • A s s u m p t i o n 4: independent demand. T h e demands for the different fare classes are m u t u a l l y independent. A s s u m p t i o n 2 and A s s u m p t i o n 4 together means that at an arrival epoch, whatever action is taken the arrival process w i l l start stochastically anew. It's understood that a policy is assumed not to affect arrival process but it can affect seat inventory and hence affect the system state. Under A s s u m p t i o n 2 and A s s u m p t i o n 4 we w i l l have P[(n - a,q,k) | P[(n — a, q, k) | t] (n,t,f);a] a € 0 < q k = (2.21) {0,1} < t 1,2,..., m Define then v \n,tj) = p + 52 = p + v(n-l,q,k)dP[(n-l,q, k)\t] f f v°(n-l,t), (2.23) Chapter 2. Formulation the system of equations (2.15)-(2.18) is the following equivalent from the system of equations (2.24)-(2.28) we can infer the follwoing C o r o l l a r y 2 Under an optimal policy the fare classes should be nested; i.e. if we accept f at state (n,t,f),n come. > 0, we accept the fare class i , i = l , 2 , . . . , / — 1 as well should they Chapter 3 Nonhomogenous Poisson Process 3.1 F u r t h e r Assumptions To be more specific let's make the following A s s u m p t i o n 5. • A s s u m p t i o n 5: arrival processes. T h e arrival process of i t h , i = 1,2,... ,m, class is a nonhomogenous Poisson process {Ni(t) fare : t < T} w i t h intensity function Xi(t), 0 < Xi(t) < +oo, which is piecewise continuous and has directional limits at each point t, 0 < t < T; also these processes are independent of any policy being used i n the booking process. Let A,-(t) = J t A,(ç) dq, i = 1 , 2 , . . . , m, and T m N(t) = i=l 2 ^ ( 0 m Ht) = I>« «=i m A(t) = Y, Ht)- i=l {N(t) : t < T} is the Poisson process w i t h intensity \(t), the superposition of arrival processes of a l l fare classes. If i n some time interval where X(t) = 0 we can remove this period of time from the overall booking period T beforehand, so we w i l l assume without loss of generality that X(t) > 0. We shall inherit a l l the assumptions we made i n C h a p t e r 1. 16 Chapter 3. Nonhomogenous Poisson Process Now we can write P ,a(s') explicitly i n differential form s (3.29) is consistent w i t h the assumption that an action taken w i l l not affect arrival process but w i l l affect the state the system w i l l enter next. The following verifies that the Contraction A s s u m p t i o n is met 3.2 T h e Solution of the Functional E q u a t i o n In this section we w i l l solve the functional equation (2.8) for v(so) i n the nonhomog Poisson case as the following Chapter 3. Nonhomogenous Poisson Process Define from the system of equations (3.36)-(3.44) we can infer the same corollaries we did i n C h a p t e r 1. It's clear from the system of equations (3.36)-(3.44) that we only need to Chapter 3. Nonhomogenous Poisson Process We make the following derivation from (3.46) D i v i d e b o t h side of (3.50) by At, let At approaches 0, and apply mean-value theorem to the first t e r m of the righthand side we get Chapter 3. Nonhomogenous Poisson Process It's clear now that we only need to solve (3.51) w i t h the following i n i t i a l condition to solve the function equation (3.30)-(3.33). Chapter 3. Nonhomogenous Poisson Process Taking into account C o r o l l a r y 4 we can write (3.51) as 3.3 A n Algorithm For ease of exposition let's concentrate on the case that only two types of fares are offered, i.e. m = 2. T h e multiple fare (more than 2 types of fares are offered) case is analogous. Chapter 3. Nonhomogenous Poisson Process Chapter 3. Nonhomogenous Poisson Process 23 Using (3.58)-(3.60) we can write (3.57), (3.53),(3.54),(3.55) as V'(t) = V(t,V(t)) (3.61) V(0) = O (3-62) < t < T 0 T h e existence and uniqueness of (3.61)-(3.62) has been established by the Contraction A s s u m p t i o n ; however, to develop an algorithm to solve it practically and to prove the convergence of the algorithm we would like to use the following theorem from the theory of differential equation which states that T h e o r e m 1 The initial-value if V(t,V(t)) problem (3.61)-(3.62) is bounded and continuous and satisfies Lipschitz has a unique solution V{t) on [0,T] on the strip I = {(t; V) | 0 < t < T , V G 3 £ a + 1 condition || V(t, U) - V(t, W)\\ <L\\U for all t G [0, T] and all U, W G 3 £ c + 1 |U -W 00 (3.63) , L is a constant and || U ||oo= m a x I u n I . 0<n<G Suppose A i ( t ) , X^it) are continuous then V(t, V(t)) is continous and bounded and we need to verify that Lipschitz condition || V(t,U)-V(t,W) ||oo = < m a x I Vn(t,U)-v (t,W) n 0<n<C | (3.64) LWU-WU L 0<n<G m a x I u — w. n is met. } Chapter 3. Nonhomogenous Poisson Process 24 For any function g, if g(U) is a linear function of U, then \g{U)-g(W)[<L'\\U-W for some constant L'. {{oo A n d for any two functions gi,g , 2 (3.65) if they satisfy (3.65), then max(<7i,#2)5 <7i + 9i l s ° satisfy (3.65) for some constant L". This k i n d of reasoning can a be extended to finite number of functions; and because (3.60) only involves addition and m a x i m i z a t i o n operations of some functions which is linear i n U we can conclude that Lipschitz condition (3.64) is met indeed. In the case where A i ( t ) , \2(t) are piecewise continuous and their appropriate directional l i m i t s exist as we have assumed ( A s s u m p t i o n 5) Lipschitz condition is still satisfied and V(t,V(t)) is bounded, but piecewise continuous and its appropriate directional limits exist as well. N o t i n g that V(t) is continuous over the interval [0,T], we can divide the interval [0,T] into subintervals such that i n each of these subintervals V(t,V(t)) is continuous; while the above theorem of ordinary differential equation asserts the existence and uniqueness of the solution to (3.61)-(3.62) i n each of these subinterval the following theorem of ordinary differential equation asserts that the solution to (3.61)-(3.62) exists, is unique over the interval [0, T ] . So we can solve (refeq265)-(3.62) i n each subinterval of [0, T] where the conditions of T h e o r e m 1 is satisfied and then pieces together a solution to (3.61)-(3.62). T h e o r e m 2 Let V(t),a (3.61)-(3.62). V(ti) Ifb^ < t < b, be a complete solution + 0 0 andti 1 to the differential equation is a sequence such that ti —> 6, (£,• < b), and the sequence has a limit e, then the point (6, e) is a boundary point. A solution V(t), (a < t < b) of the differential equation (3.61)-(3.62) is a complete solution if there does not exist solution V\ (t) defined in a larger interval and coinciding with V(t) for a < t < b. 1 Chapter 3. Nonhomogenous Poisson Process To solve (3.61)-(3.62) numerically we can discretize t h e m as the following (3.61)-(3.62) can be solved numerically by the 'one-step' method defined as the following Chapter 3. Nonhomogenous Poisson Process T h e o r e m 3 The one step method defined by (3.68)-(3.69) is convergent in the sense Chapter 3. Nonhomogenous Poisson Process 27 It should be mentioned that the analysis of the multiple fare case is tedious but completely analoguous to what we have done so far. 3.4 Incremental Revenue and the O p t i m a l Policy To further study the structure of the o p t i m a l policy we make the following derivation. F r o m (3.57) we can have Chapter 3. Nonhomogenous Poisson Process (3.73)-(3.75) are the following equivalent Chapter 3. Nonhomogenous F r o m (3.76) we conclude Poisson Process 29 Chapter 3. Nonhomogenous Poisson Process Since equation (3.81)-(3.82) are derived from (3.61)-(3.62), a l l the statements we made about equation (3.61)-(3.62) are also valid i n terms of (3.81)-(3.82); especially the solution to (3.81)-(3.82) exists, is unique i n the interval [0,T], and can be computed by the onestep method defined as the following. Chapter 3. Nonhomogenous Poisson Process is the least integer that the theorem holds hence for some t we have Chapter 3. Nonhomogenous Poisson Process Because of the continuity and monotonicity of two disjoint 'regions': A n analoguous analysis w i l l lead to the conclusion that i n the multiple fare case, the n — t plane w i l l be divided into m disjoint 'regions': Chapter 3. Nonhomogenous Poisson Process C o r o l l a r y 8 In the multiple fare case the optimal policy will accept booking requests from class 1 only in the 'region' R 1 and accept booking requests from class 1 through class k, in the 'region' R , k = 2 , 3 , . . . , m. k To prove the proposition we define two regions as the following Chapter 3. Nonhomogenous Poisson Further define Following Section 3.4 we define Process Chapter 3. Nonhomogenous Poisson Process or i n m a t r i x form We have proven i n Section 3.4 that the monotone Chapter 3. Nonhomogenous Poisson Process 36 U n i f o r m convergence implies (see Section 3.4) I p - Av(n, t) I < I p - Av°(n, 2 2 < I p - Av°(n,t) n = 0,1,...,C 0 < t) \ + \ Av°(n, t) - Av(n, t) \ I + o (At) 2 t < T Suppose at t* we have Av°(n,t*) — p , then | p — Av(n,t*) 2 point at which we first have p — Av(n,t) 2 Jo I 7T*(ra, t, 2) - 7r(n, t, 2)\dt< \< o(At). 2 Let t be the time < 0, apparently we have | t* — t |< A i ; hence At, and || 7T* - 7T ||< m • C • At. T h e result follows. C o r o l l a r y 9 | v-^^so) — Vjr(s ) \~* 0 as A t —> 0, where s — 0 0 3.6 (C,T,0). Littlewood's F o r m u l a vs. O p t i m a l i t y T h e o p t i m a l i t y can be achieved by solving the differential equation either (3.61)-(3.62) or (3.81)-(3.82) and following the o p t i m a l policy indicated thereof. In Section 3.4 we have mentioned that t — n plane be divided into two regions and the dividing 'line' is: p - Av°(n,t) 0 < t < T n = 0,1,. 2 = 0 (3.92) ..,C It's understood that the o p t i m a l i t y is achieved by comparing the incremental o p t i m a l expected revenue of accepting requests from class 1 passengers only w i t h that of accepting requests from both classes. A l o n g the dividing 'line' the two incremental expected revenues are equal. Chapter 3. Nonhomogenous Poisson Process 37 O n the other hand, if we use Littlewood's formula instead at time t and we should protect n seats for the booking requests of first class passengers as long as n is the m a x i m a l integer which solves the following inequality Chapter 3. Nonhomogenous Poisson Process where we have used the subscript a to denote the policy determined by using Littlewood's formula continuously. Let U,i = 0 , 1 , . . . be the dividing points, the dividing 'line' of the two regions can be found directly from (3.97), i.e. Chapter 3. Nonhomogenous Poisson Process i.e. the dividing 'line' computed by Littlewood's formula w i l l lie below that computed by o p t i m a l i t y equation. In other words, Littlewood's formula does not protect enough seats for the first class passengers. Chapter 3. Nonhomogenous Poisson Process (3.100) can be w r i t t e n out as the following Chapter 3. Nonhomogenous Poisson Process F r o m (3.104) we can derive that To actually compute v (n, t, f) we only need to solve the system of differential equations a (3.105). conclude C o m p a r i n g (3.105) w i t h (3.57) and the boundary condition (3.53)-(3.55) we Chapter 3. Nonhomogenous Poisson Process 42 i.e. T h e derivative of the expected revenue from policy a is small than that from o p t i m a l policy. Because two systems of differential equations have the same i n i t i a l condition, we conclude that Littlewood's formula, even being used continuously overtime, underestimates the m a x i m a l expected revenue. T h e above conclusions also hold i n the m u l t i p l e fare case. Chapter 4 T h e Directions of Further Research It seems immediate that the model we have developed can be extended i n two directions. F i r s t , we may be able to take cancellation and overbooking into consideration possibaly at the cost of a more complicated state space. Second, we may remove A s s u m p t i o n 1, i.e. consider multileg problem, a problem which is more realistic; but the structure of the o p t i m a l policy, if exists, w i l l probably be complicated to interprète. 43 Bibliography A l s t r u p J . , S. Boas, O. B . G . Madsen, and R . V . V . V i d a l . 1986. B o o k i n g Policy for Flights w i t h T w o Types of Passengers. European Journal of Operational Reserach 27,274-288. Banerjee, P. K . and B . Viswanathan. 1989. O n O p t i m a l R a t i o n i n g Policies. Journal of Administrative Science 12, 1-6. Canadian B e c k m a n n , M . J . 1958. Decision and Team Problems i n A i r l i n e Reservations. Econometrica 26, 134-145. Belobaba, P. P. 1987. A i r Travel D e m a n d and A i r l i n e Seat Inventory Management. P h D Dissertation. M I T , Cambidge, Massachusetts. Belobaba, P. P. 1989. A p p l i c a t i o n of a Probablistic Decision M o d e l to A i r l i n e Seat Inventory C o n t r o l . Operations Research 37,183-197. B h a t i a , A . V . and S. C. Parekh. 1973. O p t i m a l A l l o c a t i o n of Seats by Fare. Presentation by T W A A i r l i n e to A G I F O R S Reservations Study G r o u p . B r u m e l l e , S. L . , J . I. M c G i l l , T . H . O u m , M . W . Tretheway and K . Sawaki. 1990. A l l o c a t i o n of A i r l i n e Seats Between Stochastically Dependent Demands. Transportation Science,24,183-192. Curry, R. E . 1988. O p t i m u m Seat A l l o c a t i o n w i t h Fare Classes Nested on Segments and Legs. Technical Note 88-l,Aeronomics Incorporated, Fayetteville, G A . Curry, R. E . 1990. O p t i m u m A i r l i n e Seat A l l o c a t i o n w i t h Fare Classes Nested by Origins and Destinations. Transportation Science 24 193-203. Deetman, C. 1964. B o o k i n g Levels, i n Proceedings J^th AGIFORS Airlines, N . Y . , N . Y . Symposium, Am. Denardo, E . V . 1967. Contraction Mappings i n the Theory U n d e r l y i n g D y n a m i c P r o g r a m m i n g . Siam Review vol.9, No.2, 165-177. Desten, L . 1960. E e n mathematisch model voor een reserveringsprobleem. Neerlandica 14, 85-94. Statistica Dror, M . , P. Trudeau and S. P. Ladany. 1988. Network Nodels for Seat A l l o c a t i o n on Flights. Transportation Research B 22B, 239-250. 44 Bibliography 45 [14] Gerchak, Y . , M . P a r l a r and T . K . M . Yee. 1985. O p t i m a l Rationing Policies and P r o d u c t i o n Quantities for Products w i t h Several Demand Classes. Canadian Journal of Administrative Science, 161-176. [15] Glover, F . , R . Glover, J . Lorenzo and C. M c M i l l a n . 1982. T h e Passenger M i x P r o b l e m i n the Scheduled A i r l i n e s , Interfaces 12, 73-79. [16] Howard, R . A . 1960. D y n a m i c Programming. Princeton University Press, Princeton, N . J . , 1957. [17] J o r n , B . 1982. O p t i m a l Sales L i m i t s for 2-Sector F l i g h t s , i n Proceedings 25th AGIFORS symposium, Athens, Greece. [18] K e n , W . 1983. O p t i m a l Seat A l l o c a t i o n for M u l t i l e g Flights w i t h M u l t i p l e Fare Types, i n Proceedings 23rd AGIFORS symposium, M e m p h i s , Tennessee. [19] Ladany, S. 1976. D y n a m i c Operating Rules for M o t e l Reservations. Decision Sci. 7, 829-840. [20] L i b e r m a n , V . and U . Yechiali. 1978. O n the H o t e l Overbooking Problems. Sci. 24, 1117-1126. [21] L i t t l e w o o d , K . 1972. Forecasting and C o n t r o l of Passengers, i n Proceedings AGIFORS symposium, A m e r i c a n A i r l i n e s , New Y o r k , 95-117. Mgmt. 12th [22] M a r t i n e z , R . , and M . Sanchez. 1970. A u t o m a t i c B o o k i n g Level Control, i n Proceedings 10th AGIFORS Symposium. [23] M a y e r , M . 1976. Seat A l l o c a t i n , or a Simple M o d e l of Seat A l l o c a t i o n V i a Sophisticated Ones, i n Proceedings 16th AGIFORS Symposium, 103-135. [24] M c G i l l , J . I. 1988. A i r l i n e M u l t i p l e Fare Class Seat A l l o c a t i o n . Presented at F a l l T I M S / O R S A Joint N a t i o n a l Conference, Denver, Co. [25] M c G i l l , J . I. 1989. O p t i m i z a t i o n and E s t i m a t i o n Problems i n A i r l i n e Y i e l d Management. P h D dissertation, University of B r i t i s h C o l u m b i a , Vancouver, B . C . , Canada. [26] O u m , T . H . and M . W . Tretheway. 1986. A i r l i n e Seat Management. Logist. Rev. 22, 115-130. [27] Pfeifer, P. E . The A i r l i n e Discount Fare A l l o c a t i o n P r o b l e m . Decision 157. Trans. Sci. 20, 149- [28] Richter, H . 1982. T h e Differential Revenue M e t h o d to Determine O p t i m a l Seat A l lotments by Fare T y p e , i n Proceedings 22nd AGIFORS Symposium, 339-362. 46 Bibliography Robinson, L . W . 1990. A Note on Belobaba's " A p p l i c a t i o n of a Probabilistic M o d e l to A i r l i n e Seat Inventory C o n t r o l " . W o r k i n g Paper 90-03, Johnson Graduate School of Management, Cornell University, Ithaca, N Y . Rothstein, M . and A . W . Stone. 1967. Passenger B o o k i n g Levels, i n Proceedings 7th AGIFORS Symposium, A m . A i r l i n e s , N . Y . , N . Y.,1967. Rothstein, M . 1971. A n A i r l i n e Overbooking M o d e l . Trans. Sci. 5(2), 180-192. Rothstein, M . 1985. O R and the A i r l i n e Overbooking P r o b l e m . Operations 33(2), 237-248. Research Shlifer, R . and Y . V a r d i . 1975. A n A i r l i n e Overbooking Policy. Transportation ence 9, 101-114. Sci- Taylor, C . J . 1962. T h e Determination of Passenger B o o k i n g Levels, i n Proceedings 2nd AGIFORS Symposium. A m . A i r l i n e s , N . Y . , N . Y . Thompson, H . R . 1961. Statistical Problems i n A i r l i n e Reservation Control. Opnal. Res. Quart. 12. 167-185. T i t z e , B . and R . Greisshaber. 1983. Realistic Passenger B o o k i n g Behaviours and the Simple Low F a r e / H i g h Fare Seat A l l o t m e n t M o d e l , i n Proceedings 23rd AGIFORS Symposium. 197-223. Tretheway, M . W . 1989. Frequent F l y e r Programs: M a r k e t i n g Bonanza or A n t i Competitive Tool. Proc. Can. Trans. Res. Forum 24, 433-446. Wollmer, R . D . 1986. A Seat Management M o d e l for a Single Leg Route, unpublished company report, Douglas Aircraft Company, M c D o n n e l l Douglas Corporation, Long Beach, C A . Wollmer, R . D . 1988. A Seat Management M o d e l for a Single Leg Route when Lower Fare Classes Book F i r s t . Presented at F a l l T I M S / O R S A Joint N a t i o n a l Conference, Denver, C O . Wollmer, R . D . 1990a. A n A i r l i n e Seat Management M o d e l for a Single F l i g h t Leg. W o r k i n g Paper, California State University, Long Beach, C A . Wollmer, R . D . 1990b. A n A i r l i n e Seat Management M o d e l for a Single Leg Route when Lower Fare Classes Book F i r s t . W o r k i n g Paper, California State University, Long Beach, C A .
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Airline yield management : a dynamic seat allocation...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Airline yield management : a dynamic seat allocation model Sun, Xiao 1992
pdf
Page Metadata
Item Metadata
Title | Airline yield management : a dynamic seat allocation model |
Creator |
Sun, Xiao |
Date Issued | 1992 |
Description | Suppose an airplane has a seat capacity of C, we have time T left before the airplane will take off, the fare structure is given, and the arrival process of booking requests is stochastic, we want to know if there is an optimal policy to control booking process in order to maximize total expected revenue from this particular airplane. We formulate the problem as a continuous time Markov decision problem. Under certain conditions the existence and some of the properties of an optimal policy are shown. In the case where the arrival process is a nonhomogenous Poisson it is shown that the optimal policy has a very simple structure and that an e-optimal policy can be easily computed. It is also shown that in general 'Littlewood-type' formula, even being used continuously overtime, does not protect enough seats for full fare passengers and results in less total revenue. |
Extent | 991540 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2008-12-18 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0086594 |
URI | http://hdl.handle.net/2429/3109 |
Degree |
Master of Science - MSc |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
Graduation Date | 1992-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_1992_fall_sun_xiao.pdf [ 968.3kB ]
- Metadata
- JSON: 831-1.0086594.json
- JSON-LD: 831-1.0086594-ld.json
- RDF/XML (Pretty): 831-1.0086594-rdf.xml
- RDF/JSON: 831-1.0086594-rdf.json
- Turtle: 831-1.0086594-turtle.txt
- N-Triples: 831-1.0086594-rdf-ntriples.txt
- Original Record: 831-1.0086594-source.json
- Full Text
- 831-1.0086594-fulltext.txt
- Citation
- 831-1.0086594.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0086594/manifest