Greedy-Like Algorithms for Dynamic Assortment Planning Under Multinomial Logit Preferences
Greedy-Like Algorithms for Dynamic Assortment Planning Under Multinomial Logit Preferences
复制标题
多项Logit偏好下动态分类规划的类贪婪算法
作者：
Ali Aouad;R. Levi;D. Segev
研究了由多项Logit(MNL)选择模型描述的联合选货计划与库存管理问题，其中缺货事件引起动态替代效应。在最近的文献中，已经广泛地研究了这种设置的特殊情况，特别是静态分类规划问题。然而，在这项工作之前，一般的公式并不允许有分析性能保证的高效算法，而且它的大部分计算方面仍然是开放的。本文设计了MNL模型下的第一个可证明良好的动态分类计划的近似算法，获得了对广泛的需求分布的恒定因子保证，并且满足不断增加的失败率特性。我们的算法依赖于贪婪过程的组合，其中库存决策仅限于特定类别的产品，目标函数采用修改的形式。我们证明，我们的方法在性能和速度方面远远优于最先进的启发式方法，导致在合成实例上的收入增加6%到10%。在建立我们的主要结果的过程中，我们开发了可能独立感兴趣的新算法想法。这些概念包括子模和单调性的较弱概念，尽管使用了目标函数的噪声估计，但这些概念被证明足以获得恒定因子的最坏情况保证。
We study the joint assortment planning and inventory management problem, where stock-out events elicit dynamic substitution effects, described by the Multinomial Logit (MNL) choice model. Special cases of this setting have extensively been studied in recent literature, notably the static assortment planning problem. Nevertheless, the general formulation is not known to admit efficient algorithms with analytical performance guarantees prior to this work, and most of its computational aspects are still wide open.In this paper, we devise the first provably-good approximation algorithm for dynamic assortment planning under the MNL model, attaining a constant-factor guarantee for a broad class of demand distributions, that satisfy the increasing failure rate property. Our algorithm relies on a combination of greedy procedures, where stocking decisions are restricted to specific classes of products, and the objective function takes modified forms. We demonstrate that our approach substantially outperforms state-of-the-art heuristic methods in terms of performance and speed, leading to a revenue gain of 6% to 10% on synthetic instances. In the course of establishing our main result, we develop new algorithmic ideas that may be of independent interest. These include weaker notions of submodularity and monotonicity, shown sufficient to obtain constant-factor worst-case guarantees, despite using noisy estimates of the objective function.