Title: An approximate dynamic programming approach for network capacity control problem with origin-destination demands

Authors: Feng Liu, Qizong Wu, Yanan Wang, Ying Qu

Addresses: School of Management and Economics, Beijing Institute of Technology, Beijing, 100081, China; Department of Information Management, Central Institute for Correctional Police, Baoding, Hebei, 071000, China. ' School of Management and Economics, Beijing Institute of Technology, Beijing , 100081, China. ' College of Economic and Management, Hebei University of Science and Technology, Shijiazhuang, Hebei, 050018, China. ' College of Economic and Management, Hebei University of Science and Technology, Shijiazhuang, Hebei, 050018, China.

Abstract: Bid-price control is a popular method for controlling the sale of inventory in revenue management. It is well known that the network capacity control problem can be formulated as a dynamic programming model. However, this formulation is intractable in practice due to the enormous size of the state space. As a result, various approximation methods are proposed in the literature. In this paper, we approximate the optimal dynamic programming value function with an affine function of the state vector and develop our model based on stochastic demand between origin-destination (O-D) pairs. We show that the resulting problem is the deterministic linear programming (DLP) for bid-price control. The DLP yields tighter bounds than the classical DLP. We give a column generation procedure for solving the DLP within a desired optimality tolerance, and present numerical results which show the policy perform from our solution approach can outperform that from the classical DLP.

Keywords: revenue management; network capacity control; dynamic programming; bid price control; deterministic linear programming; column generation.

DOI: 10.1504/IJMIC.2011.041308

International Journal of Modelling, Identification and Control, 2011 Vol.13 No.3, pp.195 - 201

Published online: 21 Mar 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article