文章链接：http://dx.doi.org/10.1287/opre.2015.1422
1
研究背景
报童问题是一个经典的库存控制问题，但是往往实际的需求分布无从得知，只能根据一些历史数据来估计分布信息，由此本文探讨了SAA（Sample Average Approximation）方法在数据驱动的报童问题的应用。同时，SAA方法往往对样本数量有一定的要求，样本数量越多，估计的SAA解与实际分布的最优解更接近，相对后悔值（relative regret）更小。
2
模型介绍
对于一个传统的报童问题，需求分布给定，管理者在需求不确定的情况下进行库存决策以最小化库存持有成本（h）和缺货成本（b）。其目标是最小化期望成本，可以表述为：
令F表示D的累积分布函数。由于成本函数是凸函数，知道需求分布的全知情况下的最优数量为：
给定独立同分布的样本，管理者学习需求分布，通过大数定律确定最佳数量。然而在收集到足够的信息前，任何订购策略都会付出代价，这可能会导致随着时间的推移而累积大量的成本。如何根据样本进行订货以最小化一段时间的总期望成本？一个常用的方法是SAA：
给定N个独立样本，{D1,D2,...,D_N}是随机独立样本，{d1,d2,...,d_N}是特定的实现值。
SAA的目标最小化经验需求分布下的期望成本：
经验CDF（Cumulative Distribution Function）表述为：
求得SAA最优解为随机样本的b/(b+h)分位数：
定义相对后悔值（Relative Regret）：
3
算法分析
首先根据分布生成随机样本，样本数量为count，从小到达依次统计其中小于等于q的数量num，若num/count大于等于rho（报童分位数），则这个q就是根据这count个样本得到的SAA最优解。
根据真实分布求此报童问题的最优解，记为q*，计算(C(q)-C(q*))/C(q*)，得出relative regret。
4
算法复现
首先展示1000次实验的SAA解的生成过程。拿N=200，rho=0.6，分布为exponential distribution举例，输出SAA解的直方图。
结果展示如下：
计算样本数量分别为25, 50, 100, 200；报童分位数rho分别为0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.95, 0.99；在真实分布分别为uniform, normal, exponential分布下的relative regret，并输出结果。以下拿exponential distribution举例。
输出的结果为：
同样地，均匀分布的结果为：
正态分布的结果为：
可以看到，随着样本数量的上升，SAA解的error越低（relative regret越低），但同时，算法运行时间也会增加。下图为exponential分布下，不同的sample size的算法运行时间。
// 扫码获取本文算法代码
识别二维码关注我们
文章推荐人 | 付严亮
校对 | 王子川
排版| 付严亮
