Network Revenue Management with Product-Specific No-Shows

Abstract

Revenue management practices often include overbooking capacity to account for customers who make reservations but do not show up. In this paper, we consider the network revenue management problem with no-shows and overbooking, where the show-up probabilities are specific to each product. No-show rates differ significantly by product (for instance each itinerary/fare combination for an airline) as sale restrictions and the demand characteristics vary by product. However, models that consider no-show rates by each individual product are difficult to handle as the state-space (or the variable space in approximations) increases significantly. In this paper we propose a randomized linear program to jointly make the capacity control and overbooking decisions with product-specific no-shows. We establish that our formulation gives an upper bound on the optimal expected total profit and that this upper bound is tighter than a deterministic linear programming bound that appears in the existing literature. We describe how the randomized linear program can be used to obtain a bid price control policy. Numerical experiments indicate that our approach is fast, able to scale to industrial-size problems, and can provide significant improvements over standard benchmark methods.