A I R L I N E Y I E L D M A N A G E M E N T — A D Y N A M I C S E A T A L L O C A T I O N M O D E L B y X iao Sun M . Eng . X i a n Jiaotong University A THESIS 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 R E Q U I R E M E N T S F O R T H E D E G R E E O F 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 A D M I N I S T R A T I O N 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 July 1992 © Xiao Sun, 1992 In presenting this thesis i n part ial fulfilment of the requirements for an advanced degree at the University of Br i t i sh Columbia , I agree that the L ibrary 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 my 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 my written permission. Faculty of Commerce and Business Administrat ion The University of B r i t i s h Co lumbia 2075 Wesbrook Place Vancouver, Canada V 6 T 1W5 Date: Abstract Suppose an airplane has a seat capacity of C, we have time T left before the airplane wi 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 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. 11 Table of Contents Abstract ii Acknowledgement iv 1 Introduction 1 2 Fomulation 6 2.1 Assumptions 6 2.2 Markov Decision Process 7 2.3 The Revenue Function 8 2.4 The Functional Equation 10 2.5 Some Properties of an O p t i m a l Pol icy 13 3 Nonhomogenous Poisson Process 16 3.1 Further Assumptions 16 3.2 The Solution of the Functional Equation 17 3.3 A n Algor i thm 21 3.4 Incremental Revenue and the Opt ima l Pol icy 27 3.5 The Proof of the Convergence 33 3.6 Littlewood's Formula vs. Opt imal i ty 36 4 T h e Directions of Further Research 43 Bibliography 44 m Acknowledgement I 'm very grateful to Professor Shelby L . Brumelle for his v i tal ly important supervision. I thank Professor Tae H . O u m and Professor M a r t i n L . Puterman for serving on my supervisory committee. I also thank Professor Derek R. Atkins for his encouragement. IV Chapter 1 Introduction The deregulation of North American Airl ines 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 wi th a significant operational problem — the problem of determining an opt imal booking policy: a booking policy which allocates optimally the seats of a particular airplane among the various fare classes. In other words, on the one hand, 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 maximize total revenue(Smith et al . 1992). Pr ior work on this problem falls into one of two categories and correspondingly, there are two distinct approaches to the problem. Firs t , those work which attemp network opti-m a l l y , the corresponding approach incorporates some or a l l complications, for example, multiple-flight itineraries, cancellations, overbookings, etc., v ia network flow and mathe-matical programming(Mayer 1976; Glover et al . 1982; Wol lmer 1986; Dror, Trudeau and Ladany 1988). Second, those work which studies the problem in isolated settings, the corresponding approach is based on some restrictive assumptions (Rothstein 1971; L i t t le -wood 1972; Bhat ia and Parekh 1973; Richter 1982; Alstrup et al . 1986; Belobaba 1987; 1 Chapter 1. Introduction 2 Curry 1990; Wollmer 1990a 1990b; Brumelle and M c G i l l 1991). This 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 optimization; while the second ap-proach may not produce globally opt imal solution it does produce easily implemantable solutions which are opt imal under the assumptions they are based. Those works which fall into the second category used either explicitly or impl ic i t ly 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: The demands for the different fare classes are mutually inde-pendent . 3. low fare booking first: The 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: The 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 in lower fare classes. Whi le assumption 6 is a common practice in airline reservation system today, assumptions 1 through 5 are restrictive. These sometimes overly restrictive assumptions serve the purpose of making the problem tractable. Chapter 1. Introduction 3 In 1972, Litt lewood 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 P2>PlP[X1>Pl], (1.1) where pi denotes the fare or average revenue from the z'th fare class, P[.] denotes proba-bil ity, X\ is ful l fare demand, and pi is the ful l fare protection level, the number of seats protected for the ful l fare passengers. The 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 ful l fare revenue from the seat. In 1982, Richter gave a marginal analysis which proved that (1.1) gives an optimal allocation. Wollmer( 1990b), Curry(1990), and Brumelle(1991) extended Littlewood's formula to multiple fare case. In Brumelle 's terms, under the Assumption 1 through 6 listed above the optimal protection levels p\,p2, • • -, can be obtained by finding the solutions to the following system of equations P2 = PlP[X1>p*] p3 = piP[X! >P*1nx1+x2> P*2] (1.2) P k + 1 = p1P[Xi>pinx1 + x2>p*2n---nx1 + x2 + --- + xk>pi]. where p*,i = 1,2, . . . , is the opt imal protection level, the optimal number of seats pro-tected, 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. We wi 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 many cases, this is equivalent to el iminating 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 in less total expected revenue. Intuitively, the assumption that low fare books first is equivalent to closing discount fare booking permanently when ful l fare booking begins. So Littlewood's formula 'makes sure' to accept enough discount fare passengers before closing the discount fare class, and in doing so it leaves too few seats to ful l fare passengers. This thesis shows that a model which takes the time remaining unt 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 in revenue per flight. This work resembles the work of Rothstein(1971) and Alstrup et al.(1986) in the sense that the problem is formulated as a nonhomogenous Markovian sequential decision pro-cess. Rothstein considered one class of passengers and Alstrup considered two classes of passengers. Our model accomodates finite number of classes of passengers without conceptual or computational difficulty. Bo th Rothstein and Alstrup discretized time dimension on daily basis; hence to actually compute an optimal 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 con-t inuum and prove the existence of an optimal policy v ia Contraction and Monotonicity Assumption. Further, in the case that the arrival processes are nonhomogenous Poisson we w i l l show that an optimal policy has a very simple structure and that an e-optimal policy can be found by solving a system of differential equations. The existence of an e-optimal policy guarantees us a practical way to approach optimal at any prespecified degree of precision. Chapter 2 Fomulation 2.1 Assumptions We wi l l make the following assumptions: • Assumption 1: single flight leg. Booking requests are begun to be accepted on the basis of a single departure and landing. • Assumption 2: arrival process. The arrival process is a semi-Markov process which does not depend on any booking policy. • Assumption 3: no cancellations, no overbookings. Cancellations, 'no-shows' and overbookings are not considered. Assumption 2 means that given a predetermined booking policy the state the system wi l l enter next depends on its past only through the current state of the system. We wi l l elaborate on this i n the next section. Whi l e Assumption 1 and Assumption 3 serve the purpose of simplifying the problem; Assumption 2 serves a double purpose: it make the problem tractable and in 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 i = 1,2, . . . ,m, without loss of generality we assume that p\ > p2 > ... > pm. 6 Chapter 2. Fomulation 2.2 Markov Decision Process The control of booking process can be formulated as a Markov decision process. Arrival Process: The arrival process can be described by a sequence of random vectors ( T J , <j>i), 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 in i t ia l state be UJ0 = (o:o, To, <j>a) = (C , T, 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 . The restriction of ir(s) = 0 for al l s = (0,t,f) is because of Assumption 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 distribution of (2.3) independent of IT. Transition Probability: Let Ps,a(s') is the probability distribution when the system is in state s, a policy 7r is used, and the system w i l l transition into state s' next. Given 7r, (2.4) is identical with (2.3). The system starts off at the in i t ia l state s0 = (C , T, 0). In any state s = (n,t,f), when an action a G {0,1} is taken, as a joint result of s and a two things happen: Chapter 2. Fomulation 9 2. the system moves to a new state s' according to probability distribution Ps,a(s'). then the above evolution starts al l over again begining from state s'. More specifically, if we accept a booking request, i.e. take action 1, we get revenue pf and the seat inventory wi 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 The revenue function of the system can be defined as This is just the summation of revenues we get in the booking process of a particular plane. Define Chapter 2. Fomulation 10 v-n-(s) — vv(n,t,f) is the expected revenue with current state s = ( n , t , / ) , i.e. the state that there are n empty seats and t t ime before departure, a booking request of class / just arrived, and a policy IT is followed. L e m m a 1 0 < vn(n,t,f) < np\ V(n,t,f)£S. This is tr iv ia l ly 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 wi l l not get any revenue. The significance of L e m m a 1 is that it implies that vn(s) is well defined for al l s £ S. Our objective is to find a policy 7r* which maps S onto D and generates v*(s0) = sup v„(s0), the max imal expected revenue where so is fixed at (C, T, 0). 2.4 The Functional Equation Suppose 7T*, an optimal policy, exists in the sense that v*(n,t,f) = v^(n,tj) = sup vv(n,t,f) (2.7) n = 0 , 1 , . . . , C 0 < t < T f = 1 , 2 , . . . , m where vv(n,t,f), (n,t,f) € 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 optimal policy is followed. L e m m a 2 v*(n,t,f) is nondecreasing in seat inventory n for each fixed time t and fare type f. Chapter 2. Fomulation 11 proof: We need to show that v*(n + k,t,f) > v*(n,t,f) for each k > 0. Suppose ir* is an optimal policy and 7r° is the policy defined by 7r*(m — k, t, / ) for m > k; 0 otherwise. Then v*(n + k,t,f) > vvo(n + k,tj) = v*(n,tj). L e m m a 2 simply says that under an optimal policy we can expect a larger revenue if we have more seats — a very important fact to get a simple structured optimal policy in our context. Let v(s) = v(n,t,f) be the solution to the following functional equation v(s) = max {r(s,a)+ f v{s') dPSya(s')} (2.8) ae{0,l} J s = (n,t,f) s' --- (n — a, q, k) s,s' e S In order to reveal the relationship between v(s) and v*(s) we introduce some terminology. Let B be the collection of al l bounded funtions from S to reals, and define a metric d on B as d(u, v) = sup I u(s) — v(s) I ses u G B v e B The space B is complete in this metric. Define h(s, a, v) = r(s, a) + J v(s') dPs^(s'). (2.9) Chapter 2. Fomulation 12 We w i l l assume h(s,a,v) satisfies 'Contraction Assumption ' in the sense that for some constant c such that 0 < c < 1, we have To satisfy the Contraction Assumption it is sufficient to have (2.13) has a unique solution v(s) if Contraction Assumption is met. Further Denardo asserts that if Monotonicity Assumption is met as well , then 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 Assumption requirement can be relaxed to 'N-stage Contraction Assumption ' to gurantee (2.14) to hold. In our context 'N-stage Contraction Assumption ' means that there is positive probability that the Nth booking request w i l l be the last one before the plane wi l l take off. A^ can be very large as long as it 's finite. This makes sense in 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 opt imal policy w(s). 2.5 Some Properties of an Opt imal Policy The functional equation (2.8) can be written out fully as the following v(n,t,f) = max < v(d,t,f) = 0 *>(M>/) = P f v(0,0,f) = 0 n = 1 , 2 , . . . , C 0 < t<T f = l , 2 , . . . , m Ek=i So H", ?, k)dP[(n, q, k) \ (n, t, / ) ; 0]; { Pf + ET=iSov(n-l,q,k)dP[(n-l,q,k)\(n,tjy,l) J (2.15) (2.16) (2.17) (2.18) Chapter 2. Fomulation 14 Define v •°(n,t,f) = v(n,qik)dP[(n,q,k)\(n,t,fy,0]; (2.19) v \n,t,f) = Pf + Y, / v{n-l,q,k)dP[{n-\,q,k) \ {n,t,f);\\ (2.20) fc=i where v°(n, t, f) is the expected revenue if the class / booking request is not accepted and follow an optimal policy after t; v1(n, t, f) is the expected revenue if the class / booking request is accepted and follow an optimal policy after t. Let 's enhance Assumption 2 by the following • Assumption 4: independent demand. The demands for the different fare classes are mutual ly independent. Assumption 2 and Assumption 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 Assumption 2 and Assumption 4 we wi l l have P[(n - a,q,k) | (n,t,f);a] P[(n — a, q, k) | t] (2.21) a € {0,1} 0 < q < t k = 1 , 2 , . . . , m Define then v \n,tj) = pf + 52 v(n-l,q,k)dP[(n-l,q, k)\t] = pf + 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 Corollary 2 Under an optimal policy the fare classes should be nested; i.e. if we accept f at state (n,t,f),n > 0, we accept the fare class i , i = l , 2 , . . . , / — 1 as well should they come. Chapter 3 Nonhomogenous Poisson Process 3.1 Further Assumptions To be more specific let's make the following Assumption 5. • Assumption 5: arrival processes. The arrival process of i t h , i = 1,2,... ,m, fare class is a nonhomogenous Poisson process {Ni(t) : t < T} wi th intensity function Xi(t), 0 < Xi(t) < +oo, which is piecewise continuous and has directional l imits at each point t, 0 < t < T; also these processes are independent of any policy being used in the booking process. Let A,-(t) = J t T A,(ç) dq, i = 1 , 2 , . . . , m, and m N(t) = 2 ^ ( 0 i=l m Ht) = I > « «=i m A(t) = Y, Ht)-i=l {N(t) : t < T} is the Poisson process with intensity \(t), the superposition of arrival processes of al l fare classes. If in some time interval where X(t) = 0 we can remove this period of t ime from the overall booking period T beforehand, so we wi l l assume without loss of generality that X(t) > 0. We shall inherit al l the assumptions we made in Chapter 1. 16 Chapter 3. Nonhomogenous Poisson Process Now we can write Ps,a(s') explicit ly in differential form (3.29) is consistent wi th the assumption that an action taken w i l l not affect arrival process but w i l l affect the state the system wi l l enter next. The following verifies that the Contraction Assumption is met 3.2 The Solution of the Functional Equation 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 in Chapter 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) Divide both side of (3.50) by At, let At approaches 0, and apply mean-value theorem to the first term of the righthand side we get Chapter 3. Nonhomogenous Poisson Process It's clear now that we only need to solve (3.51) with the following in i t ia l condition to solve the function equation (3.30)-(3.33). Chapter 3. Nonhomogenous Poisson Process Taking into account Corollary 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. The 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) 0 < t < T The existence and uniqueness of (3.61)-(3.62) has been established by the Contraction Assumption; 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 Theorem 1 The initial-value problem (3.61)-(3.62) has a unique solution V{t) on [0,T] if V(t,V(t)) is bounded and continuous on the strip I = {(t; V) | 0 < t < T , V G 3 £ a + 1 } and satisfies Lipschitz condition || V(t, U) - V(t, W)\\00<L\\U -W |U (3.63) for all t G [0, T] and all U, W G 3 £ c + 1 , L is a constant and || U ||oo= max I un I . 0<n<G Suppose Ai ( 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 = max I Vn(t,U)-vn(t,W) | 0<n<C < LWU-WU (3.64) L max I un — w. 0<n<G 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 {{oo (3.65) for some constant L'. A n d for any two functions gi,g2, i f they satisfy (3.65), then max(<7i,#2)5 <7i + 9i a l s ° satisfy (3.65) for some constant L". This k ind of reasoning can be extended to finite number of functions; and because (3.60) only involves addition and maximizat ion operations of some functions which is linear in U we can conclude that Lipschitz condition (3.64) is met indeed. In the case where Ai(t ) , \2(t) are piecewise continuous and their appropriate directional l imits exist as we have assumed ( Assumption 5) Lipschitz condition is st i l l satisfied and V(t,V(t)) is bounded, but piecewise continuous and its appropriate directional l imits exist as well. Noting 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 Theorem 1 is satisfied and then pieces together a solution to (3.61)-(3.62). Theorem 2 Let V(t),a < t < b, be a complete solution1 to the differential equation (3.61)-(3.62). Ifb^ +00 andti is a sequence such that ti —> 6, (£,• < b), and the sequence V(ti) has a limit e, then the point (6, e) is a boundary point. 1 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. Chapter 3. Nonhomogenous Poisson Process To solve (3.61)-(3.62) numerically we can discretize them 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 Theorem 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 Optimal Policy To further study the structure of the opt imal policy we make the following derivation. From (3.57) we can have Chapter 3. Nonhomogenous Poisson Process (3.73)-(3.75) are the following equivalent Chapter 3. Nonhomogenous Poisson Process 29 From (3.76) we conclude Chapter 3. Nonhomogenous Poisson Process Since equation (3.81)-(3.82) are derived from (3.61)-(3.62), all the statements we made about equation (3.61)-(3.62) are also valid in terms of (3.81)-(3.82); especially the solution to (3.81)-(3.82) exists, is unique in the interval [0,T], and can be computed by the one-step 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 Corollary 8 In the multiple fare case the optimal policy will accept booking requests from class 1 only in the 'region' R1 and accept booking requests from class 1 through class k, in the 'region' Rk, k = 2 , 3 , . . . , m. To prove the proposition we define two regions as the following Chapter 3. Nonhomogenous Poisson Process Further define Following Section 3.4 we define Chapter 3. Nonhomogenous Poisson Process or in matr ix form We have proven i n Section 3.4 that the monotone Chapter 3. Nonhomogenous Poisson Process 36 Uniform convergence implies (see Section 3.4) I p2 - Av(n, t) I < I p2 - Av°(n, t) \ + \ Av°(n, t) - Av(n, t) \ < I p2 - Av°(n,t) I + o (At) n = 0 , 1 , . . . , C 0 < t < T Suppose at t* we have Av°(n,t*) — p2, then | p2 — Av(n,t*) \< o(At). Let t be the time point at which we first have p2 — Av(n,t) < 0, apparently we have | t* — t |< A i ; hence Jo I 7T*(ra, t, 2) - 7r(n, t, 2)\dt< At, and || 7T* - 7T ||< m • C • At. The result follows. Corollary 9 | v-^^so) — Vjr(s0) \~* 0 as A t —> 0, where s0 — (C,T,0). 3.6 Littlewood's Formula vs. Optimality The optimality can be achieved by solving the differential equation either (3.61)-(3.62) or (3.81)-(3.82) and following the optimal policy indicated thereof. In Section 3.4 we have mentioned that t — n plane be divided into two regions and the dividing ' l ine ' is: p2 - Av°(n,t) = 0 (3.92) 0 < t < T n = 0 ,1 , . ..,C It's understood that the optimality is achieved by comparing the incremental optimal expected revenue of accepting requests from class 1 passengers only wi th that of accept-ing requests from both classes. Along the dividing ' l ine ' 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 maximal 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 ' l ine ' of the two regions can be found directly from (3.97), i.e. Chapter 3. Nonhomogenous Poisson Process i.e. the dividing ' l ine ' computed by Littlewood's formula wi l l lie below that computed by optimality 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 written out as the following Chapter 3. Nonhomogenous Poisson Process From (3.104) we can derive that To actually compute va(n, t, f) we only need to solve the system of differential equations (3.105). Comparing (3.105) with (3.57) and the boundary condition (3.53)-(3.55) we conclude Chapter 3. Nonhomogenous Poisson Process 42 i.e. The derivative of the expected revenue from policy a is small than that from optimal policy. Because two systems of differential equations have the same in i t ia l condition, we conclude that Littlewood's formula, even being used continuously overtime, underesti-mates the max imal expected revenue. The above conclusions also hold i n the multiple fare case. Chapter 4 The Directions of Further Research It seems immediate that the model we have developed can be extended in two directions. F i rs 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 Assumption 1, i.e. consider multi leg problem, a problem which is more realistic; but the structure of the opt imal policy, if exists, w i l l probably be complicated to interprète. 43 Bibliography Alstrup J . , S. Boas, O. B . G . Madsen, and R. V . V . V i d a l . 1986. Booking Policy for Flights wi th Two Types of Passengers. European Journal of Operational Reserach 27,274-288. Banerjee, P. K . and B . Viswanathan. 1989. O n Opt ima l Rationing Policies. Canadian Journal of Administrative Science 12, 1-6. Beckmann, M . J . 1958. Decision and Team Problems i n Air l ine Reservations. Econo-metrica 26, 134-145. Belobaba, P. P. 1987. A i r Travel Demand and Air l ine Seat Inventory Management. P h D Dissertation. M I T , Cambidge, Massachusetts. Belobaba, P. P. 1989. Appl icat ion of a Probablistic Decision Mode l to Air l ine Seat Inventory Control . Operations Research 37,183-197. Bhat ia , A . V . and S. C. Parekh. 1973. Opt imal Al location of Seats by Fare. Presen-tation by T W A Air l ine to A G I F O R S Reservations Study Group. Brumelle , S. L . , J . I. M c G i l l , T . H . O u m , M . W . Tretheway and K . Sawaki. 1990. Al locat ion of A i r l ine Seats Between Stochastically Dependent Demands. Transporta-tion Science,24,183-192. Curry, R. E . 1988. O p t i m u m Seat Al location wi th 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 Air l ine Seat Al locat ion wi th Fare Classes Nested by Origins and Destinations. Transportation Science 24 193-203. Deetman, C. 1964. Booking Levels, i n Proceedings J^th AGIFORS Symposium, A m . Airl ines, N . Y . , N . Y . Denardo, E . V . 1967. Contraction Mappings i n the Theory Underlying Dynamic Programming. Siam Review vol.9, No.2, 165-177. Desten, L . 1960. Een mathematisch model voor een reserveringsprobleem. Statistica Neerlandica 14, 85-94. Dror, M . , P. Trudeau and S. P. Ladany. 1988. Network Nodels for Seat Al location on Flights. Transportation Research B 22B, 239-250. 44 Bibliography 45 [14] Gerchak, Y . , M . Parlar and T . K . M . Yee. 1985. Opt imal Rationing Policies and Production Quantities for Products with 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. The Passenger M i x Prob-lem in the Scheduled Airl ines, Interfaces 12, 73-79. [16] Howard, R. A . 1960. Dynamic Programming. Princeton University Press, Princeton, N . J . , 1957. [17] Jorn , B . 1982. O p t i m a l Sales L imi ts for 2-Sector Fl ights, in Proceedings 25th AGI-FORS symposium, Athens, Greece. [18] K e n , W . 1983. O p t i m a l Seat Al location for Mult i l eg Flights with Mult ip le Fare Types, in Proceedings 23rd AGIFORS symposium, Memphis , Tennessee. [19] Ladany, S. 1976. Dynamic Operating Rules for Mote l Reservations. Decision Sci. 7, 829-840. [20] L iberman, V . and U . Yechiali . 1978. O n the Hotel Overbooking Problems. Mgmt. Sci. 24, 1117-1126. [21] Litt lewood, K . 1972. Forecasting and Control of Passengers, in Proceedings 12th AGIFORS symposium, American Airl ines, New York, 95-117. [22] Mart inez , R . , and M . Sanchez. 1970. Automatic Booking Level Control , i n Proceed-ings 10th AGIFORS Symposium. [23] Mayer , M . 1976. Seat Al locat in , or a Simple Mode l of Seat Al locat ion V i a Sophisti-cated Ones, in Proceedings 16th AGIFORS Symposium, 103-135. [24] M c G i l l , J . I. 1988. Air l ine Mult ip le Fare Class Seat Al location. Presented at Fa l l T I M S / O R S A Joint National Conference, Denver, Co. [25] M c G i l l , J . I. 1989. Opt imizat ion and Est imation Problems i n Air l ine Y i e l d Manage-ment. P h D dissertation, University of Br i t i sh Columbia , Vancouver, B . C . , Canada. [26] O u m , T . H . and M . W . Tretheway. 1986. Air l ine Seat Management. Logist. Trans. Rev. 22, 115-130. [27] Pfeifer, P. E . The Air l ine Discount Fare Al location Problem. Decision Sci. 20, 149-157. [28] Richter, H . 1982. The Differential Revenue Method to Determine Opt ima l Seat A l -lotments by Fare Type, in Proceedings 22nd AGIFORS Symposium, 339-362. Bibliography 46 Robinson, L . W . 1990. A Note on Belobaba's "Appl i cat ion of a Probabil istic Model to A i r l ine Seat Inventory Contro l " . Working Paper 90-03, Johnson Graduate School of Management, Cornell University, Ithaca, N Y . Rothstein, M . and A . W . Stone. 1967. Passenger Booking Levels, in Proceedings 7th AGIFORS Symposium, A m . Air l ines , N . Y . , N . Y.,1967. Rothstein, M . 1971. A n Air l ine Overbooking Model . Trans. Sci. 5(2), 180-192. Rothstein, M . 1985. O R and the Air l ine Overbooking Problem. Operations Research 33(2), 237-248. Shlifer, R. and Y . Vard i . 1975. A n Air l ine Overbooking Policy. Transportation Sci-ence 9, 101-114. Taylor, C. J . 1962. The Determination of Passenger Booking Levels, i n Proceedings 2nd AGIFORS Symposium. A m . Air l ines , N . Y . , N . Y . Thompson, H . R. 1961. Statistical Problems in Air l ine Reservation Control . Opnal. Res. Quart. 12. 167-185. Ti tze , B . and R. Greisshaber. 1983. Realistic Passenger Booking Behaviours and the Simple Low Fare /High Fare Seat Al lotment Model , in Proceedings 23rd AGIFORS Symposium. 197-223. Tretheway, M . W . 1989. Frequent Flyer Programs: Market ing Bonanza or A n t i -Competitive Tool. Proc. Can. Trans. Res. Forum 24, 433-446. Wollmer, R. D . 1986. A Seat Management Model for a Single Leg Route, unpublished company report, Douglas Aircraft Company, McDonnel l Douglas Corporation, Long Beach, C A . Wollmer, R. D . 1988. A Seat Management Model for a Single Leg Route when Lower Fare Classes Book Firs t . Presented at Fa l l T I M S / O R S A Joint National Conference, Denver, C O . Wollmer, R. D . 1990a. A n Air l ine Seat Management M o d e l for a Single Fl ight Leg. Working Paper, California State University, Long Beach, C A . Wollmer, R. D . 1990b. A n Air l ine Seat Management Mode l for a Single Leg Route when Lower Fare Classes Book Firs t . Working Paper, Cali fornia 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 |
FileFormat | 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 |
GraduationDate | 1992-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | 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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0086594/manifest