Using Lagrangian Relaxation to Compute Capacity-Dependent Bid Prices in Network Revenue Management
Author:
- 1 June 2009
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 57 (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
This publication has 7 references indexed in Scilit:
- Pricing and Revenue Optimization2020
- Relaxations of Weakly Coupled Stochastic Dynamic ProgramsOperations Research, 2008
- Dynamic Bid Prices in Revenue ManagementOperations Research, 2007
- The Theory and Practice of Revenue Management2004
- Revenue Management in a Dynamic Network EnvironmentTransportation Science, 2003
- A Randomized Linear Programming Method for Computing Network Bid PricesTransportation Science, 1999
- An Analysis of Bid-Price Controls for Network Revenue ManagementManagement Science, 1998