链上镖师 / Chain Biaoshi
IJPE|非平稳随机批量订货：惩罚成本下的图启发式方法
用过滤图最短路和负订单修复，加速(R,S)策略参数计算
这篇论文把惩罚成本下的非平稳随机补货批量问题转成过滤图上的最短路，并用状态空间增广修复负订单，使中长周期(R,S)库存策略计算更可扩展。
- 01：研究对象是单品、单库存点、非平稳随机需求下的(R,S)补货策略，目标是在固定订货成本、持有成本和缺货惩罚成本之间取得期望总成本最小。
- 02：方法从松弛后的状态空间图出发，用支配关系和三角不等式过滤弧，再对最短路中出现的负期望订单做增广修复。
- 03：1620个基准算例显示，SSA在中长周期实例上明显快于cut generation，T=250时平均192秒，CG超过6000秒。
研究背景
库存控制要在需求波动、服务响应和运营成本之间做动态权衡。论文聚焦的批量问题要求决定补货时点和订货量；在随机需求下，如果每期都随需求重新调整，会带来设置导向和数量导向的系统紧张。
Bookbinder和Tan提出的静态-动态不确定性策略，把一类决策放在期初确定，另一类决策留到需求实现后执行。本文研究的(R,S)策略就是期初固定补货时点和订货上限，实际订货量在补货期根据库存补到目标水平。
难点来自惩罚成本版本：服务水平约束下常有可用的解析或线性化工具，惩罚成本下需要为每个候选补货周期求解多期newsvendor问题，候选周期数量又随计划期长度平方级增长。
来源：Fig. 1，Rossi et al. MILP方法得到的近优补货计划，展示基准补货节奏与库存轨迹。
核心问题
论文处理的是单品、单库存位置、非平稳随机需求下的随机批量问题。模型中，期初决策包括是否在周期t设置补货以及对应的订货上限St；需求实现后，订货量Qt把库存补到该上限，期末库存可以为正，也可以表现为缺货。
01目标函数最小化期望总成本，成本项包含固定订货成本、比例订货成本、持有成本和缺货惩罚成本。
02库存守恒约束连接期初库存、订单数量和随机需求，补货期的订单数量由max(St-It-1,0)决定。
03确定性非线性重构引入期望库存、期望正库存和期望负库存，把随机规划转成可计算的结构化模型。
基准实验规模
1620个算例
计划期集合
T=40、100、250
来源：Fig. 3，最短路径松弛得到的运行示例补货计划，用于观察图模型初始解对应的补货时点和库存水平。
方法框架
作者先把松弛后的问题表示为有向无环图：节点代表补货时点和终止节点，弧(i,j)代表从i覆盖到j-1的补货周期，弧成本由对应多期newsvendor模型计算。这样，选择一组补货周期就对应从1到T+1的一条路径。
来源：Fig. 2，松弛问题的图结构表示，粗线为最短路径，弧上标注循环成本。
状态空间过滤在建图时进行。算法利用支配关系和三角不等式剪掉成本较高的候选弧，同时检查是否存在潜在负期望订单；某条长弧即使被短弧组合支配，只要可能在修复不可行状态后成为候选解，就会被保留。
来源：Fig. 4，数值例子的过滤后松弛图结构，粗线为最短路径，体现状态空间过滤后保留的候选弧。
1构造过滤后的状态空间图G，并为每条弧计算补货周期成本和订货上限。
2在G上求从起点到终点的最短路径，把路径映射为(R,S)补货计划。
3检查相邻补货周期之间是否出现St小于前一期期望库存的负订单状态。
4若出现不可行状态，执行状态空间增广，更新图后重新求最短路，直到没有负订单。
案例或实验设置
状态空间增广用于修复最短路计划中的负订单。如果某一周期末的期望库存高于下一周期订货上限，模型会出现期望负订单。算法找到这段受影响的周期序列，新增节点、删除问题弧，并用合并后的成本函数重新连接图结构。
来源：Fig. 7，增广后的松弛图结构，红色弧表示fix_negative_orders移除的弧，展示负订单修复后的图结构变化。
来源：Fig. 5，增广连接矩阵，用矩阵形式呈现新增节点和后续节点之间的连接关系。
计算实验使用Tunc et al. (2018)的Set-A基准，需求服从固定变异系数的正态分布。参数覆盖计划期T∈{40,100,250}、固定订货成本K∈{225,900,2500}、惩罚成本b∈{2,5,10}和变异系数ρ∈{0.1,0.2,0.3}。
来源：Fig. 6，第一次迭代后的补货计划，展示负订单修复后补货节奏和库存轨迹的变化。
结果分析
实验对比对象是Tunc et al. (2018)提出的cut generation方法。两种方法都求解第4节的确定性非线性模型D到最优；差异在于CG依赖紧线性cuts，本文SSA通过图过滤、最短路和状态空间增广来组织搜索。
来源：Table 1，SSA与CG在需求形态、计划期、固定成本、惩罚成本和变异系数下的运行时间对比。
总体结果显示，SSA平均运行时间为84.9秒，中位数36.8秒；CG平均运行时间为2088秒，中位数90.3秒。长周期差异更集中：T=250时，SSA平均192秒、中位数155秒，CG平均6163秒、中位数6171秒。
来源：Fig. 8，SSA与CG的计算时间箱线图对比，直观展示不同计划期下运行时间分布。
来源：Table B.1，SSA平均增广图规模与CG平均cut数量统计，补充解释长周期实验中的计算负担来源。
管理启示
对库存计划人员来说，论文的价值在于把非平稳需求下的(R,S)参数计算做成更可扩展的搜索过程。计划期变长时，直接枚举候选补货周期和求解cut模型会快速变重，过滤图能先压缩候选空间。
✓中长计划期场景更适合优先评估SSA类图算法，尤其是T=100和T=250这类候选补货周期很多的设置。
✓惩罚成本、固定订货成本和需求变异系数变化时，应关注运行时间分布和极慢实例，平均值和中位数需要同时查看。
✓补货策略落地前要检查负订单可行性，算法中的状态空间增广提供了从松弛解修复到可行解的自动化路径。
来源：Fig. 1，MILP基准补货计划，可作为理解补货周期、订货上限和库存轨迹的参照。
论文给出的直接结论是：过滤状态空间加增广修复可以在保持最优性求解目标的同时显著降低搜索负担，长计划期随机库存批量问题由此获得更可操作的计算路径。
论文：A graph-based heuristic for the non-stationary stochastic lot-sizing problem under penalty costs
作者：Xiyuan Ma，Roberto Rossi，Thomas Welsh Archibald
期刊：International Journal of Production Economics
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
