D Y N A M I C C O N T R O L OF INVENTORIES O V E R FINITE HORIZON W I T H A N A P P L I C A T I O N TO A I R L I N E R E V E N U E MANAGEMENT By Darius Walczak M . Sc. (Applied Mathematics), Politechnika Wroclawska M . Sc. (Mathematics), University of British Columbia 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 THE REQUIREMENTS FOR T H E DEGREE OF DOCTOR OF PHILOSOPHY in T H E F A C U L T Y OF G R A D U A T E STUDIES 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 UNIVERSITY OF BRITISH C O L U M B I A July 2000 © Darius Walczak, 2000 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. Operations and Logistics Division, Faculty of Commerce and Business Administration The University of British Columbia 2053 Main Mall Vancouver, Canada V6T 1Z2 Date: Abstract When a customer requests a discount fare, the airline must decide whether to sell the seat at the requested discount or to hold the seat in hope that a customer will arrive later who will pay more. I model this situation for a single leg flight with multiple fare classes and customers who arrive according to a semi-Markov process (possibly nonhomogeneous). These customers can request multiple seats (batch requests) and can be overbooked. Under certain conditions, I show that the value function decreases as departure approaches. If each customer only requests a single seat or if the requests can be partially satisfied, then I show that there are optimal booking curves which decrease as departure approaches. I provide counterexamples to show that this structural property of the optimal policy does not hold in general. When customers are allowed to cancel I show that booking curves exist and may be monotone in certain cases. I also consider the situation where the customer's request size and fare offered are not known, but their joint probability distribution is available, and show that under certain conditions existence of booking curves obtains, and that under further assumptions, they are monotone. Finally, the theoretical results are used in realistic numerical examples, which are compared to certain deterministic upper bounds and revenues obtained under heuristic policies. The airline yield management problem described above is an instance of a generic revenue management problem, which, in turn, can be cast into a finite horizon semi-Markov dynamic optimal control problem. I provide examples of other applications of revenue management. ii Contents Abstract ii List of Figures vii Acknowledgements ix Dedication x I 1 Introduction 1.1 1.2 1.3 1.4 1.5 II Some Applications 4 1.1.1 Event Ticket Sales 4 1.1.2 Hotel Revenue Management 5 1.1.3 Option Selling 7 1.1.4 Product Rationing 7 1.1.5 Medical Services 8 1.1.6 School Admissions 9 Contribution of the Thesis 10 Thesis Layout 12 Literature Reviews 13 A General Finite Horizon Markov Renewal Decision Process 30 35 F u l l Information II. 1 Airline Seat Inventory Control with Full Information about Customer's Request 35 II.2 Airline Seat Inventory Management Problem As A Finite Horizon Semi-Markov Decision Process 36 iii 11.2.1 The Arrival Process 37 11.2.2 The Finite Horizon Semi-Markov Decision Process 38 11.2.3 The Revenue Function and Action Sets with Examples . . . . 43 11.2.4 Transformed Control Problems 11.3 Basic Results 47 51 II.3.1 Monotonicity of the Optimal Value Function with Respect to Time 53 11.4 Booking Curves for Splittable Batches 58 11.4.1 Existence of Booking Curves for Splittable Batches 59 11.4.2 Decreasing Booking Curves 61 11.5 Examples 66 11.5.1 A Discrete-time Counterexample for Lee & Hersh 67 11.5.2 A Continuous Time Counterexample for Lee k, Hersh 68 11.5.3 Single Requests Without Critical Time Property 70 11.5.4 Counterexample With Modified Accept/Reject 72 74 III Cancellations 111.1 Introduction 74 111.2 Modelling Issues 77 III.2.1 A Simple Cancellation Model with Nonrefundable Tickets . . . 79 111.3 Stochastic Concavity 83 111.4 Cancellations, Overbooking and No-Shows with Full Information . . . 84 111.4.1 Attributes of the Cancellations Process with Examples . . . . 87 111.4.2 Basic Results and Discrete Concavity 88 111.4.3 Monotonicity of the Value Function in Time 90 111.5 Condition for Monotone Booking Curves in Presence of Cancellations IV Partial Information 93 99 IV. 1 Dynamic Inventory Control with Partial Information about Customer Type 99 IV. 1.1 Market Segmentation, Diversion and Strategic Behaviour . . . 100 IV. 1.2 Sources and requests 101 IV.1.3 Offering Seats when Request Type is Unknown 101 iv IV. 1.4 Information Process 102 IV.2 Semi-Markov Decision Process with Partial Information IV.2.1 A More Specific Model 103 105 IV.3 Discrete Concavity with Partial Information 108 IV.3.1 Booking Curves with Partial Information 108 IV.3.2 Basic Results and Existence of Booking Limits 110 IV.4 Monotonicity in Time 118 IV.4.1 Monotone booking curves 120 IV.5 Supermodularity and the Optimal Revenue from the First Customer . 121 IV.6 Upper Bound for the Revenue Function 125 IV.7 An Omnibus Formulation 127 s IV. 7.1 Discussion of the Assumptions IV.8 Static vs. Dynamic Models 131 IV. 8.1 Discrete Time Model with Partial Information IV. 9 Examples of Chatwin [1999] V 131 133 Numerical Examples 135 V. l No-Shows and Overbooking 136 V. l . l Data 138 V.l.2 System of ODEs 139 V.l.3 Upper Bound 141 V.l.4 Solution 143 V.l.5 Optimal Policy 143 V.l.6 Computational Issues 144 V . l . 7 Conclusions V.2 130 146 Cancellations with No-Shows and Overbooking 148 V.2.1 System of ODEs and Its Solution 149 V.2.2 Case 1 151 V.2.3 Case 2 156 V.2.4 Case 3 156 V.3 Full vs. Partial Information 160 V.3.1 Partial Information 160 v V.3.2 Full Information 168 V.3.3 Full vs. Partial Information 172 V.3.4 Dynamic and Heuristic Policies 174 Bibliography 176 Bibliography 176 A 182 Appendix A.l Proof of Remark II. 1 182 A.2 Proof of Lemma III.3 183 A.3 184 Proof of Lemma III.8 A.4 Proof of Lemma IV.8 186 vi List of Figures 11.1 Graph of Av°(2,i) vs. time t 71 11.2 Graph of Av°(4,i) vs. time t 73 V.l Overbooking cost as a function of inventory. 140 V.2 Graph of A (t) 141 V.3 Graph of v° vs. time t, r\ = 440 144 V.4 Graph of J 145 V.5 Graph of ^j^- V.6 Graph of J V.7 Graph of V.8 Graph of J V.9 Graph of V.10 Booking curves, (-100,0] 151 V.ll Booking curves, (-400,0] 152 2 D D - v° vs. time t, rj = 440 100% vs. time t, 77 = 440 - v° vs. time t, 77 = 100 100% vs. time t, r? = 100 D - v° vs. time t, r) = 10 100% vs. time t, r? = 10 146 147 148 149 150 V.12 A7j°(440,t) < ATJ°(100,£) < Au°(10,£) 153 V.13 v°(100,t) and u^(100,t) vs. time t 153 V.14 v°(50,t) 154 andv° (50,i) vs. timet z V.15 v°(10,t) &ndv° (10,t) d vs. timet 154 V.16 Ai$(2,t), pi(t) vs. time 155 V.17 A7j°,(20,t) « 155 pi(t) vs. time V.18 u°(100,£) and u^(100,t) vs. time t 156 V.19 pi,...,p4 157 and L\v° for ry = 2, 5,15, 20 d V.20 v°j(100,t) is smaller than v°(100,t) only close to departure vii 158 V.21 Av° (lOO,t) < Av° (50,t) < Av° (20,t) < A^(10,i) < Av (2,t) time t cl cl d d vs. 159 V.22 p = 400 and Av°(30,t) vs. time t 160 V.23 Booking curves from highest (p ) to the lowest (pi) 161 V.24 Graph of J 163 4 4 D - v vs. time t, r/ = 300 Q g V.25 Graph of —f$- vs. time t, rj = 300 164 V.26 Graph of J 164 J D - v° vs. time t, r\ = 100 V.27 Graph of ^jfi vs. time t, n = 100 165 V.28 Booking curve, with first 30 critical times, partial information 167 V.29 Graph of Av° (300,t) vs. time t 167 g V.30 Graph of Jf - v° vs. time t, r) = 300 V.31 Graph of vs. time t 168 169 V.32 Booking curve, full information 170 V.33 Booking curve, first 30 critical times 171 V.34 Graph of v° — v° vs. time t, rj = 300, partial information 173 V.35 Graph of " ~o vs. time t, rj = 300, partial information 173 V.36 Graph of vs. time t, r? = 300, Littlewood's policy 175 V.37 Graph of vs. time t, rj = 100, Littlewood's policy 175 g 3 viii Acknowledgements My particular thanks go to Professor Shelby L. Brumelle, my research supervisor. Shelby introduced me to the revenue management, provided many contributions throughout the project and spent countless hours patiently reviewing and discussing it with me. Professors Tae Oum and Hong Chen, who served on my thesis committee, provided valuable suggestions to improve my research and monitored its progress throughout the years—I thank them greatly for that. I am grateful for the financial support I received over the years from the Operations and Logistics Division and the Faculty. My final, heartfelt thanks are due my family, especially my parents and my wife Malgorzata for all their encouragement and patience. ix Moim S. P. Dziadkom x Chapter I Introduction Yield management (or revenue management) is concerned with making efficient use of a given fixed resource that becomes worthless (or has a constant scrap value) after a given time. It uses controls such as booking or sales limits at various price levels. Yield management is particularly important in businesses, such as airlines, with low margin operations where an improvement of even a fraction of a percentage point can mean a significant increase in profit. The yield management methodology can be applied in many various settings that share those characteristics. In the next section I present a number of different examples to indicate the range of possible applications. Since the airline setting exhibits most of the yield management features that have to be modelled and since it seems to be researched best, I will use it as an instance of a generic yield management model in this thesis, together with corresponding terminology. From this chapter it should be clear that many terms that refer to airline industry can be interchanged with corresponding ones from other applications, with obvious restrictions. For example, instead of airline seats one could be selling bagels, though in the latter case cancellations or no-shows usually do not take place. (Although it is possible to imagine that a customer returns purchased bagels, it is hard to think of a baker re-selling those.) 1 2 CHAPTER I. INTRODUCTION A typical airline single-leg yield management problem is as follows. The airline sells seats on a plane departing at a certain date. The sales can start up to one year in advance and this interval of time is called the booking horizon. There are several classes of customers with each class paying different fare for a seat. This market segmentation is often achieved by imposing restrictions on customer classes paying less. The aircraft has a fixed capacity of seats and the objective is to maximize expected revenue from collected fares. When a request for a seat (booking request) arrives the airline can either accept it or reject it, and the particular action should depend on how many seats are left unsold (inventory on hand), how much time is left to departure, what customer is requesting (customer type) and possibly some other information. The goal of the revenue management is then to devise a policy of selling seats which maximizes the expected revenue from the initial inventory of seats. The policy should be simple enough to be described in terms facilitating applications, e.g. booking curves that divide the (inventory x bookinghorizon) space into two easily distinguishable accept/reject regions. In other words it is desirable that the policy possess certain structure. There are other factors that complicate the picture. A customer may not show up at departure (a no-show), he may also cancel in advance by letting the airline know that he will not be flying (a cancellation). Customers who do not show up or who cancel may be entitled to a refund. So it could be beneficial to sell more seats than the aircraft capacity. How many seats to overbook depends in turn on the cost of accommodating booked passengers who show up at departure and are in excess of the aircraft capacity. In reality, booking requests can arrive at any point during the booking horizon, and they arrive randomly. Frequency of requests depends on each class and may differ from one time interval to the other. For instance, full fare customers tend to book late, i.e. closer to departure date. Finally, the requests can be for one or more seats and may have to be accepted or rejected as a whole or it may be possible to satisfy them only partially (splittable batches). When the market segmentation is less pronounced, it can be worthwhile CHAPTER I. INTRODUCTION 3 to model customer's behaviour in response to an offered price, possibly given some indicators about his buying pattern. In other words the decision then will be to set the price. Following that a customer buys a ticket with probability depending on that price. I call this a situation with a partial information about customer's request as opposed to the full information case described earlier. My main objective in the thesis is to include all the aforementioned features in the single-leg model and then to study structural properties of the optimal value function and the optimal policy. In particular, under certain conditions the optimal seat allocation policy has a critical time property which is very desirable — namely, that for each inventory level rj and each arrival type (j) (for instance fare class and request size) there is a critical time t*(r),4>) such that it is optimal to sell a seat (at least one) to such a request whenever there are less than t*(r),<j)) units of time left until departure and to save the seat otherwise. I give conditions for this property to hold and examples of when it does not. In the latter case I provide assumptions that imply existence of booking limits. Booking limit is a number of seats that will not be sold to the current request (or a limit that one sells down to), given time, fare offered and possibly some additional information. The methods that I mainly use in this work are successive approximations and pathwise arguments (coupling) that exploit various concavity properties, as opposed to relying on backward induction or intensity control theory. I consider them more basic and general. For instance, a popular example of a request process is the Poisson process (usually homogeneous) for which it seems to be standard to use intensity control theory to demonstrate monotonicity results, especially so in the setting that corresponds to partial information. However, the same results follow from the ones developed for a more general nonhomogeneous semi-Markov process, and which can be obtained through successive approximation. This is, for instance, the case with the discrete concavity of the value function. CHAPTER I. INTRODUCTION Ll 4 Some Applications There are many actual and potential applications of the models described in the literature and this work. Particular examples are often scattered amongst various papers. The recent research overview by McGill & van Ryzin [1999], lists, with references, a number of applications in some important fields: airlines, passenger railways, nonprofit sector, lodging and hospitality, internet service provisions, cruise lines, broadcasting, car rentals. Others have reported applications in fashion industry (Gallego & van Ryzin [1994]), shipping industry, production (Gerchak et al. [1985]) and telecommunications. I tried to describe here a few examples, where models of this work could be potentially directly applied and which span across various sectors of life to underscore the flexibility of the approach. 1.1.1 Event Ticket Sales This is an example bearing a lot of similarities with the airline yield man- agement. The objective is to maximize expected revenue from selling ticket for seats at an event. The seats are worthless after an event has started (or a few minutes after), there are various classes of customers that can compete for the same seat, so when not enough of demand is expected for the highest priced seats, it might be profitable to sell them for less. It often happens in practice that the venues are not sold out. Alternatively, seats could be sold as part of certain deals, e.g. group sales to tour operators, receptions after an opera performance or a backstage party after a rock concert. There obviously are no-shows and cancellations which may lead to overbooking, and refunds might be present. Depending on the type of event, the booking horizon may be similar in length to airlines' and vary from a month to a year. The size of the problem for big arenas would be greater, namely in thousands of seats, but with demand relatively homogeneous farther from the event date, based CHAPTER I. INTRODUCTION 5 on my observations in Chapter V, the optimal policy should have a convenient form (constant intervals between critical times). 1.1.2 Hotel Revenue Management According to Bitran &; Gilbert [1996], the revenue management problem in this setting can be reasonably well approximated by assuming that reservations are for single rooms (this reflects quite well the situation in airport hotels and some motels), for one night only and with three classes of customers: guaranteed reservations, 6 p.m. hold reservations and walk-ins (the last one includes same-day reservations due to high probability of showing up). The rooms are assumed to be identical. Costs for turning down customers with a reservation should be significant (" walking customer"), and there may be a number of no-shows in the 6 p.m. hold reservation class as well as in the guaranteed reservation class. Bitran Sz Gilbert [1996] present a static model where the three types of guests arrive during nonoverlapping time intervals: 6 p.m. hold reservations arrive first, followed by walk-ins, with guaranteed reservations coming last. The problem is to find a policy of accepting or rejecting the walk-ins that maximizes the expected revenue. The problem fits into the dynamic setting of this thesis. The booking horizon is one day, (ends at midnight), there are three customer types with arrival intensity changing in time. No-shows and possibly cancellations are present, with a high overbooking cost. Since the model is dynamic we can allow for all types of customers to arrive at any time, but with the probabilities that reflect the fact that the bulk of each type arrives in certain time window. Group bookings for single nights can be included. When group reservations can be only partially satisfied then structural results of this work are applicable. From another point of view, different aspects of the hotel revenue management can be modelled. When expected demand for a certain type of suite in a given price category is below the capacity (number of rooms in that category) then it might be worthwhile to rent it at a lower price. An example of it would be a more luxurious CHAPTER I. INTRODUCTION 6 suite that could be rented at lower price or a room that can accommodate two or more persons that can be rented as a single room at lower price. Then ignoring multiple nights reservations, one can think of the problem as having a deadline at midnight of each date, i.e. for each date there is a number of rooms in a given price category. The booking horizon could be, say, 60-90 days and there might be costs associated with rejecting a customer. The problem can include cancellations, no-shows and overbooking. It may be cast either as a full information or partial information case. In the latter, given a request for a room, a customer will be offered a price, which he can accept or turn down. Under certain assumptions, the structural results given here imply that hotel staff could be given schedule that determines a number of rooms to be offered at each particular price, or, when probability distribution of accepting an offer is more general, a minimum acceptable price could be offered. A typical number of rooms that are available for customers is up to several hundreds for a single hotel. In that case it should be possible to use the software employed in this work to compute the optimal policy. Bitran & Mondschein [1995] describe a dynamic model (single night, simplified model without reservations, ibid.) that approximates Poisson arrivals by nonhomogeneous Bernoulli process with a finite number of customer types with the full information about each request, and which exhibits structural properties similar to those described here. A good review of earlier applications of revenue management in hotel industry is given in Bitran Sz Gilbert [1996]. There is a number of more recent articles in the hospitality journals that deal with hotel revenue management. It appears that more hotel chains are getting involved with various yield management systems provided through consulting companies. The share of the industry using a yield management system is estimated to be significantly higher than the reported 40% for 1998. An interesting feature is that there are companies that offer yield management services for hotels who do not want to maintain an in-house system. CHAPTER I. INTRODUCTION 1.1.3 7 Option Selling Suppose that a fixed number of options on certain stock can be sold before the strike date (each option could be for a block of shares, the type of options could be either call or put). The objective is to find a policy of disposing of the options so as to maximize expected revenue and might be especially useful when the seller and potential buyers value the options differently. All, some or none of the options could be sold. The state is described by a given time t to the expiry, number of options left and the current price of the underlying stock, say x. There is a terminal reward that depends on the difference in price of that stock on the strike date and the original amount paid for each option, and its expected value changes with time. Suppose that the seller models the price of the stock as a continuous time nonhomogeneous semi-Markov stochastic process, whose probability distribution is known. It could be for instance a compound nonhomogeneous Poisson process, although a more general semi-Markov process is probably more realistic. Immediately after each price change, the seller sets the price at which he offers the options to the market. It is assumed that a transaction (if any) at that price takes place before next change in stock's price. Cancellations and no-shows are not modelled as they are not very relevant in practice, but overbooking might be profitable and would correspond to selling the options short. The model as described above would fit into the partial information case, where the information process is the (independently defined) process describing the price of the underlying stock. Under certain assumptions, the results of this work would apply and would provide an easily applicable optimal policy described by critical times. 1.1.4 Product Rationing Suppose that a given number of units of a certain product have to be sold and shipped by a fixed deadline. The product after the deadline is either worthless or has only a salvage value. The product can be sold in several different markets at different total profit contribution per unit, due, for instance to varying transportation 8 CHAPTER I. INTRODUCTION costs or purchasing power of customers across the markets. No backordering is allowed. Orders for a product can come at any point during the booking horizon, can be multiple and it may be possible to satisfy them only partially. Orders can be cancelled before the deadline, if it is done before shipment. No-shows are possible in the following situation. Suppose that the product is shipped only after the payment is received. If that is the case, then orders for which no payment has been received by the deadline will correspond to no-shows, with the refund modelled as the value of the order less penalty for late cancelling. If either cancellations or no-shows can happen then it might be advantageous to accept more orders than the initial stock. The overbooking penalty would then reflect the loss of goodwill, or cost of finding another supply source for the missing stock, in either case it has to reflect the cost of short-selling the stock. 1.1.5 Medical Services I propose an application to optimally control access to a medical testing facility, for instance an MRI. There is a finite number of slots during each working day into which patients requiring the procedure can be booked. Splittable multiple bookings are conceivable, it could be for instance requests for the test originating in one place, e.g. in some remote hospital and arriving together. Unlike in the hotel revenue management, requests for test over a number of days should only be an exception. Assume that each patient's need for testing can be quantified, or that there exists urgency index, which could be used in a numerical criterion. For instance it could be better to test a patient with index 25 than one with index 10. Alternatively, one could assume that all patients are the same from the point of view of the facility. The objective then is to maximize the expected value of the total index (sum of all indices) over the booking horizon of a few months (in the second case one would maximize the expected number of patients tested). Cancellations, and to some extent no-shows (but likely no refunds) can happen that can be due to either improvement or decline in patients health, and each can be seen as happening 9 CHAPTER I. INTRODUCTION independently. The index of patient requesting a test will usually be known so the full information setting might be appropriate. 1.1.6 School Admissions Zhao &; Zheng [1999] mention that revenue management can be applied to a school admission problem. I propose two models that differ in their respective criteria, and which fit easily in the framework of the thesis. Assume that there is a clearly defined and quantifiable criterion. It might be, for instance, the total GPA over new students at the beginning of an academic year (but another blended criteria would do as well). Students usually apply with several institutions. This and other factors (events in personal life, etc.) cause a significant number of cancellations. There might also be no-shows, due for instance, to student's sudden change of planes without informing the institution in question. Cost of overbooking will be most likely caused by increased demand for instructional resources given a limited operational budget. The booking horizon will be typically up to a year. It is probably best modelled as a full information case since it is customary to request a GPA (or results of certain tests) from a student before responding to application. With a large number of individuals independently applying for admission, a nonhomogeneous Poisson model might be suitable. Another possible criterion that can be thought of, takes into account the cost of a student to the institution. As evidenced by recent discussion about the tuition fee structure at UBC, it is clear that given a pool of students who all are acceptable based on some academic criteria, those who bring external funding will constitute lower cost (usually in form of a top-up) than those who need internally based sources of funding. Cancellations and no-shows are bound to happen due to similar factors as before: apart from personal reasons, students usually apply with a number of institutions, and here in addition, chances are that students with external funding may be subject to a bidding process and will follow the better offer at short notice. The model described here may be particularly suitable to graduate research 10 CHAPTER I. INTRODUCTION based programs within each faculty. 1.2 Contribution of the Thesis Implementing optimal seat allocation policies can mean significant increase in profit. It is particularly important in businesses that operate in low-margin environment, such as airlines. The thesis presents and investigates properties of a mathematical model that can be applied to a real-life situation. Realistic conditions are given for a structured optimal policy, which makes its calculation easier in applications. The continuous time, finite horizon, nonhomogeneous semi-Markov dynamic control problem with batch requests, although it uses existing concepts, does not seem to have been presented in the OR literature. As well, a yield management application of this more general model seems to be missing from the literature. Existing published dynamic control models are usually formulated for less general customer arrival processes: discrete time, deterministic or nonhomogeneous Bernoulli, homogeneous Poisson. Most are for single arrivals and do not include overbooking. Specifically, there seem to be no published results asserting existence and (under natural assumptions) monotonicity of booking curves even when booking requests arrive according to nonhomogeneous semi-Markov process in presence of overbooking and no-shows only (no cancellations). I provide those and apply them in realistic-size numerical examples obtained with a readily available software. Models in this thesis use a more general customer arrival process, which should be sufficient for airline applications. Multiple fare classes are allowed. Arrivals can be nonhomogeneous in time, which is important for modelling of arrivals (of booking requests) with intensities that change over the booking horizon. Arrival processes for different fare classes can be correlated as long as they form a semiMarkov process. Closing and reopening of fares is allowed. The thesis gives sufficient conditions for structural properties of the value function and the optimal policy CHAPTER I. INTRODUCTION 11 and provides examples where the properties break down for more general arrival processes. A counterexample for the critical time property (cf. Lee Sz Hersh [1993]) is included when the arrival process is nonhomogeneous in time and batches have to be accepted or rejected as a whole. To better model reality I allow cancellations and show existence of the booking curves in the semi-Markov setting when cancellations satisfy the requirement of stochastic concavity. This generalizes results of Lewis et al. [1999] and Chatwin [1998] (single fare class), obtained for a controlled birth and death process and Subramanian et al. [1997] (the case with the same total inventory state variable). In that setting, I provide a new proof of a condition for monotonicity of the booking curves (Lewis et al. [1999]), which may point to some generalizations. Finally, I consider a situation where the customer's request size and fare is not known, but their joint distribution is available. The airline learns about the true type of request after the transaction has taken place. This includes the Poisson arrivals, single requests setting of Zhao Sz Zheng [1999], and some of the models in Gallego &; van Ryzin [1994]. I formulate it as a finite horizon semi-Markov control problem with a general state space, where the state consists of current inventory, time and the information variable (possibly a probability distribution). Given a request, the airline has to determine how many seats to allocate at each price. Under certain assumptions, for each particular value of the information variable and time, the existence and in some cases monotonicity of the booking curves is demonstrated. This more general formulation includes, in addition to the model already described in the beginning, salient static optimization results (Brumelle &; McGill [1989], Robinson [1995]). It seems that the distinction between models with either full or partial information about customer's request has not always been noticed in the literature, especially in earlier papers. This may have been due to the fact that in the partial information situation structural properties of both are the same, whenever requests are single and the processes involved are homogeneous in time. I provide examples where they differ (cf. also Zhao &; Zheng [1999], single requests CHAPTER I. INTRODUCTION 12 Poisson setting). The semi-Markov decision process employed in the thesis elucidates questions raised recently in examples of Chatwin [1999] concerning optimality of booking limit type policy when demands are correlated (Section IV.9). I also believe that the methods used in this work: successive approximations and pathwise arguments (coupling), are more fundamental and intuitive than, respectively, the backward induction used in nonhomogeneous Bernoulli models or the intensity control theory that seems to be the tool of choice in most articles that deal with monotonicity in time (Poisson models). The results of the thesis should lead to more efficient algorithms for computing the optimal policy, which in turn should induce the practitioners of yield management to using optimal seat allocation policies as opposed to various suboptimal policies now mainly in use. On the theoretical side, they might provide inspiration to search for better sufficient conditions and for asymptotic results to further facilitate the computation of the optimal dynamic policies. 1.3 Thesis Layout In the foregoing section, I have provided examples of the yield management in areas other than airlines, to which models of this thesis could be directly applied. In the forthcoming section I review salient articles dealing with dynamic models of yield management and provide comparisons to this work wherever warranted. The last section presents an abstract formulation of the semi-Markov, finite horizon, dynamic control problem, which serves as a theoretical basis for other chapters. Chapter II is the basic chapter of this work and it is fairly self-contained. Therein a number of key concepts and definitions is introduced. In that chapter, I am primarily concerned with the situation where the controller (the airline) knows precisely what the customer requests and where multiple requests as well as no-shows and overbooking are allowed. A number of examples and counterexamples concludes CHAPTER I. INTRODUCTION 13 it. The more general models of Chapters III and IV do inherit some of the properties of the full information model. So later on, to avoid repeating in some cases essentially the same proofs, I refer, wherever necessary to results in the full information case. In Chapter III, I consider the same basic model of the foregoing chapter but in presence of cancellations. Some issues related to modelling of cancellations are discussed and sufficient assumptions are given for the existence of booking curves along with a theorem. Monotonicity of the optimal expected value function is investigated. The chapter concludes with the section on monotonicity of booking curves when the booking requests process can be modelled as a birth and death continuous time process. In the last main chapter, Chapter IV, I generalize the full information setting to one where size and fare of customer's request are only known up to a probability distribution. Under natural assumptions on that joint distribution, I give results on existence and monotonicity of booking curves and the optimal expected revenue. A short section presenting typical assumptions for a model with no-shows, overbooking and cancellation when only partial information about a customer is available closes the chapter. The purpose of the final Chapter V is to apply and illustrate the theoretical results of previous three chapters by means of realistic numerical examples. Here, "realistic" refers to the size of the problem that can be solved in practice. The solutions I obtain using Mathematica are compared to deterministic upper bounds and, in some cases, to those resulting from heuristic policies. It contains a number of graphs of optimal expected value functions, expected increments, and booking curves. 1.4 Literature Reviews Over the last forty or so years the literature has offered us a sizable number of applications, heuristics and partial results obtained under various restrictions. CHAPTER I. INTRODUCTION 14 Many models are static, only allow the use of inventory information, and assume that lower fare classes book first. In that category the papers by Brumelle et al. [1992] and Brumelle & McGill [1993] offer an analysis. The series of papers by Gallego & van Ryzin [1994,1997] and Gallego & Feng [1995] gives a set of optimality conditions, useful heuristics and examples of the dynamic pricing question when the demand is a function of price. As far as dynamic programming models the literature is relatively scarce, and even more so when booking requests arrive according to continuous time processes. This is probably due to the fact that dynamic programming approaches were thought to be impractical because of high computational requirements. There is only few papers, most of them relatively recent that include models with cancellations, or no-shows and overbooking (Subramanian et al. [1998], Chatwin [1996a,b, 1998, 1999], Lewis et al. [1999]). In that setting, Lewis et al. [1999], as well as Chatwin [1999, 1996] (single fare class) have potentially directly applicable results, when the problem can be cast into a nonhomogeneous, continuous time birth and death process. Numerical examples (and other results) for a related model (dynamic and stochastic knapsack problem) can be found in Kleywegt & Papastavrou [1998]. In addition to the articles already mentioned I have included a number of other important papers that consider simpler or different dynamic programming models. Gerchak et al. [1985] This seems to be the first paper that applies discrete time dynamic programming to revenue management problem. Although applications to airlines are mentioned, the problem is directly motivated by how to optimally ration a fixed quantity of stock when the product is perishable and there is no backordering, with a specific example of a delicatessen in New Brunswick selling bagels. A bagel can either be sold as is or as part of a meal at a greater profit contribution. This is an example of a more general situation where a product can be sold to different sources of demand at varying profit contribution, so it may be optimal to reject requests from CHAPTER I. INTRODUCTION 15 certain sources when the amount of product is fixed. The monotonicity of the policy is asserted: the rejection policy is of a booking limit-type and the limits decrease as we approach the end of planning horizon. These results are then used to find the optimal production quantities. Finally, authors indicate that their rationing problem can be cast in Poisson setting with two classes of customers which can be analyzed in a manner similar to that with the discrete time. Mamer [1986] The author introduces a finite horizon, continuous time, semi-Markov control model with general state and action spaces, and unbounded one-period rewards. The objective is to maximize the expected total undiscounted reward but discounting may be included. Data are assumed to be sufficiently regular for the optimality equation to be valid. The probability that an arrival will occur before deadline is uniformly less than one, the fact which is used to demonstrate that iV-step contraction assumption is satisfied so that the validity of successive approximations can be then established. Existence and measurability of an optimal policy are later assured when the union of all actions sets is assumed to be finite. In Chapter II, I show how to decompose the dynamic programming operator slightly differently, and then show, from first principles, that it is a TV-step contraction when the next stage operator (defined there) is. Mamer specializes the general model to the problem of asset liquidation, with and without recall. I will describe the problem without recall, which is more relevant to my thesis. Offers are independently and identically distributed, and the times between their arrivals are independent and identically distributed with cumulative distribution function G. The optimal expected revenue is shown to be monotone in time left to the deadline and in the value of the offer on hand (this corresponds to the fare class of the current arrival in our setting). For two problems with cumulative distribution functions of interarrivals G and G', it is shown that the expected revenue is greater for the one with a stochastically smaller cumulative CHAPTER I. INTRODUCTION 16 distribution function. The optimal expected revenue for a given state x is shown to converge to the optimal revenue for the infinite horizon model when the time to deadline approaches infinity. According to the author the G can be thought of as describing liquidity of an asset: the asset with offers coming more often (interarrivals stochastically smaller) than the other one can intuitively be seen as more liquid. The question of liquidation of k identical assets is then considered. Monotonicity of the optimal expected revenue in k, t and x (value of the current offer) is shown, and it is later pointed out that same method of proof can be used to demonstrate that the reservation price is decreasing in k and increasing in t. Chapter II of this thesis follows the same approach to certain extent. Like Mamer, I use successive approximations but without specializing to a homogeneous semi-Markov process of the type described above. So, for instance, the discrete concavity of the value function can be shown for a fairly general nonhomogeneous semi-Markov process. The monotonicity in time of the value function follows as well, when one observes that assumption of a stochastically increasing process is a natural one to make successive approximations work. As far as the latter result, the methods of the paper do not seem to demonstrate monotonicity in time for a nonhomogeneous Poisson arrival process, which, in general, need not be stochastically monotone. Thus, I have substituted coupling as an alternative method of proof, and provided formal proofs of monotonicity of booking curves in certain cases. As the examples at the end of Chapter II illustrate, there might be problems with monotonicity of the value function for general processes. Gallego & van Ryzin [1994] The article treats a generic yield management problem with (cited) applications i n a number of industries, mainly the fashion producers/retailers. Demand is modelled as a time-homogeneous Poisson process with intensity depending on price: if the price p is set over some interval 6 then one item is sold with probability \(p)5 + o(S) and no item is sold with probability 1 — \(p)6 — o(5). The 17 CHAPTER I. INTRODUCTION function A(-) is called the demand function. Based on some economic stipulations a family of regular demand functions is denned. By setting the price the seller sets the corresponding intensity of the demand process in such a way so as to maximize the total expected revenue from a stock of identical items. The pricing is dynamic and is a function of a stock level and the control horizon. Hamilton-Jacobi sufficient conditions and the theory of intensity control are used to show the existence of unique optimal solution. Authors obtain structural (monotonicity) results for the optimal price, and for the exponential family of demand the optimal pricing policy in closed form. The demand function A(p) is ae~ where a > 0 is a parameter, the maximizer of p\(p) is p then A* = a/e and p* = p(X*) = 1. The optimal expected revenue r{n t)=log(J2(\*ty±). f i=0 The optimal price p*(n,t) = AJ*(n,t) + 1. For a general demand function, the deterministic version of the problem is analyzed, which provides upper bounds and asymptotically optimal fixed price policies are given. Their model can be described in terms of this work as follows. It is a case of a single arrivals model with incomplete information about customer type. The information process is a homogeneous Poisson process and the distribution of the fare type at each arrival is given and depends only on time of that arrival (it is independent from the arrival of the underlying Poisson process so the assumptions of ChapterIV are satisfied). The distribution of the customer type can be more general than a finite collection of customer classes each arriving with certain probability. The function J*(n,t) corresponds to our auxiliary function v°(n,t). The same properties of J* can be derived from our work, which allows more general types of demand process and does not use the somewhat complex theory of intensity control. For the Poisson case the monotonicity and concavity in time of J* can as well be derived from the form of the respective ODEs using merely the discrete concavity of J* (v° in our case). In correspondence with decreasing Av° they show that the optimal price is decreasing in inventory n and increasing as time to departure increases. 18 CHAPTER I. INTRODUCTION A model with a given, predetermined set of prices, and with compound Poisson demand is also treated. The random-size demand occurs at arrivals of a specific nonhomogeneous Poisson process — namely the dependence on time is through a multiplicative factor to make a reduction to a homogeneous case possible. Holding costs, discounting, reordering may be allowed. In addition to controlling the price, the initial quantity of stock could be controlled as well. As far as cancellation are concerned the model with independent Bernoulli cancellations is formulated and a closed form solution is presented for the case with exponential demand and no cancellations when the reordering/overbooking cost is linear in the number of items to be reordered (overbooked). To summarize, the authors analyze the model that is essentially homogeneous Poisson, which makes an application of intensity control easier. On the other hand it presents potentially very useful, asymptotically optimal fixed price policies and comparisons with deterministic models. Lautenbacher et al. [1998] The article considers the following setting: single flight leg, multiple fares, single requests, finite horizon. Not included are cancellations, no-shows, sell-ups and recaptures. Demand is modelled as discrete-time, nonhomogeneous Bernoulli process with finite number of decision periods. The key concept is the suitably (U (x) — U (x+ 1) increasing in x) defined (discrete) concavity of the undiscounted n n expected revenue U (x) from periods n, n — 1,..., 1,0, when x tickets have been sold, n this property is then showed to be preserved under maximization. It assures that it is optimal to accept class % request in period n if and only if 0 < x < bi , where n bi is the optimal booking limit. As presented the results can be obtained in our n setting if the semi-Markov arrival process (booking request process) were assumed to be the nonhomogeneous Bernoulli. In addition, note also that from my Theorem II.7 follows that the booking curves are monotone in that case. Careful comparisons to salient static and two dynamic models are provided: 19 CHAPTER I. INTRODUCTION [ibid.] "We demonstrate that a single Markov decision process (MDP) underlies both the static and dynamic approaches to the single-leg Y M problem, and that direct calculation of the associated optimal value functions by backward (in time) induction is an effective means of deriving the optimal solution." Finally, the authors present the following omnibus model that contains both static and dynamic approach as special cases. m oo Un(x) = Y] y^Pij* i • i + n-lix + a)} + p U -l(x), *•—' *•—' 0<a<7 i=l j=0 —^ m a X a r U 0n n H = 0, 1, . . . , N (1.4.1) where Pij = P{ j class i customers arrive in period n). In this model multiple splitn table batches are allowed. When the second summation is dropped and batches are single then we recover the dynamic model (of the paper). If the first summation is dropped and N = m then we obtain the static model. Our results for the case with partial information about customer type include both the dynamic model of the authors and the static models they refer to. In addition, the monotonicity of the booking curves is assured under reasonable assumptions. Subramanian et al. [1997] The paper extends previous M D P with discrete time, finite horizon, nonhomogeneous Bernoulli arrival process by including cancellations, no-shows and overbooking. In that setting the authors flesh out the equivalence of the yield management problem to the problem of the optimal queue control. Section 1 of that article extends the model of Lee k. Hersh [1993]. A number of ways to include cancellations is presented and the effects of including cancellations are highlighted through numerical examples. A general model, where the airline keeps track of reservations in each fare class is formulated. When cancellation and no-shows probabilities are the same for all classes, then only the total number of reservations needs to be kept as part of the state 20 CHAPTER I. INTRODUCTION variable. In this case existence and (under some assumptions) monotonicity of the booking curves can be deduced from my results. Two potential ways of applying their results to time-dependent Poisson process are presented and a proper motivation for those approaches is given. Kleywegt & Papastavrou [1998] The authors define the dynamic and stochastic knapsack problem (DSKP) .as follows. Items arrive according to a homogeneous Poisson process. The reward of each item is random but becomes known upon arrival and prior to making a decision. The rewards are independent and identically distributed random variables that are in addition independent from the arrival (Poisson) process. Requests are for exactly one unit (single batches) and can be accepted or rejected, there is no recall. Both infinite horizon and finite horizon variants are given. The whole process can be stopped before deadline is reached or the capacity is exhausted. There is a holding cost and a terminal reward, both can depend on the remaining inventory on hand. The goal is to maximize expected discounted revenue (net of accumulated costs). The results are demonstrated by cleverly exploiting a relationship between the DSKP and a Markov Decision Problem that can switch on and off. They are of similar type that I show in the thesis: monotonicity of the expected value in time and inventory, and optimality of a memoryless, deterministic threshold policy. The threshold introduced in the article corresponds to our Av (r), t) less penalty for 0 rejecting an item. An offer is accepted when its value is more than the threshold value less that penalty. When there is no discounting, the terminal reward and the waiting costs are constant (in capacity left) then a number of monotonicity and concavity results is presented. When one assumes even more by requiring that the maximum price a customer is willing to pay is exponentially distributed and that waiting cost and penalty for rejecting are zero, then authors present a closed form solution for the optimal value function. Finally, the authors point at possible extensions of the formulation by including random sizes of requests and refer to another paper of theirs CHAPTER I. INTRODUCTION 21 for some counterintuitive examples. When the setting of this thesis is specialized to a homogeneous Poisson arrival process, then the formulation and results in Kleywegt k, Papastavrou [1998] are more general since they include holding cost, penalty for rejecting requests, general distribution of the reward offered by arrivals and the additional feature that the booking process can be stopped. I conjecture, however, that all of those features could be included in the nonhomogeneous semi-Markov setting of this thesis, using its more basic method of proofs at a moderate increase in effort required. The new features seem to be only of secondary importance in the airline setting, but are probably more important in asset liquidation, investment selection, shipping and batch scheduling which were the main motivation for the article. Lewis et al. [1999] The authors obtain results on existence and the monotonicity of the booking limits for a finite horizon homogeneous birth and death process control model, which is then coupled with an infinite horizon model. Convex and increasing overbooking cost is present, customers can cancel with an intensity (death process) decreasing and convex in the number of inventory left, which is one of the conditions that I give in Chapter III. Fares seem to be left unadjusted (constant). A condition, for monotonicity (decreasing or increasing) of booking curves with respect to time is given. In Chapter III, I provide a different proof of that result, which hopefully can shed some light on possible generalizations. The model, and especially the coupling used, is interesting, since it reflects the fact (cf. Chapter V) that far away from the deadline where customers are very likely to cancel the airline earns revenue by essentially exploiting the difference between fare and the refund, so a different kind of optimality criterion - average revenue per unit time might be more appropriate. This behaviour can be observed in one of the numerical examples in Chapter V . CHAPTER I. INTRODUCTION 22 Liang [1999] This is a multiclass, nonhomogeneous Poisson model of one of the types considered in this thesis, with single arrivals. No-shows and overbooking, as well as cancellations are not allowed. By methods that seem tailored to this particular setting Liang derives essentially the same results as I do: discrete concavity of the optimal expected revenue, also called monotonicity of the expected increment in inventory, and its monotonicity in time to departure. Using those properties and an ingenious application of integration by parts, recursive formulae for the critical times are found. Each such time appears as an upper limit in an integral involving critical times and the expected increments for lower inventory levels. That integral is in turn equated to a given fare and in principle the critical time can be found numerically. As the formulae do depend on expected increments (Au° in this thesis) it seems that finding these is essential and has to be done first by some other methods. In Chapter V, I first solved the system of ODEs to find v° for each inventory level and then a binary search was employed to find the critical times. I also believe the methods used in this thesis have more general scope and can better demonstrate some properties, e.g. that under certain conditions, monotonicity of the expected increment is preserved when overbooking and no-shows are introduced. Chatwin [1998] The author considers a multiperiod (discrete time) airline overbooking problem for a single-leg flight and a single fare class where cancellations and no-shows are allowed. Under some conditions on fares, refunds, distributions and an overbooking penalty, the booking-limit policy is shown to be optimal and (under further conditions) monotone in time. The main point of the paper is an extension of author's ideas already presented in author's 1996 papers, which I discuss afterwards. Two models are presented: "Stationary-Fares Model" and "NonstationaryFares Model." In the first one, the (single) fare does not vary over time, and the CHAPTER I. INTRODUCTION 23 customer receives a full refund for cancellation/no-show. The airline observes all reservations requests in a period, and then makes decision whether or not to accept each reservation request (i.e. multiple requests in a period are allowed). Following that cancellations happen (same period). The single-fare and full-refund assumptions enable one to treat the model as if all the fares (and refunds) were paid at the flight time. The flight time revenue is assumed to be quasi-concave in the inventory (number of reservations on-hand). The distribution of reservations in the next period is assumed to be stochastically increasing in the number of reservations on-hand (the more reservations on-hand the more potential reservations in the future), it is allowed to change from period to period. The distribution of cancellations is assumed to be totally positive of order 3 (TPs). It is shown that a booking-limit policy is optimal and, later on, that the booking curve is decreasing in time to departure. The maximum expected revenue is decreasing in time. In the second model, the fare and the refund are allowed to vary with time, but the refunds are independent from the fare paid by a customer. When compared with the stationary-fares model the assumptions are stronger. The flight time revenue function is required to be concave, the distribution of reservations either has independent increments or is TP3 with increasing affine mean. The distribution of cancellations is TP3 with contracting linear mean. As in the first model, the booking-limit policies are optimal and under an additional assumption on fares and refunds in each period, the booking curve will be decreasing in time to departure. By introducing special control periods just before the departure, no-shows, no-records, walk-ups and stand-bys can be accommodated. The nonstationary model is further applied to the multiple fare classes where customers do not cancel and the show-up is certain. The number of future reservations in a fare class may depend on the number of current bookings. There are no assumptions on the order in which fares book but customers in the same class book in the same period. These results are then compared to earlier results by Lee CHAPTER I. INTRODUCTION 24 &; Hersh [1993], Robinson [1995] and Curry [1990]. In particular, if the potential reservation distribution either has independent increments or is TPs with increasing affine mean and the fares increase with time and there are no cancellations then the optimal booking limits are shown to be increasing (as opposed to optimal booking limits being decreasing, in the previous case). Finally, the author presents examples where booking-limit policies are not optimal. This may happen when the dependencies between reservations are modelled directly and happen to be of certain type. Below, is the more detailed comparison to this thesis. Terminal rewards. The assumptions on terminal rewards are essentially of the same type, namely concavity. Optimal policy. I use the convention that I always pick the greatest of the maximizes in the optimality equations for a given state, unlike Chatwin who considers all possible maximizers and then shows that they form an interval due to the optimal expected value being quasi-concave. Arrival process. Chatwin allows the booking requests process to depend on the number of seats already booked, but requires it to be either stochastically increasing (in the current inventory, or to possess independent increments, or to be TPs with increasing linear mean). In contrast to this, in my model the booking requests arrive according to a process that is defined independently from the control process (it is exogenous). Existence of booking curves follows for a fairly and (apart from the discretetime assumption) general, nonhomogeneous and continuous-time semi-Markov process which includes the discrete time process of the type used in the paper. Single vs. Multiple fare classes. In the thesis multiple fare classes are allowed throughout. Cancellations. I either assume that cancellations happen between arrivals of booking requests (control epochs) or (in the section on birth-and-death process) that CHAPTER I. INTRODUCTION 25 at each time point only one of the three can happen: a booking, a cancellation, or a null arrival. This is different than in the paper but the difference is not essential. The requirement for the number of cancellations to be stochastically increasing and stochastically convex as a function of current inventory seems to be more natural and more general than the one in the paper (TPs or TP3 with a contracting linear mean), although the ideas underlying both assumptions and the examples given seem to be similar. M o n o t o n i c i t y of the b o o k i n g limits. Both in the paper and in this thesis additional assumptions are required for this type of results (case with cancellations). It is not clear how to apply the paper's results to the case with multiple fare classes, and to a significant degree they hinge on the assumption of the single fare, since, as my examples show with more different fares the booking curves exhibit more complex behaviour. While I can show the monotonicity of the booking limit for multiple classes, birth-and-death setting, the additional assumptions seem to be more of theoretical interests. On the other hand I conjecture that a bound on the number of modes of a booking curve could be given, which would extend the use of my condition. O p t i m a l i t y of the b o o k i n g - l i m i t t y p e policy. Chatwin presents a number of in- teresting examples where the booking limit-type policy is not optimal. I believe that my results for the nonhomogeneous semi-Markov model, especially in the chapter on partial information case, clarify it even further. In general, for each possible type of current customer there will be a different booking curve, e.g. for one with (p2,1) and with (02,2) type of request (one seat at p2> two seats at P2, respectively), and the decisions made using those curves will be different. Only in some cases I am assured that there is only one booking curve for each customer type, for instance when the arrival process for each type is an independent Poisson or Bernoulli. I discuss those examples in more detail in Chapter IV. 26 CHAPTER I. INTRODUCTION Total posit ivity. Chatwin uses the total positivity framework and results to establish that, essentially, the quasi-concavity of the terminal reward as a function of current inventory is preserved when one moves back from the departure time. From that he infers the optimality of the booking-limit type policy. In the thesis, I demonstrate the latter by a more fundamental approach: successive approximations. The n—th approximation can be interpreted as taking into account only the potential revenue (and cancellations) from the first n customer arrivals. The deployment of the total positivity differs substantially too: I use it in showing the monotonicity of the optimal booking limit in time (under additional conditions), as opposed to demonstrating the quasi-concavity in the inventory variable. Chatwin [1999] This paper deals with continuous-time problem with cancellations and overbooking with a single fare class. The fares and refunds are piecewise-constant functions of the time left to departure. Customers cancel independently from each other with a common rate fi. The control problem is then formulated as controlled birthand-death process. The terminal rewards are assumed to be increasing and concave in inventory left and the no-shows have to be TP3 with contracting linear mean: for all 77 e C, 2~Z 1ris s = ^ wri ere 0 < 7 < 1 and q® is the probability that s customers s will show up for the flight given that there are n reservations at flight time. It is shown that booking limit-type policies are optimal and that the booking curves are decreasing when fares are assumed to be decreasing with the time to departure. As in the first paper, key to the results are: the use of total positivity to show that monotonicity and concavity of the terminal reward in inventory variable is preserved as more time becomes available, and the earlier result of Miller [1968] which assures that the optimal policy is piecewise constant in time. When the fare is always greater than the refund and it is increasing in time left to departure, the CHAPTER I. INTRODUCTION 27 optimal booking curve is shown to be decreasing in time as well. As for comparison with this thesis, all the similarities and differences listed for the first paper apply here too. In addition, I show monotonicity in time without using Miller [1969] general result on the optimal policy being piecewise-continuous. Chatwin [1996a, b] Chatwin [1996a] seems to be the first paper in the series that was published, with following articles presenting versions of its main results. The model is presented as a continuous-time terminal-value birth-and-death process, and all of the features discussed previously (optimality of booking curves, monotonicity and concavity) are shown. An added one is that the airline could be allowed to control the cancellation (death) rate, which I do not allow in my model. As before the formulation is for one fare class. The second paper considers a multiclass, discrete time setting. The vector of reservations in each fare class is the state variable. Only one class of passengers per period can cancel, the number of cancellations is independent from number of reservations in this and other classes and probability of cancellation is the same. The methods of the paper rely on TP3 properties preserving quasiconcavity in inventory (vector) variable, which is assumed continuous. It is shown that submodularity of the value function is preserved, so the optimal policy is of the booking limit-type. In my view the assumption that cancellations are independent from the number of reservations and that their probabilities are the same for each fare class weaken the motivation for the enlarged stated space that keeps track of reservations in each class. I believe that working with the same assumptions, the same goal can be achieved more easily using methods of Subramanian et al. [1997] or of this thesis (for a more general booking request process). Namely, the cancellation refunds can depend on the fare type when passengers cancel independently with the same probability. 28 CHAPTER I. INTRODUCTION In the language of this thesis, the article can be described as dealing with what is essentially a nonhomogeneous Poisson model, with single arrivals and with partial information about the request (no-shows, overbooking and cancellations are not allowed). Existence of booking limits (reservation price) is shown by means of a method that seems specific to that particular setting. Monotonicity of the booking limits is shown using intensity control theory, under conditions that are equivalent to imposing certain requirements on the ratios that are used in Chapter IV. Interesting examples are given of when monotonicity fails despite the expected optimal increment (my Av°) being monotone in time. Karaesmen & van R y z i n [1998], Queyranne & F i l l [1999] Karaesmen & van Ryzin [1998] introduced an overbooking model with multiple reservation and inventory classes. The model was two period and the problem was to determine the joint overbooking levels for the reservation classes. In the first period (reservation period) reservations are accepted and in the second (services period) the cancellations are realized and surviving customers are optimally assigned to inventory classes. They have identified submodularity as being the natural property in this setting and' show that the optimal overbooking level is decreasing in the reservation levels in remaining classes. Queyranne &; Fill [1999] have further investigated the model. They have simplified proofs in certain situations and have come up with natural assumptions that make computations more feasible. Feng & Gallego [1995] The authors study the instance of the yield management problem of when to increase or decrease the price from one given price to another given price, i.e. when only the policies that allow at most one price change are allowed. This approach is inspired by the results of Gallego, van Ryzin [1994] that these policies are asymptotically optimal when volume of sales increases. By suitably choosing 29 CHAPTER I. INTRODUCTION the time of the change a range of (average) prices can be synthesized from the two given prices. The switch is effected when time-to-go crosses the time threshold that depends on the number of inventory left. The pair of prices need not be optimal. Using tools similar to those in the theory of intensity control, sufficient conditions for the optimal revenue function are derived when each of the two different prices is in effect over one of the two complementary and disjoint intervals that add up to the full control interval. The conditions are then used to show that the optimal policies have the threshold property. To this end the authors use the variation diminishing property of the totally positive kernels. The markdown case and the markup case are considered where the only change allowed is either to the higher or to the lower price, respectively. The results are subsequently generalized to cover the situation, where starting at some price p a change either up or down is allowed. The threshold properties prove to be useful in constructing algorithms and the authors describe a number of ways to apply the precomputed threshold values. The results used are essentially for the Poisson demand, whose intensity is controlled by adjusting the price, but authors anticipate that they could be useful in the stopping problems with some other point processes. In the airline setting the markdown case might be more relevant and we describe here how the algorithm developed in the paper is applied. Start with a sequence of precomputed optimal switching times: {x : n = 1,2,... }. n Then [ ibid.], "Given n items and t > x n for at least t — x n units of time, we continue pricing at p\ units of time. At this point, the remaining time-to-go is x and n it is optimal to start sale at price P2 only if we still have n units in stock. Otherwise we update n, the number of remaining units, and repeat the procedure. The procedure ends with a price decrease at some threshold x , or with n = 0. Thus n given n and t > x the stopping rule calls for at most n observations of the stock at time thresholds {x\,X2, • • • ,£n}-" When price can be adjusted in both directions then one precomputes two increasing sequences of time thresholds x < z such that n n it is optimal to increase or decrease the initial price as soon as the time-to-go t falls above z or below x respectively, where n is the inventory left. n n CHAPTER I. 1.5 30 INTRODUCTION A General Finite Horizon Markov Renewal Decision Process I formulate a finite horizon Markov renewal program with general state and action spaces and general one-period immediate revenue, adopting ideas from Schellhaas [1980], Hinderer & Waldmann [1998], and Denardo[1967]. The formulation will include both the full information case (Chapter II) and the partial information case (Chapter IV), to which it will be later specified. Since we are interested in situations where time t left to departure plays a role, I make t explicitly a part of state variable. S and A are the (arbitrary) state space and action space, endowed with some a-algebra S and A, respectively. The extended state space that includes I 1 time t is So = S x — T, 0, with the product cr-algebra <Sb- D(s,t) C A is the set of admissible actions in state (s,t). We assume that the constraint set D = {((s,t),a) € S x A | a G D(s,t)} is measurable and that it contains a graph of a measurable mapping from S into A. The transition probability distribution from D into S, the Q(s', q \ s, t\a), defines a joint probability distribution of the next arrival epoch q and the next state s' given that action a was taken at time t in state s. One-stage reward r(s, t, a, s', q) is earned at the beginning of each decision epoch and a terminal reward LQ(S) is allowed, both are assumed measurable. Discounting is allowed. The one-stage reward may consist of a reward earned at the beginning of the decision epoch plus a reward earned at the next decision epoch and a continuously earned reward during sojourn z. It can often be defined as f(s, T,a,s',a) := 1[_T,O](T) 9(s,r,a. -\-h(s,r, a, s',a)e ' ( T T ) • l(0,oo)(<7) for T < a and 0 otherwise. For instance, with s = rj, the inventory left on hand, the 31 CHAPTER I. INTRODUCTION function h could be equal to io(??)l(o,cx))( ) cr a n d g could be equal to ap(4>,t). Let H be the set of all n-stage histories, /„ = (so,to, an,..., s , t ), n n n (sk,tk,cik) G D. A randomized policy TT = (n ) is a sequence of transition proban bilities 7r„ from H to A, such that ir (l , •) assigns probability one to D(s ,t ) for n any n n n n G H , n € N. Let IT denote the set of all policies. Given an initial state n So, and an initial time to, the transition law and the policy TT G U define (Schellhaas[1980], p.34 and references therein) a probability measure P(i t),n o n t space SxAxSxAx... X, N A„), n G A^}, where and a stochastic process {(X ,T , n the product n T , A are the usual projection operators from the just described product space n n onto the n-th state space, time space and the action space, respectively. We can now write a total reward under a given policy as o o V := J2e~ ~ r(Xn,T , a(cT A ,X ,T ). T) n N n+1 n+1 n=0 Remark 1.1. Defining /?(T_i,T ) := 1, 0(T -i,T ) 0 k := exp [~ot(T - T -i)} we can k k k write V as follows: o o V := P(T-i,T )...0(T -i,T ) 0 n n • f(X ,T , n n A ,X n n + 1 ,T n + 1 ). n=Q The total expected reward starting in some state (s, t), under a given policy, is E V | XQ = s, To = t; TT . The goal is to maximize this reward among all policies. So formally the finite horizon Markov renewal decision process is a tuple (S,A,D,Q,T,g,h). Intuitively then, given a state space S, finite horizon —T and a general action space A it can be described as follows. The process is observed at discrete time points t , n — 0,1,2,..., until time 0. If the process is in state s at time n t n n > —T then the action a G D(s ,t ) C A is chosen and the process will move to state n n n at time t +i > t according to a transition law Q. This probability n n is independent from earlier states and actions, but in general it may depend on the current state s , the arrival time t„, the action taken a and the stage n. If n n t +i > — T this action results in reward p ( S n ) t , a „ , s + i , t „ i ) paid at t n n n + n (this 32 CHAPTER I. INTRODUCTION includes a fixed reward rf(s ,t ,a ) n reward h(s ,a , t , s i,t i) n n n n+ n+ n n paid at time t n as well ); if t \ n+ > 0 a final is paid. For t > 0 the process moves in a similar way n but no rewards are accumulated. In the current formulation the reward structure covers in particular fixed immediate rewards paid at time t , accumulated rewards, terminal rewards and discounting, n all of which can depend on s , t , t +\ a , and T. Our model can be thus n n n n regarded as general decision model in the sense of Schal [1975] with state space S and the set D(s, t) of admissible actions in the state s. Under suitable conditions (eg. when f is finite, or when so-called bounding functions exist) an immediate expected reward r(s, t, a) := J rdQ(s', q \ s, t; a) exists. The formulation of the decision model with semi-Markov reward f is more general than needed in this thesis, so in the sequel I will assume that the immediate reward r is equal to the expected immediate reward r(s,t,a). With that reward one can construct an optimality equation that, under fairly general conditions, is satisfied by the optimal expected revenue. To this end we work in the Denardo [1967] framework of local income functions, which requires assumptions of boundedness, monotonicity and either a contraction or TV-step contraction assumption. Let B denote the space of bounded, Borel-measurable, real valued functions: S —• R; it becomes a Banach metric space when equipped with the sup norm : \v\ — s u P x £ S |f (as)|. Informally, the local income function h(x,a(x),v) : X xDxB 0 —• R is (Denardo [1967]) "The total payoff when 'starting' at point x and choosing a(x) with the prospect of receiving v(z) if the pair (x, a(x)) causes a 'transition' to point z. (Whether v(z) could be realized by any policy is immaterial; h(x, a(x), •) describes what the pair (x,a(x)) yields as a function of i>,.)". In our case Denardo's local income function h(s,t,a,v) is r(s,t,a) + /v(s',q)dQ(s',q | s,t;a). Each policy determines one-stage reward operator H : DxB —• B, w [H (v)](x) := h(x, a(x), v) w is an operator on B such that H (B) C B, (boundedness). n [(7w](cc) := sup ( ) ( ) h(x,a(x),v) is the maximization operator, U(B) C B. To a x e£) x 33 CHAPTER I. INTRODUCTION assure that the optimal value function can be obtained by successive approximations as a unique solution of the optimality equation Denardo imposes certain conditions on the operator H and the function h. w Assumption 1.1. Monotonicity assumption Wr G IT, Vu, v G B ifu>v then H„(u) > H (v). v Assumption 1.2. Contraction assumption: 3c, 0 < c < 1, s.t. \/u, v G B, x G X, a(x) G D(x) : \h(x, a(x),u) — h(x, a(x),v)\ < c • \u — v\. Assumption 1.3. N-stage contraction assumption: The operator H^ has modulus c < 1 with c, N independent of TT, for each TT H has modulus 1 or less. n Moreover, (Denardo [1967]) when h(s,t,-,v*) is continuous in a topology making D(s,t) compact then there exists a policy realizing the optimal expected value and, under some conditions, it can be taken to be deterministic and historyindependent. In the next chapter a more in-depth analysis of the AT-step contraction assumption is offered. I will assume (or show) that Denardo's conditions are satisfied in the thesis. In all models considered the action sets are discrete and finite, the immediate rewards are bounded by (highest fare) • (available capacity) + max(overbooking penalty). The local income function h is clearly monotone. Assumptions that result in the N-step contraction property will be valid throughout. For completeness, I mention that problems with unbounded rewards have been treated in Lippman [1975], Schellhaas [1980], Mamer[1986]. Lippman[1975] asserts validity of the optimality equation and successive approximations when either the state space or the action space is countable. General treatment with weaker or different assumptions (such as upper semicontinuity) is given in Hinderer [1970], Dynkin & Yushkevich [1975], Schal [1975], Rieder [1975]. 34 CHAPTER I. INTRODUCTION Successive approximations Successive approximation, when valid, provide one with a powerful tool to show various structural properties, and the method seems to be part of the folklore. Key results in this thesis will rely on it. Hinderer [1985] reviews applications of the successive approximation in showing structure of solutions to dynamic programs. He identifies six steps in the process: (a) Show that vo has the desired property E. (b) Show that E is preserved under integration with respect to the transition law. (c) Show that E is invariant under multiplication with positive constants. (d) Show that E is preserved under addition. (e) Show (or assume) that r has property E. (f) Show that E is preserved under sup agD ( )(...). (This implies conditions on D.) s It is mentioned [ibid.] that steps (b) and (f) are often more difficult, while some others may be simple. Mamer [1986] seems to be the first applications of successive approximation to show structure in the problem of liquidating a collection of identical assets. Chapter II Full Information II. 1 Airline Seat Inventory Control with Full Information about Customer's Request This is the basic chapter of the thesis, in which I introduce most of the concepts and definitions needed throughout the work. I consider the situation where the airline (the controller) has full information about the current customer. The request size and the price per seat that he is willing to pay are known precisely, for instance a customer requests up to (or exactly) three seats at a discount rate. In contrast to that, in Chapter IV, I relax this assumption and only require that request size and price per seat be known up to a joint probability distribution (this is essentially the setting in the series of papers by Gallego and van Ryzin[1994,1997] and Gallego and Feng[1995]). So the only actions available are to accept or reject a customer (or group of customers) who offers a specific price for the ticket. These decisions should not influence the demand (booking requests) process. In my model, arrivals of booking requests are assumed to follow a semiMarkov process, so that the arrival processes for different fare classes can be correlated. Decisions are made whenever booking requests arrive and are based on the number of seats in inventory and the time left until departure. Closing and reopening 35 CHAPTER II. FULL INFORMATION 36 of fare classes is allowed, which should make the model attractive in a highly variable demand environment. No-shows and overbooking are allowed with customers showing up independently and with convex and increasing overbooking cost. The main objective is to study structural properties of the optimal value function and the optimal policy. In particular, under certain conditions the optimal seat allocation policy has a critical time property which is very desirable — namely, that for each inventory level 77 and each arrival type 4> (fare class, request size) there is a critical time t*(rj,(p) such that it is optimal to sell a seat (at least one) to such a request whenever there are less than t*(n,4>) units of time left until departure and to save the seat otherwise. I show that for certain types of arrival processes if the customers only request one seat or if the batches are splittable (i.e. I can partially satisfy the demand for a batch) the property is obtained. I provide some counterexamples that this property need not exist if batch must be accepted or rejected as a whole. I also include a counterexample to a claim by Lee k, Hersh [1993] that the property holds for their discrete time (essentially a nonhomogeneous Poisson) model with batch requests. II.2 Airline Seat Inventory Management Problem As A Finite Horizon Semi-Markov Decision Process One major assumption, which I make, is that the arrival process can be defined independently of any seat sale policy. That is, the decisions whether or not to sell seats to specific customers do not affect the arrival process. For example customers requesting, but denied, a discount will not return later. As a consequence of this assumption, I can model the arrival process independently of the decision theoretic structure, and do so in the next subsection. Then in the subsequent subsection I introduce the additional structure needed for a (possibly nonhomogeneous) semi-Markov decision process. Some Notation To avoid overloading parentheses, the closed interval from CHAPTER II. 37 FULL INFORMATION a to b is denoted by a, b, as used by Feller [1966]. The minimum of two numbers, say a and b, is sometimes written as a A 6 and the maximum as a V b. The positive part of a number a is a + (rj,(j)) = (rj,p,P) if (j) = (p, — a V 0. I will also abuse vector notation by writing 0). The terms increasing and decreasing will be used in their weak sense in preference to nondecreasing and nonincreasing, respectively. II.2.1 The Arrival Process A customer is characterized by his or her fare type 4> = (p, where p is a fare class and f3 is the number of seats requested or batch size. Given a fare type <j), I will sometimes write (j) and <f>p to represent the fare class and batch size p associated with <f>. Let C denote the set of possible customer fare types. The set of fare classes is denoted by TZ and the set of possible batch sizes is denoted by Ai. Note that C C TZ x Ai. It is sometimes convenient to allow a zero batch size to introduce some event which is not really a customer arrival. (See the example in Section II.5.1.) For example, when booking is initiated at time —T, I will generally assume that there is a customer arrival at this point. Since there will generally not be a real arrival at time —T, I can use an arrival of type (p, 0). I assume that our arrival process is a nonhomogeneous semi-Markov process {(<!>„, T ),n = 0,1,2,...}, where T is the arrival time and n is the type of the n-th n customer. I use basic definitions of the nonhomogeneous semi-Markov processes as laid out in Janssen and De Dominicis [1984], and refer the reader to Cinlar[1975a, 1975b] for comparison with (homogeneous) semi-Markov and Markov-renewal processes. The semi-Markov property is that there are epochs in the process (arrival epochs in our case) at which the past and future are conditionally independent given the current state. More precisely, we assume that Pr($ n + 1 = </>,T -T n+1 n <t | $ o , . . . , * n ; T , . . . T ) 0 = Pr($„+i = <f>, T J n+1 n - T < 11 $„, T ) n holds for T = — T and for all fare types 0 € C, n = 0,1,2,... and t > 0. 0 n CHAPTER II. FULL 38 INFORMATION In accordance with Janssen and De Dominicis [1984], I impose certain conditions on the probability transition function P(4>, s \ <f>,t) := P r ( $ „ i = (f>',T i < + n+ s | <fr = (j),T = /j). In Janssen and De Dominicis, condition (c) requires that the ra n probability has total mass one for each fare type <j> and time t. I have relaxed this condition to allow for discounting if desired. Note that if the transition function P(<j>', s | <j),t) only depends on s — t then I have the usual homogeneous semi-Markov process. Assumption II.1. (a) Let P(s,t) be the matrix whose ((f),(j>') component is P(<p', s \ Cf),t). Assume that P(s, t) is a measurable map as a function ofs > —T and t > -T; (b) If s < t then P((f>',s \ (f>,i) — 0 for each <f> and <p', so that time moves forward. (c) For each ((f), t) II.2.2 The Finite Horizon Semi-Markov Decision Process Having denned an arrival process I now show how our problem fits into a nonhomogeneous semi-Markov decision process framework. The inventory level or number of seats available, n, takes values in 1 = {—c,..., —1,0,1,..., c} where c is the capacity of the plane and negative inventory indicates overbooking. The state of the system when a customer arrives is the inventory level found by that customer together with the customer type and the I 1 time of arrival. Thus the state space is 5 = I x C x —T, 0. For each state (77, </>,£), let D(rj,(f>,t) be the set of admissible actions. If a G D(rj, cj}, t) seats are sold to a customer who found the system in state (77, </>, t), then the revenue generated is given by the value of the revenue function r(n, 4>, t; a). In the next subsection, a revenue function will be described which corresponds to a simple CHAPTER II. FULL INFORMATION 39 model with overbooking and no-shows. I will also introduce there some attributes of the revenue function which will be needed i n latter sections of our paper. Throughout the thesis, I assume that the action sets are finite and only depend on inventory or the batch size and that the revenue function is bounded. The finiteness assumption can be replaced by compactness as in Denardo [1967], and the boundedness assumption can be relaxed using the techniques from Mamer [1986]. However, in our context these assumptions are not restrictive. Assumption II.2. The revenue function is bounded and the action sets are finite. A policy is a rule which determines the action to be taken as a function of the information available, which is the history of the process up to the current time. The rule might involve choosing an action according to some probability distribution. Let n be a set of all policies. A policy can be very complex. Fortunately, under certain conditions specified in Theorem II.1 (also see Denardo [1967]) one can show that a policy of a simple form will be optimal. I call a policy simple if it is deterministic and only depends on the current state, not on the history of how it arrived at that state. Such policies are sometimes called stationary. However, in our context "stationary" might be misleading since time is included as part of the state space. I now describe the probability transition function Q, which governs the dynamics of the semi-Markov decision process. Suppose that the process is in state (n, p, P, t) and choose admissible action a. Then the probability that the next arrival occurs before time s, is of customer type (p',/3')) and finds inventory level rf is ^ , , a, , a s \p(p',P',s\p,3,t) Mrf = n-a I0 otherwise. Q ( ? / , p ' , / ? ' , s | ? 7 , P , / M , a ) := < If a customer buys a seats of type <fi = (p, ft) at time t when the inventory level is rj, then the revenue generated is r(n, <j>,t\ a), provided that a is an admissible action i n D(r), d>, t) and — T < t < 0. For a given policy ir, the stochastic process consisting of the states visited and the actions chosen is well defined. Let v^rj, <j>, t) 40 CHAPTER II. FULL INFORMATION be the expected total revenue generated by policy TT given that there is an arrival of a customer of type <j> at time t (—T < t < 0) who finds inventory level rj. The optimal value function is v*(r),(f),t) = sup„ nv^(ri,<t>,t). & Under certain conditions which will be established later in Theorem II. 1, v* is the unique solution to the optimality equation v(r),4>,t)= max:{r(r),<f>,t;a) + V a€D(ri,<t>,t) / v(-n - a, <f>', s)P(<j>', ds \ <f>, t)}. J t Operator notation will be used in the sequel. Note that the value of any policy 7r is bounded since the revenue function is bounded by Assumption II.2 and the capacity of the plane is finite. So in considering value functions it is enough to consider functions in the space B of bounded, Borel measurable, real-valued functions defined on the state space S. Define the operators T and T which each map B into (.7V)(?7,0,i) = max {r(r),<j),t;a) +v(r) - a,(f),t)} (11.2.2) aeD(ri,4>,t) and f° I 1 (Tv)( ,<p,t) = J2 v(vA',s)P(<j>',ds | <M) for t G - T , 0 <t>'ec V J T for each state (77,4>, t) G S. Using operator notation the optimality equation becomes v = (TT)v. Define a partial order, <, on B by / < g if f(x) < g(x) for each x € S. An operator Q is increasing if Qf < Qg whenever f < g. Let || • || denote the supnorm on B. For an operator, say Q on B, define the modulus of Q to be | Q \= sup f<g£B || Qf - Qg \ \ / || / - g || (cf. Denardo [1967]) An operator with modulus less than one is a contraction. The function l(-) is the function on B which has the value 1 for all states. The notation | • | is overloaded, but its meaning should be clear from context. In addition to its use as the modulus of an operator, e.g. | T |, and its use (II.2.1) CHAPTER II. 41 FULL INFORMATION as the absolute value of a number, e.g. | f(x) |, I also write | / | as the function whose value at x is | f(x) \. A n additional assumption is needed to ensure that the optimality equation has a unique solution. I will assume that there is positive probability, uniform for all states, that there will be no more than N arrivals between the time of the state and the departure at time 0. Note that if I am in state (r],4>,t), then (Tl)(r),4>,t) is the probability that an arrival will occur before the plane departs. If these probabilities are uniformly less than one, then T is a contraction. Hence I can state our assumption as an N-step contraction assumption. Denardo [1967], in his definition of the N-step contraction property, also requires the operator to have modulus no greater than one. In our case, the operator T already has modulus no greater than one, since | T\(x) |< 1 for each state x. (Also see Schellhaas [1980], particularly his condition A3.) Assumption II.3. For some integer N, T N is a contraction operator. This assumption, which will be in force throughout the rest of this paper, is not at all restrictive in practice. For example, suppose that the interarrival distributions are such that there is at least probability e that an interarrival will exceed 5 regardless of the state. Then T N is a contraction for N > T/5. M y results are similar to those of Schellhaas [1980] and Mamer [1986], who prove analogous results in the time-homogeneous semi-Markov setting. L e m m a II.1. Let Q be an arbitrary operator on B. Then | FTgf( , <f>,t) - FTg ( ,<f>,t)\< max T | Qj - Qg | (77 - a,<j>,t). V g V a&D(n,(j>,t) Proof. First note that for any pair of real-valued functions, say u and w, defined on a space X, \ sup u x€X — s u Px€X' Y I— P i e x I ~ s u u v I ( ^- Hinderer [1970], Lemma c 3.3). It follows that I FTGf(r],<f>,t) - mg{r],4>,t) \< max | TQf{r, - a, 0,t) - Tg (n -a,4>,t)\. aeD(r),<t>,t) g CHAPTER II. 42 FULL INFORMATION Applying the linearity of T and the fact that | Tu \ < T \ u \ for any u G B completes the proof. • When I select the optimal action for each state in the following theorem, the largest optimal action will be selected. This is a convenient convention, which will be used when the structure of the optimal policy is studied in later sections. T h e o r e m II.1. The optimal value function, v*, is the unique solution of the opti- mality equation andv* = lim _ (.FT')™0. An optimal policy, it*, can be obtained by n >oo setting it(n, (p, t) equal to an action which maximizes r(r), <fi, t; a) + Tv*(r] — a, <j>, t). Proof. The operator T is increasing since it is linear and maps nonnegative functions to nonnegative functions. It follows from Theorem 4 in Denardo [1967] that the optimal value function is the unique solution to the optimality equation. If I show that (TF) is a contraction, then the next claim of our theorem is N immediate from the comments which follow Theorem 4 in Denardo. The contraction property, in turn, follows easily from Assumption 11.3 and | (rT) ttv, n <f>, t) - (rr) g( , <j>, t) n V |< ( T ^ f a , 4>,t)-\\f-g\\, (II.2.3) which I establish by induction. Let G be the identity map. Then Lemma II. 1 implies that | (FT)f(ri, </>, t) - (rT)g(ri, </>,t) \< max T \ f - g \ (n - a, </>, t). aeD(v,4>,t) Since T is increasing, replacing | / — g \ (n — a, <f>,t) with l(r) — a, (j),t) • \\ f — g || does not decrease the right hand side of the above expression. Moreover, once this replacement is made, the expression inside of the maximization no longer depends on the action a. Hence, equation (II.2.3) holds for n = 1. Now suppose that (II.2.3) holds for n and let Q be (TT) 71 in Lemma II.1 to obtain I (rr) M<l>,t) n+1 < max a e D ( 7 ^ - (rrr+igfaht) T I (TT) f n ) t ) \ - (FT) g n | (77 - a, </>, t). 43 CHAPTER II. FULL INFORMATION After substituting the bound for | {TT) f' — (J T) g 71 r n | from the induction hypothesis, this reduces to (II.2.3) by an argument similar to that used for n = 1. Thus (II.2.3) has been established and the proof of the first claim is complete. The last claim follows immediately from Corollary 2 in Denardo [1967], since D(r), 4>, t) is finite for each (n, <fr,t). II.2.3 • The Revenue Function and Action Sets with Examples The revenue generated by action a in state (77, (j), t) is described by the function r(n,4>,t;a). The incremental revenue from one additional seat in inventory is Ar(?7, (p, rj; a) = r(r), 4>, t; a) — r(r) — 1, <f>\ a). The incremental value of selling a seats versus not selling any seats is Sr(n, 4>, rj; a) = r(jj, 4>, t; a) — r(r), <f>, t; 0). Note that I do not assume that r(r), (j), rj; 0) — 0. Some attributes of the reward function, which are plausible and which will be used in the following sections are now defined. Increasing in inventory: r(rj, <f>, t; a) is increasing in inventory 77 for each (</>, t) and action a. Discretely concave: Ar(?7,4>, rj; a) is decreasing in inventory 77 for each (0, rj) and action a. Decreasing in time: The revenue function r(n,<j),t;a) is decreasing in time rj for each (77, <p) and action a. Afflne form: r(?7 + a,<j),t;a) = r(n,(f),t;Q) + ap(<f),t) for each state (r),<j),t) and admissible action a, where p(<j>, t) does not depend on 77. Increasing increments: The revenue function is affine, p(<p, t) is decreasing in time rj, and 6r(r),(j),t; 1) is increasing t. Note that 6r(rj,4>,t;a) increasing in rj is the property used to name this attribute. Ordered fare classes: The fare classes can be ordered so that p' > p implies that r(?7,p\(3,rj; a) > r(i],p,0,rj; a). CHAPTER II. 44 FULL INFORMATION Accept/Reject and Splittable Batches I consider two possible cases — splittable batches and accept/reject. In the accept/reject case D(n,p,{3,t) — {0,/3} if (3 < n + a and is {0} otherwise; i.e. the whole batch must be accepted or nothing. The quantity a is the limit on the number of seats which can be overbooked, and is referred to as the "overbooking pad" by Subramanian et al. [1997]). It is introduced to ensure that the revenue function is uniformly bounded. In the case of splittable batches, D(r),p,(3,t) = {0,1,2,..., (3 A (n + cr)}; i.e. I decide how many seats out of the batch of size (3 to accept. Note that D does not depend on the time of arrival or the fare class, but only on (n,p). Simple Model with No Overbooking One of the simplest models is to let the revenue function be r(r}, p, j3, t; a) = ap and a = 0 so that there is no overbooking. This will be the setting of all our examples in Section II.5, both for the accept/reject and the splittable batch cases. For simplicity I have identified the fare class p as the revenue generated by a ticket in this fare class. It is easy to verify that that this revenue function possesses all of the attributes which were denned above. Simple Model with Overbooking A simple model which accommodates no-shows and overbooking is adopted from McGill [1989] and Subramanian et al. [1997]. In this model, as in the previous one, I denote both the amount of the fare and the fare class of fare type <f> by (j> to p simplify the notation. A booked customer will show-up at departure with probability p. This probability does not depend on the customer's fare type or time of arrival, and the customers decide whether or not to show independently. So if the final inventory at departure is n, then the number of customers who show-up at departure, X(TJ), has CHAPTER II. FULL 45 INFORMATION a binomial distribution with parameters c — 77 and p. At departure, the airline has to refund a portion of each no-show's fare. I assume that this refund, denoted by 9, is the same for each customer. (This assumption can be relaxed.) The airline is, in addition, penalized for the customers who cannot be seated in the plane. It is reasonable that this penalty is a convex increasing function, say /(•), of the number of customers who were denied boarding, [X(r]) — c]+. Let L (r]) = —E[f([X(rj) — c] )] represent the expected loss due to + 0 overbooking. Using the arguments in McGill [1989] and Subramanian et al. [1997]), one can show that LQ is concave and increasing. Let 7r be a fixed, measurable and admissible policy n that results in action a in state (rj,<p,t). The revenue under policy ir for the model with overbooking can be written as /•OO v (r), <f>, t)=a<j) -Y^ n / p [E(c - (r? - a) - X(rj - a)))0 - L {rj - a)]P(4>', ds | 0, t) Q d>>£C ^° + X) / v*(r>-a,<t>',s)P{<j>\ds \<}>,t) = a[<j> - 9(1 -p)P(<j>,t)} + p -[9(c-r )(l-p)-L (n-a)]P(^t) } + Y Q where P(<f>,t) = Y ^ p e c I o ° ^(^'J J / ~ a,<j>',s)P(<{>',ds \ <f>,t), ds | <j>, t) is the probability that the current arrival is the last before departure. Consider now a model without overbooking but with immediate revenue function r(n, <f>, t; a) of the form r(rj,</>,t] a) = a{<l> - 9(1 - p)P(4>, t)\ - [9(c -r,)(l-p)p L (v - a)]P{<f>, t). 0 That model, under the same policy it, achieves revenue v that satisfies n v (rj,(t),t) =r(rj,(p,t;a)+ n / Mv ~ a,$,s)P(<p\ds \ 4>,t), which has exactly the same form as the revenue for the model with overbooking. Thus one obtains that both models generate the same revenue under the same policy. The (11.2A) 46 CHAPTER II. FULL INFORMATION last one can be formulated as a Markov decision problem with optimality.equation {r(r,,<f>,t;a) + Y^ f° v{n ~ a,(j>',ds | <f>,*)}. (II.2.5) So the optimal policy and optimal revenue for the model with overbooking are the same as those of the model without overbooking and with immediate revenue function as above. The solution to the latter model can be found using the optimality equation II.2.5 (without overbooking). As mentioned, the concavity attribute for a revenue function of essentially this type was shown by McGill [1989] and by Subramanian et al. [1997]. The revenue function is decreasing in time provided I assume that the closer a customer arrival time is to 0, the more likely the customer is to be the last arrival; i.e. P(4>,t) is increasing in t for each <j>. The fare classes are ordered provided <f> and P(<fi, t) are p ordered. The other attributes are easily verified. It is apparent from Equation (II.2.4) that the refund 9 to no-shows can depend on fare type and time provided that the refund is increasing in t and is ordered by fare type. Simple M o d e l with Terminal R e w a r d The simple overbooking model can be somewhat generalized, by dropping the requirement that the immediate revenue be affine and introducing any (measurable) terminal reward, say Lo(n), which is not required to be npnpositive. The main requirement is that the nonzero immediate reward when selling no seats be due to the terminal reward only: r(n,(f),t;0) = Lo(r))(l — Tl(r),<f),t)). If that is the case then I call it a simple model with terminal reward LQ. To obtain structural results, further assumptions on LQ such as monotonicity, concavity in inventory n will be needed. CHAPTER II. II.2.4 47 FULL INFORMATION Transformed Control Problems The existence and uniqueness of a solution to the optimality equation imply that given the same state space So, sets of admissible actions D(n, (p, rj) and the same next stage operator T, control problems that result in the same immediate rewards are equivalent in the sense that the optimal expected revenue (value function) and the generated optimal policy are the same. It is also possible to transform the original formulation to one with different immediate reward but with the same optimal policy and the optimal value function that can be adjusted by certain function that can be computed separately. I formulate the latter result as a lemma after introducing some definitions. Definition II.l. Define L(n,<j),t) := ££L (T) r(-, •, 0)(n, <j), t). (T) n 0 n is then-fold composition of the operator T with itself with the convention that (T)°f(n, (j), t) =• L can be interpreted as the expected revenue, given state (n,(j),t), under the policy rejecting the current and all subsequent arrivals until departure. It has the property that TL(n,4>,t) + r (77, </>,£, 0) Ar(?7,cM,0) = = L(rj,(f),t), and that TAL(n,<j),t) + ALfafrt). Lemma II.2. A dynamic control problem with the immediate revenue r\(n,<p,t;a) can be transformed to one with immediate revenue r?., such that 7-2(77, <f>, t; 0) =0 and with the same optimal policy. If in the first case the optimal expected revenue is v then in the second one it is v — L: Proof. Let TT be a fixed, measurable and admissible policy TT that results in action a in state (77, <fi,rj). The revenue v under policy TT for the original model satisfies n 1^(77,(f>,t) = r(?7,(p,t,a)+ f v*dQ(rf,</>',q | 77,</>,t;a) 48 CHAPTER II. FULL INFORMATION It can be written as v (n, <j>, t) = r(ry, <f>, rj, a) - r(n - a, <f>, rj, 0) + r{n - a, <p, rj, 0) + n +TL(rj - a, <j>, rj) - TL(n - a, 0, t) + Tv (n - a, cj), t) w = r(n, </>, t, a) - r(n - a, (j), t, 0) + +L(r? - a, </>, t) + T(v„ — L)(rj — a, (j), t) = L(n, 4>, t) + r(n, <j), t, a) - r(n - a, (f>, t, 0) + -L(n, (p, 0) + L(n - a, <f), t) + T(v„ - L)(n - a, <f>, t). In the above I have added and subtracted identical terms and used the identity r(n — a, <fr,t, 0) + TL(n — a, <f),t) = L(r) — a, cf>, rj). It obtains that Vn(v, <i>, t) - L(r), (j), t) = r(n, (j), rj, a) - r(r? - a, <p, t, 0) - (L(rj, ep, t) - L(n - a, 0, t)) + T(v n Denoting v' = - L)(r/ - a, <p, t). — L we can write it as w <(r?, 4>, rj) = r(rj, <j), t\ a) - r(r? - a, <p, t, 0) + -(L(rj,<f),t) - L(r) - a,<f>,a)) + f vLdQ(rf,<!>',q\rj,^,t;a)}, so v and v' + L are equal for the same policy TT. Since TT was arbitrary the optimal n w policy for the original problem will be optimal for the transformed problem and vice-versa. • Suppose that if the first arrival after 0 at time q has type <j>' and finds an inventory of n, then the terminal reward is Lo(rj,(j)',t). The immediate reward in the Markov optimality equation includes a term due to that terminal reward of the form 2~Z^'ec Jo°° -^O(T?, 0', q)dP(</>', q \ 4>,t). In the next lemma, I show that for a given immediate revenue r i , with a corresponding L as defined above, if L is independent of time and fare type then there exists an equivalent problem with r2(n,4>,t;0) = XVec Jo°° L(r))dP(<j)', q | <f>,t). Equivalency means that the optimal expected revenue and the optimal policy are the same for both problems. L e m m a II.3. For a given r(r],<f),t;a), let L be the expected revenue from a policy selling no seats. If L is independent of time t and of the arrival type <p, then the control problem is equivalent to simple model with terminal reward L. 49 CHAPTER II. FULL INFORMATION Proof. Let TT be a fixed, measurable and admissible policy 7r that results in action a in state (77,0, i). The revenue v„ achieved under policy7r in the original problem satisfies Vn(v, <t>, t) = r(r/, </>, t\ a) + Tv^irj - a, <f>, t) This relationship can be transformed, by Lemma II.2, into v' (V, <t>, t) = r(n, <p, t; a) - r(r) - a, <f>, t; 0) + (II.2.6) v -(L(77,4>) - L(r, - a, </>)) + TvUv - a, <f>, t) (II.2.7) where v'^ = v — L. n Consider now a simple model with terminal reward equal to L(rj), and with immediate revenue /•OO r (r?, (j), t; a) := r(r], <f>, t; a) - r(r? - a, <f>, t; 0) + L(n - a) V 2 / dP(<p', q\<f>,t) for — T < t < 0. Note that the last term corresponds to the effect of the terminal reward L in the simple model with terminal reward and that r2(r],(p,t;0) = M*7)E^ /o~ W><zU>*)ld eC The expected revenue under a policy rejecting all customers in the new model is = E( "E / T L (»7^,«) 2 OO /• ^OO = m E "E / R ^w.ffiv) W) = \ ^'>«1 •. •))(*, 0 = LDP 00 = L(T?) ^ P(there is exactly n arrivals before departure | 4>, t) = £(77) n=0 So it obtains that L2(n,4>,t) = L2(rj) = L(rj). I now transform the simple model with terminal reward and immediate revenue function r , into a problem with r (ry, 0, t;0) = 0, using Lemma II.2. The 2 2 CHAPTER II. 50 FULL INFORMATION revenue v' achieved in the transformed problem under the same policy it is K(V, 4>i t) -r (v 2 a, = r(rj, <p, t\a) - r(rj - a, 0, t\ 0) + r (r] - a, <j>, t; 0) 2 0, t; 0) - (L(rj) - L( - a)) + V Tv' (v ~ a, <f>, *)}. (II.2.8) w By comparing Equations II.2.6 and II.2.8 it obtains that revenues in the corresponding transformed models are equal under the same policy, v' =• v' . That n n implies that the optimal policies in the transformed models are the same. Since any transformed model has the same optimal policy as the model before transformation, it follows that the optimal policies in the original model and in the simple model with terminal reward are the same. Because v = v' + L, and % =v' -\-L the revenues v„ n w lx and v are the same, which yields that the optimal revenues in both models have to n be the same, so the model with L independent from <f> and t, and the simple model with terminal reward L are equivalent. • L e m m a II.4. A given simple model with overbooking is equivalent (same optimal policy and optimal value function) to a simple model with overbooking with fares adjusted by the expected customer-dependent refund and the terminal reward due only to overbooking cost. Proof. Recall that the revenue function in the simple model with overbooking is r(ri,<f>,t\a) = a[<j> -6(l-p)P(<f> t)}-[6(c-r))(l-p)-L (>n-a)}P( f>,t) and P(<f>,t) = p E^'GC JO°° t 0 ( ds | (f>,t) is the probability that the current arrival is the last before departure. This can be written in the following way r(v, 0, t; a) = acj) - [9{c - (r? - a))(l - p) - L (i] p = a<p - [Li(n - a, p 0 a)]P(0, t) = (j), t) - L (v - 1,0, t)]P(<f>, t) 0 where Li(rj, <j),t) = 9(c — r})(l —p)) can be interpreted as part of the terminal reward due exclusively to expected no-show refunds. The revenue when rejecting a request is equal to [-Li(r?, (f), t) + Lo(r), (f), t)]P((f), t). The expected revenue under policy selling no seats, L(r), <f>,i) can be calculated to be equal to —Li(r],<f),t) + Lo(r),(f),t). By 51 CHAPTER II. FULL INFORMATION Lemrna II.2 the optimality equation with the immediate revenue in the new form can be transformed to one with the revenue being zero when rejecting a request. Since L\ is linear in 77, the revenue function for the transformed problem obtains as f (77,<f>, t; a) = a4 ~ A [Li(77,4>, t) - L (v, <j>, t)] = a[<t> - 9(1 - p)\ - A L (n, <t>, t). a a P 0 p 0 In the last expression one can assume the refund to be fare type dependent, denote it by <j)g, so that f(rj, t\ a) = a[<t> - <j> (l - p)\ - A L (v, <£, t). a p e 0 With that revenue function the optimal value function v* is equal to the original value function v* less L(rj,<j),t). Now note that when the booking process starts with capacity c = 77 then no no-show refunds are due, so that Li(c,<p,t) = 0, which yields that v* = v* — LQ. The same optimal value function obtains should one start with fares equal to 4> — 4>g(l — p) instead of <p and without no-shows refunds. Therefore each of p p the models with cf) and cj) — 9(1 —p) leads to identical transformed problem, with p p the same revenue and the same optimal value function and policy. Since Lo is the same in both cases it follows that by adjusting given fares by the expected amount of no-show refund an equivalent control model is obtained. II.3 • Basic Results Adopting notation from Sun [1992], define the function v° = Tv*, where v* is the optimal value function. Note that v°(r),p,P,t) is the expected value of having inventory level 77 just after the demand from a customer at time t was dealt with, given that there was an arrival of type (p, P) at time t and that an optimal policy is used from then on. The following lemma follows immediately from the optimality equation, which can be written as v* = !Fv . Q Lemma II.5. Suppose there is a request from a customer of type (p, P) who arrives at time t tofindan inventory level ofn. CHAPTER II. 52 FULL INFORMATION (a) If the request is splittable, then it is optimal to sell a* seats, where a* € arg m a x a € D ( ^ A t ) { r ( ? 7 , <j>, t; a) + v°(n- a, p, 0,t)}. (As mentioned prior to Theorem II.1, the largest action in the set will be chosen by convention.) (b) If the request is accept/reject, then it is optimal to accept the request for 0 seats if v°(rj, p, 0, t) - v°(rj - 0, p, 0, t) < dr(n, <P, t; 0). An example of an arrival process, which satisfies the hypothesis in the following corollary is when customers arrive according to a (single) renewal process and the fare type of each arrival is chosen independently with constant probabilities I 1 over the whole period — T, 0. The corollary follows from the previous lemma by noting that v° will not depend on the fare class p of the current arrival and from the hypothesis that the fare classes order the revenue function. C o r o l l a r y II.I. Suppose that the probability transition function for the arrival pro- cess does not depend on the fare class of the current state and that the fare classes are ordered by the revenue function. In this case, the fare classes under the optimal policy are nested. That is, if I accept a seats from the fare type (p, 0) then I accept at least the same number of seats from all fare types (p',0) with higher fares for the same inventory level, batch size and time. (i.e. p! > p). I use the above lemma to give a version of a theorem due to Sun [1992] in the semi-Markov setting. Similar results are shown in Lautenbacher and Stidham [1997] and Gallego and van Ryzin [1994]. T h e o r e m II.2. Suppose that the revenue function is increasing in inventory n. Then v*(n, 4>, t) is increasing in n for each ((f), t). Proof. Let TT* be an optimal policy and for inventory levels n > rj let k = n — rf. Define policy TT° as the policy, which ignores k seats in the inventory, but otherwise 53 CHAPTER II. FULL INFORMATION behaves like the optimal policy TT*. I.e. \TT*(ri-k,(j),t) for 77 > k I0 otherwise. First suppose that the revenue function is constant in 77. Then for each realization, policies TT* and TT° will choose the same actions and generate the same revenue. With the assumption that the revenue function is increasing in 77, policy 7r° might generate more revenue than 7r* because of the higher inventory levels. The optimal policy will generate expected revenue at least as large as TT°. Hence v*(v,4>,t) > TV,(r/,0,t) >v*(7/,<j>,t). (IL3.1) • Theorem II.2 states that when using the optimal policy, having more seats is better than having fewer. This result is true much more generally than for the nonhomogeneous arrival process which I am using, since the argument which leads to Equation II.3.1 holds for each realization. Thus the theorem holds for essentially any arrival process which is not affected by the policy being used and with immediate expected rewards increasing in inventory. II.3.1 Monotonicity of the Optimal Value Function with Respect to Time. A question similar, but more difficult, to that answered in Theorem II.2 is whether v*(r),4>,t) is decreasing in t. It seems as though the affirmative should be correct, since in a longer interval one should be able to make more money. There are some cases where applying a policy "as if less time were available" in the spirit of Lemma II.2 works. Two cases, which are familiar in the stochastic processes literature, are the nonhomogeneous Poisson process and the homogeneous semi-Markov processes. The last case I generalize to a process with a stochastically increasing transition function. 54 CHAPTER II. FULL INFORMATION Define a nonhomogeneous Poisson arrival process as an arrival process with a probability transition density of the form PO',ds | <f>,t) = \#(s)exp [A(s) where A^ is the intensity of fare type 4> a n A(t)1 ds (II.3.2) d A(rj) = / ° J2d>'£C ^'<)>( )dss t Note that the probability transition function does not depend on the current fare type <p, that this process has independent increments, and that probability of two or more arrivals at any time is zero. This type of nonhomogeneous Poisson arrival process has been used in other papers such as Gerchak et al. [1985]. Lee & Hersh [1993] used a discrete version of this model with the exponential interarrival distribution replaced by a geometric. Define A L(n,<j>,t) := L{n, <f>, t) - L{n - a,(p,t). a Theorem II.3. Assume that the arrival process is either nonhomogeneous Poisson or is homogeneous semi-Markov. In the homogeneous case assume that the revenue function r(r),<f),t;a) is decreasing in t. In both cases assume that r(r],(j),t;0) > 0. Then v*(n, (j), t) is decreasing in t. Proof. Suppose that tf < t < 0 and let h = t — t'. In the homogeneous semi-Markov case, the arrival process starting in state (77, 0, rj') will have the same distribution as the arrival process starting in state (r?, (j), t) except for the shift in the time parameter by h. So if I start the process in state (rj,(j),t'), run it for |rj| units of time using the optimal policy TT* as though I started at time t, then the arrival process will have the same distribution as the process started in state (77,4>, t) and the corresponding rewards will be higher since the revenue function is decreasing in time. Thus, after taking expectations, the value received will be no less then if starting in state (77,0, rj). More formally, let 7r°(77,4>, s) = TT*(n,(p,s + h) for t! < s < t' + \t\ and 7r°(77,4>, s) = 0 otherwise. Because the arrival process is homogeneous, the distribu- tion of the arrival process {($„, T„), n = 0,1,2,...} given the initial state (77,4>, rj') is 55 CHAPTER II. FULL INFORMATION identical to the distribution of the arrival process given the initial state (77,<f>, t). Since r(ry,<fi,s + h;a) < r(n,<fi,s;a) the corresponding rewards are higher when starting at t'. For s > t! -f \t\, I reject all arrivals, but do not lose revenue as r(r],4>,t;0) > 0 . Consequently, v*(rj, t') > v o(n, 4>, t') > v*(rj, 4>, t). n If the arrival process is nonhomogeneous Poisson, then the following argument shows that I can couple the end (from t on) of the process which starts at t' with the process starting at t. This is in contrast to the homogeneous case, where the first parts of the processes were matched. By hypothesis, probability of more than two arrivals at any given time is zero, so let N(t', s) count the arrivals during the interval t', s, given that the process starts in state (77, <f>, t'). It also holds that the distribution of the excess at time t of the process starting at time t', i.e. T^^i^i — t, is the same as the distribution of Ti — To of the process starting at time t. In fact, the realizations of the process {($7i, T„—t),n = N(t', t) + l,N(t',i)+2,...} starting in state (77, <f>,t') can be coupled with those of the process { ( $ « , T ), n = n 1,2,...} which starts in the state (77, (j), t). Construct a policy I T , which sells no seats between t' and t, as follows. 0 7T*(77, 4>,t) for s = 0 for t' < s < t 7r*(?7, (j), s) for t < t' s. Now consider a realization of the process starting in state (77, (j), t'), which has been coupled with that of a process starting in (n,(p,t). For that realization, since r(rf, <j>, t; 0) > 0, the policy 7r° achieves at least the same revenue starting in state (rj,(j),t') as does policy TT* starting in state (j},<f),t). Hence v^o(r],(j),t') = v*(r),4>,t). The optimal policy might do better than 7T°, so v*(r), (j), t') > v*(rj, (f),t). • C o r o l l a r y II.2. Assume that for each 77,0,t and a, bothr(r],<f),t;a)—r(r)—a,(f),t;0— A L(rj 4>, t) and L are decreasing in t. Also assume that a ) (77, <p, i). Then v*(r/, <f>, t) is decreasing in t. 0 £ 1^(77, </>, t) for each state CHAPTER II. 56 FULL INFORMATION Proof. By transforming the problem to one with immediate revenue r(r],4>,t;a) — r(n — a, 0, t; 0) — AL (r?, (fi, t), I am in the setting of Lemma II.3, since, by hypothesis, a the new immediate revenue is decreasing in t and zero for a = 0. So by Lemma II.2, the transformed model has the same optimal policy, and its optimal value function is equal to v* — L, where v* is the optimal value function for the original formulation and L is the expected loss from a policy rejecting all arrivals. Since v\ = v* — L one sees that if v* is decreasing in time then so is v* = v* + L, given that L was assumed decreasing in t. • The homogeneous semi-Markov process can be generalized somewhat. Define the arrival process (i.e. the probability transition function P) to be stochasti- cally increasing if for each faretypes <po and 0 i (a) Pr[<&i = 0 i | $o = 0o, TQ — t] is constant in t; and I (b) Pr[Ti > x | $ i = 0 i , $o — 00) To = t] is increasing in t for each x £ —T, oo. Property (b) is an ordering which was introduced by Veinott [1974] in an inventory context (also see Brumelle and Vickson [1975]) and is known asfirstdegree stochastic ordering. This ordering can be characterized by a cone of decreasing functions. For example (b) can be rewritten as (b') E[f(T\) | $ i = 0 i , $o = 0o, To = t] is decreasing in t whenever / is nonnegative I and decreasing on —T, oo. I One slight problem is that in (b') the decreasing test functions are defined on —T, oo, whereas the value functions which we are interested in are naturally defined on 1 I —T, 0. This problem is easily handled by defining value functions to be zero for positive values, which is reasonable since no money can be made from the flight after departure. Using the definition of stochastically increasing process contained in (a) and (b') yields the following lemma. Lemma II.6. If the arrival process is stochastically increasing, then Tf(n,(j),t) is I 1 decreasing for t € — T, 0 and nonnegative for each n and 0 whenever f is. CHAPTER II. FULL INFORMATION 57 Another assumption on the arrival process, that may sometimes be useful, and which leads to the same conclusion as Lemma II.6 is described next and proven in the Appendix. Remark I I . l . If f" dP((fi', q\(fi, t) is decreasing in t, for each pair (fi',(fi GC and for I 1 T each a < 0, then Tf(n,(fi,t) is decreasing for t G —T, 0 and nonnegative for each rj and (fi whenever f is. Let L(rj, (fi, rj) = VJ^° T r(-, •, •; 0)(T7, (fi, rj) be the expected revenue from foln lowing a policy which sells no seats. Lemma II.7. Assume that the arrival process is stochastically increasing and that 0 G D(r),(fi,t) for each state (77, (fi, rj). Also assume that for each (n,4>) and action a, r(n, (fi, t; a) is decreasing in t and that r(n, (fi, t; 0) > 0. Then {FTv) is decreasing in t and is nonnegative whenever v is decreasing in t and nonnegative. Proof. Suppose that v is decreasing in t and is nonnegative. We need to show that TTv(n, <fi, rj) = max{r(r?, (fi, t; a) + Tv(n — a, (fi, f)} (II.3.3) is decreasing in rj and nonnegative. The proof first shows that (fF'Tv) is nonnegative. Since TTv is no smaller than the expression being maximized evaluated at a — 0 and since r(rj,(fi,t;0) > 0, it is enough to show that Tv(n,(fi,t) >0. (II.3.4) But because T is just integration with respect to a nonnegative measure, v > 0 implies that Tv > 0. Hence the left hand side of (II.3.4) is greater than or equal to 0. To show that TTv is decreasing, write (II.3.3) again TTv{r], (fi, rj) = max{r(?7, (fi, t; a) + Tv(i] — a, (fi, t)} 58 CHAPTER II. FULL INFORMATION For each a, the first term in the expression being maximized is decreasing by hypothesis, and the last term is decreasing by Lemma II.6 since by hypothesis v is decreasing and the arrival process is stochastically increasing. Taking the maximum of a collection of decreasing functions preserves monotonicity. It follows that FTv is decreasing in t. • Theorem II.4. If the hypotheses of the lemma hold, then v*(r),<f>,t) is decreasing in t. Proof. Let Vo(ri,4>,t) = 0. Then by Lemma II.7, (TFvo) is decreasing in t and nonnegative since Vo = 0. It follows that (TF) (vo) is decreasing in t for each n. n Since the ordering in t and nonnegativity are preserved under limits it follows that v* is decreasing and nonnegative. • Corollary II.3. Assume that for each (77, <f>) and action a, both L(n, (j), t) and r(r), 4>, t; a) — r(rj — a, </>,£; 0) — A L(ri, a 0, t) are decreasing in t. Also assume that 0 G D(n,4>,t) for each state (77, 0, t). Then (FTv) is decreasing in t and is nonnegative whenever v is decreasing in t and nonnegative. Proof. I demonstrate the corollary by making use of the transformed problem with the same optimal policy and optimal value function adjusted by L. If the original immediate revenue is r(rj, 0, t; a) then the transformed formulation has the immediate revenue equal to r(j],<j),t;a) — r(n,(j),t;0) — A L(r],<f),t), which is decreasing a by hypothesis and is zero when a customer is rejected. Thus I am in the situation described by Lemma II.7, which yields that v* — L is decreasing (cf. Lemma II.2). Since L is decreasing in t, (v* — L) + L must be decreasing and so is the optimal value function of the original problem. II.4 • Booking Curves for Splittable Batches Some policies are more convenient to work with than others. A class of policies of interest are those which can be described by a set of integer-valued book- CHAPTER II. FULL INFORMATION 59 ing curves, r?*(0, rj), one curve for each fare type. Given a set of booking curves, the corresponding policy in a state (r],p,j3,t) sells no seats if rj < n*(p,/3,i); and otherwise (for splittable batches) sells the minimum of the batch size and rj — r)*(p,/3,t). The booking curves thus determine a critical inventory level for each fare type and time, below which no sales take place and above which as many seats as possible are sold. A policy of this class will be referred to as a booking curve policy. A booking curve which is decreasing in rj for fixed <j>, is particularly convenient computationally since it is piecewise constant and can thus be characterized by critical times, t*(n,(p) = max{rj : n*(<p, rj) — r]}, at which the critical inventory level changes. Only a finite number of critical times are needed — one for each inventory level up to the capacity of the plane and each fare type. One might also consider the class of policies which can be described by a set of critical times, t*(n,(p). Given a set of critical times and a state (77,4>,t), the corresponding policy is as follows: sell as many seats as possible to the customer if rj > t*(r},4>). As pointed out by Lee k, Hersh [1993], a set of critical times might exist for an optimal policy which cannot be determined by a set of booking curves if t*(ri, <f>) is not decreasing in rj for each fare type (j>. In the rest of this section, batches are assumed to be splittable. I first show a concavity property of the optimal value function which ensures that an optimal set of booking curves will exist. Then I consider two special arrival processes, nonhomogeneous Poisson and stochastically increasing, for which there is an optimal set of booking curves which are decreasing as the departure approaches. II.4.1 Existence of Booking Curves for Splittable Batches I begin this section by deriving some structural properties of the optimal value function and its auxiliary function v° = Tv, assuming that batches are splittable. Definition II.2. A function v € B is discretely concave if v(n,(j),t) —v(n — l,<f>,t) CHAPTER II. FULL INFORMATION 60 is decreasing in r) for each fare type 4> and time t. Results similar to the following lemma can be traced to Stidham [1978], Langen [1982], Lautenbacher and Stidham [1997], and Lewis et al. [1999] Lemma II.8. Assume that the revenue function is discretely concave in inventory and has affine form. Then J^viri^^t) is discretely concave whenever v € B is. Proof. Let <fi = (p,(3) and suppose v(r),<f) t) is discretely concave in 77, so that : AU(T7, <p, t) = v(r), (j), t) — v(r) — 1, <fr, t) is decreasing in 77. Let rj* — min{77 : p((j), t) > Av(n,<j),t) + Ar(r),<j),t;0)} — 1 if the set over which the minimum is defined is not empty, and rj* = c otherwise. If the current state is (rj, (p,t) and a seats are sold, then the expected value is r(r), <fr, t\a) + v(n - a, 0, t) = ap(0, t) + r(rj - a, 0, t; 0) + v(r) - a, 0, t). (II.4.1) Because v(-,<p,t) and r(-,4>,t;0) are discretely concave, the definition of rf implies that p(<j),t) > Av(r),4>,t) + Ar(rj, <fr, t; 0) for in > rf and that the reverse inequality holds for 77 < 77*. It follows that for 77 > 77*, the change in expected revenue from selling one seat, p{4>,t) — Av(r),<j),t) — Ar(n,(j),t;0), is not negative. So one should sell {77 — 77*} A + j3 seats. Similarly, no seats should be sold if 77 v(vA,t)+r(r],(j>,t;0) ^TJ(T7,0,£) = ^ 7j(77*,0,i) + r(77,0,t;?7-77*) 7J(T/ - 0, p, P, t) + r(n - p, p, p, t; 0) < 77*. Hence, if 77 < 77* if 77* < 77 < 77* +/? if 77 > 77* + (H-4.2) p. Using the affine form of the revenue function, the increment ATJ(77, <p, t) + Ar(77, <f>, t; 0) ATv(r),4>A = <p(0,i) if 77 < 77* if 77* < 77 < 77* +/3 ATJ(T7 - p, <f>, t) + Ar(77 - p, <j>, f, 0) can be seen to be decreasing and is discretely concave. ( -3) IL4 if 77 > 77* + p • CHAPTER II. Lemma II.9. 61 FULL INFORMATION The operator T preserves discrete concavity. Proof. This is clear as T is linear on B and transforms nonnegative functions into nonnegative functions. • The two previous lemmas immediately provide the following result. Lemma 11.10. If the revenue function is discretely concave with affine form, then the composed operators TT and TT preserve discrete concavity. Theorem II.5. If the revenue function is discretely concave with affine form, then the optimal value function v* (rj, <p, t) and the corresponding auxiliary function v° = Tv* are each discretely concave. Moreover, there is an optimal booking curve policy. Proof. The function which is 0 for all states is discretely concave, so (TT) 0 is also n discretely concave by the preceding lemma. By Theorem II.1, v* = l i m „ ^ ( ^ T ) 0 . r n oo Hence, v* is discretely concave. Since T preserves concavity, v° = Tv* is also discretely concave. II.4.2 • Decreasing Booking Curves The construction in Lemma II.8 of rf leads to a set of booking curves, which under certain conditions established in this section, will be decreasing. Let r?*(0, t) be the inventory level computed in the proof of Lemma II.8, where v is some discretely concave function in B. Then {rj*((f), -),<f) £ $} is a set of booking curves which correspond to the policy TT (JI,p,(3,t) = (rj — r)*(p,P,t)) A/3. + V Define a function v € B to have decreasing increments if Av(r},<f),t) = v(n, <p, t) — v(r) — 1, (j), t) is decreasing in t for each (77,4>). As it was the case with showing monotonicity of v* in t, it is easier to use a transformed formulation with the same optimal policy but with different immediate rewards that are equal to r(r}, (j), t; a) — r(r), (j), t; 0) — A L(r}, <j), t). If v\ is the optimal a 62 CHAPTER II. FULL INFORMATION value function of the transformed model then v* = u* + L, and if Av* is decreasing then so is Au* = ATJ* + A L , given that A L is constant in time. Lemma 11.11. Suppose that the revenue function has increasing increments and that the increments in L are constant in time, in addition to the hypotheses in Lemma II. 8. Then Tv has decreasing increments, AFv > 0 and 77* is a decreasing set of booking curves whenever v £ B is increasing and discretely concave and v has decreasing increments and is nonnegative. Proof. The definition of n* in Lemma II.8 can be rewritten as r]*(4>,t) — min{r? : 6r(rj,(p,t;l) > Av(rj,4>,t)} — 1. Since Sr(ri, <f>,t; 1)) is increasing and Av(n,4>,t) is decreasing in t (by increasing increments and the assumption of the theorem, resp.), it follows that rj*((j),t) is decreasing in rj. The transformed problem (cf. Lemma II.2) chooses the same optimal action in each state as the original problem. Let T' be operator that corresponds to T in the latter formulation. The AT'v for the transformed problem has the following form which one obtains using the affine form of the revenue function Av(r],(f),t) if 77 < 77* p(<fi,t)-AL( ,<fi,t) if 77* V < <v*+P V , (II.4.4) Av(r)-(3,p,0,t) -AL(n^,t) + AL(n-a,4>,t) if 77 > 77* + f3 Each of the three expressions on the right-hand side of the above equation is decreasing since, for any inventory 77, Av(rj,4>,t) and the p{(j>,t) were assumed to be decreasing for any (77, </>), and A L is constant by assumption. Hence AF'vin, (j),t) is decreasing in t. One has that AF'v > 0 in the first and the third case, since the Au > 0, A L > 0 and AL(n—a, 4>, t) > AL(n, <f>, rj), the latter by concavity and monotonicity of L . The second case obtains only when p(4>,t) > Av(r),4>,t) + AL(n,4>,i), so AT'Tv > 0 as well. From Lemma II.2 follows that that AFv is decreasing in t and nonnegative. AJFTJ = AJF'TJ + A L , which yields • CHAPTER II. 63 FULL INFORMATION Corollary II.4. Suppose that the revenue function satisfies the hypotheses of Lemma 11.11, AL is constant in time, and that v° has decreasing increments. Then v* has decreasing increments and there is an optimal set of decreasing booking curves. Proof. Recall that v* = Fv . 0 By Theorem II.1 TT* = TT O V So by Lemma 11.11, v* has decreasing increments. is an optimal policy. And by Lemma 11.11, this policy corresponds to a decreasing set of booking curves. • Decreasing Booking Curves for Stochastically Increasing Processes Theorem II.6. Suppose that the revenue function satisfies the hypotheses of Lemma 11.11 and that the arrival process has a stochastically increasing probability transition function. Let v° = Tv*. Then the increments Av*(n,4>,t) and Av (n,(j),t) are Q decreasing in t, and nonnegative. Proof. Let v(rj,<j),t) be the function which is 0 for all states. This function has decreasing (constant) increments in t because of the assumption, and is (clearly) greater or equal than 0. Since T maps decreasing nonnegative functions into decreasing nonnegative functions as argued in Theorem II.4, Tv has decreasing increments. By the previous lemma, (FT)v also has decreasing increments and (A!FT)v > 0. Conse- quently, v* = lim„_ o(^ ^")"0 has decreasing increments. Also, v° has decreasing r >O increments. • Decreasing Booking Curves for Nonhomogeneous Poisson Processes Theorem II. 7. Suppose that the revenue function has increasing increments and that the increments in L are constant in time, in addition to the hypotheses in Lemma II. 8. If the arrival process is nonhomogeneous Poisson then the increments Av°(n,4>,t) are decreasing int. Proof. From the assumption that L is constant in time it follows by Lemma II.3, that there is an equivalent formulation of the optimization problem with modified 64 CHAPTER II. FULL INFORMATION immediate rewards that are the same as those of simple model with the terminal reward Lo = L. As discussed in subsection II.2.4, since the immediate revenue is affine, I can take a simple model with overbooking with immediate revenue equal to ap(4>, t) when action a is taken in state (ry, 4>, t), and a terminal reward Lo which will now depend on each realization. As in Lemma II.3 suppose that t' < t < 0. Let ryo be an inventory level which is at least —a +1 but otherwise arbitrary, and let 0o be an arbitrary fare type. It is enough to show that Au (ryo, <j)o,t') > Ai>°(ryo, 0o, £). 0 For t' < s < 0 define V^rj, s) to be a random variable representing the revenue generated during the interval s, 0 using the policy TT given that there is inventory ry at time s and given that there was an arrival of type 0o at time t'. More explicitly, let to = {(0o,to), ( 0 i , £ i ) , . . . } be a realization of the arrival process with to = t'. Let N(t',s) be the counting variable introduced in the proof of Theorem 11.3. Then the value of V(r/, s) for the particular realization to is n=N(t',0) n=N(t' where rj +i n — r] — 7T(rj , <fr , t ) for n > n n n n N(t', s) + l and VN(t',s)+i — V- I the proof of n Theorem II.3,1 argued that the distribution of the arrival process from time t onward, i.e. the distribution of the arrival process {(<f> ,T -t),n = n n N(t' ,t)+2,...} N(t' ,t)+l, starting in state (4>o,t') is the same as that of the process { ( $ , T ) , n = 1,2,...}, n n which starts in the state (0o,i)- And, in fact, the realizations of one process can be coupled with each other. So consider a realization u> of the process starting in state (/?, (j>, t'), which has been coupled with that of a process starting in (ry, 0, t). Then one way of describing Av*(r]o, <f>o,t) is that it is the expected value of the first ticket which would be sold to a customer if the inventory at t were r/o but would not be sold if the inventory at t were r?o — 1. With this characterization in mind, define Y to be the random variable representing the time at which the extra seat is sold. So for the realization u, Y takes the value Y(u) = mm{t | tn > t,TT*(T] ,(j)n,tn) for u> — {(00)*')) (01) n n • • •} a n > TT*(Vn ~ l,<Pn,t )} n d where the inventory at time t is ryo. If the set CHAPTER II. 65 FULL INFORMATION defining Y is empty, I set Y = 1 or any other positive value, since no rewards are accumulated after time 0 (the departure). Note that because of discrete concavity, the booking curves exist and AV, .(f7o t)=TY r > (H-4.5) > where ry represents the additional revenue from the extra seat sold at time Y. Define the policy TT for the arrival process starting at t' with inventory rjo as follows: set one seat aside and apply the optimal policy as though the initial inventory were r/n — 1. However, once the time Y is reached, sell the seat which was set aside. Note that for each realization, the optimal policy might sell the extra seat before Y, but never after because of discrete concavity. More explicitly, the policy TT is TT*(r) - l,<j), s) n(V,<f>,s) = { 7r* The TT*(n - 1,0, s) + 1 (77, cj), s) for s < Y fors = Y for s > Y. policy TT is not Markov since after time t it needs to keep track of what the inventory would be assuming that there was inventory 770 at time t in order to tell if Y has been reached, as well as keeping track of the actual states. Nevertheless, TT is in the class of policies n which are admissible. Note that from the construction of TT, Vjrfao.O - K * ( ? 7 o - 1 , 0 = ry, (II.4.6) which by equation (II.4.5) is equal to AV -*(77o,i). Taking expectations, I have n £[V (77o,0] # -V°(VO - 1,0 = A 7 j ° ( 7 7 o , 0 , t ) , o which is less than or equal to Aw (770,0o, t') since the policy 7Jr is not necessarily 0 optimal. • As in Corollary II. 1, the booking curves are ordered by fare classes whenever the revenue function is ordered by fare classes. CHAPTER II. FULL INFORMATION 66 Corollary II.5. When the booking requests arrive according to a nonhomogeneous Bernoulli process then the booking curves are monotone. Proof. The proof in the nonhomogeneous Poisson case relies on the fact that the distribution of the next arrival after a fixed time t for a process starting at t' is the same as if the process started at t. In other words, the distribution of that excess time starting at t' is the same as that of the original interarrival times. This is clearly the case in the nonhomogeneous Bernoulli setting since arrivals happen at fixed time points and independently of each other. Therefore, in this case as well one can construct the same type of policy that was used to show the monotonicity of the increment. 11.5 • Examples In this section I present four examples which show that the optimal policy may lose the desired critical time property because Av°(rj, t) is not necessarily decreasing in t. All of the examples use the simple model with no overbooking from Section II.2.3. Two of the examples are for the accept/reject case. The first is a counterexample for Theorem 3 in Lee Sz Hersh [1993]. The second is a continuous time version of the counterexample with nonhomogeneous Poisson arrivals. The third example shows that even in the case of customers who request single seats, the critical type property might not hold. A variation of this example has independent increments. The fourth example shows that even if I relax the accept/reject constraint slightly, the function Av°(r], t) is not necessarily decreasing, and moreover, the critical time property need not hold. In this modification of the accept/reject constraint I continue to require that batches be either accepted or rejected as a unit whenever there is enough inventory to satisfy the request. However, a request can be partially satisfied if there is not enough inventory to satisfy it totally. So only the last batch which receives any seats can be split. CHAPTER II.5.1 II. FULL 67 INFORMATION A Discrete-time Counterexample for Lee & Hersh Lee Sz Hersh [1993] state that in the discrete time case, when the arrivals occur in batches that are either accepted or rejected as a whole, the optimal policy can be formulated in terms of critical times for each class and batch size. Their proof claims that the expected increment A V°(T], p, /?, t) = v°(r), p, (3, t) — v (ij — (3, p, (3, t) I3 Q is decreasing in time t for fixed fare type (p,ff)andfixedinventory level n. While for the single arrival case their work (ibid. pp. 255-258) is consistent with our previous results, there seems to exist a counterexample both in discrete time and continuous time for the accept/reject batch case. Consider a three-period decision model with two fare types in which batches are either accepted or rejected. Fare type 1 customers have fare pi = 1 and batch size two ((pi = (pi,2)). Fare type 2 customers have fare pi = .5 and batch size one (02 = (p ,1)). I also will use the fictitious fare type 0 ((po = (0,0)) as mentioned in 2 Section 2.1 to simplify the modeling of independent periods. Let — T = —2 so that the periods will correspond to times —2, —1, and 0. Suppose that for — 2 < t < — 1 and all fare types <fi that for — 1 < t < 0 and all fare types (p and that all other transitions have probability 0. At time 0 it is optimal to fill any request which can be filled, so 2 if v(v, (P, 0) 7? > 2 and (p =- (pi = < .5 if ry > 1 and (p = (p 2 0 otherwise. (II.5.1) 68 CHAPTER II. FULL INFORMATION At time —1 with 77 = 1 it is optimal to sell a seat to a request from fare type 02 since that is the only way a single seat can be utilized. If the inventory level is two, then a request from fare type 02 should be rejected since there will be no 02 arrival in the future to utilize the single seat, and the immediate revenue of .5 is less than the expected revenue of 2 x .3 = .6 which is obtained from the two seats in period 0. The value of two seats at time —1 is thus At time —2 with inventory level 2 a type 2 request for one seat should be satisfied since it yields a revenue of .5 plus the expected revenue of .5 x .5 for a total of .75, which is greater than the expected revenue of .6 which is obtained by rejecting the request. The value of two seats at time —2 is thus There is no critical time for inventory level 2 and fare type 02 since a type 2 request is accepted at time —2, rejected at time —1 and accepted at time 0. Also v(r),0I,O) is not discretely concave since Ai>(l,0i,O) = 0 and Au(2,0i,O) — 2. II.5.2 A Continuous Time Counterexample for Lee &c Hersh This is essentially the same example as in the previous subsection, but trans- lated to the nonhomogeneous Poisson context, which was described in Section II.3.1. From Section II.2, it follows that the optimal value function v and the auxiliary function v° satisfy the optimality equations for the nonhomogeneous semiMarkov case — namely, v* = Fv° and v° = (TjF)u°. Substituting Equation II.3.2 into the optimality equations, I obtain max {r(r?,0'; a) + ^(77 - a, 0', s)}A^(s) e x p ' A(s) - A(4)1 ds CHAPTER II. FULL INFORMATION 69 and u°(0,<M) =v°(vA,0) = 0 for all states (n, 4>, t). From the above I obtain in the usual fashion a system of backward Kolmogorov ODEs for v° and Av°. For v° the equations are <t>'€C subject to the conditions u°(0,^«) = « ° ( ' 7 . ^ 0 ) = 0 for all states n, <f> and £. And for Av° the equations are [Av°( ,<P,t)}'= -J2[^°(v^',t)-Tv ( ~l,<P',t)-Av ( ,cf>',t)\ 0 V 0 V V • V(t) <£'GC subject to the conditions Au (0,^,t) = Au°(r?,0,O) = 0. 0 I mention that for this type of process the monotonicity of v° and Av° in t could be derived directly from the discrete concavity and the form of the corresponding ODEs. It also holds that v°(r],4>,t) does not depend on 0. In this example I have two fare types, namely <f>\ = (1,2) and <p = (-5,1). 2 The process starts at time — T = — 3 and the intensity functions are Ai(t) = 0 t < -.5 1 t>-.5 70 CHAPTER II. FULL INFORMATION and \ (t) = 1 - Xi(t). 2 The corresponding increments as functions of time were generated as a solution to the following system of ODEs derived from the optimality equation: Av°(2,t)' -2 • = • Ai(t) + Ai(t) • v°(2, t) - X (t) • \{p - Av°(2, t)} - {p - Au°(l, t)}+] + P l 2 Av (l,t)' = 0 2 2 -\ (t)-{p -Av°(l,t)} + 2 2 Av°(2,0) = Av°(l, 0) = ATJ°(0, t) = 0, where the fare type component, (j), of the state has not been indicated since v° for a nonhomogeneous Poisson arrival process does not depend on it. This system was numerically solved using built-in Mathematica routine NDSolve. From Figure 1 it is clear that Av°(2,t) is not decreasing in t which implies that I do not have the optimal threshold policy with respect to time. It is possible to construct even more irregular examples using more fare types. IL5.3 Single Requests Without Critical Time Property This example shows that the critical time property need not hold even when each arrival has only one request. Customers arrive according to a renewal process with independent and identically distributed interarrival times each of which takes the value 2 with probability 0.5 and otherwise takes the value 5. There are two fare classes — <f>\ = (3,1) and <p = (1,1)- If an arrival 2 happens at time t, then the type of request is chosen independently of the arrival epochs and of the fare classes of the other arrivals. An arrival at time t requests first class with probability p\(t) and the discount class with probability p (t) {pi(t) + 2 P2(t) = 1). 71 CHAPTER II. FULL INFORMATION 0.5 Figure II.l: Graph of Av°(2,t) vs. time t. The probability that a customer has fare type <j>i is p\(t) = 1 if t > — 1 and 0 otherwise. The probability that a customer is fare type 2 is P2(t) = 1 —Pi{t), so that low fares arrive before high. Suppose that the initial inventory at time — T = —4 is one. If a type 2 customer arrives at time t < — 3 and the inventory level is still one, then in order for there to be a type 1 arrival before departure at time 0, then the next two interarrivals would have to be length 2 which has a probability of .25. So the request by the type 2 arrival should be satisfied since its revenue of 1 is larger than the expected revenue from a type 1 customer of .25 x p\ — .75. If there is a type 2 customer who arrives at a time — 3 < t < — 2 and the inventory level is one, then there will be a type 1 customer with probability .5 with an expected revenue of p\ x .5 = 1.5, so the type 2 customer should not be satisfied 72 CHAPTER II. FULL INFORMATION since its revenue is only p — 1. 2 If there is a type 2 customer who arrives at a time — 2 < t < 0, then there will not be a subsequent type 1 customer before departure at time 0, so the request should be satisfied. Consequently, the optimal policy does not have the critical time property for an inventory level of 2 since a type 2 request is accepted for —3 < t < —2 and rejected otherwise. Similar examples can be constructed using the above idea of a mixture of distributions (one short and one long) for the interarrival time distribution and with 1 low fares booking before high. An interesting one is to mix a constant 0 with an exponential. This gives an arrival process with independent increments which is not Poisson, by choosing the parameters suitably, the critical time property will not hold. II.5.4 Counterexample With Modified Accept/Reject Working in the same general setting I can show that even if I am allowed to split a batch as I run out of inventory, the nonhomogeneity destroys the monotonicity. With this modification, the set of admissible actions becomes D(n, p, 0,t) = {0,/?} if 0 < V and {0, rj] otherwise. Each fare type arrives according to an independent nonhomogeneous Poisson process, independently of the other processes. The intensity function for fare type <p = (p,P) will D e denoted by \ p. p There are two fare classes with revenues pi = 1 and p = -5, respectively. Class one customers always request a single seat. 2 Class two customers request either one or two seats. So there are three fare types with intensity functions An(t) = 1.4 if t > — 1 and 0 otherwise, A21CO = 0 if t > —1.5 and 10 otherwise, \ (t) = 0 if t > -0.5 and 1.2 otherwise. 22 Solutions were generated using the NDSolve routine in Mathematica to solve 73 CHAPTER II. FULL INFORMATION Figure II.2: Graph of Av°(4,t) vs. time t. the equations Av°(l,t)' = - \ (t) n •[ Pl - A « ° ( l , t ) ] - [A i(t) + A (t)] • {p 2 22 Av°(l,t)} , + 2 Av°(2, t)' = - An(t) • [ATJ°(1, t) - Av°(2, t)] - A i(*) • [{p - Av°(2,t)}+ 2 2 - {p - Av°(l,t)}+] 2 - A (<) • [{2 • p - Ar;°(2, t) - Av\l, 22 Au fa,*)' 0 *)}+ - {p - Ai/°(1, t} ], + 2 2 = - An(t)[Av°(r7 - 1) - Ar,°(ry,*)] - A (t)[{p - A ° ( r , t ) } 21 - {p - ATJ°(77 - U - {2 • p - Av°( 22 V - 1, t) - Av°( 2 V + ? - A (i) • [{2 • p - Av°( ,t) 2 2 2 V - Av\ n - l,t}+ - 2, *)}+] for ry > 3. As before the fare type component, </>, of the state has not been indicated since v° for a nonhomogeneous Poisson arrival process does not depend on it. The plot in Figure 2 shows that At>°(4, t) crosses the p level twice, and so 2 the optimal policy does not have the critical time property. Chapter III Cancellations III.l Introduction In this chapter I study modelling of cancellations. A cancellation happens when a customer who has bought a ticket or has paid for a reservation decides not to fly and informs the airline about his decision some time before the plane takes off. Since he does not fly, the customer may get some refund, depending on his agreement with the airline (type of the ticket bought). Typically, customers in higher fare classes such as full fare class, are granted full refund of the fare they paid. For other customer classes the refunds may vary and some may not be allowed to cancel (i.e. they forfeit the money paid for the ticket in the case they do not show up). The refund may be paid out following the cancellation. When an airline is informed of a single cancellation it knows that a one more seat is available for booking. In other words, the state variable - inventory of seats on hand, increases. This has an impact on the future decisions of accepting or rejecting booking requests from new customers. As evidenced by a series of examples in Subramanian et al. [1997], approaches that partially capture the effects of cancellations — be it by adjusting the fare and/or adjusting the probability of a no-show to make up for the losses due to 74 CHAPTER III. CANCELLATIONS 75 cancellations, can be improved upon significantly in terms of additional revenue so as to merit a more careful modelling of it. The yield management literature that includes cancellations is relatively scarce, and especially so when dynamic optimization models are concerned. The situation is somewhat better with respect to no-shows and overbooking, with a number of articles, some of which go back to 1960/70's. On the other hand, in the area of the optimal queue control, most of the models include the basic concept of customers leaving the system after completion of service, which naturally translates into customers' cancellation in the yield management setting. However, with a few exceptions (Miller [1969]), the models consider a queueing system in a steady state, where neither final overbooking costs nor refunds are an issue, and where time to departure is not part of the state variable. Still, as evidenced by relatively recent papers by Lautenbacher Sz Stidham [1997] and Subramanian et al. [1997], there are techniques like backward induction and concepts like "equivalent charging" that can be applied to nonhomogeneous Bernoulli-type processes, and possibly extended to Poisson models. Inclusion of cancellations leads to a more complex model that exhibits fewer useful features that could be used to prove structural properties of the optimal policy. Specifically, in the presence of nonlinear (convex) overbooking costs and some natural assumptions on the cancellation "process", the booking curves obtain but they need no longer be monotone. To fully model cancellations in the stochastic model one has to keep track of reservations in all customer classes that are allowed to cancel. This leads to a drastic increase in the number of possible states and may be perceived less practical. And without additional assumptions even less can be said about the structure of the optimal policy. Subramanian et al. [1997] and, to some degree, Karaesmen Sz van Ryzin [1999] present such models with part of the state variable being the vector of reservations in each class. In that respect, compared to the two articles, my model keeps track only CHAPTER III. CANCELLATIONS of the total inventory left. 76 Thus I am assuming that the "rate" of cancellations depends on that total number. This approach is reasonable with a judicious choice of the "rate". Subramanian et al. [1997] demonstrate that it can produce revenues within 0.5% of the revenue obtained for the more general model, provided the "rate" is chosen so as to correspond to the average cancellation rate in the more general model. With my state variable and with the assumption that cancellation "rate" is "convex" in the number of seats already sold, I obtain existence of booking curves. The aforementioned assumption is satisfied in the relatively realistic case where customers cancel independently from each other with the same probability. The concept of "concavity" of the cancellation "rate" is formalized in the definition of stochastic concavity, that can be found in various forms in the queueing or reliability literature. A stronger form of the stochastic concavity has been recently employed by Karaesmen & van Ryzin [1999] in the yield management context, in an (essentially) two stage problem, where the state variable was the vector of reservations in all fare classes. In that setting Queyrarme &; Fill [1999] present natural conditions that simplify the analysis of the previous paper. As I have already mentioned, monotonicity of the booking curves does not obtain in general. Some of the counterintuitive examples of Subramanian et al. [1997] may suggest that this is mainly due to the fact that after adjusting the fares for expected losses due to cancellation refunds the ordering of fares is not preserved, e.g. the net expected revenue from a first class customer might be less than a discount customer since the first one is more likely to cancel. From Lewis et al. [1999] (fares constant in time and the expected loss due to refunds apparently included in the terminal reward) and from my numerical examples in Chapter V, it may be inferred that booking curves are not necessarily decreasing even if ordering of fares is preserved. When the booking process consists of independent Poisson processes for each fare and if the cancellation process is modelled as a Poisson death process it CHAPTER III. CANCELLATIONS 77 is possible to give conditions assuring that the booking curves either decrease or increase with time left to departure. In that respect I present a condition, due to Lewis et al. [1999], with a new proof based on the theory of totally positive kernels. In addition, I include a conjecture on the maximum number of times the booking curve can cross a given straight line (and thus provide a conjecture on the bound on the number of times the optimal policy can change for a given inventory state). Existence of booking curves and some monotonicity results obtain, as well, for the more general model of Chapter IV when cancellations are included (similar assumptions). I present modifications necessary for that in the context of the more general state variable at the end of that chapter. III.2 Modelling Issues How does a model with cancellations differ from the one with no-shows? Firstly, cancellations, unlike no-shows, need not all happen at the same time-point and they occur strictly before departure. When a cancellation occurs, the inventory level will go up, which can affect the decision making in subsequent periods. In contrast, with only the no-shows present, whether a customer will or will not show up, does not influence it directly: I regard him as booked until departure. Secondly, with only the no-shows included, for a given inventory rj, the expected loss from the no-show refunds can be calculated either at the end of the booking horizon or sometimes at the time of booking a customer (say, when customers show up independently with the same probability of a show-up, as it will be the case in my model). The situation is different for cancellations. I would have to know the past history of inventories to be able to calculate, at departure, the refund owed due to cancellations. So in the model, the cancellation refunds have to be accounted for either when customer leaves or books. In the latter case another difficulty arises that has to do with computing L(r],<j),t), the expected revenue under a policy selling no seats. The definition of L CHAPTER III. 78 CANCELLATIONS now has to account for cancellation refunds. Note that since only the total number of seats in inventory is part of the state variable, given (77, (p, t), it may not be possible to calculate the expected loss due to cancellation refunds over the remaining booking horizon without further assumptions. One remedy is to assume either that refunds are class independent or that customers cancel independently from each other and from everything else with time to cancellation distributed exponentially with the same parameter. Thirdly, if the refunds are made at the time customer leaves, then since no cancellations can happen without seats sold beforehand, a slight technical problem is present when trying to apply successive approximations when cancellations are independent from any policy (cf. Section III.2.1): if <p is the cancellations event, p c c is the cancellation refund, n = c (the capacity of the plane, no seats have been sold) and v is the revenue function, then Av(c, (p , t) = v(c, <p , t) — (v(c, (j) , t) — p ) = p is c c c c c not necessarily smaller than Av(c — 1, <f> , t) = v(c, (p , t) — p — (v(c — 1, cj) , t) — p ). c c c All the above issues can be circumvented in special, but realistic situations. For instance, the fare offered at the instant when a customer books can be adjusted by the increment in the expected loss due to cancellation refunds. Distributing this penalty between decision periods has the additional benefit of making the refund customer-type dependent and there is no need to include it in the function L. It is relatively straightforward when customers cancel independently, with the same probabilistic distribution, but in general calculating that increment in penalty may lead to a more challenging subproblem. Subramanian et al. [1997] discuss it in the nonhomogeneous Bernoulli case with cancellations. As in previous chapter, the overbooking cost can be nonlinear but convex in the number of excess bookings. Lastly, the next stage operator T will now depend in general on the inventory left after decision was made in the current state, since the "intensity" of cancellations usually depends on the number of seats already sold. As a result of all those differences, with the cancellation present the conclusions that I can draw about optimal policies and value functions are weaker. c c 79 CHAPTER III. CANCELLATIONS Informally, I can still obtain the discrete concavity of the optimal value function and of the v° under very reasonable assumptions. With the existence of the booking curves being less of a problem their monotonicity remains subject to an additional condition. Fortunately, from results of Miller [1969], in the birth and death setting, there will only be a finite number of switches in the optimal policy. Based on my numerical examples it seems that in practical cases there should be at most two switches in the optimal policy, which still makes for a simple description of the optimal policy in terms of two critical times (instead of one) for each inventory level and fare. In the next section, I begin by considering a relatively simple model, where cancellations happen independently of inventory and no refunds are paid when they occur. At each such event the inventory level increases by one unless that level is equal to capacity. This case already exhibits essential features of what happens when customers are allowed to cancel. III.2.1 A Simple Cancellation Model with Nonrefundable Tickets I show here how to include cancellations by adding a new type of request to the arrival process considered in Chapter II. This is a straightforward way to expand the model of that chapter and it already displays essential features and difficulties attendant when customers are allowed to cancel. It is not completely satisfactory since it does not allow the "intensity" of cancellations to depend on the number of seats sold, so, for instance, a cancellation event can happen when inventory left on hand is equal to the capacity of the plane. Therefore a more general approach is presented in the following Section III.4. The new "customer type" corresponds to a cancellation and is denoted by <p . The arrival process remains denned independently from any policy. Sets c D(rj,(f),t) of admissible actions are unchanged for <p ^ 4> , but for 0 , D(rj,<j) ,t) is c C defined to be {0}. I will keep N-step contraction assumption on the arrival process. Since discrete concavity results are of interest, I will assume whenever necessary that c 80 CHAPTER III. CANCELLATIONS the batches are splittable so that for 0 ^ D(r),4>,t) <j) , c { 0 , 1 , . . . ,77 = A P{4>)}. I assume that bounded and measurable immediate revenue r(r?, 4>, t; a) is given. When a cancellation request (j) arrives and finds inventory level rj < c then that level c increases by one and r{q+1, <p , t; 0) is earned. If it finds inventory c (plane capacity) c then the inventory level does not change since no tickets have been sold, and revenue r(c,(f),t;0) is earned. The transition probability function (cf. Section 1.5 and II.2.2) for this instance of a semi-Markov decision process is defined as follows P(<p', s \<f),t) P(<p', Q(r)'.,(p',s | r?,0,a) := < if r/ =- 7? - a and <f> ^ 4> C s\cj) ,t) if r/ = c 77 + 1, 77 < c and <f> = P(4>\s\(f)c,t) if 77' = 7? = c and <j> = <p 0 otherwise. 4> C c I will call such model the simple cancellation model. Using the operator notation of Chapter II, the optimality equation is v = TTv. The operator T denned in Equation II.2.2, has the form (Tv)(ri,<f>,t) = X) / ° v(v,<l>',s)P(<l>',ds \ <P,t), for t ^ 0 € and for each state (77, </>, t) £ 5 , which now includes arrival type <p . It is the expected c value of function v at the next epoch of the arrival process given the current arrival type ((f), t) and given that immediately after making decision there are 77 seats left. When the revenue function is bounded and the AT-step contraction assumption on operator T is satisfied then the solution to the optimality equation can be obtained by successive approximations. The operator T has the following form. max ( ,^,,t){r(77, (j), t; a) + v(n - a, (p, t)} aeD 77 Tv(r),<\>,t) ?J(77+ = { l,(p ,t) c v(v, + l,0 ,t;O) +r(77 c <Pc t) + r(77, <f> , t; 0) c if <j) ^ 4> C if (j) = (p c and 77 < c if 4> = 4>c and 77 = c The operator T is a Af-step contraction if, for instance, P(4>',s \ 4>,t) is such that 81 CHAPTER III. CANCELLATIONS there is at least probability e that an interarrival will exceed d regardless of the state (cf. remarks after Assumption II.3). Lemma III.l. Assume splittable batches. The operator T preserves discrete concavity whenever r(rj,<f>,t;a) is increasing and discretely concave in n for any (4>,t) (including <p = <f> ) and a. c Proof. Let v, discretely concave and monotone in 77, be given. When 4> ^ <f> or when c (j) = cj) and n < c the proof is the same as in Lemma II.8. When 4> = <j) and 77 = c c c then ATv(c,</> ,t) = 0 < Av(c,4> ,t) + Ar(c,(f) ,t), c c c which concludes the proof since the right-hand side is nonnegative by hypothesis. • Lemma III.2. The operator T preserves discrete concavity. Proof. Follows by the same argument as proof of Lemma II.9. • Theorem III.l. Assume simple cancellation model with splittable batches. If the revenue function has affine form and r(n, (j), t; a) is increasing and discretely concave in 77, for any (<p,i), a € D(rj,<[),t), (including (j) =• 4> ) and batches are splittable C D(rj,(j),t) = { 0 , 1 , . . . , 77 A / ? } , then the optimal value function v*(r],<f),t) and the corresponding auxiliary function v° = Tv* are each discretely concave. Moreover, there is an optimal booking curve policy. Proof. I first note that TT preserves monotonicity in 77. Start with Vo = 0, which is monotone and discretely concave. Using Lemmas III.l and III.2, those properties are preserved at each iteration. By successive approximation I obtain that v* is discretely concave, and so has to be v°. As before, discrete concavity of v° implies existence of booking curves. • Corollary III.l. Assume a simple model with terminal reward and splittable batches. Assume that the arrival process is defined independently from any policy and that it 82 CHAPTER III. CANCELLATIONS includes a cancellation type. When tickets are nonrefundable in the event of a cancellation and when the terminal reward is increasing and discretely concave in inventory rj, then v* and v° are discretely concave. Moreover, there is an optimal booking curve policy. Proof. In the simple model with terminal reward Lo(rj) it was required that r(n,(p,t;0) = Lo(rj)(l — Tl(rj,(j),t)), for all types of request <p. Since there are no cancellation refunds (tickets are nonrefundable) this requirement is satisfied for (j> = <f> , c i.e. r(n,(pc,t;0) = Lo(r?)(l — Tl(n,(f> ,t)), which is monotone and discretely concave c in n by hypothesis. The assumptions of Theorem III.l are satisfied and the claim follows. • The property of establishing whether the booking curves are decreasing is a trickier one, and will be addressed in the section on total positivity. The monotonicity of v* follows under same assumptions as in the full information case without cancellations (Chapter II). The validity of those assumptions for the current model follows naturally and will be demonstrated from results of the forthcoming sections, where I consider a more general situation that includes the simple cancellation model with nonrefundable tickets, cf. Example III.2. The function L, the expected revenue under a policy selling no seats has the following form. Define an operator To : B —• B if 0 r(rj, <f>, t; 0) + v(n, (j), t) T v(r], <t>,t)v(r) = <+ 1, <j> , t) + r(rj + 1, <j> , t; 0) 0 c c v(r], (j) , t) + r(r), <f> , t; 0) c c ^ <p c if 4> = <\> and r? < c c if (p = 4> and r? = c . c The L has then the form oo L(77 0,t) = ^ ( r ^ o ) u ( » 7 , ^ t ) . n ) n=0 Theorem III.2. Assume that the arrival process (which now includes booking requests and cancellation requests) is stochastically increasing in t and that for each (n,<p) and action a, either r(n,4>,t;a) is decreasing in t and r(rj, 4>,t;0) > 0 or both CHAPTER III. 83 CANCELLATIONS L(T], (j), t) and r(jj, 0, t; a) — r(n — a, 0, t; 0) — A L(n, <f>, t) are decreasing in t. Also a assume that 0 e D(n,(j),t) for each state (n,<f>,t). Then v*(n,<j),t) is decreasing in Proof. Same as that of Theorem II.4. Note that for <p = <p , r(n,<f),t;a) — r(n — c a, (p, t; a) — A L(r?, 0, t) equals 0 as the only action available is a = 0. Also note that a T preserves monotonicity in time. III.3 • Stochastic Concavity In this subsection I present the definition of the stochastic concavity with a lemma that I will find useful in modelling cancellations. I use the definition of stochastic concavity as presented by Li &; Shaked [1994]. The same property, however, can be found in earlier work of Helm &; Waldmann [1984], who in turn refer to Kirstein [1976], they call it the (2)-monotonicity. Definition III.l. (C.f. Li & Shaked [1994]-) A sequence of random variables X , t] = — a, . . . , c is stochastically concave if for every increasing and concave v function v, Ev(X ) v+1 - Ev(X ) < Ev(X ) - EviX^Jor v v all -a + 1 < rj < c - 1. Lemma III.3 provides an analytical condition for stochastic concavity. The idea behind it is closely connected to the second order stochastic dominance. Lemma III.3. Let v be increasing and concave in inventory n. If F„ is the tail of the cumulative distribution function of X„ then Ev(X i) — Ev(X ) is decreasing in v+ v rj if and only if Va?, AF i(s)ds is decreasing inn. v+ Proof. Brumelle & Vickson [1975]. An intuitive proof that follows ideas in Hanoch Sz Levy [1969] is included in Appendix. • CHAPTER III. CANCELLATIONS III.4 84 Cancellations, Overbooking and No-Shows with Full Information I show here how to include cancellations in addition to the no-shows and overbooking costs, in the full information model. The main assumption I make is that the decision epochs are the times of arrivals of booking requests and that between each two consecutive customer arrivals a random number of cancellations happens (in the queueing theory terminology, the system is inspected at arrivals of booking requests). It is a reasonable model as there are no available actions to the decision maker when a cancellation request arrives. The number of cancellations can, in general, depend on the type <j>, time t of the current arrival and inventory left n and on the type (j)' and time q of the arrival of the next booking request. The fare charged to a customer will be adjusted by his expected cancellation refund (and ultimately will be adjusted for a no-show refund as well). In the model the airline credits itself with the expected revenue rather than simply allow for a debit at time of cancellation. An additional benefit of including the expected cancellation refund at the time of booking the customer is that, in some situations, I can make the refund depend on the fare type and booking time as well. This possibility has been noticed in an earlier work of Johansen & Stidham [1980]. The approach was named the equivalent charging scheme. It has been used in the relatively recent article in the yield-management literature, Subramanian et al. [1997]. For instance, when customers show up independently from each other with the same probability and when they cancel independently from each other with the time to cancellation distributed exponentially with the same intensity then the adjusted fare can be taken to be independent from the current inventory. That approach is possible because of the fact that cancellations and no-show refunds enter linearly into the revenue under any policy, so I can allow them to depend on the customer's fare and credit the revenue function with the expected reward at the CHAPTER III. CANCELLATIONS 85 time of the booking. The adjusted fare will in general be time dependent, since probability of cancellation depends on the time customer books. So, henceforth I assume that, in the model, there are no refunds made at the time customer cancels. Assumption III.l summarizes those properties that underlie model considered here. It will be in force throughout the remainder of this work, whenever cancellations are considered. Assumption III.l. 1. Semi-Markov Cancellations. Decision epochs are times of arrivals of booking requests. Cancellations happen between consecutive decision epochs. The number of cancellations C between two consecutive n decision epochs n and n + 1 conditioned on time of the current arrival T and n its type the time of the next arrival T i and its type $ +i and the invenn+ n tory of r\ seats left after a decision was made at time T is independent from n all other random variables of the model. 2. Adjusted fares. / assume that each fare is net of the expected cancellation and no-show refund (e.g. if customers cancel and show up independently from each other). In the model, nothing is paid out when a customer cancels. Let C denote the random variable that counts the number of cancellations n that happen between n-th and (n + l)-st arrival of the booking request process. To explicitly show the dependencies involved I will sometimes use C(<f)',s\<t>,t,n) to denote the number of cancellations after the current arrival of type 4> at time t with inventory on hand n and before the next arrival of type 4>' at time s. I will suppress some of the arguments of C whenever context allows. When <f>, <f>' are fixed, I will write simply C(s,t,n). For fixed (<j>,t) and (</>', s), define Y , n = a, . . . , c to be v the inventory at the next arrival epoch after all the cancellations that happened in between have been accounted for: Yr, = Y„(<j>, t, <(>', s)= V + C (<(>', s; (f>, t, rj). It follows from the assumption of semi-Markov cancellations that given state (77,4>, t) and policy u the inventory level at the next state of the decision process will CHAPTER III. 86 CANCELLATIONS be 77 - 7r(r?, /,s;0,t,7?-7r(77,0,t)). cM) + C((j)' Let pi(<j)',s,<j),t,k) denote the probability that C((j)',s;<j),t,k) = i. When <f> and <j>' are fixed, I will denote it by Pi(s,t, k). The arrival process is defined independently from any policy. So for a given type and time of current request (</>, t), the time and type of the next request are independent of the remaining history of the process. Given inventory 77 left after an action was taken in the current state, the number of cancellations that will happen until the next arrival, by definition does not depend on any past inventories or arrival types or their times. So for any Markov policy TT, the states visited by the decision process do form a semi-Markov process. The probability transition function Q, which governs the dynamics of the semi-Markov decision process (cf. Section 1.5), is defined next. Suppose that the process arrived into state (77, cf), t) and that an admissible action a has been chosen. Then the probability that the next arrival occurs before time s, is of customer type (<f)'), and finds inventory level 77' is = 77 — a +i otherwise. For a fixed Markov policy 7T, realizations of the semi-Markov decision process can be obtained in the following way. Start with a current arrival type $ 0 at time To and an initial inventory of 770 seats. After action 7r(?7o, $o,To) was taken, 77 = Vo — 7r(?7o, $0, To) seats are left. The type $1 and time T\ of the next arrival are then sampled from P ( $ i , T\ | $0, To). The number of cancellations Co that occur until the next arrival epoch is sampled fromp(.)($',Ti, | <fr,To,?7). That arrivalfindsinventory of 77 + Co and the process is repeated. So, for a fixed policy TT, the decision process moves from state (r)n - 7 r ( » 7 n , * n , T „ ) , $ , T ) to state ( 7 7 i , $ „ i , T „ i ) with random sojourn time n n n + + + in between of length ( T i — T ), and a random number of cancellations C with n + n n CHAPTER III. 87 CANCELLATIONS distribution depending on r?„ - 7 r ( r ? „ , $ , r „ ) , $ , T „ and $ „ + i , T i , where Vn+i = n Vn -ir(Vn,$ ,T ) n n + n n + C. n The immediate revenue function r(r/, 0, t; a) and actions sets D(v, 4>, t) have been defined for a general Markov renewal decision process in Section 1.5. Assumptions and examples are presented in Section II.2.2 and in Section II.2.3 respectively. To obtain discrete concavity-type results I will assume, whenever necessary, that batches are splittable, i.e. that D(rj,</),t) =- {—a,..., rj A The optimality equation {r(v,(f),t;a)+ / v(rf,<f/,q)dQ(rf,4>',q\ri-a,<l>,t)} can be written using operator notation as v =- TTv. Specific forms for those op- erators that reflect the current situation are given in the sequel, after necessary definitions have been introduced. When T is an TV-step contraction (Assumption II.3), immediate revenue function is bounded, action sets are finite and only depend on r) and (3 then the optimality equation is valid and its unique solution can be obtained by successive approximations (Section 1.5 and Section II.2.2, Theorem II.1). I will henceforth assume that the arrival process determined by P((p',s \ 4>,t) and underlying the operator T, makes T an TV-step contraction, and that all the properties just mentioned are in force. Let Ey denote expectation with respect to the v distribution of the random variable Y , which depends on (0, t) and ((f)', s). With the v probability transition function Q as above, the operator T has the following form pec III.4.1 Attributes of the Cancellations Process with Examples I define now two plausible attributes of the distribution of cancellations that will be needed in demonstrating discrete concavity of v* and v°. 88 CHAPTER III. CANCELLATIONS Stochastically monotone cancellations. The random variables Y„ are stochas- tically increasing in n, for fixed (4>,t,(j)',s). Stochastically concave cancellations. The random variables Y are stochastiV cally concave in 77, for fixed (<f>,t,(j)',s). Example III.l. When the number of cancellations between two consecutive arrivals, given inventory r/ is equal to the number of deaths in a death process with intensit that is decreasing and convex in rj then Assumption III.l is satisfied and the cancel tions are stochastically increasing and concave (Helm & Waldman [1984],Kirstein[197 Example III.2. Assumption III.l is satisfied when the lengths of customers' stay in the system are independent and identically distributed with expon(fi). C(s,t,k) is then binomially distributed with (c — k, 1 — e ^ ^ ) , where c is the capacity of the - 3- plane. It is also satisfied in the simple cancellation model with nonrefundable ticke In both cases cancellations are stochastically increasing and concave. III.4.2 Basic Results and Discrete Concavity I formulate now an analog of Theorem II.2. Compared to it, its proof requires more work because of the presence of cancellations that depend on the inventory r}. Theorem III.3. Assume stochastically increasing cancellations. Suppose that the revenue function r is increasing in inventory 77. Then v*(r),(f),t) is increasing in 77 for each (<j),t). Proof. Let ^0(77, <f), t) = 0. Clearly, 7jo(77 + 1, <fi, t) > 1*0(77,<p, t). If Vi is increasing in 77 then so is Tvi since r is increasing in inventory. Recall that for fixed 77, t, s and 4>', <f>, ^77+1 > S T ^77, by hypothesis. This inequality is preserved when I take expectations with respect to both random variables. Therefore, EY Y I V+1 V+ > EY Y increasing in inventory for fixed (<f>,t) and (cf)', s), and so is (t>'£C V V and Ey^Y^ is 89 CHAPTER III. CANCELLATIONS One obtains that T preserves that property so it has to follow that the composed operator TT preserves it as well. Passing to the limit I obtain the inequality 7/(77 + 1,0,*) > • 7/(77,0,i). From its form it is clear that T remains linear and that it transforms nonnegative functions into nonnegative functions. The operator T defined in Equation II.2.2 retains all the properties I demonstrated in previous sections. Therefore I omit proof of the next lemma. Lemma III.4. Assume splittable batches. Operator T preserves discrete concavity whenever r(n,<j),t;a) is discretely concave for any (4>,t) and a. Lemma III. 5. Operator T preserves discrete concavity and monotonicity in inventory n, whenever cancellations are stochastically concave and monotone. Proof. Let a function v be increasing and discretely concave in 77. Fix the t, s and the corresponding faretypes 0,0', and suppress them as arguments. By hypothesis, {Y , r} = —a,..., c} is stochastically increasing and concave. v Therefore E MYrH-i) > E v(Xv) Ytl+ Yn and £ ? y , « ( r „ ) - EY„V(Y ) < EY v(Yn) + 1 + 1 v n ^ w p V i ) . Both inequalities hold for each (4>',s, 0, t). For instance, when this dependence is written out explicitly, the last inequality becomes £ ^ 7 X ^ + 1 ( 0 ' , s, 0,t), EY V(Y ((P\ V V 8 0', s) - E v(Y„(<l/, , 0, t), 0', 8) Yv - EY^AYV-I S, 0,rj), 0', s) < *. <t>y *).<£', )- s Averaging with respect to P(0', s | 0, rj) was shown to preserve monotonicity (cf. the definition of T and proof of Lemma II.9). It obtains that the modified operator T preserves monotonicity and concavity in 77. CHAPTER III. CANCELLATIONS 90 • The discrete concavity of v* and its consequences now follow from the last two lemmas in exactly the same way as in Theorem II.5, so the proof of the next theorem is omitted. Theorem III.4. If the revenue function is discretely concave with affine form and batches are splittable, then the optimal value function v*(rj, (j), t) and the correspondin auxiliary function v° = Tv* are each discretely concave. Moreover, there is an optimal booking curve policy. Proof. Omitted. • In my model with cancellations, given the fact that the current customer arrival is the last one before departure, there still may be cancellations taking place after that arrival. Their expected number should change with time to departure. So, for instance, the expected value of the overbooking penalty should change as well if one nears departure. In particular, when I add cancellations satisfying Assumption III.l to the simple model with overbooking, the function L will become a function of both inventory r? and time t, it will remain concave and increasing in inventory and may be strictly decreasing in t, in contrast to the case with the no-shows only, where it was constant in time. III.4.3 Monotonicity of the Value Function in Time Under the same conditions as in the full information case, monotonicity of the expected value obtains for homogeneous semi-Markov, stochastically increasing and for a nonhomogeneous Poisson process. I state the theorems without proofs, which go verbatim as in the case without cancellations. Theorem III.5. Assume that the arrival process is either nonhomogeneous Poisson or is homogeneous semi-Markov and that 0 G D(n, <j), t) for each state (n, <p, t). Let, in addition, for each n, <j), t and a, either r(r], (j), t; a) be decreasing in t and r(r?, <p, t; 0) > 91 CHAPTER III. CANCELLATIONS 0 or both r(rj, <f>, t; a) — r(n — a, 4>, t; 0) — A L(n, </>, t) and L be decreasing in t. Then a v*(rj,(f),t) is decreasing int. Theorem III.6. Assume that the arrival process is stochastically increasing, and that 0 £ D(rj,4>,t) for each state (n, <p, t). Let, for each rj and action a, either r(rj,(f),t;a) be decreasing int andr(rj,(/),t;0) > 0 or both L(-n,<f),t) andr(n—a,(j),t]0) A L(rj,(j),t) be increasing int. Then v*(n,4>,t) is decreasing int. a When investigating when L(r\, (f>, t), and AL(r],4>,t) are monotone in time, 1 need to look at the variable Y(n,<t>,t)i which is defined below. Definition III.2. Random variable Y^ \ >t is the inventory at departure time just before the no-shows are realized, given that the current arrival is of type </> at tim t, inventory left is rj and under a policy selling no seats. Let F^^ \, F^,t) t be its cumulative distribution function and its tail distribution, respectively. In some situations it is easier to see whether L and AL are monotone. One of those is the simple model with overbooking from Section II.2.3 that has been adapted to accommodate cancellations satisfying Assumption III.l. In that model the revenue function has an affine form and by Lemma 11.4, I can assume that fares have been adjusted for the no-show refund and take r(rj,cj),t;a) = ap(<j),t) + r(r) — a,<p,t;0). The terminal reward Lo(rj) that is due to the overbooking cost has been distributed among decision epochs and results in r(r/, </>, t; 0) = Lo(n)P(4>,t), with P(4>,t) — 2~2<j>'ec Ja° Pift'ds \ 4>,t). When cancellations are allowed to happen between two consecutive epochs then r(n, (p, t; 0) takes on different form since the final inventory when no more arrivals occur is now greater than inventory rj left in the current state. It is now r(n, 4>, t; a) = ap(<fi, t) + E Lo(y^_ ^,t) | current arrival is last, (rj — a, 4>, t) ai •P(current arrival is last | <j>,t). I will call such a model a simple model with overbooking and cancellations. I have the following two lemmas. CHAPTER III. 92 CANCELLATIONS L e m m a III.6. Assume a simple model with overbooking and cancellations. IfY^^t) is stochastically decreasing in t for each (n, <f>) then L(rj, 0, t) is decreasing in t. Proof. From the definition of L follows that oo L(ri,<l>,t) = Y (X) r(;;-,0)(V,<l>,t) n l = n=0 oo = J2E[r(Vn,$ ,T ;0) n \ n = r?,$ = 0,T = t . n 0 0 O n=0 For any realization of the arrival process, under policy selling no seats the final inventory just before the no-shows, starting with no = n and <&o = </>, To = t, is equal to N(t,0] where the last term C(n o],^ ( ] ,T } ,^N(t,o}, N(t,o]) T N(tt N tt0 +1 N{tfi +1 is understood to count the number of cancellations between TJV^O] and departure time (immediately after time 0). This yields 5 ^ , , * T „ =- ^ o . ^ o . T o n ni It follows that oo L(n, </>,t) = ^ E [ £ [ L ( y 0 W i $ 0 i T o ) |T > O,^,^,^]- n+l n=Q P(T n+1 ^2E^Lo(Y > 0 | $ „ , T „ ) I r? = n, $ 0 ) {Vi<Ptt) 0 = 0,T = t O | exactly n arrivals,n = n,$o = <f>,T = t 0 0 n=0 P(exactly n arrivals | rjo — n, $o = 0, To = t) = = EL (Y^ )) 0 TT Now claim follows from the fact that the LQ is increasing in n and that Y( \ VTPIT stochastically decreasing in t. is • CHAPTER III. 93 CANCELLATIONS Lemma III.7. Assume a simple model with overbooking and cancellations. If F{n+i,4>,t){ ) — F(-q,<t>,t)( ) * increasing in t for each (n,<f)) and z then A L(n,< z z s a is increasing in t. Proof. It is enough to demonstrate the claim for a = 1. As in the proof of Lemma III.6, I obtain that L(ri,4>,t) = EL (Y^ _ j - ). 0 v ELQ^Y^^)) and that AL(i],<j),t) = EL (Y( 0 \.) V!4>TT — Following the idea of the proof (Appendix) of Lemma III.3, the last 1< >it ) difference can be written as EL (Y 0 ) {V+LTM - EL (Y 0 ) (RII<J>IT) = f (F , j (z) (r +1 tt) - F (z))dL (z). (rJ!<j>>t) 0 J—a This expression will be increasing in time if the integrand is increasing in time for each z, and (77, <p). • Corollary III.2. Assume either the simple cancellation model with nonrefundable tickets and with stochastically increasing or Poisson arrival process or the case where cancellations between two consecutive arrivals follow a Poisson death process with inventory dependent intensity p,^. Then the function L is decreasing and A L is a increasing in t. Proof. Omitted. III.5 Condition for Monotone Booking Curves in Presence of Cancellations In this section I present a condition, which ensures monotonicity of the expected optimal increment Av° in time, and which consequently implies that the booking curves are monotone when fares are constant (e.g. unadjusted). The condition is due to Lewis et al. [1999]. I offer a different proof, based on total positivity, that in my opinion can shed some light on the possible generalization of the condition in question. • 94 CHAPTER III. CANCELLATIONS The setting is that of Poisson arrivals of single booking requests that are independent for each fare and of cancellations following a Poisson death process with intensity depending on the number of the already booked customers. There is K fare classes, with each fare p arriving with intensity X , A := 2~2k=\ ^k- The point of k k view in this section can be described as that of a birth and death process where the birth rate can be controlled by admitting only some classes of customers and where cancellations occur with intensity fj,„ that depends on 77. I will assume that the cancellation rate is decreasing and convex in 77: p, +i —n > p^ — p -\. Overbooking v TI n cost that is convex and increasing in excess bookings is present. In the model no refunds are paid at time of cancellation. It is required that each fare (possibly net of the expected cancellation and no-show refunds) be constant. It can be verified that such a model fits into the framework of Section III.4. Results of that section imply now that v° is concave in 77 and that the booking curves exist. Apart from restrictions that follow from the above assumptions, the results of this section may be only of moderate importance to practitioners as they imply that, informally, the influence of the terminal overbooking costs are either small (for decreasing booking curves) or large (for increasing booking curves). I include a conjecture about a maximum number of switches in the optimal policy, which, if proved could likely be of more use in applications. Total Positivity Definition IIL3. A function K(x,y) of two real variables ranging over linearly ordered one dimensional sets X and Y respectively, is said to be totally positive of order k (TP ) if for all x\ < • • • < x , y\ < ••• < y , and 1 < m < k k m m det(f(xi,yj)) > 0. Totally positive functions possess a variation diminishing property, an important feature that I will employ in this section: if f(t, q) is TP and g(q) changes k sign j < k — 1 times, then h(t) = f f(t,q)g(q)dy changes sign at most j times; 95 CHAPTER III. CANCELLATIONS moreover, if h(t) actually changes sign k — 1 times, then it happens exactly in the same order as g(q) does when t and q traverse the real line from left to right. Note that K(t, q) = e (i_<?) l(t. < q) is TP of any order k G Af. k Decision Problem and Uniformization Recall the original integral equation v = TFv satisfied by v° which is c-r, v°(v,t) = 0 , K Yl / ( S Ajmax{r(77 + ?:,j,(/;l) +U°(T7 - 1 + i,q), r(r? + q; 0) + v°(n + i, q)}Pi(v, t, q)e ^dq, x (III.5.1) where Pi{r],t,q) is the probability of i cancellations between times t and q when the inventory left at time t is rj. In the case under consideration the Pi's are determined by the Poisson death process, and r(r?, <j>, t; a) = ap(4>) + Lo(r] — a)e . M The incremental value of selling a seats versus not selling any seats is 5r(n,4>,t;a) = r(r),<f),t;a) - r(n,4>,t;0) = ap((j)) - A L (r],4>,t)e . The booking a xt 0 curves are determined by comparing 6r(n, (j), t; 1) and Av°(n, 0, t). So a booking curve for a given fare pj is determined by pj — ALo(n)e and Av°, i.e. the fare is accepted xt if and only if Pj - AL (r))e > xt 0 Av°(n,t). This in turn is equivalent to > AL (ri)e + Av°(n,t) = A(v(n,t) + Lo(r?)e ). xt P j At 0 It is more convenient to work with the last expression instead of Av°, so I will define my new v° to be the sum of the old v° and Lo(?7)e . Formally, At V°(T?,<M) : = T 7 / ( 7 7 , ( M ) + Lo(r/)e . Af The (new) v° satisfies -n o / c v°(v,t)=Yl K r / ( A i ax{ m P j + 7J°(77 - 1 + g),^ (r? + ^, 0 CHAPTER III. 96 CANCELLATIONS c—n + ^L (ri + i)p (v,t,q)e* -4dq, . (III.5.2) t 0 i i=0 Following Lewis et al. [1999], I transform the birth-and-death control model into an equivalent setting, which has the same optimal policy and optimal value function and is easier to work with. Let a Poisson process be given with intensity such that A M > AM 2~2iLi ^» + At each arrival of the new process one of A*-<r- three things can happen: I have a booking request for fare i with probability a cancellation with probability (1 — 2~IiLi ~~ j^)- I c a n or a null event with the remaining probability assume, without loss of generality, that all the intensities are rescaled so that A M = 1Lemma III.8. v° satisfies f° ( K v°(v, t) = jf 1^(11°(V +l,q)- J2 i X v°(ri,e^dq m a x ^ ~ + «). + Lo^e . ?}+ (III.5.3) 4 Proof. See Appendix. • From Equation III.5.5, I obtain, after simplification, an equation for the increment Av°, Av°( t) V> = jf° (j>[{ - Av°( ,q)}+ Pi V - { Pi - Av°(ri - l,q)}+] + Av°(v,q) + / V ^ ° ( ? 7 + 1 Q , ) ~Ibr-i&v°(n,q))e ~ dq (t q) (III.5.4) + AL (*7)e*. 0 From the equation i n Lemma III.8 follows that the new v° satisfies f° ( v°(v, t) = jf K [Y^ i X + 1, q) + (1 - a x ^ + ~ «)> °(»7. u \ i ~ /*>°(»7> q) ) e - dq + L^eK K (i^in m X {t q) (III.5.5) CHAPTER III. 97 CANCELLATIONS Monotone booking curves I now state the main result of this section. Theorem III.7. (Lewis et al. [1999]) The increment Av°(r),t) is decreasing (increasing) in t if, for every —a + l>n<c-\-l, K ^ [{Pi ~ AL (r?)} - { i - AL (n - 1)}+] + + 0 P 0 »=i AL (77) > ( < )0. +/i AL (7? + 1) 77 0 0 Proof. I prove the result for the "decreasing" case. The proof in the other direction is analogous. Let K(t,q) = e^~ ^l(t < q). I note that for any t, j K(t,q)dq = 1. q t Therefore, for any number a, and a function f(q), h(t) — a — f K(t,q)f(q) — a = t J K(t, q)(f(q) — cn)dq and by the variation diminishing property, if f(q) is monotone t then so is h. I write the Equation III.5.4 as follows. Av°(r,,t) = K Y \i [{Pi ~ Au°(ry, q)} + - { Pi - Av°( - 1, q)}+] + V i=l + i Av (v + 1, q) + (1 - tir,-i)Av°(r,, q)j l(q < 0) + AL (r))l(q > 0 ) j e^dq 0 t T1 0 I use successive approximations and start with VQ(TI, t) = LQ(TJ). I obtain that AVQ is decreasing (constant) in t. With this Av^ the integrand is a decreasing function in q by the hypothesis of the theorem. (It is constant for q < 0 and for q > 0.) Then Avi is decreasing in t since the kernel K(t,q) is at least TP . 2 Assume that Avf is decreasing in t. The term K Y A, [{ t=i Pi - Av?(n, q)}+ - { Pi - Av?(r, - 1, q)}+] + (1 - ^ _ ) A v ° ( , q) a V 98 CHAPTER III. CANCELLATIONS is decreasing since it is of the form j E j X ^ + C - E 1 i=l K A i - ^ - 1 ) A u ° ( 7 7 , ?) - E i=l ^ - A A ^ - > l i=l for some j . The other term, n„Av^(n + is decreasing as well. Note that for t > 0, Av°(rj, t) = AL (ri), so I indeed obtain that the whole integrand is decreasing. Q Thus the iterations preserve monotonicity and by going to the limit, I obtain that Av°(r), t) is decreasing in t. " • When trying to extend the proof in a way exploiting the kernel K(t, q) being in fact TPk for any k, one is tempted to argue that if K E Ai [{ Pi - AL (r?)}+ - { 0 Pi - AL ( 0 V - 1)}+] + -\-fi AL (n + 1) - Hn-iALoirj) v 0 changes sign k times then the successive iterates cannot change sign more than k times. The stumbling block here is that a sum of functions with that property does not, in general, inherit it. I think, however, that a multivariate version of the TPk property (MTPk) for k > 2 should be helpful in overcoming the problem. The version available in literature, Karlin &; Rinott [1980], is MTP , which is mainly 2 used to show monotonicity in certain situations. Short of developing a MTP^, k > 2 theory, I offer the following conjecture. Conjecture III.l. The number of times that the expected increment Av° crosses any given straight line as t changes from 0 to —oo is smaller or equal to 1+ the number of times that the expression K E Ai [{Pi - AL ( )}+ - { i=l 0 +H AL (v v changes sign. 0 V Pi - AL (n - 1)}+] + 0 + 1) - (1 - ^-I)ALO(T7) Chapter IV Partial Information IV. 1 Dynamic Inventory Control with Partial Information about Customer Type In this chapter I extend the model from Chapter II into the situation where the size and fare of customer's request are known up to a probability distribution. This type of dynamic control problem, beside the full information case, includes models considered in Brumelle &; M c G i l l [1989], Robinson [1995], some of Gallego Sz van Ryzin [1994], and the omnibus formulation found i n Subramanian et al. [1997]. In addition, since I allow a general state space, I can model situations where an airline learns about customer's request during the booking process. I make one major assumption of the same type as in Chapter II, namely that the arrival process can be defined independently of any seat sale policy. That is, the decisions whether or not to sell seats to specific customers do not affect the arrival process. For example customers requesting, but denied, a discount will not return later. A model similar to mine but with single requests and for a nonhomogeneous Poisson case (cancellations, overbooking and no-shows were not allowed) has been considered in Zhao Sz Zheng [1999], where authors asserted existence of booking curves and their monotonicity using tools from intensity control theory and some 99 100 CHAPTER IV. PARTIAL INFORMATION intuitive arguments. IV. 1.1 Market Segmentation, Diversion and Strategic Behaviour It is natural to expect that the more general model should be more flexible. I will try to provide some motivation for it coming from a few different aspects of inventory control. The situation where the airline (the seller, controller, etc.) knows how many seats and at what price (per seat) are requested is well suited to selling seats (or other items) as parts of a number of different products, or to selling them in different markets. In other words, it is suitable when the market has been divided into segments with customer from a specific segment asking for a specific product. This segmentation in airline setting is achieved through various restrictions (fences) imposed on particular fares (week-end stay-over, cancellation restrictions, etc.). When the market segmentation is far from perfect and there are no distinct groups of customers it makes sense to adopt another point of view and model customer's willingness to buy a ticket as a function of price. This might, at least partially, capture phenomena like diversion ("sell-up") and strategic behaviour. In the first case, the estimate of the probability of a sale at a given price may include the possibility of a sell-up. For instance if I arrive at those estimates by "counting" how many past customers have bought at a given price it will certainly include some who bought the ticket at that price since it was the only available. As for the strategic behaviour of customers, it may be plausible to assume that the airline's model of the willingness to buy reflects an equilibrium situation between a customer and the airline. Especially so, if the data have been gathered over long period of time using the same control method. CHAPTER IV. IV. 1.2 PARTIAL INFORMATION 101 Sources and requests The point of view, which allows partial information offers more opportu- nities for modelling. One example that I want to mention is that the information states x can be regarded as labels for distinct sources of request. Depending on the source the distribution of customer's request can differ. Along those lines we can expand on the example of Gallego and van Ryzin [1994], by giving up the requirement that there is one underlying process at whose arrival epochs we have some given probability that a customer will buy a ticket at a given price. So we assume that requests can arrive from a finite number S of sources, and conditioned on x = s, a particular source, the distribution of (f3, p) can itself be a function of time t. Some of the structural properties, like monotonicity of the booking curves may not hold in general (cf. Zhao & Zheng [1999]). IV. 1.3 Offering Seats when Request Type is Unknown There is a number of ways in which one can model the transaction that takes place between an airline and a customer when the airline does not know the customer's type. I.e. the airline knows that there is a request for seats but does not know for how many or at what price. Here are a few examples of making decisions in that situation. 1. Set a single price per seat and sell whatever the customer is willing to buy at that price as long as the inventory lasts. 2. Set a single price per seat and a maximum number of seats to be sold at that price. 3. Offer seats for sale one-by-one at possibly different prices. The approach that I adopt is the following one. • The airline determines how many seats to offer for sale in each price category. The customer will then fill his order starting with the lowest available fare up CHAPTER IV. 102 PARTIAL INFORMATION to the maximum allocated to this fare (or up to his request size, whichever is smaller), then he will go to the next higher fare and so on. I will show that under certain reasonable conditions the optimal policy can be determined by booking limits, as was the case with full information about customer request. As shown in Example IV.1, that structural property need not hold, in general, even for a plausible form of the immediate revenue function. IV. 1.4 Information Process The development in this section parallels that, of Section II.2.1. The information about the booking customer is characterized by x, the information variable. The information variable takes values in X, a general space that is Polish (separable, metric, complete). When booking is initiated at time — T, the model assumes that there is a customer arrival at this point. However, similar to the full information case, an information state can be introduced which corresponds to a customer who will pay nothing for a seat for the initial customer. An information process is a nonhomogeneous semi-Markov process {(X ,T ),n — 0,1,2,...}, where T is the arrival time and X n n n n is the information about the n-th customer. So the information about booking customer changes from (x,t) to (x',t') in a semi-Markovian way. The theory of semi-Markov processes on general state space is developed in Cinlar [1969] and Jacod [1971,1974]. Let o(X) be the Borel cr-field of X, and B a set in a(X). Conditions analogous to the full information case are imposed on the probability transition function P(B,a\x,t) := Pr(X € B,T Assumption IV. 1. (a) For each B and s, P(B,s \ x,t) is a measurable map n+1 n+1 < s \ X = x,T = t) as in Section II.2.1. n n as a function of (x, t), and for each x, s > —T and t > —T it is a measure on X; (b) If s <t then P(B, s | x, t) = 0 for each B and x, so that time moves forward. CHAPTER IV. PARTIAL INFORMATION 103 (c) For each (x, t) lim P(X,s \x,t)< 1, s—»oo so that discounting can be allowed. IV.2 Semi-Markov Decision Process with Partial Information Having defined an information process in the previous section, I will now describe the finite horizon nonhomogeneous semi-Markov decision process. The general model of Section 1.5 and discussions of II.2.2 regarding policies, admissible action sets and revenues all apply here so I will only stress the main points, and differences when present. It is natural to let inventory level or number of seats available, 77, take values in X — {—a,..., —1,0,1,..., c} where c is the capacity of the plane and negative inventory indicates overbooking. However, to decrease the notational burden, I will let X = {0,..., a + c}. So inventory level 0 actually indicates that the plane is overbooked by c r , inventory level a + c indicates that no seats are booked, and so forth. This shift in the inventory space does not affect properties of the revenue function that rely on the ordering of the space, namely discrete concavity and monotonicity in inventory. Properties related to the arrival process are unchanged as well since the probability transition function P(B, s \ x,t) does not depend on inventory. The state of the system when a customer arrives is the inventory level found by that customer together with the information variable and the time of arrival. Thus I 1 the state space is S = T x X x —T, 0. For each state (v,x,t), let D(rj,x,t) be the set of admissible actions. An action will be denoted by u as opposed to a which was used in Chapter II. The actions still concern allocation of seats to customers but are more involved in this model than in the full information one and will be described in more detail later. If CHAPTER IV. 104 PARTIAL INFORMATION an allocation u S D(r),x,t) of seats is provided to a customer who found the system in state (77, x,t), then the revenue generated is given by the value of the revenue function r(n,x,t;u). Assumption IV.2. The revenue function is bounded and the action sets are finite and only depend on n. Define Z(r], x, t; u) to be a random variable that counts the number of seats sold to a customer arriving at time t to find inventory 77 and information x when the seats offered correspond to action u. The random variable Z is required to be conditionally independent from the past of the decision process given current state and action. The inventory at the beginning of the next decision epoch is then rf : = 7 ? - Z(rj,x,t;u). The transition probability function governing the dynamics of the semiMarkov decision process can now be defined. If the process is in state (77, x, t) and an admissible action u is chosen, then the probability that the next arrival occurs before time s, has information x', and finds inventory 77' is { P(x' s I x, t) Pr(Z(77, x, t; u) = z \ x, t) if 77' = 77 - z 0 otherwise. : As in the full information model, the optimality equation v(r],x,t) = max u€D(rj,x,t) \r(rj,x,t,u)+ I f E[ Jx'&X v(r]-Z(r],x\t;u))P(x',ds\x,t)} J-T (IV.2.1) J will be written in terms of operators T and T as v = FTv. The operator T is defined by Tv(r],x,t) = / Jx'&X / v(n,x',t)P(x', ds \ x,t), J-T and the operator T is defined by ^(77,x,t) = max \r(r},x,t;u) + Ev(rj - Z(rj,x,t;u),x,t) \. u&D(ri,x,t) I J 105 CHAPTER IV. PARTIAL INFORMATION Assumption IV.3. For some integer N, T N is a contraction operator. Note that the introduction of an expectation in the new form of operator T does not increase its modulus. Hence the above contraction assumption and Assumption IV.2 ensures the validity of the optimality equation and of successive approximations just as in the full information model. The model just defined will be referred to as the basic model with partial information. IV.2.1 A M o r e Specific M o d e l This section adds some detail to the basic model by associating a fare type $ with each customer just as was done in the full information model, giving a model referred to as the specific model with partial information. As in the full information model, the fares are ordered p\ > p , • • •, > PK > 0- This model should 2 satisfy the following assumption in addition to all of the assumptions in the basic model. Assumption IV.4. Sufficient statistic. The pair (X ,T ) is a sufficient statistic n n with respect to the history of the decision process for the random variable for every n = 0,1,... P($„ | ri ,X ,T ,r) - ,$ - ,X - ,T - ,...,r}o,$o,X ,To) n n n n 1 n 1 n 1 n 1 0 = P($ n I X ,T ). n n The actions have not yet been described. An action u is a vector u = (iti,M2,... ^K) where u represents the number of seats offered at price p to the k k current customer. With this framework the number of tickets sold, Z(rj,x,t;u), can be modelled in more detail. Given that a customer of fare type $ = (p, 3) arrives to find the information process in state (x,t), inventory at level 77, and u seats allocated, consider how many seats, ZK, of fare class px will be purchased. First, the customer will buy nothing unless p > PK so that he is willing to pay at least K- And if he P CHAPTER IV. 106 PARTIAL INFORMATION does buy tickets at all, then the number bought will be the minimum of the inventory level 77, the customer batch size 0, and the number of tickets offered UK\ that is, z (v,x,t;p,0;u) = l(p > p )[v A 0 A u ]• K K K For an arbitrary fare class, the number of tickets sold will be represented by a similar expression except that the inventory available and the customer's demand will be reduced by the number of cheaper seats sold. So z (r), x, t; p, k where z >k = p )[(v - > *i Pi Hence the total number of seats sold given the x J2i >k (IV.2.2) u) = l(p > 0; 0> )u >k) z k A (0 - z ) >k A u\ k state (rj,x,t), allocation u, and fare type $ = (p, 0) is K z(r],x, t; p,0;u) =Y k(v, x, t;p,0\ u) z fc=i and the random variable Z(n, x, t; u) can be defined by Z(rj,x,t\u) = z(n, x,t;$;u). As in the full information case, an affine revenue function will be convenient. Given $ = (p, 0), a plausible form for the revenue generated from an allocation u is K r(rj,x, t\p,0;u) =YPiZiiv,x,t;p,0;u) + r(r? - z(rj,x,t;p,0;u),x, t;0). (IV.2.3) i=l The term r(n, x, t; 0) in the revenue expression allows the model to handle a terminal reward L at departure (e.g. due to overbooking cost) by setting r(?7, a;,i;0) = L(rj) -Pr(current arrival is last | x,t). An affine revenue function is defined to be a revenue function of the form r(n, x, t; u) = Er(n, x, t; u). (IV.2.4) The revenue function is denned for u G T . Since only the splittable batch case will K be considered, the decision set for state (j],x,t) is assumed to be D(rj,x,t) = 1 . K CHAPTER IV. PARTIAL INFORMATION 107 Discussion of the M o d e l In spirit, the current approach is similar to the one in Helm &; Waldmann [1984]. The authors introduced a fairly general formulation for the problem of the optimal control of arrivals to a queueing system by making use of the concept of a random environment. They prove the optimality of a general booking limit-type policy. Their queueing system is inspected at a sequence of random times and the state of the environment is recorded. The environment changes in a semi-Markovian way (with a general state space), the rewards offered by the customers are random but are known to the controller before making decision and so are the request (batch) sizes. The main difference is that in my setting this information (fare and batch size) is available to the controller only through a probability distribution. This type of formulation is essentially a partially observable Markov decision process (POMDP) and structural results are generally harder to come by. Loosely speaking, the difficulties are due to the fact that controller's actions can influence information available at the next arrival about the customer type. In this chapter, I have assumed that the arrival process is defined independently of any policy. As a consequence of this assumption, it is modelled independently of the decision theoretic structure. So when the knowledge of the realized demand does not influence next stage distribution $ (only the (x,t) does), then more can be shown. This type of setting works with the independent Poisson arrivals and in situations where the reservation system is inspected and some demand is found but arrivals of booking requests are not modelled explicitly as, say, an underlying semi-Markov process. Some Bayesian models fall into that category as well. The current setting includes Poisson intensity control models of Gallego & van Ryzin[1994], Gallego & Feng[1995] as well as salient static models. It is better suited to situations where market segmentation is less pronounced and where customers will buy least expensive tickets if these are available. In other words we can model customer's behaviour in response to price. This is essentially the view in Gallego & van Ryzin [1994], where demand is a function of price. They model the CHAPTER IV. PARTIAL INFORMATION 108 random demand as a controlled compound Poisson process that is essentially time homogeneous. Setting the price corresponds to setting (controlling) the intensity of arrival process, which thus becomes a control variable. In the case with a finite prescribed set of prices or fare classes, their approach means that the controller (seller) chooses the price which in turn determines the probability that an arriving customer will be willing to pay this price. For example, if the price is set high then it is less likely that a customer will arrive and buy a ticket. In Chapter V, I investigate the expected value of full (perfect) information about customer's request by comparing their model to one in which the fare class offered by a customer is known. As already mentioned, in this more general model, in contrast to Chapter II, the available actions are different, instead of rejecting or accepting customers one sets the price, or when multiple requests are allowed, sets the maximum number of seats to be sold at each price. IV.3 Discrete Concavity with Partial Information The main result in this section is that the optimal revenue function v* and the auxiliary function v° are discretely concave under certain assumptions, thus establishing the existence of a booking limit policy. IV.3.1 Booking Curves with Partial Information A customer requests up to a certain number of seats (batch size) and he is willing to pay up to a certain amount per seat, which is the same for each seat in the batch. Both the batch size and the maximum price are random variables (unknown to the controller before making decision) with a (known) distribution depending on t and x. Once the controller has decided upon an allocation of seats among all fare classes, the customer fills his request starting from the lowest available fare class and moves to a higher fare class if no more seats are available for sale in the lowest class. CHAPTER IV. 109 PARTIAL INFORMATION The process is repeated until the customer's batch size is reached or inventory is depleted or all the available seats cost more than the maximum price the customer is willing to pay. In the setting of Chapter II, when the fare and size of customer's request were known, the optimal policy was determined by a booking curve for each arrival type <f> = (p, P). So for a fixed arrival type and time of its arrival there existed a booking limit such that it was optimal to sell seats to the current request down to that limit. With only partial information about current request available, the actions are not to sell or reject but to allocate numbers of seats at each price. By analogy to the full information case, one would then hope that for a given information state x and time of its arrival t the optimal policy would be described by a limit for each fare such that it is optimal to offer seats in that fare down to that limit. As evidenced in an example at the end of this subsection, this is not the case in general. However, under certain assumptions on the joint distribution of fares and batches given information x and time t, there do exist inventory levels r)*.(x,t) with the aforementioned property (and which I will continue to call booking limits). So for a given inventory on hand 77 one allocates seats optimally in the following way. Let (x, t) be fixed and let rf kQ be the greatest booking limit strictly smaller than 77, then no seats are offered at prices lower than pk , V ~ vt 0 ^s are offered at price sea 0 Pfc , and for each k > ko, in*. — ?7^_ seats are allocated at price p - This seems like 0 1 k a natural extension of the booking curve concept of Chapter II, so for each fixed x and k, I will continue to call n* (x, •) the booking curve. k These booking curves obtain, for instance, when 3 and p be independent given (x,t) or when only single requests are allowed. Example IV.1. Consider one stage problem with two types of customers: first class (pi) customers arrive in batches of two only, this happens with probability Pi; discount customers (p ) arrive in single batches, which happens with probability 2 P2i P\+P2 — 1- Assume also that p\p\ < p , there are no terminal rewards and 2 CHAPTER IV. 110 PARTIAL INFORMATION the value of unsold inventory is nil. One can verify that the optimal decision when inventory 77 = 1 is to set the price to p , i.e. to accept any customer. For every 2 77 > 2 it is optimal to offer one seat at p (i-e. to any class) and one at p\. Thus the 2 optimal policy cannot be described by the booking curves analogous to those that were introduced in Chapter II. IV.3.2 Basic Results and Existence of B o o k i n g Limits The model considered in this section is the specific model described in section IV.2.1. The analogue of Theorem II.2 holds and the proof used in the full information case is still valid. Theorem IV. 1. Suppose that the revenue function is increasing in inventory 77. Then v*(r),x,t) is increasing in 77 for each (x,t). One additional assumption is made concerning the joint distribution of the coordinates of namely that they are independent. Assumption IV.5. Independent batches and fares. Given an arrival in the information process (x,t), the coordinates of $ = are conditionally in- dependent. The arguments utilized in this section generally proceed by conditioning on batch size and utilizing the independence of batch sizes and fares. To assist in this approach, a version of T is defined conditioned on — (3: K Fpv(in,x,t) = max {Y"[r(i],x,t; p ,/3;u) ueD(ri,x,t) k f—* fc=l + 7J(T? - 2(77,x, t; p ,/3;u),x, t)}p (x, t)} k k (IV.3.1) where p (x,t) = Pr[<fr = p \ ®p = 0,%,t\ =- Pr[<& = p \ x,i\. The last equality k p k p follows from the independence of <fr and p k given (x, t). Note that u £ D(r),x,t) can be replaced by u £ 7J(?7 A /?, x, t) since there is no benefit from offering more seats than the customer wants. CHAPTER IV. 111 PARTIAL INFORMATION Recall from Chapter II that a function v £ B is discretely concave if v(n,x,t) — v(n — l,x,t) is decreasing in r? = 1,2,... for each information x and time t. Lemma IV.1. Assume that the revenue function has affine form and r(n,x,t;0) is discretely concave in inventory for each state (rj,x,t). Then Tpv is discretely concave whenever v £ B is. For each (x,t), booking limits n*.(x,t) can be determine so that the allocation maximizing T$ is u* — [rj — r]* {x,t)\ and for k < K, u* = + K [r/A77* K k -Vt\ + +1 Proof. Fix (x,t) and suppose that v(n,x,t) is discretely concave in n. The recursive argument on the number of fares is based on an application of Lemma II.8 at each iteration. At iteration k, only customers of fare types 1 through k will be considered. The probability that a customer is fare type i (1 < i < k) conditioned on the event that the customer is some fare type 1 through k is denoted by p ,i; that is p ,i = P r ( $ k k p = > p ,x,t); p k k>k is the probability that the customer is one of the higher fare types conditioned on the event that it is some fare type 1 through k, i.e. p ktk = P r ( $ > p \ § > p ,x,t). p k p k The event [3>/? = /?] can be omitted from the condition because of the independence assumption. Denote the maximization operator that corresponds to allocating seats only to fares in classes 1 through k by Fp,k,p where p*, is the vector k of fare type probabilities p^ = (pk,i,Pk,2, • • • )Pk,k) and (3 is the number of seats left in the batch. First assume that there is only one fare class (K=l). Then an arrival must be fare class pi and from IV.3.1 and the affine form of the revenue function IV.2.3 F/3,i, v(ri,x t) = P1 y max {p\U\ + r(r) — ui,x,t;0) + v(r) — ui,x,t)}. (IV.3.2) 0<UI<TJA(3 By applying Lemma II.8, ^3,1^!^ is seen to be concave. Moreover, let rj*(x,t) = mm{n : p\ > Ar(r?, x, t; 0) + Av(n,x,t)} — 1 if the set over which the minimum is defined is not empty, and rj* = c otherwise. Then the action u\ — [r? — r)*\ is a + CHAPTER IV. 112 PARTIAL INFORMATION maximizer. Although the maximization was restricted to U\ < Q it does not hurt to offer u\ since the customer will not accept more than 0. The following form of Fp,i,p\ obtains v v(rj,x,t)+r(ri,x,t;0) if n < 77* Pi(v-Vi) if 77* < 77 < 77* + 0 + v(rfi,x,t)+r(ri-ril,x,tiO) _ 3 + v( - 3, x, t) + r(77 - 0, x, t; 0) Pl if 77 > 77* + 0. V (IV.3.3) For /? — 1 and 77 — 1 it is T/3-i,i, v(v ~ Pl 7j(77 - l,a;,t) + r(?7 — l,x,t;0) = < Pi(T? - if 77 — 1 < ?7i 1 - r?*) + 7j(/7*, x, t) + r(rj*,x, t; 0) Pi/3 + IJ(?7 - 0, x, t) + r(r? - /3, x, t; 0) if 77* < 77 - 1 < 77* + 3 - 1 if 77 > 77* + /?. (IV.3.4) Define a new type of increment AFk, v(V,x,t) Pk •= Fp-Uk.k-lvk-AV ~ >*, , U X * ) - ^-Ufc-l.ifc-l.Pfc-iU (77 - Wfc - 1, £, £). For i f = 1, from (IV.3.3) and (IV.3.4), the right-hand side in the above definition does not depend on 0 as long as 0 > 1 so that increment for i f — 1 is well defined and has the form AF v(r),x,t) = Av(r),x,t) + Ar(n,x,t;0) if 77 < 77* ltP1 Pi if 77 > (IV.3.5) . The increment A - F i ^ is decreasing in 77 by construction of 77*. It can be written as Pr($ < p P j I $ > p )(A7j(r7,a;,t) + r(77,x,t;0)) + Pr($ > p,- | $ > pi)pi, if 77 < 7 ? ; p 1 p + 1 for j = 0 or 77J < 77 for j — 1, with the convention that po = + 0 0 and 770 = 0. Now assume that there are k (k > 1) fare classes and that the following statements are true (inductive hypothesis): CHAPTER IV. 1. u* = PARTIAL INFORMATION [77 A r ? * + 1 — 113 rf-\ , j < k — 2 and u* _ + k x = [77 — 77fc_ ] + I are optimal allocations with A; — 1 fare classes. 2. Fp^-i&^virj, x,t) is discretely concave in 77. 3. ^ 3,fc-i _ 7;(77,a;,t) r / lPfc 1 - ~ M , * ) = AJ Fp-it-i^Mv r fc _ 1)Pfc _ 7;(77, 1 a;, i) is well defined and decreasing in 77. 4. A^]fc_i _ v('7.«.*) lPfc 1 = P R ( P $ < Pj I P > p -i)(&v(r),x,t) + Ar(n,x,t;0)) $ k + Pr($ >p; I 9 >p -i)pj p whenever 77^ < 77 < ?7!- +1 for j < A; — 2, or 77J < 77 for j = p k — 1, and it^ > 0. By IV.3.1 and the affine form of the revenue function k Fp,k,p v(ri,x,t) = max {Y][r(v,x,t; p , P;u)+v(r}-z(rj,x,t; p , P;u),x,t)}p } k { u£D{n,x,t) { kji r-7 k u&D(t)hP,x,t) ^—' j=l + TJ(T7 - z(r),x,t;pk,P;u),x,t)]p k kt k-l k-l + *; Pi, «) + r(rj - 2(77, a, <; p;, u), a;, t; 0) i=l j=l + TJ(?7 - 2(77, a;, t\pi,/3; u), x, t)]p ,i}. (IV.3.6) k This can be rewritten in recursive form as Fl3,k,p v(v, x, t) k = max {p u + (r(rj - u , x, t; 0) + k k k 77(77 -uk,x, t))p k<k 0<u <nA/3 k + Pfc,fc^ /3- ,fc-i, _ f(r7 -u ,x,t)}. r Ufc PA: 1 k (IV.3.7) The maximization problem at the current stage k falls into the class of monotone stopping problems, cf. Derman & Sacks [I960]. When deciding whether it is optimal to increase the allocation at p by one seat, with inventory of seats left 77 one can k verify if the gain in the revenue is greater or equal than zero. In our situation this is 114 CHAPTER IV. PARTIAL INFORMATION equivalent to comparing p with the sum of (Av(rj — Uk,x,t) + Ar(v - u , x , t; 0))p k ktk k and of the increment AJ / _i _ pfc / . 7 c iPfc 1 ) c By the assumption of the theorem and the inductive hypothesis all three terms are decreasing in 77 and so is their sum. The increment (Au(r? — u ,x,t) + k Ar(n - u ,x,t;0))pk,k + AFk-i.Pk-A ! - u ,x,t)p ,k is bounded and well denned. 7 k k k Therefore there exists v such that it is optimal to allocate seats at p as long as k k there is enough demand and the inventory left is greater than 77*.. So let n* (x,t) = min{ry : p > ATk-i^^viv, k k x, t)p , + (Ar(v,x,t;0) + k k Av(n,x,t))p } — 1 if the set over which the minimum is defined is not empty, and ktk 77*. = c otherwise. Then, starting with inventory 77 and batch size 3 it is optimal to keep allocating seats at p as long as inventory left is strictly greater than 77*. and k the batch has not been exhausted. So u = [77 — 77*.] A /3 + k is maximal. As argued in the case for K = 1, it is OK to offer more than 3 since the excess will not be bought and we can take the optimal allocation at price p to be u* = [rj — k k If it happens that 77*. < 77*, for some j < k, then it is no longer optimal to allocate at pj so all such rf's are reset to c, the capacity of the plane (ii* = [7?A77* -c] =0). + + 1 The value of Tp^ k;Pk can be expressed as if r\ < v* + Pk,k^,k-i, ^v(ri,x,t) \pk,k( (V, x,t) + r(7?, x, t; 0)) v Pk k Pk(v ~ Vt) + Pk,k( ( i> x, t) + r(v* , x, rj; 0)) v n (IV.3.8) k + ^,fc^3_( _ .),fc_l,p _ 7j(77^, x, t) T7 77 fc 1 if 7?^ <V<V* + P k pkP + Pk,k{v(v - P, x, t) + r(?7 - P, x, t; 0)) + Pfc,fc-^0,fc-l,p fc v(v -P,x,t) ± \iV>Vi + P- CHAPTER IV. It follows that 115 PARTIAL INFORMATION is well defined and has the form A^jfc 7j iPfc p (A7j(r?, x, t) + Ar(r?, x, t; 0)) fc]fc +p AF _ _ v(v, kik k liPk 1 x, t) if ry < rfc Pk (IV.3.9) ^ V > Vi- lli the case 77 < 77*., the expression is discretely concave by inductive hypothesis, for 77 > 77*. it is constant in 77. By the construction of rf , Af v(ril,x,t) k than pt, so A^ / 7 C)Pa ,7J(T7,x,t) is decreasing in a recursive description of A^7 C]PA .7j(77, x, t). 77 A is greater kiPk as required. Equation IV.3.9 provides more explicit form of that increment is convenient for computations and is shown next using the last part of the inductive assumption. Since p ,k P r ( $ < pj \ $ > p _i) = P r ( $ < Pj | $ > ), for j < k, k p p fc p p Pk it obtains that AFk, v(v, x, t) = p (Av(r), x, t) + r(7?, x, t; 0)) Pk k<k +p ,*(Pr($ < pj I $ > Pfc_i)(Au(77,a;,i)+Ar(?7,a;,7j;0))+Pr($ > pj | $ > p _i)pj fc P P p p fc = P r ( $ < pj I $ > p )(Au(77,a;,rj) + Ar{n,x,t\0)) + P r ( $ > pj | $ > p )p , p p fc p p fc j (IV.3.10) whenever 77* < 77 < rjj for j < k — 1, or 77* < 77 for j = k, as required. Note that +1 with k fare classes if vf- = c for some j < k, then since c > 77 the corresponding form of the increment (with j) will never arise. P Concavity of Aj^p^^v^, x,t) follows the same idea as in Lemma II.8 with necessary modifications and is omitted. This completes the proof of the inductive step. Since Tp = Tp,K p the proof is completed. % K Note that from construction follows that some of the booking limits could be equal to c, which implies that no seats are allocated at the corresponding price. L e m m a IV.2. concavity. • Under assumptions of Lemma IV.1 the operator T preserves discrete For each (r),x,t) and each fare class k, the optimal allocation can be determined from the booking limits rji(x,t): u* (x,t) k = [77 A77*. — rf (x,t)] . + +1 k CHAPTER IV. 116 PARTIAL INFORMATION u* — [v^vt+i ~ Proof. Fix (x,t). By Lemma IV. 1 the allocation u* = (u* , ...,«*), K k T?^] maximizes (IV.3.1) for each /? and consequently + K Tv(r),x,t) = E{Y][r{v,x,t;pi,^p;u)+v(i]-z(ri,x,t;pi,^p;u),x,t)}p } max Kti u£D(n,x,t) r~* K = E = max ^ i ^ K ^ {Y][r(v,x,t]pi,^p]u*)-\-v(i]-z(ri,x,t-,pi,^p-,u*),x,t)}pK,i} a ; »Pi- */3;«*) + *>fo - (v, x, t\pi, z u*), x, t)]p ,i}. K (iv.3.11) i=l So the same u* is the optimal allocation for the original maximization problem. Again by Lemma IV. 1, Tp is discretely concave for each (3 and so is the expected value. a From the proof of the Lemma IV. 1 it follows that an optimal allocation is determined by booking limits r/jj's. Those booking limits may not be monotone in general, and although the proof is constructive it is more complicated to find them than in the full information case. For instance, when looking for r/j*, one searches for the smallest 77 such that p - AF v(ri, x, t)p ,k > Av(n, x, t) + Ar(r7, x, t; 0). Pk,k k Since A ^ ratio ] P ) P k k , v(r),x,t) is equal to p -i for 77 > 77£_ the search should start with the k ~ ~l ' Pk kiPk Pk k p 1 • Let pk := PK,k be the probability that customer's fare class is pk, which is the same regardless of the batch size, since batches and fares are assumed independent. The last ratio is the same as the ratio r . _ pk(Pk + • • • +Pi), - pk-i(Pk-i + • • • +Pi) Pk If n* > 0 cannot be found with rk k-i then one determines the A^ fc_i r k t iPfcl 7;(77, x,t), using relationship IV.3.10 and the 77*,... ,rjk-2 already found from the previous iterations. This in turn is helped by observing that u* = 0 if rfj < 77^, so those 77^'s can +1 be eliminated from the considerations. So, if given highest k — 1 fares and inventory CHAPTER IV. 117 PARTIAL INFORMATION 77 it is optimal to offer one seat at some pj, j < k — 1, then A^ / _i ,_ 7j(r7,x,t) is r iPA c 1 equal to (p ,k-i + • •. + Pk,j+i)(Av(r],x,t) + Ar(n,x,t;0)) + pj(pk,j + • • -+Pk,i)k Comparing the corresponding ratio with (Au(r?, x, t)+Ar(r), x, t; 0)) is equivalent to comparing the latter with rkj := P*(Pk+---+vi)-^(j^+---+pi) The following algorithm can be offered. simple algebra. ^ ^ Define 77*.^ : = mm{r) Av(r/, x, t) + Ar(ji, x, t; 0)}. Determine 77* from 7*1,0 — p\> : rkj > Av(r], x,t) + Ar(r), x, t; 0). Since the fares are ordered, for all j < K, 7*1,0 > T*J,O, so 77* is greater or equal than 77*. Next find 77^! := min{?7 : r , i > Av(r),x,t) + Ar(rj,x,t;0)}-1. (It can be shown 2 that 7*2,1 < Pi so that 7 7 ^ > 77*, the situation, however, is different for higher k.) W i t h 7 7 * , . . . ,rj _ determined, find Vk,k-v ^ ^ * g s k let 77*. =rf _ kk v 1 r e a t e r than 7 7 * . ^ then If not continue for the first j such that rf - > 77* and let 77*. = 77*.^. k The process has to stop since 77*. > 77* because of the fact that 7*1,1 > r^^, for any 1 k. Set all 77*, I < k, such that 77* > r/ to c. k The algorithm becomes relatively simple when the ratios Tk k-i are ordered t as one is then assured that 77*.'s are ordered and each 77*. is equal to Vkk-i- This is the case with two fare classes, since one always has that 7*2,1 < 7*1,0 = PiIt may seem initially that a sufficient condition for the existence of booking curves is that the ratios p P(p > p j f3 > m) - pjPjp >Pj\3>m) P(p>Pk\8>m)P(p >pj\6>m) ' fc fc be constant in m > 0 for every k and j. However, this condition and the independence of batches and fares can be shown to be equivalent, which is the subject of the next lemma, whose proof I omit. L e m m a I V . 3 . The batch size B is independent from the p if and only if for each k € { 1 , . . . , K}, the ratios PkP(p >Pk\0>m)P(p>Pk\P>m)- Pfc-iP(p > Pfc-i I B > m) P(p > p _i \6>m) fc are independent ofm. L e m m a I V . 4 . The operator T preserves discrete concavity. CHAPTER IV. 118 PARTIAL INFORMATION Proof. With the state space X, although more general than the countable space C in the full information case, the operator T is linear and transforms nonnegative functions into nonnegative functions. • The two previous lemmas immediately provide the following result. L e m m a I V . 5 . If the revenue function is discretely concave with affine form, then the composed operators TT and JFT preserve discrete concavity. Theorem I V . 2 . If the revenue function is discretely concave with affine form, then the optimal value function v*(n,x,t) and the corresponding auxiliary function v° — Tv* are each discretely concave. Moreover, there is an optimal booking curve policy. Proof. The function which is 0 for all states is discretely concave, so (TT) 0 is also n discretely concave by the preceding lemma. By Theorem II.1, v* — lim^oo^T)™!). Hence, v° is discretely concave. Since T preserves concavity, v° = Tv* is also discretely concave. • In Section IV.5 I will turn to the more general properties enjoyed by the optimal allocation, which I investigate by means of the lattice programming theory. IV.4 Monotonicity in Time When the controller knows the actual type of the current request (full in- formation) and customers arrive according to either a stochastically increasing or a nonhomogeneous Poisson process, it turns out that certain monotonicity properties hold. The optimal expected value function v*, the v° and the expected increment Au° are decreasing in time, whenever binomial no-shows and overbooking but no cancellations are allowed. With the latter assumptions still in force but with partial information about customer's request, only some of the results on monotonicity of v*,v° and Av° from Chapters II and III carry over, but even then their implications may be different. CHAPTER IV. 119 PARTIAL INFORMATION For instance, the monotonicity of v° does not immediately imply that of v*, since Tv need not preserve monotonicity in time. Also, in the context of partial information, monotone increments do not imply that the booking curves are monotone. This is because the booking curves are determined by comparing the increment Av° to a set of ratios which may vary with time. In the full information case it was compared to a current price per seat which was assumed constant. So when ratios change with time the monotonicity may be destroyed. In the language of optimal pricing I would then say that the optimal price (to set) is not decreasing in time left to departure. This phenomenon has been already observed in Zhao Sz Zheng [1999], who provide an example. The example has two prices (actions) available, customers (requests) arrive according to a homogeneous Poisson process, but the probability that a customer will buy a ticket changes with time, the idea is somewhat similar to that of examples in Chapter II, where the customer is more likely to buy at the higher fare closer to departure. Theorem IV.3. In the basic model with partial information assume a homogeneous semi-Markov or a nonhomogeneous Poisson arrival process and that 0 € D(n,x,t) for each state (n,x,t). Let, in addition, for each n,x,t and a, either r(n,x,t;a) be decreasing in t and r(n, x, t; 0) > 0 or both r(rj, x, t; a) — r(r? — a, x, t; 0) — A L(r), x, t) a and L be decreasing in t. Then v*(n,x,t) is decreasing in t forfixed(rj,x) whenever distribution of (p, f3) does not change with time. Proof. Omitted. The proof goes verbatim as the proof of the corresponding Theorem II.3, if one replaces <f> with x and (f)' with x'. In Chapter II the homogeneous semi-Markov process arrival process was generalized to a stochastically increasing semi-Markov process. I expand that definition to include partial information about customer request. Define an increasing information process (i.e. the probability transition function P) to be stochastically increasing if for information types XQ and X\ (a) Pr[Xi = x\ | XQ = XQ,TQ = t] is constant in t; • CHAPTER IV. 120 PARTIAL INFORMATION (b) Pr[Z(r?i, X i , T i , u) = z \ Xi = x\, T\ = t] is constant in £ for any z £ AAj{/}, and allocation u; and I (c) Pr[Ti > s | X i = xi,XQ = xo,To = t] is increasing in t for each s £ —T, oo. The same results can be obtained when P satisfies the condition in Remark II.1 adapted to current setting: for each x',x and a < 0, f" dP(x',q | x, t) is decreasing T in t and in addition it satisfies condition (b). Theorem IV.4. In the basic model with partial information assume a stochastically increasing information process. Let, in addition, for each n, x, t and a, either r(n, x, t; a) be decreasing in t and r(n, x, t; 0) > 0 or both r(n, x, t; a) —r(r)—a, x, t; 0) — A L(n,x,t) and L be decreasing in t and 0 € D(n,x,t) for each state (rj,x,t). Then a v*(n,x,t) is decreasing int. Proof. Omitted. In each case the proof is almost identical to the corresponding one in Chapter II, when 4> is replaced with x. One needs to note that, by hypothesis, the distribution of Z in each state does not depend on time t, which makes operator T preserve monotonicity in time. IV.4.1 • Monotone booking curves In the specific model with partial information the revenue function is dis- cretely concave with vector affine form, fares and batches are independent so the booking curves exist. In analogy to the full information case, the booking curves are montone for similar types of arrival processes. Theorem I V . 5 . Assume specific model with partial information and with nonhomogeneous Poisson information process. Then Av° is decreasing in time for fixed {rj,x). If rk,i{x,t) is increasing in time t for each 1 < k < K and 0 < I < k then the booking curves are decreasing. Proof. Again, the proof of monotonicity of Av° follows that of Theorem II.7, with <j) replaced with x. I omit that part. CHAPTER IV. 121 PARTIAL INFORMATION Increasing r i(x, t) yields, from the definition of rj*.(x,rj), that for rj' < rj < 0 k> and x fixed, {V I r (x,t') > Av°(rj,x,t')} ktl C {n \ r (x,t) > k>l Av°(n,x,t)}, which imphes that r)l(x,t') > rj*.(x,t). • Monotone booking curves obtain also for a stochastically increasing information process. Theorem IV.6. Assume specific partial information model with stochastically increasing information process. Then booking curves are decreasing in time t. Proof. The proof of monotonicity of Av° follows that of Theorem II.6, with (j> replaced with x. I omit that part. By hypothesis the distribution of Z does not depend on time rj, which in case of a specific model with partial information means that the distribution of (p, [3) is time-independent. It follows that the ratios r j(x,t) are k constant in t. Together with Av°(r), x,t) decreasing it yields decreasing booking curves. IV.5 • Supermodularity and the Optimal Revenue from the First Customer The purpose of this section is to take a closer look at the optimal allocation that happens at one iteration of the booking process. In other words, I consider the revenue only from the first customer to come and seek to the optimal allocation for it. I have fixed (a;, rj) and will suppress it as argument for the ease of notation. The revenue from subsequent customers is assumed to be an increasing and discretely concave function ^(77) and the inventory level is denoted by n. I use Topkis's [1978] results on optimizing submodular functions on a lattice. To describe allocation of seats I will use different but equivalent set of CHAPTER IV. PARTIAL INFORMATION 122 variables, that can be obtained by the following transformation, 2 1 Ui, y = E ' VK = 2 U K i=K A variable y k can be interpreted as the total allocation to the nest pk, Pk+i, • • •, PK- So the optimal allocation y is a vector of K nonnegative integers y , k k =• 1,..., K, 0 < yx < • • • < yi < r?, where K is the number of available fare classes. For each k, setting y means that given the information about the state of the system k and a request for an unknown number of seats at an unknown price (unknown up to a probability distribution), a maximum of y k Pkf-tPK seats for sale to the nest of fares will be offered. I use the coordinate-wise ordering on the set Y = {0,1,... } K and o n l x F . With this ordering for two allocations y and y', I have that y < y' if and only if for each k, y k < y' , and for (ry, y), (rf, y') £ 1 xY, (r?,y) < (v',y') iff V < v' and k y < y'. I can verify that on each of the two sets, its respective relation is reflexive, antisymmetric and transitive and thus constitutes a partial order. Lemma IV.6. Each of the sets (Y, <), (1 x Y, <) is a lattice. Proof. Define the join A and meet V of any two elements in the partially order to be the coordinatewise minimum or maximum. The result follows. • Let Pk be the probability that the maximum price the customer is willing to pay is Pfc. I define F, the expected revenue from an allocation y £ Y, given inventory r? and function v. Note that the P(p = pk)'s are no longer independent from /?. Let f(v, k, /?, y) be the revenue from the lowest k,... ,K fares, given batch /?, inventory r\ and allocation y. I have that f(v, y, l , p) = pm A /? - (pi - p )yi A p 2 (pK-x - pK)yx + v(v -yi^P) CHAPTER IV. PARTIAL INFORMATION 123 for k = 1, and for k > 2 it is f(r],y,k,f3) = PkVk A /? — (pfc — p f c + 1 )y f c + i A /? (p/f_i - p/i-W A 3 + v(r) - y A 3). k (IV.5.1) Define /o to be A - /o(»7ia,2/»/?) := X] fe=i 3 : 1 *' ' ^ y P f c ' where p = p (r),x,t) = P(p = p \ P,x,t) = P(p = p \,x,t), the last equahty by k k k k the virtue of the assumed independence. Now define F(n,y) :=Epf (r,,y,p) 0 L e m m a I V . 7 . The function F(n,y) is supermodular in (n,y). Proof. The fo(v,V,P) = YX=K f(v,y,k,P)p (P) where / is of the form k f(v, V, , P) = PkVk A P - (p - Pk+i)yk+i APk k ... - (PK-I ~ PK)VK AP + v(ri-y A k P). Since F and /o are convex combinations of /(?7, y, k)'s it is enough to prove the claim for one of fs. The f(v, y, k) in its turn is a sum of a linear function of y A P, which is supermodular, and of v(n — y A P) so I only need to verify that the latter has the k desired property. Let (ri,y), (rj',y') G J x {0,1,... } be given. I need to verify that v(v V rf - (y A p) V (y' A /?)) + v(n Ar '-(yAp)A 1 (y' A /?)) >v(r -yAp)+v(r -y'AP). l 1 ] When n < rj' and y < y' then the expressions on both sides are equal so it remains to investigate the only other two cases left. If r? <rf and y >y' then v(rf —y A 3) — v(rf - y' A p) = -(v(rf - y' A p) - v(rf - y A P)) > -(v(v ~ y' A 3) - v(r] - y A p)), CHAPTER IV. 124 PARTIAL INFORMATION because of discrete concavity of v. After rearrangement the claim follows. If ry > rf and y <y' then again, by discrete concavity v(rf - y A 0 ) - v(rf - y' A 0) > v(r] - y A 0) - rj(ry - y' A/3), which after rearrangement yields the claim. Since k was arbitrary, I obtain that each f(r},y,k.p) is supermodular in (ry, y) and it follows that F(r),y), as a nonnegative combination of supermodular functions is supermodular. • I am now in the position to use some of the results on lattice programming from Topkis [1978] in the form corresponding to supermodular functions and maximization problems. The key results is the following analogue of his Lemma 6.1. Theorem I V . 7 . If S is a lattice, T is a poset, St C S is ascending in t on T, and f(x Ay,t) + f{x Vy,b)> f(x, t) + f{y,b) for all t and b inT with t < b, x £ St, and y £ then S* is ascending in t onT*. The theorem is proved in exactly the same way as in Topkis [1978] but with reversed inequalities. I verify now that theorem can be applied to the current setting. Then the lattice (Y, <) corresponds to the lattice 5, the poset T is just the set of nonnegative integers—the set of all possible inventory levels, the variable x corresponds to y and t corresponds to rj. St = Y„ = {y € Y | y < rf\, I denote the set of maximizers for a given inventory ry as Y* and Y* = {ry | Y* ^ 0}. I have already verified that F(rj,y) is supermodular in (ry, y). This implies that the condition of the theorem is satisfied (it is satisfied for a function supermodular in (ry, y), cf. Topkis's remark [ibid] right after the lemma, in the submodular case). It is also clear that Y„ C V^+i which means that Y„ is ascending (in fact a chain) in ry. Applying the theorem I obtain the following result. Theorem IV.8. For a given (x,t) the set of maximizers of the expected revenue function, Y* is ascending in ry: for any y S Y* +1 yvy'zY; +v and y' € Y*, y A y' £ Y* and CHAPTER IV. 125 PARTIAL INFORMATION Since in my setting all the action sets are compact and F(rj, y) is continuous in y for each rj in the discrete topology, Theorem 6.2 of Topkis [1978] implies that each Y* has a least and a greatest element. Using a convention that I always pick, say, the greatest optimizer I obtain that the optimal allocations for each n are increasing in r\ on the lattice (Y, <). Less formally it means that with a greater inventory of unsold seats left on hand the optimal allocation offers more seats for sale in each lower nest of fares than if the inventory were smaller. I obtain the main result of this subsection. Theorem IV.9. For afixed(x,t), the optimal allocations are ordered: if rj < rf then y* < y^,, or equivalently, if u^u^l k = 1,...,K, are the optimal allocations with inventory r\,rf then }~2i x i ^ YJi=K ! u f or U = ^ 0 < k < K. It means that I eac assign more seats to each lower nest, when more inventory on-hand is available. IV.6 Upper Bound for the Revenue Function The random variable z(n, x, t; u) introduced in Section IV.2.1 counts the number of seats sold in state (n, <p, t) to a customer type $ given allocation u. It has the following, more specific form z(ri, x, t, + (u u) = (u A (3)l(p = p )+ K K A 0 + UK-l A {0 - u } ) + K K l(p = PK-I)+ K • • • + (u A 0 + UK-l A {0 - u }+ + ---+u A{0~Y K K 1 J i=2 l(p = Pi). CHAPTER IV. 126 PARTIAL INFORMATION The revenue in that case, denoted by r(i], x, t; p, 3\ u), is r(r),x,t;p,f3;u) = p (u /\3)l(p K = p) K K + {PK{U A 3) + PK-\{U -I A {3 - u } )) l(p = PK-I) + ••• + K K K + {PK{UK A0) + p -\(u -\ K A {p-u } ) + ••• + K K K P l ( A { / ? - ^ ^ } ) ) l ( p = pi) + U l (IV.6.1) i=2 Assume that the immediate revenue in the optimality equation is of the form r(r],x,t,u) := E R(ri, p, p,u), (PtmXtt) with R defined in Equation IV.6.1. The no-shows, overbooking and cancellations are not considered. The expression under the maximization sign in the optimality equation IV.2.1 can be transformed to a more useful form (I suppress the arguments of Z and t, x as arguments of v). Lemma IV.8. r(rj, t, x, u) + Ev(r) - Z(rj, tp, t; u)) = v{rj)+ K u K k Yz^[ ~ Pk fc=l + 1 ~ t rn=l K Z~l i j=k+l + u \) m " (P P ^ Yl Uj+ >P> m Pk\x, t). j=k+l (IV.6.2) Proof. See Appendix. • From the form of this expression one can see that for its maximization, the properties of P(P > Y2f=k+i j + i P — Pk I i *) should be important. When written out fully u m x the double sum in Equation IV.6.2 is a sum of at most n terms, each of the form (p — Av(r] — j + l))P(P > j,p > ft | x,t) for some fare pP G {PK, • • • ,Pi}- This 7 observation leads to an upper bound on the maximum of the respected revenue with respect to (UK, • • • (p> - Av(r] -j + • • • + u\ < n. Namely, for each j find p*i maximizing ,U\),UK + l))P(p >j,p>p \x> t). The sum i j=r, v(v) + Y [P* -Mv-j j=i j +1) • P(P>i,P>P* \V,t,x) J 127 CHAPTER IV. PARTIAL INFORMATION will provide the best upper bound for revenue for each allocation (UK, • • •, UJ),UK + • • • + ui < 7], and for the maximum over those allocation. In general the p^'s thus selected will not provide an allocation that could be used since the successive maximizers p* need not be increasing, which is required by my model where the J customer starts buying with the lowest priced seats. However, if it turns out that the maximizers form an increasing sequence (for fixed (n,t,x) then this allocation will satisfy that requirement and the optimal expected revenue will be equal to that upper bound. IV.7 A n Omnibus Formulation Combining results of Chapter III and the current chapter gives, under cer- tain assumptions, an airline yield-management model that includes cancellations, no-shows and overbooking in the more general setting when information about the current request is partial. In Chapter III, cancellations were introduced in the full information setting, i.e. where the type of the arrival process <j> e C, consisted of (p, /?). The same construction can be done when only partial information x about arrival type is available, with x and x' playing the roles of <f> and (j)' and under the analogous requirements of semi-Markov cancellations and adjusted fares. Inclusion of cancellations changes the form of the operator T and additional assumptions of the same type as before are needed to demonstrate that it preserves discrete concavity and monotonicity in inventory. Allowing partial information, on the other hand, changes the form of the operator T and the number of seats sold is now a random variable. In that case, requiring that fares and batches be independent ensures that !F preserve discrete concavity. Independent and identically distributed no-shows with increasing and concave terminal reward are allowed. So with partial information and no-show, cancellations and overbooking CHAPTER IV. PARTIAL INFORMATION 128 included both T and T have different forms, but since each of them preserves discrete concavity so does their composition. With a discretely concave and affine revenue function the expected increment in the opportunity loss Av°(rj,x,t) is decreasing in 77 and booking curves obtain. I present current forms of T and T after assumptions ensuring existence of booking curves are introduced. Independent batches and fares. (Given time and current information state.) This is satisfied, when, for instance, request size (batch) or the fare (or both) are known. Their joint distribution may change with time. When requests are single, then independence clearly holds. I. I. D . no-shows. Each customer shows up at departure independently from everything else with the same probability. Stochastically increasing and concave, semi-Markov cancellations. The usual example is that of each customer cancelling independently from everything else with the same intensity fi. Increasing and concave overbooking cost in the inventory left at departure. A natural condition, especially in situations, where there is some type of auction at departure time to mollify the customers denied booking. Adjusted fares. I subtract the expected value of a no-show refund and the expected increment in cancellation refund. The adjusted fares may change with time but nothing is paid out at time of cancellation in the model. Example I V . 2 (Immediate Revenue). Let NSRF(x,t) be the amount to be refunded to the customer that is booking at time t, given information x, in case he does not show up. Assume that customers show independently from each other and the arrival process with the same show-up probability equal to p. Let ACLTOT(n, x, t) be the marginal increase in the total of cancellation refunds due to booking a cus- tomer in the state (r),x,t). When each customer cancels independently from others, then with CLRF(x,t) being the actual amount of the refund, ACLTOT(-n,x,t) = 129 CHAPTER IV. PARTIAL INFORMATION ACLTOT(x, t) and it is equal to ACLTOT(x,t) = CLRF(t,x)P( the booking customer will cancel | x,t) Then the adjusted fare is Pi(x,t) = pj - NSRF(x,t)(l-p) - ACLTOT(x,t). In notation of this chapter, Z is the random number of seats sold given (n,x,t) an an allocation u. The Y -z is the inventory level at departure time, right before th n no-shows are realized after accounting for cancellations that happened since the l arrival, for a given r] — Z seats in inventory and information x at time t. To take into account overbooking cost I adjust the immediate revenue to be r(n, t, x; u) = E ,x,t)R(v, P, 0, L «)+ ip>/3)l(TI +P(current arrival is last \ rj,x, t)Ez\( ,t,x;u)EY _ \( -z,x,t) o(^ri-z)^ (IV.7.1) L v v z TI where Lo(r}) is the increasing and concave expected terminal reward (loss due to o booking in practical cases). I note that due to stochastic concavity assumption, th zliv-zx t)Lo(Yn-z) is discretely concave. Then, due to remaining assumptions Ez\{T,,t,x;u)EY ^ \{r,-Z,x,t)LQ{Y -z) n 2 v is concave. Consider the optimality equation v = TTv with operators T and T taking on the following forms for v G B. Tv = max {r(r], t, x; u) + E ur,,t x u)v{n - Z, x, t)} u£D(n,x,t) z % t •0 E v{Y ,,x',n)dP(x',q\x,t) Tv{r),x,t) = V Yri T -T With all the listed assumptions in force, the immediate rewards bounded and measurable and action sets finite, the validity of the optimality equation obtains, whenever T is TV-step contraction. Results of of this chapter and Chapter III then imply existence of booking curves n* (x, t). k CHAPTER IV. PARTIAL INFORMATION IV.7.1 130 Discussion of the Assumptions The few available results in the literature that model cancellations explic- itly, seem to consider the setting that corresponds to the full information case with single requests. Therefore they do not need any assumptions on independence of fares and batches given current state. The assumption of increasing convex terminal overbooking cost is common to Subramanian et al. [1997], Chatwin [1999] and this work. It is justified if there is some sort of auction held at departure to reward passengers willing to postpone their flight. The likely most practical example of the first article, where booked customers cancel independently from each other and from the booking request process, assumes, in addition, that the probability of cancellation is class-independent, but may vary with (discrete) time. The latter work, which is essentially a controlled birth and death process assumes that each customer cancels independently with the same intensity fi, but the state variable keeps track of the number of reservations in each class. I have generalized one aspect of it to suit the semi-Markov situation, and only require that the cancellations be realized between customer arrivals and that the inventory level (as a random variable) at the next arrival (or at the next inspection of the system) be stochastically increasing and stochastically concave in the current inventory. As already mentioned, Subramanian et al. [1998] applies the equivalent charging scheme, and so the rewards can be looked at as adjusted and the refunds can depend on customer's type and time of the actual booking. The second paper assumes that fares and refunds are piecewise constant function of time and that the cancellation refund depends only on time at which a customer cancels and is unrelated to his fare-class. CHAPTER IV. PARTIAL INFORMATION IV.8 131 Static vs. Dynamic Models As mentioned in the Introduction, the semi-Markov dynamic control setting includes many existing static models of airline yield management. In this section I propose one particular model that generalizes, for instance, Brumelle h McGill [1993] and Robinson [1995]. The first article assumes that fares book in increasing order, the latter does away with that assumption. Their common feature is that only one fare per period is allowed to book, their order is fixed and that demands are independent between periods. The model presented here includes the omnibus formulation from Lautenbacher & Stidham [1997] as well. Certain forms of cancellations, no-shows and overbooking can be allowed. In addition it can model situations with dependent demand between periods, where the controller learns the true demand after transaction. It does not immediately cover models with censored observations of the size of demand, e.g. the model of Brumelle, McGill et al. [1992]. IV.8.1 Discrete Time Model with Partial Information Assume a specific model with partial information where the information process is a discrete time process with fixed arrival times and a fixed, finite horizon, i.e. one with the number of request epochs and their location on time axis fixed. At each epoch a request comes in with a random size and a random fare. The role of the information variable can be played by the epoch (period) number (although one could introduce some other indicators). The controller knows that a request has arrived, and given a particular value of the information variable and the time period, he knows the joint distribution of the fare and request size (batch). His goal is to optimally allocate seats for sale in each fare class. For independent fares and batches, either when requests are independent from period to period or when the true request type becomes known, results of this chapter apply and there exist booking curves that determine optimal allocations at each time point. In other words at each decision epoch, given inventory of unsold seats there is a sequence of booking limits, which determine how many seats to offer in each price category. 132 CHAPTER IV. PARTIAL INFORMATION So assume that the booking process start at —N, with departure at 0, and that decision epochs are consecutively numbered from —N to —1. Let p(i,m \ x,n) be the probability of request type (pi,m) conditional on current information x and time n (pi is the maximum fare customer can pay and m is the maximum number of seats he can buy). information. I will call this the discrete t i m e m o d e l w i t h p a r t i a l It already includes models of Brumelle h McGill[1993], Robinson [1995], Lautenbacher & Stidham [1997]. Static M o d e l of R o b i n s o n [1995] In the model of Robinson [1995], demands are independent between periods and such that in each period the fare p(n), offered by a customer is known and fixed, but the size of the request is unknown. The discrete time model with partial information can be specified to that case by taking the information variable to be equal to the period number, x = n. Since the fare offered in each period is known, the fares and batches are independent given n, p(i,m | x,n) = p(m \ n), whenever i = p(n), the fare arriving in period n and 0 otherwise. By results of this chapter P booking curves obtain by comparing the ratios rk,j{n) to Av°(rj,n). However, since given a period number n one knows which fare is booking only r/ / _i(n) = p(n) is Ci c needed. S t a t i c M o d e l of B r u m e l l e & M c G i l l [1993] That model obtains when when fares book in increasing order, i.e. when p(n) = p _ „ , PK < ••• < Pi- T h e O m n i b u s F o r m u l a t i o n of L a u t e n b a c h e r & S t i d h a m [1997] If bounded demands are assumed ( M < oo) then this formulation (cf. Equation 1.4.1 in the Introduction) obtains from the discrete time model with partial information when the information variable in the discrete time model with partial 133 CHAPTER IV. PARTIAL INFORMATION information is the same as the type of current arrival, i.e. x = (p,/3). The authors point out that their omnibus model includes the aforementioned static models. In the two static models the demands are strictly speaking unknown to the controller. Since given a period number n one knows which fare is booking, rk,k-\{ ) = P( )> n n and effectively compares the expected opportunity loss to p(n). Further, it can be shown by induction, that the optimal policy and the v° are the same as if the request size were known. So their claim is reasserted. No-shows, Overbooking and Cancellations From the results of Section IV.7 follows that in each of the three models presented here I can include those additional (but important) features under certain conditions. Specifically, it is possible when customers survive between periods independently from each other and from period to period but with the same probability that can depend on time. The refunds may depend on customer fare type. IV.9 Examples of Chatwin [1999] I show how my formulation of the airline yield management problem in terms of semi-Markov control problem elucidates examples from Chatwin [1999]. The setting is that of a fixed, discrete period, model of arrivals with each class of customers booking in separate period. The first example in the article refers to Brumelle, McGill et al. [1992]. Chatwin points out that the booking limit-type policy may not in fact be optimal when demands are associated between periods. The two stage dependent demands model of Brumelle, McGill et al. [1999] does not immediately fit into the partial information framework since it allows the possibility that the observation of the realized demand in the first period be censored. However, a similar phenomenon that Chatwin refers to can already be observed in the simpler setting of mine, for instance even when demands are independent between periods. In the partial information CHAPTER IV. PARTIAL INFORMATION 134 case, when the distribution of the request size and the fare are not independent, the existence of booking curves usually does not obtain, cf. Example IV. 1. However, it does not matter much for the original example of Brumelle k McGill [1992] as the there are only two periods with one class booking in each and the booking process is started from the capacity of the plane. Thus, for a given capacity and positively associated demand the authors do show that there exists a booking limit policy that is optimal. That booking limit may indeed depend on the initial capacity. Because of that, there may be no booking limit in the usual sense: one that the airline sells seats down to regardless of at what level the booking had started. Examples 2 and 3, of the same author can be set in the full information setting of this work. Again, they describe two-period models with dependent demand, two fares booking in separate periods. The author shows that depending on the size of the request in the first period two different decision will be optimal in that period and concludes that optimal booking limit-type policy does not exist. Based on the more general considerations in this work one can notice that the optimal booking policy is of the booking-limit type for each type of current request. The booking curves corresponding to different types of current request, in general, may be different. In other words, the type of current request is essential in the case where I allow demands to be correlated, which is one of the features of semi-Markov processes. Loosely speaking, conditioned on different types of current events the future may indeed look different but still yield similarly structured policy. Researching when and how booking curves for different types of current information can be compared might be of some interest. Chapter V Numerical Examples I present three examples to apply some of the theory developed in the previous three chapters, with comparisons: 1. Monotone booking curves and critical times in presence of no-shows and overbooking. 2. Existence of booking curves and their behaviour when cancellations are allowed in addition to no-shows and overbooking. 3. Comparison of full versus partial information about customer's request (data from Gallego & van Ryzin [1994]). The common feature of the examples is that arrivals of booking requests are modelled as Poisson processes. From the optimality equation I have derived in each case a corresponding system of ordinary differential equations (ODEs). In general the ODEs obtain under regularity conditions on the intensity functions involved, for instance continuity in time. In all the cases involved I use intensities that are piecewise continuous and then solve the equations on corresponding segments of continuity. The numerical solutions were obtained using a student-version of Mathematica on a Pentium III computer. The respective systems of ODEs were included in short programs written in Mathematica interpreter language and then solved by 135 136 CHAPTER V. NUMERICAL EXAMPLES means of the built-in routine NDSolve. The main point of this exercise was to apply structural results and demonstrate that some of the concepts can be easily presented and numerically verified with an off-the-shelf software in a reasonable time. No doubt a custom-tailored code can cut computational time by orders of magnitude. In the third example I have numerically verified one asymptotic property of critical times by means of such a program that calculates the critical times using conditioning (as opposed to solving a system of ODEs), with an arbitrary precision but at the expense of the running time. This asymptotic property consist in the critical times exhibiting a very regular behaviour for a homogeneous arrival process and for higher inventory levels, namely the difference between two such consecutive times seems to converge to a constant. This fact may be very helpful in finding the optimal policy for large inventories. The most likely reason for this behaviour is the optimal revenue becoming flat for large times to departure and a fixed inventory level. With the exceptions of Gallego &; van Ryzin [1994] (partial information), there seems to be an absence of numerical results for continuous time, finite horizon, dynamic optimal control models of the type considered in the thesis. Therefore, in Section V . l , I have derived a deterministic upper bound, which I then use as a benchmark to compare my solutions to. In addition, in Section V.3.3, I have compared the optimal dynamic solution to one obtained with a continuous time version of Littlewood's heuristic policy. V.l No-Shows and Overbooking In the first of the three examples I consider a realistic-size yield management problem for a single-leg flight with four customer classes. Requests in each class arrive according to an independent, nonhomogeneous Poisson process. There are four classes of single requests, and one class where splittable batches of 2, with the same fare as in the single request class 3, are allowed. The initial capacity is 400 seats, and the booking horizon is 360 days. The airline has full information about each requests, i.e. it knows what price per seat a customer offers and up to how many 137 CHAPTER V. NUMERICAL EXAMPLES seats the each customer is willing to buy. Each customer shows up independently from everything else, with class independent show-up probability p = 0.95. Thus it may be optimal for the airline to overbook. I chose an overbooking pad of 10% of the initial capacity, i.e. a = 40. There is a decreasing and convex (in inventory left to departure) cost for overbooking, the expected value of the overbooking penalty is pictured in Fig V . l . According to Lemma II.4 in Chapter II, the fares used in the model are assumed to be net of the expected no-show refund. For instance, with full refund in case of a no-show and the gross fare denoted by pi, the fare i = ppi. P The system of 440 (capacity plus overbooking pad) ordinary differential equations was solved in less than 10 minutes. The optimal value function, for two inventory levels 77 = 400 + 40 and 77 = 60 + 40 was then compared to the deterministic upper bound obtained when the demands are deterministic and equal to respective expected numbers of requests in each class. The critical times where then found using simple binary search and the booking curves were plotted, the inventory left at time t is 77. Let L be the expected terminal reward (due in this case to the overbooking cost) and A(rj) the total arrival rate (the sum of intensities for each arrival type). In the case under consideration the revenue function is r(rj, cj), rj; a) = ap(c6) + L(r] — a)e/t (<J)<^. The incremental value of selling a seats versus not selling any seats is a 5r(n,(/),t;a) — r(n,(j),t;a)-r(r),<f),t;0) — ap((j))-A L(r),c6, t)e . The booking curves a xt are determined by comparing Sr(ri, 4>, rj; 1) and Av°(rj, (j), rj). So a booking curve for a given fare pj is determined by pj — AL(rj)e$t ( )^ and Av°, i.e. the fare is accepted A q if and only if - AL(j))e!* mM P j > Av°(r],t). This in turn is equivalent to Pj > AL(rf)e + ATAT?,*) = A ^ f o t ) + L{n)e^ xt ). A(<7)dq It is more convenient to work with the last expression instead of Av°, so I will define CHAPTER V. 138 NUMERICAL EXAMPLES my new v° to be the sum of the old v° and L(r])e^° ^ x d q . Formally, v°(r), <f>, t) := Tv*(r), 0, t) + L{r])e^ Note that since v* and L are discretely concave, the (new) v° is discretely concave. In Fig. V.12 I presented sample expected opportunity loss, the At; , that 0 were used in finding the critical times. V.l.l Data Capacity, c = 400 Overbooking pad, a = 0.1c = 40 Booking horizon, T = 360 days, but the solution was obtained for a slightly longer horizon of 400 days. Gross fares, (before adjustment for the expected no-show refund, full refund in each class): p\ = 1052.63, p = 894.74, p = 631.58, p = 421.05. 2 3 4 Fares (adjusted), pi = 1000, p = 850, p = 600, p = 400. 2 3 4 Intensities of booking requests, 0.7 Ai(z) A (a:) 2 < 0.6 0>a;>-10 -10 > x > -70 0.1 otherwise. 0.5 0>o:>-10, 0.7 -10 > x > -70 0.2 -70 > x > -210 0.1 otherwise. < CHAPTER V. NUMERICAL EXAMPLES 139 0.1 0 > x > -10. 0.1 -10 > x > 70 A ( z ) •= < 3 0.2 -70 > x > 210, 0.3 otherwise. The intensity of batch size 2 arrivals is A§ = 0.1 and A 4 = 0.2. The intensities were chosen so that they reflect the phenomenon that higher paying customers tend to book closer to departure. An example has been plotted in Fig. V.2 (for Ai(aO)Expected number of arrivals, Aj(t) is defined as \j(q)e^ ^ ' x qn>dq dq. For the fare P3, I use the sum of intensities of the single and the batch 2 arrivals, since the latter are splittable. Terminal reward. The terminal reward L(rj) is equal to the negative of the expected value of the overbooking cost for inventory 77. The overbooking cost is convex and decreasing in inventory left on hand (Fig V.l). For a given fare pj, the smallest inventory level, for which AL(n) < pj is denoted by rjj + 1. One notes that I have AL(2) < p u AL(7) < p , AL(13) < p , AL(17) < p , so 2 3 4 that 771 = 1,772 = 6,773 = 12,774 =- 16. V.1.2 S y s t e m of O D E s I solved numerically the system of ordinary differential equations for TJ° (440 equations). I changed the system to one over [0,T], with the corresponding change in the sign of derivative to conform to the software requirements, and I renumbered inventory levels to {0,..., 440} instead of {—40,..., 400}. I will use this convention from now on as far as inventory is concerned. 4 Av,ty = -J2iPj 3=1 {v°(v,t)-v°( -i,t))} x (t)+ + V j 140 CHAPTER V. NUMERICAL EXAMPLES 40000 30000 20000 10000 Figure V . l : Overbooking cost as a function of inventory. 2 -J2{ps-(v (v,t)-v (n-rn,t))} , 0 0 + m=l with V°(T], 0) = L{rj). Note that for v° defined in this chapter to be Tv* + Let? ~ , x( q)dq the increment Av° remains decreasing in time, when one observes that the righthand side of each of the O D E in the system is nonpositive due to discrete concavity of v°. The computing time was less than 10 minutes and can be further significantly cut when the system is solved directly in the Mathematica kernel without using front-end features. In the absence of cancellations, each v°(r],t) depends explicitly only on v°(n — 1, t). This observation paves the way to solving the system iteratively, starting from r? = 1 and then using the solution in finding v°(2, t) and so on, without simultaneously solving the whole large system of differential equations. In contrast to that, the situation when cancellations are allowed is much different, since I have to solve the system simultaneously. 141 CHAPTER V. NUMERICAL EXAMPLES 07 , 0.6 0.5 0.4 0.3 0.2 0.1 -30TT - ' -3do ' '' ' -2d0 Figure V.2: V.1.3 ' ^TofJ Graph of X (t). 2 Upper Bound Inspired by the deterministic upper bound J (n,t) introduced by Gallego D k. van Ryzin[1994] for a two-class, partial information model (no overbooking etc.) I have derived an analogous upper bound for the full information case with more classes and expected overbooking cost. The original bound, [ibid.], was obtained (by inspection) from a mathematical program and was shown to dominate the expected revenue. In the same, intuitive manner, I demonstrate that property in the full information case. I assume that deterministic demand is available and equal to the expected number of arrivals in each fare. In that case I define recursively the number of seats allocated to each fare by Sj(n t), starting with the highest fare. The number } of seats left from allocation to higher fares will be denoted by Cj. The r/j's are as defined above. Let c\ :— n, si(rj,t) := (r? — rjj) A Ai(rj), then c = rj — SI(T], t) and I 2 set Cj := Cj-i — Sj_i(r?, t), Sj(cj,t) :— {CJ — r]j} A Aj(i). I define the deterministic + 142 CHAPTER V. NUMERICAL EXAMPLES upper bound K J (v, t) = Y Pite - ^ } j=l D +A A ; W+ ^ ) L With this definition I obtain the following lemma. Lemma V . l . It holds that v°( ,t)<J (ri,t). D V Proof. I note first that since the Av° is monotone in time, for t < 0, I must have that Av°(n,t) > Av°(rj,0) = AL(ry). Therefore if I reject an arrival at time 0, when Pj < Av°(rj,0), then I will never accept that fare at earlier times given the same inventory of 77. Thus, for each fare there exists an inventory level below which I will always reject that fare, which is the Vj defined above. The same is true when the demand is deterministic. It will not be advantageous to book one more seat in a fare class when the overbooking cost exceeds the given fare. So assume that Vj' have s been determined by inspection, comparing the increments AL and each individual fare. Let Nj(t) be the total number of fare class j arrivals over t, 0 and NJ(t) the number of arrivals accepted under some admissible policy 7r. Since the arrival process is defined independently from any policy, it holds for its every realization that 0 < NJ(t) < Nj(t) /\{rj-rij} , and that ENJ(t) < Aj(t), where Aj(t) = ENj(t). + Start with the highest fare i, its corresponding intensity of arrivals Xi(t) P and the expected number of first class arrivals over t, 0 , Ai (t). If A i (t) > rj — n\, then there is more than enough first class demand to fill capacity available for that fare and a policy booking only the first class cannot be improved upon. The total revenue for this case will then be pi(Ai(t) A {n — r}\}+), which is the same as the revenue with a deterministic demand equal to Ai(i). Otherwise, let / be the highest fare class such that 2~Ij=i Aj(t) < V — Vi and Y?j=i^j(t) — V — Vi- Construct a policy ff, which accepts all fares greater or equal than i_i and in addition accepts fare pi independently with probability P 143 CHAPTER V. NUMERICAL EXAMPLES p= v m ^( ) f lAj ^ ) all other fares are rejected. The expected revenue under this policy is equal to E j = i PJAJ'(£) + Piiv ~Vi- E j = i Aj(£)), ^ich is equal to J (n, t). w D Now note that no admissible policy 7r can generate more revenue than policy TT. This is because the expected number of customers in each fare class that if accepts is greater than that of TT and so is the total expected number of accepted customers under TT (rji is increasing in /). Since TT was arbitrary it obtains that v°(n, t) < J (T], t)D Since the batches of 2 that may arrive with fare p can be split, I lump 3 them together with single arrivals of the same fare p . 3 There remains now the issue of the terminal reward. To this end it is easiest to assume that L has been interpolated linearly between the integer values. I count all the inventory used up by the process described in the first part of the proof and subtract it from the current inventory of n. Since fractional values might be involved and L is increasing, I add 1 to the total and add L(l + total allocated) to the revenue obtained in the first part. V.1.4 • Solution The difference between the expected revenue obtained and the upper bound decreases as the initial inventory increases and it does fluctuate with time for a fixed inventory level. However, it is significantly smaller for large inventories (of the order of 0.2% for 7? = c across all the booking horizon, with a peak of 1.5% for T = 400 days). This confirms that a dynamical optimization is very efficient. The series of graphs in Fig. V.4 to V.7 illustrates that point The plot of 7j°(440, t) is in Fig. V.3. V.1.5 Optimal Policy In the case under consideration results of Chapter II yield that the optimal policy can be determined by means of booking curves that are monotone (four). Their monotonicity implies that it is enough to find the critical times, one for each combination of fare and inventory, for a maximum of 4 • 440 = 1760 numbers. As 144 CHAPTER V. NUMERICAL EXAMPLES Figure V.3: Graph of v° vs. time t, n — 440. already discussed monotonicity of Av° implies that it is not optimal to book fares when the inventory level is lower than the corresponding r/j, j = 1,... ,4. The rjj's can be found by inspection (comparing AL to each fare pj). The booking curve for fare p\ is simply a constant at n =- 1. To find the critical times I performed a simple binary search to look for zeros of (pj — Au (r?, £)). The booking curves for the interval —100,0 are depicted 0 1 in Fig. V.10 and in Fig. V . l l for the full interval -400,0. V.1.6 Computational Issues As evidenced in Fig. V . l l the behaviour of booking curves for p and p 2 3 is more erratic when compared to the booking curve for p . This has to do with 4 a number of factors. The most significant is that the Av°(r],t) for larger times to departure becomes almost flat whenever it nears each fare level. This affects the precision of the numerical solution, which, in turn, causes the Av° to wiggle in the vicinity of that fare level. Both make it more difficult to find the exact time that CHAPTER V. NUMERICAL EXAMPLES 145 Av° crosses the fare level. Fig. V.12 exhibits this type of behaviour of Av° for three distinct values of inventory. However, it is also clear from the picture that for most part, the booking curves tend to grow in a regular manner on intervals. More precisely, the differences between consecutive critical times (same fare) tend to a constant as r? grows on intervals where the intensities are constant. The last section of this chapter presents an example (homogeneous Poisson case, 2 classes) where this phenomenon is even more pronounced and which I have verified by comparing to a program finding critical times with arbitrary precision. One way to ameliorate the problem is to solve the system of ODEs with greater precision and/or intensify the search, both at the expense of the computing time. It also seems that since the intervals of flatness of Av° tend to grow there is quite a bit of room in picking a critical time for large inventory levels without significantly affecting the overall value of the expected revenue. 146 CHAPTER V. NUMERICAL EXAMPLES V.1.7 Conclusions When booking requests arrive according to nonhomogeneous Poisson pro- cesses then solving the system of ODEs provides efficient means of quickly assessing the optimal expected revenue and finding the optimal critical times (and thus the optimal policy). Higher inventory levels and more customer classes can be included with larger batch requests at only a moderate increase in computing time. The most time intensive seems to be the inclusion of larger batches. Solving the system iteratively starting from 77 = 1 dramatically cuts the computing time needed. As one will see in the next example, this is much different from the case where cancellations are included and dependencies in each ODE are on both v°(n + 1, t) and v°(n - l,t). Overall, the difference between the deterministic upper bound and the optimal expected revenue becomes almost negligible as inventory grows (J-°(440,360) — TJ°(440, 360) < 300 < p and ° ^ j o J 4 6 ^ ^ 0 ' ^ 100% < 0.2%). The optimal policy can be relatively easily found and is of a convenient form, especially for higher inven- CHAPTER V. NUMERICAL EXAMPLES 147 f\ t 1 5 0 0 / lj| 1250 / | 1000 I 750 I 500 I -4T50" - ' ' -300 Figure V.6: ' ' -200 Graph of J D ' ' ^0 250 1 — v° vs. time t, rj = 100. tories and longer time intervals. For smaller inventories and less time to departure the optimal policy can be found exactly and then for higher ones and more time available the critical times can be assumed to grow in constant increments, at virtually no loss in expected revenue. This only strengthens the point that applying dynamic optimal policies can deliver the sought after improvements in expected revenue. CHAPTER V. NUMERICAL EXAMPLES V.2 148 Cancellations with No-Shows and Overbooking I expand the example of the foregoing section by including cancellations. I assume that each customer cancels independently from everything else, with a given intensity p (later allowed to change with time). In that case the results of Chapter III guarantee existence of booking curves, and, under additional restrictions, their monotonicity. The setting is that of Section III.5, i.e. that of a controlled birth and death process, with the death intensity equal to (c + a — rj)p, requests arriving according to nonhomogeneous Poisson processes with intensities Xj(t), and a concave and increasing terminal reward L. I consider several instances that differ in amounts of refund clj available to fare pj and in intensity p. The behaviour displayed by the expected optimal revenue and the expected increment Av d can vary a lot qualitatively, depending on those parameters. One feature that might be guessed is that when the refunds for at least some of the fares are less than full, then the revenue will keep growing with the amount of time available to departure, i.e. there will be no flat asymptote CHAPTER V. NUMERICAL EXAMPLES 149 1050 iooj -400 -300 -200 Figure V.8: Graph of J D -100 — v° vs. time t, n = 10. as previously. Another important feature is that the increments Av d need not be decreasing. Consequently the optimal policy may be more complex. However, in the cases considered here the booking curves seem to be quasiconcave and I conjecture that it may often be the case in practice. V.2.1 System of ODEs and Its Solution I have modified the system of ODEs to include the cancellations, in accor- dance with considerations in Section III.5, i / W , < ) :=Tv*(r), j ,t) + Lo(v)e . xt ( ) The (new) v° satisfies -" r° / c K v°(v,t)=J2 / ( J2\jmax{ +v°(riPj i=o Jt 1+i,q),v (r] + i,q)} 0 S=i c-77 (V.2.1) CHAPTER V. 150 NUMERICAL EXAMPLES 25 20 Figure V.9: -100 -200 -300 -400 Graph of ^-j^. 100% vs. time t, 7? = 10. The derived system of ODEs is v (0,ty = -(c + d K „_i ryA2 o)n{v (l,t)-v° (0,t)) d cl , + ™_i I ' j=l m=l +(c + a-n)p{v (n + d v°d(c,ty = E E (pi - - m e ^ ) ) j = l r a = l *• l,t)-v (v,t))Jorl<v<c-l, d - (*>*) - °^ -"»•*))[ v c '> with the initial condition, v (r), 0) = L(rj), clj is the refund paid to customer offering d fare pj. As already mentioned that system had to be solved with respect to v (n,t) d simultaneously for all 77. To solve it for capacity c+a = 100 (which includes overbooking pad), on an interval —210,0 (booking horizon 210 days) took about 30 minutes depending on the values of the parameters. 151 CHAPTER V. NUMERICAL EXAMPLES 175 -TOO ^ Figure V.10: V.2.2 ^40 ^60 : 20 Booking curves, (—100,0]. Case 1. I solved first two cases with the same constant intensity fj, = 0.1 but with different amounts of refunds. With cl\ = pi, c/ = $600, dz = $100, 0/4 = 0 one obtains that the expected 2 revenue is decreasing in time, and for small t (farther from departure) it is greater than the revenue when no cancellations where allowed. This is depicted in Fig. V.13, Fig. V.14 and in Fig. V.15, for initial capacities 100, 50, and 10, respectively. The expected increments Av (r),t) are increasing in time, completely in d contrast to the first example of this chapter. One can verify that the condition given in Section III.5 is satisfied in the form corresponding to increasing increments. The fares (already adjusted for expected no-show refund) were further adjusted with respect to the expected cancellation refund which made them timedependent, in this case increasing. Consequently in this case the critical times are possibly multiple and have somewhat different meaning than previously. For in- 152 CHAPTER V. NUMERICAL EXAMPLES -TM 3oo Figure V . l l : 2uT5 ^Too' Booking curves, (—400,0]. stance, if Av (n,t) starts below pj(t) at t = 0 and then crosses it twice then I reject d that fare at each time that is between the two critical times. However, in this particular case the increments Av d are small. For capaci- ties larger than 20 they are effectively 0, for lower ones they are nonzero only on short intervals (Fig. V.16, Fig. V.17, illustrate this for c = 2,20, respectively). What this means for the optimal policy is that I only need to find the crossing times for inventories 1 to 20 (possibly multiple), and for larger capacities I simply accept all fares. The crossing time can be found for instance by successively applying binary search. I omit that part as it is relatively straightforward. As it turns out, the increments are increasing with time and cross each adjusted fare (varying with t) at most once. So in this case the booking curves are increasing. CHAPTER V. NUMERICAL EXAMPLES 1000 Figure V.12: Av°(U0,t) < Au°(100,i) < Av°(10,t). Figure V.13: 7j°(100,t) and v (W0,t) vs. time t. d CHAPTER V. NUMERICAL EXAMPLES Figure V.14: v°(50,t) and t^(50,t) vs. time t. Figure V.15: •u (10,t) and v (10,t) vs. time t. 0 d 155 CHAPTER V. NUMERICAL EXAMPLES 1000 ^otr ^OTT Figure V.16: Av (2,t), pi(t) vs. time. d 1000 Figure V.17: Av (20,t) « d pi(t) vs. time. 156 CHAPTER V. NUMERICAL EXAMPLES V.2.3 Case 2. In that case I have assumed that there are no refunds, and in addition increased the highest fare to p\ = $2000. The expected optimal revenue grows even faster (Fig. V.18). The increments Av d although greater than before are still increasing and effectively 0 for larger capacities (Fig. V.19). Figure V.18: V.2.4 u°(100,t) and ^(100, t) vs. time t. Case 3. In this example I have kept the same data as in Case 1, save for the can- cellation intensity p. With the old p = 0.1 one can see that a customer, who books long enough before departure is virtually certain to cancel. I think that this is not very reflective of reality for a number of reasons. Firstly, a higher paying customer with a full refund should have some positive probability of not cancelling, even if he bought a ticket at the beginning of the booking period. Secondly, in the situation where I model the overall intensity for an average customer, regardless of his class, I can expect a number of lower paying customers, who are less likely to cancel, to 157 CHAPTER V. NUMERICAL EXAMPLES Figure V.19: pi,..., p and Av 4 d for r? = 2, 5,15,20. be booked early, therefore this average intensity should reflect that as well. Thirdly, a cancellation rate of that range, while it may seem small compared to the total intensity of arrivals Ylf=i AjOO when close to departure (0.1 < 1.3), effectively means that in an average situation with, say, 50 seats sold near departure, I can expect 5 cancellations per day which seems somewhat unrealistic. To take all those points into account I have decreased the intensity p, and allowed it to vary (constant on intervals). So p(t) = 0.01 for t > —10 and p(t) = 0.005 for rj < —10. In Fig. V.20 I have compared the optimal revenue obtained with the new p(t) and that of the first example in this chapter (no-shows and overbooking only). Figure V.21 illustrates various possible behaviours of Av° as function of time t. For fare class four, with no cancellation refunds, the adjusted fare is simply equal to p4 = $400 (already adjusted for no-show refund), so a typical Av° for lower inventories will cross that level two times (Fig. V.22). CHAPTER V. NUMERICAL EXAMPLES 158 Figure V.20: v (100,t) is smaller than u°(100,£) only close to departure. d Optimal Policy The expected increments Av° in this case display a more complex behaviour than before. They are quasiconcave: grow and then decrease, as the departure time nears and they cross each adjusted fare j(t) = pj — c/j(l — e^) at most twice. I have P determined those crossing points for each adjusted fare by successively applying the Mathematica's FindRoot routine (which is based on Newton's algorithm) and confirmed that each adjusted fare intersects an increment at most twice. Those critical times were then used to construct booking curves which are depicted in Fig. V.23. I note that with the given refund structure and the p(t) as chosen the nestedness property is preserved, i.e. if I accept a given fare then I accept all higher fares. Conclusions When cancellations are allowed the behaviour of booking curves is more complex and, to some extent, opposite to the case where they are not allowed. I 159 CHAPTER V. NUMERICAL EXAMPLES 1000 Figure V.21: time t. A t £ ( 1 0 0 , t ) < Av (50,t) < Av (20,t) < Av (10,t) < Av° (2,t) d d d d vs. have itemized the main points. Quasiconcavity. Both the expected increments and the booking curves seem to be quasiconcave (increase and then decrease) in time t for reasonably realistic models. Sensitivity to cancellation rate. The cancellation rate exerts profound influence on the qualitative and quantitative behaviour of booking policy. W i t h the refund structure kept fixed, changing the rate from 0 (no cancellations) to 0.01 and then to 0.1 makes the booking curves go from decreasing through quasiconcave (with a hump) to increasing. Long-term behaviour. For a given inventory level and with at least some refund less than full, for large enough times and with fj,(t) constant there, the airline can make money off the difference between the fare and the refund. This effect causes the expected revenue to grow almost linearly with more time, at a maximum rate which means that it is optimal to accept all fares. 160 CHAPTER V. NUMERICAL EXAMPLES Figure V.22: p = 400 and Av°(30,t) vs. time t. 4 V.3 Full vs. Partial Information In this numerical example I compare the partial information (intensity con- trol) example of Gallego &; van Ryzin [1994] with the situation where the type of the current request is known, i.e. that of Chapter II. There are two customer classes, one buying full fare p\ — $358, arriving with intensity 0.5 customers per day, and one buying the discount fare class p = $198, 2 with intensity of arrivals equal to 0.5 customers per day. I start booking with c = 300 seats available, the initial booking horizon is 360 days. Overbooking is not allowed. In each case the optimal expected revenue and the optimal policy were obtained by numerically solving a corresponding system of ODEs. V.3.1 Partial Information For the Poisson process described above, the rate at which booking requests arrive is A = Ai 4- \2 — 1 customer per day. Knowing that there is a request for CHAPTER V. NUMERICAL 161 EXAMPLES TJ -^5 Figure V.23: Booking curves from highest (p ) to the lowest (pi). 4 a booking the airline sets the price. The customer buys with probability ^ = 0.5 when price is set at $358. When price is set to p2 := $198 that probability is 1. From my earlier considerations follows that the optimal value function and the v° are both monotone in time and inventory. Theorems in the Chapter I V yield that the booking curves exist since requests are for single seats and, i n addition, since the process is nonhomogeneous Poisson I know that Av° is decreasing i n time. It further follows that given inventory r? the optimal policy sets the fare to p2 if and only if 7"2i = P 2 iIo5° 5 — A g(v) v (cf- Lemma IV.2). Constant probabilities of accepting a given price mean that r \ does not change with time, which implies that the optimal 2 policy can be characterized by one critical time for each combination of inventory level and price. 162 CHAPTER V. NUMERICAL EXAMPLES Upper Bounds I use the upper bound J (rj,t) introduced by Gallego & van Ryzin[1994]. D The bound J (ri,t) := p min jr?, A ( { 0 , r ? - A i t } + - {0,r? - A t } ) / A } + D + 2 2 Pi min jr?, Ai ^{0, At - n}+ - {0, Ait - 7?}+j / A j 2 was obtained (by inspection) from a mathematical program and was shown to dominate the expected revenue. I use it to judge the quality of the solution. When full information about customer's request is available I use the deterministic bound derived in Lemma V . l , for the case of two customer classes and zero terminal reward, 7/(77, t, x) < Jf(r), t) := pi min{7?, Ait} + p min{{r? - A i t } , A t}; + 2 2 System of O D E s I solved numerically the system of 300 ordinary differential equations for v 1 on an interval —400,0 . g v° (v,t)' = 9 = max h i U - [v° ( , t) - v° ( - 1, t)] , (A + A ) p - [v° ( , t) -v (r,Q g V g V x 2 2 g V g with u°(77,0) = 0. Gallego & van Ryzin note that their heuristic solutions becomes close (in the ratio sense) to the deterministic upper bound as n and time t both go to infinity in a certain manner. They provide a heuristic solution that changes prices only once and report the expected revenue within 2% of the deterministic upper bound. I have confirmed their claim and note that the dynamic optimal policy improves on 163 CHAPTER V. NUMERICAL EXAMPLES it. For the same initial data it is within 0.2% of the deterministic upper bound at the beginning of the booking horizon, with a peak value of 0.5%. In Fig. V.24, I present the graph of the gap between J and v®. Fig. V.26 shows the graph for D the inventory level of 100, where one can observe that the gap J D — v® depends, in general, on rj, t, with two spikes whenever Xt = n and X\t = t). I confirm that the relative error is small, reaching at most 5% for certain combinations of r? and t, (Fig. V.25 for 77 = 300, Fig. V.27 for rj = 100). 300 250 200 150 100 50 5uTT -400" I Figure V.24: Graph of J D "^TTJO" - v° vs. time t, n = 300. CHAPTER V. NUMERICAL EXAMPLES Figure V.26: Graph of J D - v° vs. time t, n = 100. CHAPTER V. NUMERICAL EXAMPLES -400 -350 -300 -250 -200 -150 -100 J -v° D Figure V.27: Graph of j D 9 -50 vs. time t, n = 100. 0 CHAPTER V. NUMERICAL EXAMPLES 166 Optimal Policy The optimal policy sets the price to p whenever 2 I have used binary search to find the critical times where r2,i = ^iZo "' AVg(r), 1 t) 5 — AVg(r], t). crosses r ,i for each 2 77. I plotted the booking curve using the first 30 critical times in Fig. V.28. While the binary search can in principle easily find all of the 300 critical times, there are however some numerical complications that make it more difficult for large inventory levels (roughly > 200). The main reason is that the solution obtained using NDSolve is only a numerical approximation. More specifically, solving an ODE numerically encounters problems when the functions involved become flat, i.e. the derivatives are close to 0. This can be overcome by increasing precision of numbers involved (loosely speaking, one needs to work with longer numbers) at the expense of computing time. An example that well illustrates the point is in Fig. V.29. However, the situation is not entirely bad, as for larger inventory levels one can observe that t +i — t — • c, v v i.e. they seem to converge to some constant. Also, the intervals of flatness increase with inventory, which means that picking times that are slightly different than the true critical times has almost no effect on the final expected value. CHAPTER V. NUMERICAL EXAMPLES 167 168 CHAPTER V. NUMERICAL EXAMPLES V.3.2 Full Information Similar analysis to the one in foregoing subsection can be done when it is known what the customer requests. I numerically solved a corresponding system of ODEs. 2 v°(v,t)' = E m a x (^ - K M ) ~v°(V- l,t)),0}\ jf j=l with v°(r],0) =0. The behaviour of v° with respect to the deterministic upper bound is similar and is presented in Figures V.30 and V.31. The gap is within 0.5% of the deterministic upper bound at t = 360 days to departure, with a peak value of 2%. Figure V.30: Graph of jf - v° vs. time t, V = 300. CHAPTER V. NUMERICAL EXAMPLES 0.03 0.025 0.02 -400 170 CHAPTER V. NUMERICAL EXAMPLES Optimal policy I found the (optimal) critical times using the binary search, for each inventory level n finding the point in time t where Av°(r), t) crosses the p = 198. Despite 2 the usual problem with flatness of the increments involved near the fare level p , the 2 binary search, in this case, found them relatively accurately. A booking curve with all of the critical times is in Fig. V.32, and for the first 30 it is in Fig. V.33. The booking curve clearly displays the asymptotic behaviour, with t +i — t being in the v v vicinity of 1.41 for large n. I have confirmed this by comparing that number to one obtained from a program that finds critical times in a two fare case with an arbitrary precision (the more precision required, the more computational time needed). The difference between the two of them, 1.41 and 1.388, is negligible. 300 , Figure V.32: Booking curve, full information. CHAPTER V. NUMERICAL EXAMPLES Figure V.33: Booking curve, first 30 critical times. CHAPTER V. NUMERICAL EXAMPLES V.3.3 172 Full vs. Partial Information The optimal expected revenue obtained in the partial information case con- firms the intuition that it should be lower in the second case. The difference itself does depend on the remaining capacity and time to departure. It indicates how much (in expectation) the additional information about requests is worth to the controller, or in other words how much one should be willing to pay to learn more about each customer's request. I present some comparisons. In Fig. V.34, I show the difference in the expected revenue between the two cases for a fixed inventory level as a function of time, and in Fig. V.35 the relative difference is presented. It turns out that the expected value of perfect information about each request is significant, which may lead to the conclusion that certain level of expenditures to learn about customer's true request is justified. Another interesting feature is that in both cases the relative error compared to the deterministic upper bound is small. Which suggest that at least when arrivals are Poisson, the optimal dynamic policy performs very well when the initial inventory and the booking horizon are large. Together with the exhibited asymptotic property of critical times this should make the dynamic programming policy attractive. CHAPTER V. NUMERICAL EXAMPLES 174 CHAPTER V. NUMERICAL EXAMPLES V.3.4 Dynamic and Heuristic Policies One heuristic policy that is relatively well known among the practitioners is the Littlewood's rule that goes back to early seventies. It has been applied usually in static models but it can be translated into a continuous time setting. We use the two fare class, Poisson version from Sun [1992]. The policy determines the critical times and the booking curve by considering expected increment in revenue from the highest fare passengers. Sun [1992] gives a system of ODEs that have to be satisfied by that increment and shows that it is simply equal to Av^n, t) = p\P(Ni(t, 0] >rj). The critical times can be found from the Littlewood's rule: p 2 = PiP(ATi(t2,0] >n). Using Mathematica, these times can be very efficiently found, even for large capacities. They do exhibit similar asymptotic behaviour as the critical times found by means of dynamic programming. This asymptotic property is easier to prove and relatively natural to guess: in the limit tc +1 —i% —• 1/Ai. The difference is the time needed for the expected number of first class arrivals to be equal to one. In this particular case the Littlewood's heuristic performs very well, and for c = 300 and T — 360 days, the difference in the expected revenues is 0.8%, it grows with longer horizon but for a shorter one is even smaller, Fig. V.36. For lower inventories it turns out that the difference between two policies is close to 0% with a peak of 2.5 -f- 3%, whose location and width depends on the combination of the parameters rj and t, Fig. V.37 illustrates that for n = 100. While the expected revenues appear to be pretty close to each other, the story is quite different for the booking curve corresponding to Littlewood's heuristic. It is always significantly below the optimal dynamic booking curve, which confirms that this heuristic policy underprotects seats for first class customers. The two different behaviours suggest flatness of the expected revenue from a booking policy determined by a decreasing booking curve, and its relative robustness to small shifts in critical times, that are close to the optimal ones. CHAPTER V. NUMERICAL EXAMPLES Bibliography [1] Banerjee, P. K., B. Viswanathan (1989), "On Optimal Rationing Policies," Canadian Journal of Administrative Sciences, 1-6. [2] Belobaba, P., L. R. Weatherford (1996), "Comparing Decision Rules that Incorporate Customer Diversion in Perishable Asset Revenue Management Situations," Decision Sciences 27 (2). [3] Bitran, C , Mondschein, S. (1995), "An Application of Yield Management to the Hotel Industry Considering Multiple Day Stays," Operations Research 43 (3), p. 427. [4] Bitran, G., Gilbert, S. (1996), "Managing Hotel Reservations with Uncertain Arrivals," Operations Research 44 (1), p. 35. [5] Brumelle, S. L., J. I. McGill (1989), "A General Model for Airline Overbooking and Two-Class Revenue Management with Dependent Demands," Working paper, University of British Columbia, Vancouver, B.C. [6] Brumelle, S. L . , J. I. McGill, T . H . Oum, K . Sawaki and M.W. Tretheway (1992), "Allocation of Airline Seats between Stochastically Dependent Demands," Transportation Science 24(3), 183-192. [7] Brumelle, S. L., J. I. McGill (1993), "Airline Seat Allocation with Multiple Nested Fare Classes," Operations Research 41(1), 127-137. [8] Brumelle, S. L., R. G. Vickson (1975), "A Unified Approach to Stochastic Domi176 nance," in Stochastic Models in Finance, W.T. Ziemba and R.G. Vickson (eds.), Academic Press. [9] Chatwin, R.E. (1996a), "Optimal Control of Continuous-Time Terminal-Value Birth-and-Death Processes and Airline Overbooking," Naval Research Logistics 43 (2), 159-168. [10] Chatwin, R. E . (1996b), "Multi-period airline overbooking with multiple fare classes," Naval Res. Logist. 43 No. 5, 603-612. [11] Chatwin, R.E. (1998), "Multiperiod Airline Overbooking with a Single Fare Class," Operations Research 46, No.6. [12] Chatwin, R.E. (1999), "Continuous-Time Airline Overbooking with Time- Dependent Fares and Refunds," Transportation Science 33 (2), May 1999. [13] Chow, Y.S., H. Robbins, D. Siegmund (1971), Great Expectations: The Theory of Optimal Stopping, Houghton- Mifflin, Boston. [14] Cinlar, E . (1969), "On semi-Markov processes on arbitrary spaces," Proc. Cambridge Philos. Soc. 66, 381-392. [15] Cinlar, E . (1975a), Introduction To Stochastic Processes, Prentice-Hall. [16] Cinlar, E . (1975b), "Markov renewal theory: a survey," Management Science 21(7), 727-753. [17] Derman, C , J. Sacks (1960), "Replacement of Periodically Inspected Equipment," Naval Res. Log. Quart. 7, 597-607. [18] Denardo, E.V. (1967), "Contraction mappings in the theory underlying dynamic programming," SIAM Review 9(2), 165-177. [19] Dynkin, E . B., A. A. Yushkevich (1975), Controlled Markov Processes, Springer Verlag, Berlin, Heidelberg, New York. [20] Feller, William (1966), An Introduction to Probability Theory and Its Applications, Vol II, J. Wiley and Sons, New York. 177 [21] Feng, Y., G. Gallego (1995), "Optimal starting times for end-of-season sales and optimal stopping times for promotional fares," Management Science 41(8), 1371-1391. [22] Gallego, G., G. van Ryzin (1994), "Optimal dynamic pricing policy of inventories with stochastic demand over finite horizon," Management Science 40(8), 9991020. [23] Gallego, G., G. van Ryzin (1997), "A multiproduct dynamic pricing problem and its application to network yield management," Operations Research 45 (1), 25-41. [24] Gerchak, Y., 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. [25] Hanoch, G., H. Levy (1969), "The efficiency analysis of choice involving risk," Rev. Econom. Stud. 36, 335-346. [26] Helm, W. E . , K.-H. Waldmann (1984), "Optimal control of arrivals to multiserver queues in a random environment," J. Appl. Probab. 21 (3), 602-615. [27] Hinderer, K. (1970), "Foundations of Non-stationary Dynamic Programming with Discrete Time Parameter," Springer- Verlag. [28] Hinderer, K. (1978), "On approximate solutions of finite-stage dynamic programs. Dynamic programming and its applications," Proc. Conf, Univ. British Columbia, Vancouver, B.C., 1977, Academic Press, New York-London, 289-317. [29] Hinderer, K. F. (1985), "On the structure of solutions of stochastic dynamic programs," Proceedings of the seventh conference on probability theory (Bra§ov, 1982), V N U Sci. Press, Utrecht, 173-182. [30] Hinderer, K., K.-H. Waldmann (1998), "Approximate Solution of Markov Renewal Programs with Finite Time Horizon", SIAM J. Control Optim. 37 (2), 502-520. 178 [31] Jacod, J. (1974), "Corrections et complements a: 'Theoreme de renouvellement et classification pour les chaines semi-markovienne' (Ann. Inst. H. Poincare Sect. B (N.S.) 7, 83-129)", (French) Ann. Inst. H Poincare Sect. B (N.S.) 10, 201-209. [32] Jacod, J. (1971), "Theoreme de renouvellement et classification pour les chaines semi-markoviennes," (French) Ann. Inst. H. Poincare Sect. B (N.S.) 7, 83-129. [33] Johansen, S. G., S. Stidham (1980), "Control of arrivals to a stochastic inputoutput system," Advances in Applied Probability, 12, 972-999. [34] Karaesmen, I., G. van Ryzin (1999), "Overbooking with substitutable inventory classes," Working Paper, Columbia University, N Y NY. [35] Karlin, S., Y . Rinott (1980), "Classes of orderings of measures and related correlation inequalities. I. Multivariate totally positive distributions," J. Multivariate Anal. 10 (4), 467-498. [36] Karlin, S., Y. Rinott (1980), "Classes of orderings of measures and related correlation inequalities. II. Multivariate reverse rule distributions," J. Multivariate Anal. 10 (4), 499-516. [37] Langen, H.-J. (1982), "Applying the method of phases in the optimization of queueing system," Adv. Appl. Prob. 14, 122-142. [38] Kirstein, B. M . (1976), "Monotonicity and comparability of time-homogeneous Markov processes with discrete state space," Math. Operationsforsch. Statist. 7, No. 1, 151-168. [39] Kleywegt, A. J., J. D. Papastavrou (1998), "The Dynamic and Stochastic Knapsack Problem," Operations Research 46 (1), 17-35. [40] Lautenbacher, C , S. Stidham Jr. (1997), "The Underlying Markov Decision Process in the Single-Leg Airline Yield-Management Problem," Working paper. [41] Lee, Tak C , M . Hersh (1993), "A model for dynamic airline seat inventory control with multiple seat bookings," Transportation Science 27 (3), 252-265. 179 [42] Lewis, M . E . , H. Ayhan, R. D. Foley (1999), "Optimal Admission Policies for a Multi-Class Nonstationary Queuing System," Working paper. [43] Li, H., M . Shaked (1994), "Stochastic convexity and concavity of Markov processes," Math. Oper. Res. 19 (2), 477-493. [44] Liang, Y . (1999), "Solution to the Continuous Time Dynamic Yield Management Model," Transportation Science 33 (1), 117-123. [45] Lippman, S. (1976), "Countable-state, continuous-time dynamic programming with structure," Operations Res. 24 (3), 477-490. [46] Lippman, S. (1974/75), "On dynamic programming with unbounded rewards," Management Sci. 21 (11), 1225-1233. [47] McGill, J. I. (1989), Optimization and Estimation Problems in Airline Yield Management, Ph. D. thesis, Faculty of Commerce and Business Administration, University of British Columbia, Vancouver, B.C. [48] McGill, J. I. (1999), "Revenue Management: Research Overview and Prospects," Transportation Science, Vol. 33, (2), 233-256. [49] Mamer, J. W. (1986) "Successive Approximations for Finite Horizon, semiMarkov Decision Processes with Application to Asset Liquidation," Operations Research, Vol. 34 (4), 638-644. [50] Miller, B. L.(1968), "Finite State Continuous Time Markov Decision Processes with a Finite Planning Horizon," SIAM J. Control 6, 255-280. [51] Queyranne, M . , T. Fill (1999), "Hotel yield management: a stochastic integer programming model with a Monge property," Operations & Logistics Seminar, UBC, Vancouver. [52] Rieder, U. (1975), "Bayesian Dynamic Programming," Advances in Applied Probability, Vol. 7, 330-348. 180 [53] Robinson, L. W. (1995), "Optimal and Approximate Control Policies for Airline Booking with Sequential Nonmonotonic Fare Classes," Operations Research, Vol 43, 252-263. [54] Schal, M . (1975), "Conditions for optimality in dynamic programming and for the limit ofre-stagepolicies to be optimal," Z. Wahr. Verw. Geb. 32, 179-196. [55] Schellhaas, H. (1980), "Markov renewal decision process with finite horizon," OR-Spektrum 2, 33-40. [56] Stidham, S., Jr. (1978), "Socially and Individually Optimal Control of Arrivals to a GI/M/1 Queue," Management Sci., 24, 1598-1610. [57] Subramanian, J., S. Stidham Jr., C. J. Lautenbacher (1997) "Airline Yield Management with Overbooking, Cancellations, and No-Shows," Working paper. [58] Sun, Xiao (1992), Airline Yield Management: A Dynamic Seat Allocation Model, M.Sc. thesis, Faculty of Commerce, Univ of British Columbia. [59] Topkis, D. M . (1978), "Minimizing a submodular function on a lattice," Oper- ations Research 26 (2), 305-321. [60] Veinott, A.F. Jr. (1974), Class Notes, Course on Inventory Theory. Operations Research Department, Stanford University, Stanford, Calif. [61] Weatherford, L.R., S. E . Bodily (1992), "A taxonomy and research overview of perishable-asset revenue management: yield management, overbooking and pricing," Operations Research 40 (5), 831-844. [62] Zhao, W., Y . Zheng (1999), "Optimal Dynamic Pricing for Perishable Assets with Non-homogeneous Demand," Working paper, The Wharton School of the University of Pennsylvania. 181 Appendix A A.l Proof of Remark II. 1 Remark II.1. If J^ T dP((f>', q\(j>, t) is decreasing in t, for each pair cj)', 4> G C and for I 1 each a < 0, then Tf(rj, <p, t) is decreasing for t £ —T, 0 and nonnegative for each n and 4> whenever f is. Proof. Since T/(r?, 0, t) = Yl<p&: S-T fiv,^'',q)dP(<j>',q | <f>,t) it is enough to show that each term in the sum is decreasing. So fix 0', 0 and the inventory r\. Since / is measurable in t and bounded there exists a sequence of simple functions f (t) n (taking on a finite number of values only), which converges uniformly to / . I0 A, n k f := \te h T^ -T,0 : — | k*M otherwise, ,. , . (k+l)*M^ < f(v,<P,t) < - 'K Since f(t) is decreasing, the sets A n k , , k = 0,1,...,n - 1. n are just intervals. Whether the endpoints are I included or not is irrelevant for our purposes, so assume that A ^ = n The / „ has the form / (t) = n ^ M l ^ ( t ) , n k=0 182 CL ,ki n b ,kn and f (t) —• f(t) as n —• oo. Rewrite /Vs as follows: n £ JW(t) = £ fn(t) = > J b ^1[-T, „, )(t), a fc rearranging terms in the sum defining / „ . I will use the new form of / „ . / f (t)dP(q \t) = J2 -h-T,a , ){q)dP{q\t) = n k=0 n k ~ J k=0 1 ~ J 1 which is decreasing in t as each term is decreasing by assumption. Consequently Tf n is decreasing in t. By bounded convergence Tf (n, <j>, t) converges to Tf(rj, (j), t) and n it follows that Tf(r], 4>, t) is decreasing in t. A.2 • Proof of Lemma III.3 I fix the current arrival type ((j), t), the inventory left n and the type and time of the next arrival (</>', s). Let Fr, i,F + v and F -i be the cumulative distribution v functions of V^+i, Y and Y -\ respectively, and let F := l—F denote the distribution v v of a tail of a random variable. The YJ/s are the previously defined random variables that represent inventory level at the next arrival ((/>', s) given the current arrival of type (j) at time t and inventory left ry. I recall the formulation of the lemma. Lemma III.3. Let v be increasing and concave in inventory n. Then Ev(Y i) — n+ Ev(Y„) < Ev(Y„) — Ev(Y„-i), Va;, for all r\, is equivalent to f* AF i(s)ds < 0 decreasing in n. a n+ Proof. By integrating by parts I obtain that, for each 1, Ev(Y ) = f t J v(s)dF (s) =v(s) *F (s)\ _ - f c l l a —(7 F^dvis). J —<T The integrals are well defined and nonnegative since v is increasing. Taking the corresponding differences I can see that Ev(Y ) - Ev(Y ) - (Ev(Y ) - £to(y„_i)) = f v+1 v n J—a 183 {AF (s) - AF (s))dv(s). v+1 v I claim that J f a (AF i(s) — AP (s))dv(s) < 0 (first expression) for every increasing v+ v and concave v is equivalent to f* (AF i(s) — AF (s))ds < 0, (second expression) v+ n for all x. To show sufficiency note that a function with slope 1 on —a, x and then I | equal to x on x, c is increasing and concave, and integrating with respect to the measure generated by this function gives exactly (AF„ i(s) + — AF (s))ds, which n has to be negative if the first expression was. Let v be any increasing and concave function of r/. Let Av(—a + 1) < M, M > 0, each integral J fdv can be written as M J fdv, where v — JJ and Av(—a + 1) < 1. As M > 0, J fdv, M J fdv and / fdv have the same sign and to demonstrate necessity I can use v. Define "positive" area to be {s | AF x(—a + 1) — AF (—a + 1)}, and the v+ v negative area in a similar way. Note that AF i(—a + 1) — AF (—a + 1) has to v+ n be negative, otherwise for the above linear function with x = —a + 1 the second condition will not hold. Now, the positive area to the right of any negative area will weigh more with a linear function x than with a concave function v, therefore f* a (AF i(5)-AF (5))dw(5)< J* ( A F , i ( s ) - A ^ ( « ) ) r f s . Therefore if the second r7+ ?7 a + expression is negative so is the first one. Taking x = c concludes the proof. A.3 • Proof of Lemma III.8 LemmaIII.8. + v +li„ (v°( + 1, ?) - v (v, d)) je - dq 0 V (t q) + Lo^e Proof. Recall the original integral equation satisfied by v -n c o / r K 184 4 (A.3.1) + ^2L ( 0 + i) ( ,t,q)e ^d (A.3.2) x V Pi V q) i=0 I show that both forms of the integral equation for v° lead to the same differential equation, which together with the same intitial condition will imply that they have the same set of solutions, and, by uniqueness, each solution is identical with v°. I first note that the Pi(rj,t,q) satisfies a recursive relationship Pi(v,t,s)= J p - (r] + l,q,s)u. e^ - dq {t i 1 ri q} ) which leads to a differential equation Pi(r],t,s)' = Unipi^ir] + l,t,s) -pi(rj,t,s)), where pi(c,t,s) = 0 for % > 1 and by convention, P-iin,t,s) — 0. Taking the differential relationship for p^s into account from Equation A.3.2 obtains the following system of ODEs (r? € {—a,..., c}) v°(V,t)' = f ^2\ max{p + v (r]-l + i,q),v (ri + i,q}+ 0 i 0 j (A.3.3) p (v°(ri+l,t)-v ( ,t^y 0 n V With the initial condition v° = 0. Now taking derivatives of both sides of Equation A.3.1, an identical form of ODEs obtains, with the same initial condition. So v° satisfies the Equation A.3.1. A.4 • Proof of Lemma IV.8 I prove first a few preparatory results before the proof of Lemma IV.8. The first one is that the immediate revenue r(r],x,t;p,0;u) (cf. Equation IV.6.1 can be written in a more convenient form. Note that all probabilities involved are conditional upon (x,t), which has been fixed. Therefore, for the ease of notation that conditioning will be suppressed. 185 Lemma A . l . K r(rj,x,t;p,p;u) K u k =YY[ ^pk1 ^ + ™> P > Pfc) (A.4.1) Proof. In expression A.4.1, for each p I collect the terms that include p k k r(rj,X;t;p,0;u) = PK(U A 0)l(p > p )+ K K pK-i {UK-I A {/? - u } ^j l ( p > = + K PK-l)+ 2 •••+ P l (u! {8 - A ]T M ) HP > P I ) + Using the fact that a sum of any n terms a\,..., a can be written, for any I as n Y17=i iM a n — -Oi I simplify each expression enclosed by the bigger parentheses. X «j} j=fc+i Pk(u /\{/3k = Pfc(^l(/?> m=l £ + ) (P 1 > Pfc) = ^+^))l(P>Pfc) = j=k+\ 3=K uk = ^p f c l(/?> m=l E Uj+m,p>p ) k j=k+l I finish by summing all expressions for different fares Pfc. • By taking expectation with respect to (p,0), and using Lemma A . l I obtain the immediate expected revenue r(-n,t,x,u) = Er(n,x,t;$;u) , in the following form. K K u k r(r),t,x,u) =YJ2[ (P^ pkP /e=lm=l Y ^+™>P>Pfc)] ( --) A 4 2 j'=/c+l For the same allocation u, the random variable z(r],x,t;p,0;u) has been defined so as to represent the number of seats sold to a customer with z(Vi i t; p, 8\ u) — (UK A /9)l(p = PK)+ x 186 U A 0 + U -1 A {0 - U } ) 1 ( P = pK-l)+ + K K K K •••+(u A0 K + u -i A {0 - u } • • • + ^ A {0 - E 1(P = P i ) + K K 3=2 This expression counts the number of seats sold and is similar to the expression in equation A.4.1. I transform it to a simpler form in the very same manner as in the Lemma A . l . This is done in the following lemma, whose proof I omit. L e m m a A.2. K z(n,x,t;p,(3;u) = u K k ^ \}(P ^ E j+ >P^Pk) k=lm=l j=k+l u m • Proof. Omitted. • L e m m a IV.8. r(n, t,x,u) + Ev(n - Z(n,x,t; ,x,t) = v(n)+ K u K k K J ^ X ^ - ^ + l - l E « j + m])] • P(/3 > J2 Uj + j=k+l j=k+l Jk=l m=l m,p>p ). k Proof. V Ev(n -Z,x,t)=Y^ v(v - = i) = i=0 77+1 v(n)P(Z > 0) - (v ~ i + 1)P(Z > i) Av i=l = v{ri) -J2 (V-i Av + l)P(Z >i), (A.4.3) i=l using v(0) = 0. I define Av(0) = 0. For a given allocation u, the i-th seat in the inventory of rj seats is priced at some pk if and only if for this k holds that 2~2f=k+i i u i < 2~2f=k i> u or > equivalently if % = 2~2f=k+i j + u 187 m f° rs o m e < 1 < rn < Uk- If Z < i for some i then P(Z >i)=0 and the corresponding term in the sum drops out. The form of Z from Lemma A.2 yields that K K u k K m k=l m=l j=k+l if and only if d > Y%=k+i i + u m a j=k+l n d P-Pk I use those facts to transform Equation A.4.3 to the following, more convenient form. K E v(v -Z)= z u K k v(rj) - Y J2 [ ^ Av + 1 - k=\ m=l t X Uj+m]) j=k+l K •P(P> Y i + >P- Pk)- u m j=k+l Combining that with the expression for r(r],t,x;u) from equation A.4.2 I obtain r(77, t, x, u) + Ev(n K X Z, x, t) = K u k /Z [ fc=l m=l - pk ~ A v K ^+ ~( Z 1 TJ(T7)+ Uj + m) P(p> j=k+l Y Uj + m,p> j=k+l p) k a 188
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Dynamic control of inventories over finite horizon...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Dynamic control of inventories over finite horizon with an application to airline revenue management Walczak, Darius 2000
pdf
Page Metadata
Item Metadata
Title | Dynamic control of inventories over finite horizon with an application to airline revenue management |
Creator |
Walczak, Darius |
Date Issued | 2000 |
Description | When a customer requests a discount fare, the airline must decide whether to sell the seat at the requested discount or to hold the seat in hope that a customer will arrive later who will pay more. I model this situation for a single leg flight with multiple fare classes and customers who arrive according to a semi-Markov process (possibly nonhomogeneous). These customers can request multiple seats (batch requests) and can be overbooked. Under certain conditions, I show that the value function decreases as departure approaches. If each customer only requests a single seat or if the requests can be partially satisfied, then I show that there are optimal booking curves which decrease as departure approaches. I provide counterexamples to show that this structural property of the optimal policy does not hold in general. When customers are allowed to cancel I show that booking curves exist and may be monotone in certain cases. I also consider the situation where the customer's request size and fare offered are not known, but their joint probability distribution is available, and show that under certain conditions existence of booking curves obtains, and that under further assumptions, they are monotone. Finally, the theoretical results are used in realistic numerical examples, which are compared to certain deterministic upper bounds and revenues obtained under heuristic policies. The airline yield management problem described above is an instance of a generic revenue management problem, which, in turn, can be cast into a finite horizon semi-Markov dynamic optimal control problem. I provide examples of other applications of revenue management. |
Extent | 8415616 bytes |
Subject |
Airlines -- Management Airlines -- Rates -- Mathematical models |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-07-23 |
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.0099532 |
URI | http://hdl.handle.net/2429/11184 |
Degree |
Doctor of Philosophy - PhD |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
Graduation Date | 2000-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_2000-566390.pdf [ 8.03MB ]
- Metadata
- JSON: 831-1.0099532.json
- JSON-LD: 831-1.0099532-ld.json
- RDF/XML (Pretty): 831-1.0099532-rdf.xml
- RDF/JSON: 831-1.0099532-rdf.json
- Turtle: 831-1.0099532-turtle.txt
- N-Triples: 831-1.0099532-rdf-ntriples.txt
- Original Record: 831-1.0099532-source.json
- Full Text
- 831-1.0099532-fulltext.txt
- Citation
- 831-1.0099532.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0099532/manifest