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.