文章链接：https://doi.org/10.1287/moor.2018.0940
研究背景
在以往的有关库存模型的研究中，通常假定决策者（DM）知道需求分布的累积分布函数（cdf）。在这种假设下，问题易于研究且能在多项式时间内求解。而在现实情况中，此类库存决策问题往往是数据驱动的，即DM对需求分布的了解往往是通过历史数据或对未来需求趋势的市场预测获得的。此外，即使管理者能够获得真实的需求分布，有时也会因为过于复杂而难以处理。本文研究了数据驱动情况下的随机库存控制问题。
研究问题
考虑数据驱动环境下的多期有容随机库存控制问题，假设只能通过随机抽样来获取需求分布，用样本均值近似（SAA）方法来解决这个问题，并确定了在任何精度和预设置信水平下，SAA方法实现接近最优预期成本所需的样本数量上界。样本上界与时间段数以及置信度和精度参数成多项式关系，且该边界与需求分布无关。然而，SAA方法需解决的问题是NP-hard，因此，本文提出了一种多项式时间近似方案(PTAS, polynomial time approximation scheme)——Sample算法，该方案使用了多项式数量的样本。此外，本文建立了解决数据驱动的报童问题所需的样本数量下界，使其接近最优。
文章模型
假定提前期和订购成本为零。
1、数据驱动的有容库存控制模型
考虑数据驱动的有容库存控制问题，DM面对T个离散时间周期的有限时间范围，记为1,…,T。从第1期到第T期，DM①观测开始时的库存水平xt；②订货到yt，其中（参数Bt为t期的可订库存容量）；③观测t期需求Dt；④若
，将导致一个线性的持有成本
；若
，将导致一个线性缺货成本
；⑤在第t+1期时，
。
潜在的需求分布是独立的，且不一定是同分布的。DM的目标是最小化期望总运营成本（
有界）：
用表示原有容库存控制问题对应的样本均值近似问题。每期从Dt中抽取Nt个样本，SAA问题中t期的需求分布是的经验分布：
2、修正的基本库存策略
修正的基本库存策略（MBS策略）如下：
上述式子中，库存水平yt尽量靠近Rt。
最优策略可以通过求解如下的方程得到：
表示第t期的期望运营成本。为了方便后续对SAA算法的分析，引入：
因此，有，第t期开始时的库存水平表示为xt。DM从t到T期采取最优订购策略的期望运营成本。成本转移函数Ut(yt)表示在第t期订购完的库存水平为yt，且DM 在t+1到T期采取最优订货策略的期望运营成本。
用逆向归纳法得到最优策略为：
对于SAA问题，选择所有经验成本中的最小值，其最优策略表述为：
其中的需求为真实需求分布的Nt个样本的经验分布。
3、主要结果
首先，本文证明SAA要产生近乎最优的修正基本库存策略，只需使用多项式数量的样本即可。
定理1. 对于SAA问题，定义如下所示的每期样本数，则至少有的概率，MBS策略对原问题是（1+ε）优的（即MBS下的期望总运营成本是最优期望成本的1+ε倍）。
定理2. 对每个ε>0，0<δ<1，有一种算法能以1-δ的概率产生一组（1+ε）优的基本库存。所需的样本数量是关于
的多项式；此外，算法的运行时间是关于
的多项式。
数据驱动的报童问题是一个特殊的数据驱动的有容库存控制问题，该问题是单期的且没有供应约束。下面提出了解决数据驱动的报童问题使其接近最优所需的样本数量下界：
定理3.对一个在任何潜在分布下能以1-δ的概率使数据驱动的报童问题达到（1+ε）优的基本库存的算法，其所需的样本数至少为（0<ε<1/20, 0<δ<1/4）：
4、通过稀疏化实现的多项式时间近似方案
SAA问题的动态规划（即经验DP）与原问题的动态规划（即原DP）中的成本转移函数的右导数之间的接近性意味着定理1，因此定理1的证明可以简化为一阶分析。
由于SAA算法较难求解，本文提出了一种多项式时间近似方案（PTAS），得到一组原问题的近优修正基本库存策略，该方案基于SAA算法并引入稀疏化程序。
其中，1~2行构建经验需求分布；4~9行构造右导数函数，其均匀近似于原问题的右导数函数；第8行的稀疏化是PTAS与SAA算法的区别所在。
可以证明对于如下给定的样本大小Nt和η，Sample算法有至少1-δ的概率得到（1+2ε）优的基本库存解集。
仿真结果
考虑三组五个时间周期的有容库存控制问题，运用Sample算法，分别给定三种不同的需求分布，在不同的缺货成本b下得到仿真结果如表1所示。
通过仿真结果可以发现理论相对比例较为保守，其可能的原因有：文章在推导过程中对某些条件和界限的放松；没有假设需求分布属于某一参数族，甚至没有假设需求分布具有有界支撑，导致理论性只能有一个比较保守的界限。
识别二维码关注我们
文章推荐人 | 付严亮
笔记审核人 | 杨瑞瑞
校对 | 罗陈斌
排版 | 史珑琳
