AIRLINE YIELD MANAGEMENT â€” A DYNAMIC SEAT ALLOCATION MODEL By Xiao Sun M. Eng. Xian Jiaotong University A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES FACULTY OF COMMERCE AND BUSINESS ADMINISTRATION We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA July 1992 Â© Xiao Sun, 1992 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library 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 Administration The University of British Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 Date: Abstract 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. 11 Table of Contents Abstract ii Acknowledgement v 1 Introduction 1 2 Fomulation 6 2.1 Assumptions2.2 Markov Decision Process 7 2.3 The Revenue Function 8 2.4 The Functional Equation 10 2.5 Some Properties of an Optimal Policy 13 3 Nonhomogenous Poisson Process 6 3.1 Further Assumptions 13.2 The Solution of the Functional Equation 17 3.3 An Algorithm 21 3.4 Incremental Revenue and the Optimal Policy 27 3.5 The Proof of the Convergence 33 3.6 Littlewood's Formula vs. Optimality 36 4 The Directions of Further Research 43 Bibliography 44 m Acknowledgement I'm very grateful to Professor Shelby L. Brumelle for his vitally important supervision. I thank Professor Tae H. Oum and Professor Martin 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 Airlines allows airlines to practice price competition. On 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. On the other hand, the deregulation challenges airlines with a significant operational problem â€” the problem of determining an optimal 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. On 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). Prior work on this problem falls into one of two categories and correspondingly, there are two distinct approaches to the problem. First, those work which attemp network opti mally, the corresponding approach incorporates some or all complications, for example, multiple-flight itineraries, cancellations, overbookings, etc., via network flow and mathe matical programming(Mayer 1976; Glover et al. 1982; Wollmer 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; Little-wood 1972; Bhatia and Parekh 1973; Richter 1982; Alstrup et al. 1986; Belobaba 1987; 1 Chapter 1. Introduction 2 Curry 1990; Wollmer 1990a 1990b; Brumelle and McGill 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 optimal solution it does produce easily implemantable solutions which are optimal under the assumptions they are based. Those works which fall into the second category used either explicitly or implicitly some or all 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: Any fare class can be booked into seats not taken by bookings in lower fare classes. While 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, Littlewood 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 bility, X\ is full fare demand, and pi is the full fare protection level, the number of seats protected for the full 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 full 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) Pk+1 = p1P[Xi>pinx1 + x2>p*2n---nx1 + x2 + --- + xk>pi]. where p*,i = 1,2,..., is the optimal 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 will call (1.2) Littlewood's type formula. Those works which fall into second category have another thing in common: they consider Chapter 1. Introduction 4 aggregate demands. In many 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 in 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 in doing so it leaves too few seats to full fare passengers. This thesis shows that a model which takes the time remaining until 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. Both 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 tinuum and prove the existence of an optimal policy via Contraction and Monotonicity Assumption. Further, in the case that the arrival processes are nonhomogenous Poisson we will 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 will 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 will enter next depends on its past only through the current state of the system. We will elaborate on this in the next section. While 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 ith 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 (TJ, <j>i), i = 1,2,...; where T,- denotes the time of the ith 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 initial 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,..., will 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 it. The restriction of ir(s) = 0 for all s = (0,t,f) is because of Assumption 3. If the current state is s = (n, t, /), then the next state will 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 will transition into state s' next. Given 7r, (2.4) is identical with (2.3). The system starts off at the initial 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 all 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 will 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 time before departure, a booking request of class / just arrived, and a policy IT is followed. Lemma 1 0 < vn(n,t,f) < np\ V(n,t,f)ÂŁS. This is trivially true because we cannot sell more than all the seats we have and pi is the highest revenue a seat can generate; and if we don't sell we will not get any revenue. The significance of Lemma 1 is that it implies that vn(s) is well defined for all s ÂŁ S. Our objective is to find a policy 7r* which maps S onto D and generates v*(s0) = sup vâ€ž(s0), the maximal 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. Lemma 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). Lemma 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 all 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 will 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 will be the last one before the plane will 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 optimal policy w(s). 2.5 Some Properties of an Optimal 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>/) = Pf 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 mutually independent. Assumption 2 and Assumption 4 together means that at an arrival epoch, whatever action is taken the arrival process will 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 will 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 ith, i = 1,2,... ,m, fare class is a nonhomogenous Poisson process {Ni(t) : t < T} with 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 in the booking process. Let A,-(t) = JtT 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 all fare classes. If in some time interval where X(t) = 0 we can remove this period of time from the overall booking period T beforehand, so we will assume without loss of generality that X(t) > 0. We shall inherit all the assumptions we made in Chapter 1. 16 Chapter 3. Nonhomogenous Poisson Process Now we can write Ps,a(s') explicitly in differential form (3.29) is consistent with the assumption that an action taken will not affect arrival process but will affect the state the system will enter next. The following verifies that the Contraction Assumption is met 3.2 The Solution of the Functional Equation In this section we will solve the functional equation (2.8) for v(so) in 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 initial 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 An 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-620 < 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'. And for any two functions gi,g2, if they satisfy (3.65), then max(<7i,#2)5 <7i + 9i alsÂ° satisfy (3.65) for some constant L". This kind of reasoning can be extended to finite number of functions; and because (3.60) only involves addition and maximization 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 limits exist as we have assumed ( Assumption 5) Lipschitz condition is still satisfied and V(t,V(t)) is bounded, but piecewise continuous and its appropriate directional limits 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 in 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) in 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) in 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. 1A 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 optimal 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': An analoguous analysis will lead to the conclusion that in the multiple fare case, the n â€” t plane will 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 matrix form We have proven in 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 |< Ai; 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 At â€”> 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 'line' 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 with that of accept ing requests from both classes. Along the dividing 'line' the two incremental expected revenues are equal. Chapter 3. Nonhomogenous Poisson Process 37 On 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 '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 will 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 initial condition, we conclude that Littlewood's formula, even being used continuously overtime, underesti mates the maximal expected revenue. The above conclusions also hold in 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. First, 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 multileg problem, a problem which is more realistic; but the structure of the optimal policy, if exists, will probably be complicated to interprĂ¨te. 43 Bibliography Alstrup J., S. Boas, O. B. G. Madsen, and R. V. V. Vidal. 1986. Booking Policy for Flights with Two Types of Passengers. European Journal of Operational Reserach 27,274-288. Banerjee, P. K. and B. Viswanathan. 1989. On Optimal Rationing Policies. Canadian Journal of Administrative Science 12, 1-6. Beckmann, M. J. 1958. Decision and Team Problems in Airline Reservations. Econo-metrica 26, 134-145. Belobaba, P. P. 1987. Air Travel Demand and Airline Seat Inventory Management. PhD Dissertation. MIT, Cambidge, Massachusetts. Belobaba, P. P. 1989. Application of a Probablistic Decision Model to Airline Seat Inventory Control. Operations Research 37,183-197. Bhatia, A. V. and S. C. Parekh. 1973. Optimal Allocation of Seats by Fare. Presen tation by TWA Airline to AGIFORS Reservations Study Group. Brumelle, S. L., J. I. McGill, T. H. Oum, M. W. Tretheway and K. Sawaki. 1990. Allocation of Airline Seats Between Stochastically Dependent Demands. Transporta tion Science,24,183-192. Curry, R. E. 1988. Optimum Seat Allocation with Fare Classes Nested on Segments and Legs. Technical Note 88-l,Aeronomics Incorporated, Fayetteville, GA. Curry, R. E. 1990. Optimum Airline Seat Allocation with Fare Classes Nested by Origins and Destinations. Transportation Science 24 193-203. Deetman, C. 1964. Booking Levels, in Proceedings J^th AGIFORS Symposium, Am. Airlines, N. Y., N. Y. Denardo, E. V. 1967. Contraction Mappings in 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 Allocation on Flights. Transportation Research B 22B, 239-250. 44 Bibliography 45 [14] Gerchak, Y., M. Parlar and T. K. M. Yee. 1985. Optimal 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. McMillan. 1982. The Passenger Mix Prob lem in the Scheduled Airlines, Interfaces 12, 73-79. [16] Howard, R. A. 1960. Dynamic Programming. Princeton University Press, Princeton, N. J., 1957. [17] Jorn, B. 1982. Optimal Sales Limits for 2-Sector Flights, in Proceedings 25th AGI FORS symposium, Athens, Greece. [18] Ken, W. 1983. Optimal Seat Allocation for Multileg Flights with Multiple Fare Types, in Proceedings 23rd AGIFORS symposium, Memphis, Tennessee. [19] Ladany, S. 1976. Dynamic Operating Rules for Motel Reservations. Decision Sci. 7, 829-840. [20] Liberman, V. and U. Yechiali. 1978. On the Hotel Overbooking Problems. Mgmt. Sci. 24, 1117-1126. [21] Littlewood, K. 1972. Forecasting and Control of Passengers, in Proceedings 12th AGIFORS symposium, American Airlines, New York, 95-117. [22] Martinez, R., and M. Sanchez. 1970. Automatic Booking Level Control, in Proceed ings 10th AGIFORS Symposium. [23] Mayer, M. 1976. Seat Allocatin, or a Simple Model of Seat Allocation Via Sophisti cated Ones, in Proceedings 16th AGIFORS Symposium, 103-135. [24] McGill, J. I. 1988. Airline Multiple Fare Class Seat Allocation. Presented at Fall TIMS/ORSA Joint National Conference, Denver, Co. [25] McGill, J. I. 1989. Optimization and Estimation Problems in Airline Yield Manage ment. PhD dissertation, University of British Columbia, Vancouver, B.C., Canada. [26] Oum, T. H. and M. W. Tretheway. 1986. Airline Seat Management. Logist. Trans. Rev. 22, 115-130. [27] Pfeifer, P. E. The Airline Discount Fare Allocation Problem. Decision Sci. 20, 149-157. [28] Richter, H. 1982. The Differential Revenue Method to Determine Optimal Seat Al lotments by Fare Type, in Proceedings 22nd AGIFORS Symposium, 339-362. Bibliography 46 Robinson, L. W. 1990. A Note on Belobaba's "Application of a Probabilistic Model to Airline Seat Inventory Control". Working Paper 90-03, Johnson Graduate School of Management, Cornell University, Ithaca, NY. Rothstein, M. and A. W. Stone. 1967. Passenger Booking Levels, in Proceedings 7th AGIFORS Symposium, Am. Airlines, N. Y., N. Y.,1967. Rothstein, M. 1971. An Airline Overbooking Model. Trans. Sci. 5(2), 180-192. Rothstein, M. 1985. OR and the Airline Overbooking Problem. Operations Research 33(2), 237-248. Shlifer, R. and Y. Vardi. 1975. An Airline Overbooking Policy. Transportation Sci ence 9, 101-114. Taylor, C. J. 1962. The Determination of Passenger Booking Levels, in Proceedings 2nd AGIFORS Symposium. Am. Airlines, N. Y., N. Y. Thompson, H. R. 1961. Statistical Problems in Airline Reservation Control. Opnal. Res. Quart. 12. 167-185. Titze, B. and R. Greisshaber. 1983. Realistic Passenger Booking Behaviours and the Simple Low Fare/High Fare Seat Allotment Model, in Proceedings 23rd AGIFORS Symposium. 197-223. Tretheway, M. W. 1989. Frequent Flyer Programs: Marketing Bonanza or Anti-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, McDonnell Douglas Corporation, Long Beach, CA. Wollmer, R. D. 1988. A Seat Management Model for a Single Leg Route when Lower Fare Classes Book First. Presented at Fall TIMS/ORSA Joint National Conference, Denver, CO. Wollmer, R. D. 1990a. An Airline Seat Management Model for a Single Flight Leg. Working Paper, California State University, Long Beach, CA. Wollmer, R. D. 1990b. An Airline Seat Management Model for a Single Leg Route when Lower Fare Classes Book First. Working Paper, California State University, Long Beach, CA.
- 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 | 1992 |
Date Issued | 2008-12-18T19:32:28Z |
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 |
Collection |
Retrospective Theses and Dissertations, 1919-2007 |
Series | UBC Retrospective Theses Digitization Project |
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
- ubc_1992_fall_sun_xiao.pdf [ 968.3kB ]
- Metadata
- JSON: 1.0086594.json
- JSON-LD: 1.0086594+ld.json
- RDF/XML (Pretty): 1.0086594.xml
- RDF/JSON: 1.0086594+rdf.json
- Turtle: 1.0086594+rdf-turtle.txt
- N-Triples: 1.0086594+rdf-ntriples.txt
- Original Record: 1.0086594 +original-record.json
- Full Text
- 1.0086594.txt
- Citation
- 1.0086594.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
China | 11 | 5 |
United States | 10 | 1 |
Poland | 4 | 0 |
Japan | 2 | 0 |
India | 2 | 1 |
France | 2 | 7 |
Germany | 1 | 43 |
Turkey | 1 | 0 |
City | Views | Downloads |
---|---|---|
Shenzhen | 6 | 2 |
Unknown | 6 | 43 |
Beijing | 5 | 3 |
Ashburn | 3 | 0 |
Bangalore | 2 | 0 |
Tokyo | 2 | 0 |
Wilmington | 2 | 0 |
Mountain View | 2 | 0 |
Istanbul | 1 | 0 |
Pullman | 1 | 0 |
Redmond | 1 | 1 |
San Jose | 1 | 0 |
Stuttgart | 1 | 1 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
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