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 Google Scholar Articles by Zhang, D. Articles by Adelman, D.

An Approximate Dynamic Programming Approach to Network Revenue Management with Customer Choice

Desautels Faculty of Management, McGill University, Montreal, Quebec H3A 1G5, Canada
Graduate School of Business, University of Chicago, Chicago, Illinois 60637
dan.zhang{at}mcgill.ca
dan.adelman{at}chicagogsb.edu

We consider a network revenue management problem where customers choose among open fare products according to some prespecified choice model. Starting with a Markov decision process (MDP) formulation, we approximate the value function with an affine function of the state vector. We show that the resulting problem provides a tighter bound for the MDP value than the choice-based linear program. We develop a column generation algorithm to solve the problem for a multinomial logit choice model with disjoint consideration sets (MNLD). We also derive a bound as a by-product of a decomposition heuristic. Our numerical study shows the policies from our solution approach can significantly outperform heuristics from the choice-based linear program.

Key Words: network revenue management; choice behavior; dynamic programming
History: Received: August 2006; revised: June 2008; accepted: December 2008.