On the Hotel Overbooking Problem--An Inventory System with Stochastic Cancellations

M hotel rooms are available at a date n periods from now. Reservations are made by customers for that date, which is at the peak of the high season. Typically, for such a time period, a policy of overbooking is exercised by the hotel management. Customers, however, may cancel their previously confirmed reservations at any time prior to their arrival, with no penalty. On the other hand, new requests for rooms for that particular date are generated anew. At the end of each period the hotel management reviews both the "inventory" level of remaining uncanceled (previously confirmed) reservations and the total number of not-yet-confirmed new requests. At that time a decision is made regarding the inventory level of confirmed reservations with which to start the next period. A decision is one of three actions: (i) to keep the inventory at its present level (i.e., declining all new requests); (ii) to increase the level of overbooking by confirming some of the new requests and, if necessary, by trying to obtain some additional reservations (at some extra cost); (iii) to decrease the level of inventory by canceling some of the previously confirmed reservations (incurring a penalty for each such cancellation). Each occupied room at the target day carries a given profit, while each unhonored reservation at that time incurs a penalty. The problem is to find the optimal over-booking strategy that will maximize net profit. For both criteria, maximization of the expected total net profit, and maximization of the expected discounted net profit, it is shown that the optimal strategy is a 3-region policy as follows: For each period there exist upper and lower bounds and an intermediate point such that, (a) if the overbooking level at the end of a period is greater than the upper bound, it should be decreased to that bound; (b) if the inventory level is below the lower bound, two cases may occur: (i) if the discrepancy is greater than the number of new requests, all new requests should be confirmed and additional reservations should be acquired such that the inventory level will be equal to the lower bound; and (ii) if the discrepancy is smaller than the number of new requests, some of the new requests are confirmed but the inventory level may not exceed the intermediate point; (c) if the inventory level is between the two bounds there are two possibilities: (i) if it is above the intermediate point none of the new requests are confirmed, but (ii) if it is below that point, some of the new requests should be confirmed provided that the new inventory level will not exceed the intermediate point.