多产品报童问题的直接搜索算法求解

郝 爽 张大力 董 明

(上海交通大学 安泰经济与管理学院,上海 200030)

0 引言

报童问题是经典的随机库存管理模型,其基本假设为产品需求为分布已知的随机变量,当订货量过剩时,未售出的商品具有一定的残值,当订货量不足时,未满足的需求将产生惩罚成本,零售商需事先决定产品的订货量以最大化期望收益。

报童问题假设产品需求为分布已知的随机变量,在实践中难以直接运用,解决方法主要有三类:一是利用历史数据对需求的分布类型、未知参数进行估计,或以经验分布对需求的累积分布进行近似,此类方法的求解效果依赖于估计量的质量,在小样本情况下求解质量较差;二是各类数据驱动方法的应用,即利用机器学习或人工智能算法对需求进行预测,或对预测模型及库存决策进行联合优化,由于训练预测模型需要使用大量历史数据,以及与需求相关的其他类型数据,所以此类方法对于数据的质量及规模具有更高的要求,实际应用的难度更大;三是鲁棒优化方法,即利用历史数据的统计特征构建满足条件的分布集合,并最大化最差情况的期望收益,但所得的解往往过于保守,实际应用价值不高。

实践中零售商通常同时销售多种产品且面临某种资源约束,例如采购成本不能超过预算或库存容量不能超过最大库容,因此多产品报童问题的应用更为广泛。多产品报童问题可分解为报童问题,并分别计算各产品的最优订货量,若能够满足资源约束则求得最优,否则可通过拉格朗日乘子法求解,但高效准确求解拉格朗日乘子较为困难。文献[5]、[6]分别求解了产品需求服从特定类型分布且参数已知时的多产品报童问题,文献[7]设计了多种启发式方法求解多产品报童问题,其中部分方法仅使用需求量的均值和方差,因而简单易用,数值实验表明在不假设需求量分布已知的前提下,文献[7]的启发式算法可求得较好的近似解。

有别于上述研究,本文假设零售商仅有各商品需求量的少量历史数据且商品需求量的分布未知,将零售商的收益视作随机黑箱函数,利用直接搜索算法进行求解。在直接搜索算法的每轮迭代中,通过控制样本的数量,利用有限的历史数据构造期望收益的样本均值近似。本文提出的方法无须假设商品需求分布已知,数值实验表明在历史数据有限的情况下本方法仍然可以求得高质量的近似解。

1 模型

1.1 具有资源约束的多产品报童问题

具有资源约束的多产品报童问题描述如下:零售商同时销售n种产品,产品间不存在需求的替代及互补效应;零售商在销售期前决定各种产品的订货量Qi,i=1,…,n;对于产品i,其需求量xi为随机变量,具有概率密度函数fi(·);产品i的采购成本、销售价格、未售出残值及缺货惩罚分别为vi、pi、gi、Bi;零售商具有某种资源约束,其资源总量为S,单位产品i的资源消耗量为si。产品i的收益函数为:

(1)

产品i的期望收益为:

(2)

具有资源约束的多产品报童问题优化模型为:

(3)

2.2 随机黑箱多产品报童问题

minG(Q1,…,Qn)=E[g(Q1,…,Qn,x1,…,xn)]

(4)

将多产品报童问题视作随机黑箱问题为建模及实际应用提供了诸多便利。首先,随机黑箱问题假设随机参数的分布未知,避免了由参数估计造成的解的质量下降;其次随机黑箱问题不要求目标函数具有明确的表达式,对于替代性需求、需求依赖价格、存在其他随机参数等不同类型的报童问题同样适用,扩展了模型的应用范围。

2 具有可变样本量的直接搜索算法

由于黑箱函数的表达式未知,无法利用各类基于梯度的优化方法求解,所以其求解主要通过各类无梯度优化方法,包括随机近似、响应面法、信赖域法及各类直接搜索算法,例如单纯形搜索、广义模式搜索、网格自适应搜索,其中直接搜索算法由于易于实现、鲁棒性强,得到了广泛应用。

(5)

其中,Q={Q1,…,Qn}。Levi等研究得出了达到给定近似精度所需的样本数量,但实际问题中的样本数量往往较少,难以满足精度要求。本文依据Hao等提出的直接搜索算法框架,针对问题(4)设计了具有可变样本数量的直接搜索算法,步骤如下:

算法1 具有可变样本数量的直接搜索算法

[0] 初始化

循环:在第k(k=0,1,…)次迭代中,执行以下步骤:

[1] 基于方向的搜索

3.否则记k轮迭代搜索失败,保持当前解不变,缩小搜索步长Δk+1=θΔk,θ<1。

[2] 判断终止条件

如果Δk+1<Δtol,停止循环。

[3] 更新样本

1.如果搜索成功,保持样本不变,返回步骤[1]。

2.否则,令k+1轮的样本数量为

(6)

3 算例分析

本章通过数值实验证明在产品需求分布未知且产品需求量历史数据有限的条件下,算法1可有效求解具有资源约束的多产品报童问题,且结果优于文献[7]提出的启发式算法。

(7)

(8)

(9)

其中:H1基于产品成本结构、需求分布均相同的假设;H2基于产品需求均服从均匀分布的假设,产品的成本结构可以不同;H3在H1的基础上进一步考虑了产品成本结构的差异;不满足其假设时,H1、H2、H3所得结果均为近似解,但具有运算简单、无须已知需求分布的优点。在实际运用中,需求量的均值、标准差可利用历史需求进行估计,无约束最优订货量可通过历史需求的经验分布确定。

本文的测试问题取自文献[7],并考虑了更加丰富的需求分布组合。假设零售商销售2种产品,产品的成本结构为:售价p1=4,p2=3,成本v1=v2=2,残值g1=1,g2=0,缺货惩罚B1=B2=0,零售商的资源总量S=80,产品的资源需求为s1=1,s2=2。产品的需求分布分别考虑4种可能,均匀分布U(20,80)、正态分布N(50,100)、三角分布(左偏)Tri(20,35,80)、三角分布(右偏)Tri(20,65,80),共形成16组测试问题,各问题中的产品需求分布及无约束最优订货量如图1所示。

图1 产品需求分布及无约束最优订货量

试验中首先为产品i=1,2分别生成服从4种分布的1000条需求作为共同的历史需求及测试数据,针对每个问题分别考虑历史需求的数量Nhist=10,30,50,为产品i=1,2分别生成30组对应数量的历史数据,利用启发式算法H1、H2、H3及算法1分别求解。

表1 算法1与启发式算法的对比

实验结果表明:(1)产品的成本结构对算法 1 的影响较小,对于启发式算法H1、H3的影响较大,本例中产品的成本结构具有较大差异,因此在所有测试问题中,算法1均优于启发式算法H3及启发式算法H1;(2)历史数据量Nhist=10时,H2在 12个问题中优于算法1,随着历史数据量的增加,算法1逐渐优于H2,当历史数据量Nhist=30时,H2在5个问题中优于算法1,当历史数据量Nhist=50时,H2仅在2 个真实分布包含均匀分布的问题中优于算法1,表明算法1受产品需求分布的影响较小。

4 结语

产品需求分布已知的假设影响了报童模型在实际中的应用效果。当历史数据充足时,可利用机器学习、人工智能算法估计需求分布或预测未来需求;

当历史数据有限时,除少数启发式算法外尚无有效的解决方法。本文在商品需求分布未知的前提下,将具有资源约束的多产品报童问题视作随机黑箱优化问题,在基于方向的直接搜索算法框架下设计了具有可变样本量的直接搜索算法,依据算法的迭代结果确定下一轮迭代所需的样本数量,通过重抽样方法从有限的历史数据中产生样本。本文提出的方法,不依赖于产品分布及产品成本结构等假设,数值实验结果表明,本文提出的算法可利用有限的历史数据求解具有资源约束的多产品报童问题,且求解效果整体上优于已有的方法。