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

Huseyin Topaloglu ()
Additional contact information
Huseyin Topaloglu: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853

Operations Research, 2009, vol. 57, issue 3, 637-649

Abstract: 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.

Keywords: dynamic programming/optimal control; applications; probability; stochastic model applications (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (48)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1080.0597 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:57:y:2009:i:3:p:637-649

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().