In this paper, we propose a new dynamic programming decomposition method for the network revenue management problem with customer choice behavior. Similar to the traditional dynamic programming decomposition method in the literature, our approach allocates the revenue associated with an itinerary among the different flight legs and solves a single leg revenue management problem for each flight leg in the airline network. However, the novel aspect of our approach is that while the traditional dynamic programming decomposition method chooses the revenue allocations by using a deterministic linear program, our approach chooses the revenue allocations by solving an
auxiliary optimization problem that incorporates the probabilistic nature of the customer choices.
We show that our approach provides an upper bound on the optimal total expected revenue and this upper bound is tighter than the ones obtained by two standard benchmark methods. Computational experiments indicate that our approach provides significant improvements on the performances of the benchmark methods.