New Formulations for Choice Network Revenue Management
New Formulations for Choice Network Revenue Management
复制标题
Choice Network 收益管理的新配方
DOI：
--
复制
发表时间：
2014
影响因子：
2.1
通讯作者：
K. Talluri
中科院分区：
文献类型：
--
作者：
K. Talluri
模型结合更现实的客户行为模型，客户从一个报价集选择，最近已经成为流行的品种优化和收益管理。这些模型的动态规划是难以处理的，并且由称为选择确定性线性规划（CDLP）的确定性线性规划近似，其具有指数数量的列。列生成已被提出，但找到一个进入列是NP难的段考虑集重叠时。在本文中，我们提出了一种新的方法称为基于段的确定性凹规划（SDCP）的基础上段和他们的考虑集。SDCP是CDLP的松弛，因此在动态程序上形成较宽松的上界，但在非重叠段的情况下与CDLP一致。如果一个细分市场的考虑集合中的元素数量不是很大，SDCP可以应用于任何消费者行为的离散选择模型。我们收紧SDCP约束（i）模拟，称为随机凹规划方法，（ii）通过增加削减到最近的紧凑制定（SBLP）的问题的潜在的多项选择模型（MNL）的需求。后一种方法被证明是非常有效的，基本上获得CDLP值，即使是重叠的片段。通过制定一个分离问题的问题，我们深入了解为什么CDLP是很容易的MNL与非重叠的考虑集，为什么MNL的推广造成的困难。数值结果表明：（a）随机线性规划方法在较老的独立类模型下得到了线性规划上界的显着收紧，但对选择情形的影响相对较小;（B）对于MNL选择模型，我们在这里给出的用于重叠段的SBLP+公式非常快，并且潜在地可扩展到工业规模的问题。
Models incorporating more realistic models of customer behavior, as customers choosing from an offer set, have recently become popular in assortment optimization and revenue management. The dynamic program for these models is intractable and approximated by a deterministic linear program called the choice deterministic linear program (CDLP), which has an exponential number of columns. Column generation has been proposed but finding an entering column is NP-hard when segment consideration sets overlap. In this paper we propose a new approach called segment-based deterministic concave program (SDCP) based on segments and their consideration sets. SDCP is a relaxation of CDLP and hence forms a looser upper bound on the dynamic program, but coincides with CDLP for the case of nonoverlapping segments. If the number of elements in a consideration set for a segment is not very large, SDCP can be applied to any discrete-choice model of consumer behavior. We tighten the SDCP bound by (i) simulations, called the randomized concave programming method, and (ii) by adding cuts to a recent compact formulation (SBLP) of the problem for a latent multinomial-choice model (MNL) of demand. This latter approach turns out to be very effective, essentially obtaining CDLP value, even for overlapping segments. By formulating the problem as a separation problem, we give insight into why CDLP is easy for the MNL with nonoverlapping consideration sets and why generalizations of MNL pose difficulties. Numerical conclusions that we derive from the present paper are the following: (a) The randomized linear programming approach that obtains significant tightening of the linear program upper bound under an older independent-class model seems to have relatively little effect for the choice case; (b) for the MNL choice model, the SBLP+ formulation we give here for overlapping segments is very fast and is potentially scalable to industrial-size problems.