Abstract

In this paper we study optimal strategies for renting hotel rooms when there is a stochastic and dynamic arrival of customers from different market segments. We formulate the problem as a stochastic and dynamic programming model and characterize the optimal policies as functions of the capacity and the time left until the end of the planning horizon. We consider three features that enrich the problem: we make no assumptions concerning the particular order between the arrivals of different classes of customers; we allow for multiple types of rooms and downgrading; and we consider requests for multiple nights. We also consider implementations of the optimal policy. The properties we derive for the optimal solution significantly reduce the computational effort needed to solve the problem, yet in the multiple product and/or multiple night case this is often not enough. Therefore, heuristics, based on the properties of the optimal solutions, are developed to find ''good'' solutions for the general problem. We also derive upper bounds which are useful when evaluating the performance of the heuristics. Computational experiments show a satisfactory performance of the heuristics in a variety of scenarios using real data from a medium size hotel.