Choice Network Revenue Management Based on New Tractable Approximations

Sumit Kunnumkal () and Kalyan Talluri ()
Additional contact information
Sumit Kunnumkal: Indian School of Business, Gachibowli, Hyderabad 500032, India
Kalyan Talluri: Imperial College Business School, South Kensington Campus, SW7 2AZ London, United Kingdom

Transportation Science, 2019, vol. 53, issue 6, 1591-1608

Abstract: The choice network revenue management model incorporates customer purchase behavior as probability of purchase as a function of the offered products and is appropriate for airline and hotel network revenue management, dynamic sales of bundles, and dynamic assortment optimization. The optimization problem is a stochastic dynamic program and is intractable. Consequently, a linear programming approximation called choice deterministic linear program ( CDLP ) is usually used to generate controls. Tighter approximations, such as affine and piecewise-linear relaxations, have been proposed, but it was not known if they can be solved efficiently even for simple models, such as the multinomial logit (MNL) model with a single segment. We first show that the affine relaxation (and, hence, the piecewise-linear relaxation) is NP-hard even for a single-segment MNL choice model. By analyzing the affine relaxation, we derive a new linear programming approximation that admits a compact representation, implying tractability, and prove that its value falls between the CDLP value and the affine relaxation value. This is the first tractable relaxation for the choice network revenue management problem that is provably tighter than CDLP . This approximation, in turn, leads to new policies that, in our numerical experiments, show very good promise: a 2% increase in revenue on average over CDLP and the values typically coming very close to the affine relaxation. We extend our analysis to obtain other tractable approximations that yield even tighter bounds. We also give extensions to the case with multiple customer segments with overlapping consideration sets in which choice by each segment is according to the MNL model.

Keywords: revenue management; airline operations research (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0867 (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:ortrsc:v:53:y:2019:i:6:p:1591-1608

Access Statistics for this article

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