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

We consider a network revenue management problem where customers choose among open fare products according to some pre-specified 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 proposed by Gallego et al. (2004) and van Ryzin and Liu (2004). We develop a column generation algorithm to solve the problem for a multinomial logit choice model with disjoint consideration sets. We also provide new results on the well-known decomposition heuristic. Our numerical study shows the policies from our solution approach can significantly outperform heuristics from the choice-based linear program.

Download Publication