This Article Full Text (PDF) 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 Google Scholar Articles by Kunnumkal, S. Articles by Topaloglu, H.

Computing Time-Dependent Bid Prices in Network Revenue Management Problems

Indian School of Business, Gachibowli, Hyderabad 500032, India
School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
sumit_kunnumkal{at}isb.edu
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 naturally provides dynamic bid prices that depend on how much time is left until departure. We show that our method provides an upper bound on the optimal total expected revenue and that this upper bound is tighter than the one provided by the widely known deterministic linear programming approach. Furthermore, it is possible to use the bid prices computed by our method as a starting point in a dynamic programming decomposition-like idea to decompose the network revenue management problem by the flight legs and to obtain dynamic and capacity-dependent bid prices. Our computational experiments indicate that the proposed method improves on many standard benchmarks.

Key Words: network revenue management; approximate dynamic programming; Lagrangian relaxation
History: Received: October 2006; revised: July 2009; accepted: July 2009.