An Improved Dynamic Programming Decomposition Approach for Network Revenue Management

• 成果类型: Article
• 署名作者: Zhang, Dan
• 署名单位: McGill University
• 刊物名称: M&SOM-MANUFACTURING & SERVICE OPERATIONS MANAGEMENT
• ISSN/ISSBN: 1523-4614
• DOI: 10.1287/msom.1100.0302
• 发表日期: 2011
• 页码: 35-52
• 关键词: Network Revenue Management; choice behavior; multinomial logit choice model; dynamic programming

摘要

We consider a nonlinear nonseparable functional approximation to the value function of a dynamic programming formulation for the network revenue management (RM) problem with customer choice. We propose a simultaneous dynamic programming approach to solve the resulting problem, which is a nonlinear optimization problem with nonlinear constraints. We show that our approximation leads to a tighter upper bound on optimal expected revenue than some known bounds in the literature. Our approach can be viewed as a variant of the classical dynamic programming decomposition widely used in the research and practice of network RM. The computational cost of this new decomposition approach is only slightly higher than the classical version. A numerical study shows that heuristic control policies from the decomposition consistently outperform policies from the classical decomposition.