Technical Note—Product-Based Approximate Linear Programs for Network Revenue Management

Rui Zhang (), Saied Samiedaluie () and Dan Zhang ()
Additional contact information
Rui Zhang: Leeds School of Business, University of Colorado, Boulder, Colorado 80309
Saied Samiedaluie: Alberta School of Business, University of Alberta, Edmonton, Alberta T6G 2R6, Canada
Dan Zhang: Leeds School of Business, University of Colorado, Boulder, Colorado 80309

Operations Research, 2022, vol. 70, issue 5, 2837-2850

Abstract: 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.

Keywords: Revenue Management and Market Analytics; approximate dynamic programming; optimal control; transportation; yield management (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2354 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:5:p:2837-2850

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().