Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models
Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models
复制标题
容量随机库存控制模型的基于抽样的近似方案
DOI：
--
复制
发表时间：
2015
影响因子：
1.7
通讯作者：
D. Simchi
中科院分区：
文献类型：
--
作者：
Wang Chi Cheung;D. Simchi
研究了数据驱动环境下的经典多周期容量约束随机库存控制问题。我们不假设完全了解需求分布，而是假设只能通过抽取随机样本来访问需求分布。这种数据驱动的模型在实践中无处不在，其中潜在随机需求的累积分布函数要么不可用，要么太复杂而无法使用。我们认为样本平均近似（SAA）的方法的问题，并建立一个上限的SAA方法，以实现一个接近最优的预期成本所需的样本数量，在任何水平的所需的精度和预先指定的置信概率。样本界在时间段的数量以及置信度和准确度参数方面是多项式的。此外，边界是独立的基本需求分布。然而，SAA需要解决SAA问题，这是#P-hard。因此，出于SAA分析，我们提出了一个多项式时间近似方案，也使用多项式多个样本。最后，我们建立了一个下界的样本数量需要解决这个数据驱动的报童问题，以接近最优。
We study the classical multiperiod capacitated stochastic inventory control problems in a data-driven setting. Instead of assuming full knowledge of the demand distributions, we assume that the demand distributions can only be accessed through drawing random samples. Such data-driven models are ubiquitous in practice, where the cumulative distribution functions of the underlying random demand are either unavailable or too complex to work with. We consider the sample average approximation (SAA) method for the problem and establish an upper bound on the number of samples needed for the SAA method to achieve a near-optimal expected cost, under any level of required accuracy and prespecified confidence probability. The sample bound is polynomial in the number of time periods as well as the confidence and accuracy parameters. Moreover, the bound is independent of the underlying demand distributions. However, the SAA requires solving the SAA problem, which is #P-hard. Thus, motivated by the SAA analysis, we propose a polynomial time approximation scheme that also uses polynomially many samples. Finally, we establish a lower bound on the number of samples required to solve this data-driven newsvendor problem to near-optimality.