A stochastic approximation method to compute bid prices in network revenue management problems

We present a stochastic approximation method to compute bid prices in network revenue management problems. The key idea is to visualize the total expected revenue as a function of the bid prices and to use sample path-based derivatives to search for a good set of bid prices. We deal with the discrete nature of the network revenue management setting by formulating a smoothed version of the problem, which assumes that it is possible to accept a fraction of an itinerary request. We show that the iterates of our method converge to a stationary point of the total expected revenue function of the smoothed version. Computational experiments demonstrate that the bid prices obtained by our method outperform the ones obtained by standard benchmark methods and our method is especially advantageous when the bid prices are not recomputed frequently. The notion of bid prices forms a powerful tool to construct good policies for network revenue management problems. The idea is to associate a bid price with each flight leg that captures the opportunity cost of a unit of capacity. An itinerary request is accepted if and only if there is enough capacity and the revenue from the itinerary request exceeds the sum of the bid prices associated with the flight legs in the requested itinerary; see Williamson (1992) and Talluri and van Ryzin (2004)