This Article Full Text (PDF) References 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 Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Liu, Q. Articles by van Ryzin, G. Search for Related Content

On the Choice-Based Linear Programming Model for Network Revenue Management

Industrial Engineering and Logistics Management Department, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong
Graduate School of Business, Columbia University, New York, New York 10027
qianliu{at}ust.hk
gjv1{at}columbia.edu

Gallego et al. [Gallego, G., G. Iyengar, R. Phillips, A. Dubey. 2004. Managing flexible products on a network. CORC Technical Report TR-2004-01, Department of Industrial Engineering and Operations Research, Columbia University, New York.] recently proposed a choice-based deterministic linear programming model (CDLP) for network revenue management (RM) that parallels the widely used deterministic linear programming (DLP) model. While they focused on analyzing "flexible products"—a situation in which the provider has the flexibility of using a collection of products (e.g., different flight times and/or itineraries) to serve the same market demand (e.g., an origin-destination connection)—their approach has broader implications for understanding choice-based RM on a network. In this paper, we explore the implications in detail. Specifically, we characterize optimal offer sets (sets of available network products) by extending to the network case a notion of "efficiency" developed by Talluri and van Ryzin [Talluri, K. T., G. J. van Ryzin. 2004. Revenue management under a general discrete choice model of consumer behavior. Management Sci. 50 15–33.] for the single-leg, choice-based RM problem. We show that, asymptotically, as demand and capacity are scaled up, only these efficient sets are used in an optimal policy. This analysis suggests that efficiency is a potentially useful approach for identifying "good" offer sets on networks, as it is in the case of single-leg problems. Second, we propose a practical decomposition heuristic for converting the static CDLP solution into a dynamic control policy. The heuristic is quite similar to the familiar displacement-adjusted virtual nesting (DAVN) approximation used in traditional network RM, and it significantly improves on the performance of the static LP solution. We illustrate the heuristic on several numerical examples.

Key Words: network revenue management; choice behavior; multinomial logit choice model; dynamic programming; linear programming
History: Received: October 21, 2004; accepted: February 16, 2007.

This article has been cited by other articles:

				D. Zhang and D. Adelman An Approximate Dynamic Programming Approach to Network Revenue Management with Customer Choice Transportation Science, August 1, 2009; 43(3): 381 - 394. [Abstract] [PDF]

				J. J. M. Bront, I. Mendez-Diaz, and G. Vulcano A Column Generation Algorithm for Choice-Based Network Revenue Management Operations Research, May 1, 2009; 57(3): 769 - 784. [Abstract] [PDF]