Abstract
This paper considers an overbooking problem with multiple reservation and inventory classes, in which the multiple inventory classes may be used as substitutes to satisfy the demand of a given reservation class (perhaps at a cost). The problem is to jointly determine overbooking levels for the reservation classes, taking into account the substitution options. Such problems arise in a variety of revenue management contexts, including multicabin aircraft, back-to-back scheduled flights on the same leg, hotels with multiple room types, and mixed-vehicle car rental fleets. We model this problem as a two-period optimization problem. In the first period, reservations are accepted given only probabilistic knowledge of cancellations. In the second period, cancellations are realized and surviving customers are assigned to the various inventory classes to maximize the net benefit of assignments (e.g., minimize penalties). For this formulation, we show that the expected revenue function is submodular in the overbooking levels, which implies the natural property that the optimal overbooking level in one reservation class decreases with the number of reservations held in the other reservation classes. We then propose a stochastic gradient algorithm to find the joint optimal overbooking levels. We compare the decisions of the model to those produced by more naive heuristics on some examples motivated by airline applications. The results show that accounting for substitution when setting overbooking levels has a small, but still significant, impact on revenues and costs.