This Article Full Text (PDF) e-companion References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Topaloglu, H. Search for Related Content

Using Lagrangian Relaxation to Compute Capacity-Dependent Bid Prices in Network Revenue Management

School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
topaloglu{at}orie.cornell.edu

We propose a new method to compute bid prices in network revenue management problems. The novel aspect of our method is that it explicitly considers the temporal dynamics of the arrivals of the itinerary requests and generates bid prices that depend on the remaining leg capacities. Our method is based on relaxing certain constraints that link the decisions for different flight legs by associating Lagrange multipliers with them. In this case, the network revenue management problem decomposes by the flight legs, and we can concentrate on one flight leg at a time. When compared with the so-called deterministic linear program, we show that our method provides a tighter upper bound on the optimal objective value of the network revenue management problem. Computational experiments indicate that the bid prices obtained by our method perform significantly better than the ones obtained by standard benchmark methods.

Subject classifications: dynamic programming/optimal control; applications; probability; stochastic model applications.
History: Received April 2006; revision received November 2007; accepted April 2008.

This article has been cited by other articles:

				M. Akan and B. Ata Bid-Price Controls for Network Revenue Management: Martingale Characterization of Optimal Bid Prices Mathematics of Operations Research, November 1, 2009; 34(4): 912 - 936. [Abstract] [PDF]