A Lagrangian relaxation approach for network inventory control of stochastic revenue management with perishable commodities

Abstract

Airline seat inventory control is the allocation of seats in the same cabin to different fare classes such that the total revenue is maximized. Seat allocation can be modelled as dynamic stochastic programs, which are computationally intractable in network settings. Deterministic and probabilistic mathematical programming models are therefore used to approximate dynamic stochastic programs. The probabilistic model, which is the focus of this paper, has a nonlinear objective function, which makes the solution of large-scale practical instances with off-the-shelf solvers prohibitively time consuming. In this paper, we propose a Lagrangian relaxation (LR) method for solving the probabilistic model by exploring the fact that LR problems are decomposable. We show that the solutions of the LR problems admit a simple analytical expression which can be resolved directly. Both the booking limit policy and the bid-price policy can be implemented using this method. Numerical simulations demonstrate the effectiveness of the proposed method.

Keywords:

• allocation
• transport
• revenue management
• seat inventory control
• mathematical programming
• Lagrangian relaxation

Acknowledgements

I am grateful to Danny Ralph and Stefan Scholtes for their valuable discussions and comments, and to referees for their constructive comments, which have helped to improve the presentation of this paper. I am also thankful to Giovanna Miglionico for pointing out data inconsistency of some test problems in an early version of the paper.