A stochastic approximation algorithm for making pricing decisions in network revenue management problems

In this paper, we develop a stochastic approximation algorithm for making pricing decisions in network revenue management problems. In the setting we consider, the probability of observing a request for an itinerary depends on the price for the itinerary. We are interested in finding a set of prices that maximize the total expected revenue. Our approach is based on visualizing the total expected revenue as a function of the prices and using the stochastic gradients of the total revenue to search for a good set of prices. To compute the stochastic gradients of the total revenue, we use a construction that decouples the prices for the itineraries from the probability distributions of the itinerary requests. This construction ensures that the probability distributions of the underlying random variables do not change when we change the prices for the itineraries. We establish the convergence of our stochastic approximation algorithm. Computational experiments indicate that the prices obtained by our stochastic approximation algorithm perform significantly better than those obtained by standard benchmark strategies, especially when the leg capacities are tight and there are large differences between the price sensitivities of the different market segments. Pricing and capacity allocation constitute two fundamental control mechanisms in network revenu