Correspondence: Huseyin Topaloglu, School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853, USA. E-mail: topaloglu@orie.cornell.edu

¹is a PhD candidate in the School of Operations Research and Information Engineering at Cornell University. He is minoring in applied economics, mathematical programming and manufacturing systems in the same programme. His current research interests include network revenue management and pricing problems with particular emphasis on overbooking and cancellations.

²is an associate professor in the School of Operations Research and Information Engineering at Cornell University. He holds a BSc in Industrial Engineering from Bogazici University in Turkey, and a PhD in Operations Research and Financial Engineering from Princeton University. His current research interests include stochastic programming, stochastic approximation and approximate dynamic programming with applications in pricing, revenue management, logistics and supply chain management. He teaches courses on dynamic programming, revenue management, simulation modelling and systems engineering.

Received 20 October 2008; Revised 20 October 2008; Published online 28 November 2008.

Abstract

We develop a network revenue management model to jointly make capacity control and overbooking decisions. Our approach is based on the observation that if the penalty cost of denying boarding to the reservations at the departure time were given by a separable function, then the dynamic programming formulation of the network revenue management problem would decompose by the itineraries and it could be solved by focusing on one itinerary at a time. Motivated by this observation, we use an iterative and simulation-based method to build separable approximations to the penalty cost that we incur at the departure time. Computational experiments compare our model with two benchmark strategies that are based on a deterministic linear programming formulation. The profits obtained by our model improve over those obtained by the benchmark strategies by about 3 per cent on the average, which is a significant figure in the network revenue management setting. For the test problems with tight leg capacities, the profit improvements can be as high as 13 per cent.