Imperial College London
Alternate

Professor Kalyan Talluri

Business School

Professor of Analytics and Operations
 
 
 
//

Contact

 

kalyan.talluri Website CV

 
 
//

Location

 

387ABusiness School BuildingSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Kunnumkal:2018:10.1287/trsc.2018.0867,
author = {Kunnumkal, S and Talluri, KT},
doi = {10.1287/trsc.2018.0867},
journal = {Transportation Science},
pages = {1501--1799},
title = {Choice network revenue management based on new tractable approximations},
url = {http://dx.doi.org/10.1287/trsc.2018.0867},
volume = {53},
year = {2018}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - The choice network revenue management model incorporates customer purchase behavioras probability of purchase as a function of the offered products, and is appropriate for air-line and hotel network revenue management, dynamic sales of bundles, and dynamic assort-ment optimization.  The optimization problem is a stochastic dynamic program and is in-tractable. Consequently, a linear programming approximation called choice deterministic linearprogram (CDLP) is usually used to generate controls. Tighter approximations such as affineand piecewise-linear relaxations have been proposed, but it was not known if they can be solvedefficiently even for simple models such as the multinomial logit (MNL) model with a singlesegment. We first show that the affine relaxation (and hence the piecewise-linear relaxation) isNP-hard even for a single-segment MNL choice model. By analyzing the affine relaxation wederive a new linear programming approximation that admits a compact representation, implyingtractability, and prove that its value falls between theCDLPvalueandtheaffinerelaxationvalue. This is the firsttractablerelaxation for the choice network revenue management problemthat is provably tighter thanCDLP. This approximation in turn leads to new policies that,in our numerical experiments, show very good promise: a 2% increase in revenue on averageoverCDLP; and the values typically coming very close to the affine relaxation.  We extendour analysis to obtain other tractable approximations that yield even tighter bounds. We alsogive extensions to the case with multiple customer segments with overlapping consideration setswhere choice by each segment is according to the MNL model.
AU  - Kunnumkal,S
AU  - Talluri,KT
DO  - 10.1287/trsc.2018.0867
EP  - 1799
PY  - 2018///
SN  - 0041-1655
SP  - 1501
TI  - Choice network revenue management based on new tractable approximations
T2  - Transportation Science
UR  - http://dx.doi.org/10.1287/trsc.2018.0867
UR  - http://hdl.handle.net/10044/1/61792
VL  - 53
ER  -
Download