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 and
fare combination for an airline) as sale restrictions and the demand characteristics vary by
product. However, models that consider ...
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 and
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 in dynamic programming formulations (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
our upper bound is tighter than a deterministic linear programming upper bound that appears
in the existing literature. Furthermore, we show that our upper bound is asymptotically tight
in a regime where the leg capacities and the expected demand is scaled linearly with the same
rate. We also describe how the randomized linear program can be used to obtain a bid price control
policy. Computational experiments indicate that our approach is quite fast, able to scale to industrial
problems and can provide significant improvements over standard benchmarks.
+