UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Airline yield management : a dynamic seat allocation model Sun, Xiao 1992

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

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

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 .  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo 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

Comment

Related Items