Simulation-Based Optimization of Virtual Nesting Controls for Network Revenue Management

Virtual nesting is a popular capacity control strategy in network revenue management. In virtual nesting, products (itinerary–fare–class combinations) are mapped (‘indexed’) into a relatively small number of ‘virtual classes’ on each resource (flight leg) of the network. Nested protection levels are then used to control the availability of these virtual classes; specifically, a product request is accepted if and only if its corresponding virtual class is available on each resource required. Bertsimas and de Boer proposed an innovative simulation–based optimization method for computing protection levels in a virtual nesting control scheme (2005). In contrast to traditional heuristic methods, this simulation approach captures the true network revenues generated by virtual nesting controls. However, because it is based on a discrete model of capacity and demand, the method has both computational and theoretical limitations. In particular, it uses first–difference estimates, which are computationally complex to calculate exactly. These gradient estimates are then used in a steepest–ascent–type algorithm, which, for discrete problems, has no guarantee of convergence.