Product-Based Approximate Linear Programs for Network Revenue Management

• 成果类型: Article; Early Access
• 署名作者: Zhang, Rui; Samiedaluie, Saied; Zhang, Dan
• 署名单位: University of Colorado System; University of Colorado Boulder; University of Alberta
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2354
• 发表日期: 2022
• 关键词: bid prices; inequalities; relaxations

摘要

The approximate linear programming approach has received significant attention in the network revenue management literature. A popular approximation in the existing literature is separable piecewise linear (SPL) approximation, which estimates the value of each unit of each resource over time. SPL approximation can be used to construct resource-based bid-price policies. In this paper, we propose a product-based SPL approximation. The coefficients of the product-based SPL approximation can be interpreted as each product's revenue contribution to the value of each unit of each resource in a given period. We show that the resulting approximate linear program admits compact reformulations, such as its resource-based counterpart. Furthermore, the new approximation allows us to derive a set of valid inequalities to (i) speed up the computation and (ii) select optimal solutions to construct more effective policies. We conduct an extensive numerical study to illustrate our results. In a set of 192 problem instances, bid-price policies based on the new approximation generate higher expected revenues than resource-based bid-price policies with an average revenue lift of 0.72% and a maximum revenue lift of 5.3%. In addition, the new approximation can be solved 1.42 times faster than the resource-based approximation and shows better numerical stability. The valid inequalities derived from the new approximation further improve the computational performance and are critical for achieving additional gains in the expected revenue. The policy performance is competitive compared with the dynamic programming decomposition method, which is the strongest heuristic known in the literature.