1、收稿日期：基金项目：国家自然科学基金（；）作者简介：郝爽（），男，山西太原人，上海交通大学安泰经济与管理学院博士研究生，研究方向：供应链管理、随机优化。文章编号：（）市场营销多产品报童问题的直接搜索算法求解郝爽张大力董明（上海交通大学 安泰经济与管理学院，上海 ）摘要：多产品报童问题假设商品需求服从已知分布，在实践中难以直接应用，可将零售商收益视作表达式未知的随机黑箱函数，通过样本均值对收益的期望进行近似，并利用直接搜索算法最大化零售商收益。数值实验表明，直接搜索算法结合可变数量的样本均值近似可在样本数量极为有限的条件下有效求解多产品报童问题，且求解质量优于已有的启发式算法。关键词：多产品报童
2、问题；随机黑箱优化；直接搜索算法；可变样本数量中图分类号：文献标志码：犎犃 犗犛 犺 狌 犪 狀 犵犣犎犃犖犌犇 犪 犾 犻犇 犗犖犌犕 犻 狀 犵（，）：，：；引言报童问题是经典的随机库存管理模型，其基本假设为产品需求为分布已知的随机变量，当订货量过剩时，未售出的商品具有一定的残值，当订货量不足时，未满足的需求将产生惩罚成本，零售商需事先决定产品的订货量以最大化期望收益。报童问题假设产品需求为分布已知的随机变量，在实践中难以直接运用，解决方法主要有三类：一是利用历史数据对需求的分布类型、未知参数进行估计，或以经验分布对需求的累积分布进行近似，此类方法的求解效果依赖于估计量的质量，在小样本情况
3、下求解质量较差；二是各类数据驱动方法的应用，即利用机器学习或人工智能算法对需求进行预测，或对预测模型及库存决策进行联合优化，由于训练预测模型需要使用大量历史数据，以及与需求相关的其他类型数据，所以此类方法对于数据的质量及规模具有更高的要求，实际应用的难度更大；三是鲁棒优化方法，即利用历史数据的统计特征构建满足条件的分布集合，并最大化最差情况的期望收益，但所得的解往往过于保守，实际应用价值不高。实践中零售商通常同时销售多种产品且面临某种资源约束，例如采购成本不能超过预算或库存容量不能超过最大库容，因此多产品报童问题的应用更为广泛。多产品报童问题可分解为报童问题，并分别计算各产品的最优订货量，若能
4、够满足资源约上海管理科学 第 卷第期 年 月 束则求得最优，否则可通过拉格朗日乘子法求解，但高效准确求解拉格朗日乘子较为困难。文献、分别求解了产品需求服从特定类型分布且参数已知时的多产品报童问题，文献 设计了多种启发式方法求解多产品报童问题，其中部分方法仅使用需求量的均值和方差，因而简单易用，数值实验表明在不假设需求量分布已知的前提下，文献 的启发式算法可求得较好的近似解。有别于上述研究，本文假设零售商仅有各商品需求量的少量历史数据且商品需求量的分布未知，将零售商的收益视作随机黑箱函数，利用直接搜索算法进行求解。在直接搜索算法的每轮迭代中，通过控制样本的数量，利用有限的历史数据构造期望收益的样
5、本均值近似。本文提出的方法无须假设商品需求分布已知，数值实验表明在历史数据有限的情况下本方法仍然可以求得高质量的近似解。模型 具有资源约束的多产品报童问题具有资源约束的多产品报童问题描述如下：零售商同时销售狀种产品，产品间不存在需求的替代及互补效应；零售商在销售期前决定各种产品的订货量犙犻，犻，狀；对于产品犻，其需求量狓犻为随机变量，具有概率密度函数犳犻（）；产品犻的采购成本、销售价格、未售出残值及缺货惩罚分别为狏犻、狆犻、犵犻、犅犻；零售商具有某种资源约束，其资源总量为犛，单位产品犻的资源消耗量为狊犻。产品犻的收益函数为：犻（犙犻，狓犻）狆犻狓犻狏犻犙犻犵犻（犙犻狓犻），犙犻狓犻狆犻犙犻狏犻
6、犙犻犅犻（狓犻犙犻），犙犻狓犻（）产品犻的期望收益为：犈犻（犙犻）犙犻狆犻狓犻狏犻犙犻犵犻（犙犻狓犻）犳犻（狓犻）狓犻犙犻狆犻犙犻狏犻犙犻犅犻（狓犻犙犻）犳犻（狓犻）狓犻（）具有资源约束的多产品报童问题优化模型为：狀犻犈犻（犙犻）狀犻狊犻犙犻犛（）随机黑箱多产品报童问题为方便表述，下文将零售商的期望收入最大化问题转为最小化问题，同时针对资源约束狀犻狊犻犙犻犛，引入惩罚因子，具有资源约束的多产品报童问题可表示为：犌（犙，犙狀）犈犵（犙，犙狀，狓，狓狀）（）其中，犵（犙，犙狀，狓，狓狀）狀犻犻（犙犻，狓犻）狀犻狊犻犙犻犛，为随机函数，当随机需求狓犻，犻，狀的分布函数犳犻（），犻，狀未知时，犌（犙，
7、犙狀）的表达式未知，问题（）是一个随机黑箱优化问题。将多产品报童问题视作随机黑箱问题为建模及实际应用提供了诸多便利。首先，随机黑箱问题假设随机参数的分布未知，避免了由参数估计造成的解的质量下降；其次随机黑箱问题不要求目标函数具有明确的表达式，对于替代性需求、需求依赖价格、存在其他随机参数等不同类型的报童问题同样适用，扩展了模型的应用范围。具有可变样本量的直接搜索算法由于黑箱函数的表达式未知，无法利用各类基于梯度的优化方法求解，所以其求解主要通过各类无梯度优化方法，包括随机近似、响应面法、信赖域法及各类直接搜索算法，例如单纯形搜索、广义模式搜索、网格自适应搜索，其中直接搜索算法由于易于实现、鲁棒
8、性强，得到了广泛应用。直接搜索算法属于迭代算法，通过比较当前解与一组候选解的目标函数值，逐步更新当前解以及步长等算法参数。针对随机黑箱问题，目标函数值无法准确计算，需要以样本均值对目标函数值进行近似。以问题（）为例，假设商品需求的样本为狓犼犻犻，狀；犼，犿，其目标函数的样本均值近似为：珚犌（犙）犿犿犼狀犻犻（犙犻，狓犼犻）狀犻狊犻犙犻犛，（）其中，犙犙，犙狀。等研究得出了达到给定近似精度所需的样本数量，但实际问题中的样本数量往往较少，难以满足精度要求。本文依据 等提出的直接搜索算法框架，针对问题（）设计了具有可变样本数量的直接搜索算法，步骤如下：算法具有可变样本数量的直接搜索算法初始化初始可行
9、解犙犙，犙狀，搜索方向集合为犇，初始搜索步长为，终止搜索步长为狋 狅 犾，搜索步长的连续增函数为（），初始样本为狓犼犻犻，狀；犼，犖。循环：在第犽（犽，）次迭代中，执行以下步骤：基于方向的搜索上海管理科学 第 卷第期 年 月 对当前解犙犽及所有候选解犙犽犽犱，犱犇，分别计算其目标函数的样本均值珚犌（犙犽）、珚犌（犙犽犽犱）。如果存在犱犇使得珚犌（犙犽犽犱）珚犌（犙犽）（犽），即候选解犙犽犽犱使目标函数产生充分下 降，记 第犽轮迭代 搜 索 成功，更新 当 前解犙犽犙犽犽犱，更新搜索步长犽犽，。否则记犽轮迭代搜索失败，保持当前解不变，缩小搜索步长犽 犽，。判断终止条件如果犽狋 狅 犾，停止循环。
10、更新样本如果搜索成功，保持样本不变，返回步骤。否则，令犽轮的样本数量为犖犽 犖，犮犾 狅 犵（犽）犽（）从产品犻的历史需求数据中，分别抽样犖犽次，产生样本狓犼犻犻，狀；犼，犖犽，返回步骤。算法属于基于方向的直接搜索框架，其中搜索方向集合犇中的元素必须范数有界、余弦度量必须有下界且犇必须为解空间的生成集，算法中的参数要求可参考文献 。步骤 依据搜索的结果决定次轮的样本数量，犽轮搜索成功表明当前样本均值的近似程度高于搜索的精度，因而在犽轮中可保持样本不变；犽轮搜索失败时，需要在次轮缩短搜索步长以提高搜索精度，相应增加样本数量以提高 样 本 均 值 近 似 的 精 度。式（）通 过 在犖、犮 （犽）
11、犽之间取较大值，避免早期迭代中样本数量过少，其中犮为一个较小的常数，用于控制样本数量增长的速率。在一般的随机黑箱优化问题中，可通过多次重复运行黑箱函数获得样本，在报童问题中积累真实的需求数据耗时极多，因此通过对历史数据抽样产生样本。算例分析本章通过数值实验证明在产品需求分布未知且产品需求量历史数据有限的条件下，算法可有效求解具有资源约束的多产品报童问题，且结果优于文献 提出的启发式算法。文献 针对具有资源约束且需求分布未知的多产品报童问题设计了三种启发式算法，令犻、犻、犙狌犻分别表示产品的需求量均值、标准差、无约束最优订货量，犻狊犻狆犻犵犻犅犻表示产品犻的资源需求与其销售收益的比值，三种启发式
12、算法的表达式分别为：犎犙犻犻犻狀犼狊犼犼（犛狀犼狊犼犼）（）犎犙犻犙狌犻犻犻狀犼狊犼犼犼（犛狀犼狊犼犙狌犼）（）犎犙犻犻犻犻狀犼狊犼犼犼（犛狀犼狊犼犼）（）其中：基于产品成本结构、需求分布均相同的假设；基于产品需求均服从均匀分布的假设，产品的成本结构可以不同；在的基础上进一步考虑了产品成本结构的差异；不满足其假设时，、所得结果均为近似解，但具有运算简单、无须已知需求分布的优点。在实际运用中，需求量的均值、标准差可利用历史需求进行估计，无约束最优订货量可通过历史需求的经验分布确定。本文的测试问题取自文献，并考虑了更加丰富的需求分布组合。假设零售商销售种产品，产品的成本结构为：售价狆，狆，成本狏狏
13、，残值犵，犵，缺货惩罚犅犅，零售商的资源总量犛，产品的资源需求为狊，狊。产品的需求分布分别考虑种可能，均匀分布犝（，）、正态分布犖（，）、三角分布（左偏）犜 狉 犻（，）、三角分布（右偏）犜 狉 犻（，），共形成 组测试问题，各问题中的产品需求分布及无约束最优订货量如图所示。试验中首先为产品犻，分别生成服从种分布的 条需求作为共同的历史需求及测试数据，针对每个问题分别考虑历史需求的数量犖犺 犻 狊 狋，为产品犻，分别生成 组对应数量的历史数据，利用启发式算法、及算法分别求解。算法设置如下：初始解犙犛，犛，初始步长，终止步长狋 狅 犾 ，步长控制参数，判定搜索是否成功的阈值函数（犽）犽，搜索方向
14、集合犇 ，初始样本数量犖 犖犺 犻 狊 狋，控制样本数量增长速率的参数犮 。由于迭代过程中抽样产生的样本具有随机性，因此对每组数据重复运行算法十次。利用共同的测试数据对启发式算法、及算法进行比较，算法所得结果的平均近似期望收益及其与各启发式算法所得结果的百分比偏差如表所示。上海管理科学 第 卷第期 年 月 图产品需求分布及无约束最优订货量表算法与启发式算法的对比问题序号真实分布产品产品犖犺 犻 狊 狋 算法百分比偏差犖犺 犻 狊 狋 算法百分比偏差犖犺 犻 狊 狋 算法百分比偏差犝（，）犝（，）犖（，）犜 狉 犻（，）犜 狉 犻（，）犖（，）（，）犖（，）犜 狉 犻（，）犜 狉 犻（，）犜 狉
15、 犻（，）犝（，）犖（，）犜 狉 犻（，）犜 狉 犻（，）犜 狉 犻（，）犝（，）犖（，）犜 狉 犻（，）犜 狉 犻（，）实验结果表明：（）产品的成本结构对算法的影响较小，对于启发式算法、的影响较大，本例中产品的成本结构具有较大差异，因此在所有测试问题中，算法均优于启发式算法及启发式算法；（）历史数据量犖犺 犻 狊 狋 时，在 个问题中优于算法，随着历史数据量的增加，算法逐渐优于，当历史数据量犖犺 犻 狊 狋 时，在个问题中优于算法，当历史数据量犖犺 犻 狊 狋 时，仅在个真实分布包含均匀分布的问题中优于算法，表明算法受产品需求分布的影响较小。结语产品需求分布已知的假设影响了报童模型在实际中的
16、应用效果。当历史数据充足时，可利用机器学习、人工智能算法估计需求分布或预测未来需求；（下转第 页）上海管理科学 第 卷第期 年 月 费者信任重建管理学报，（）：王晓玉，吴婧产品危机情境下竞争对手响应策略对未响应者的溢出效应营销科学学报，（）：，：，（）：，：，：（）：，程红玲，陈维政服务业员工情绪失范行为的产生机制及影响因素分析四川大学学报（哲学社会科学版），（）：刘小禹，王敬，刘军好的表演需要好的观众：顾客察觉准确性在员工情绪劳动影响中的作用商业经济与管理，（）：范宝财，杨洋，李蔚产品伤害危机属性对横向溢出效应的影响研究：产品相似性和企业声誉的调节作用商业经济与管理，（）：陈治任，余明阳，薛
17、可基于消费者信任视角对原产国品牌负面溢出影响因素的研究上海管理科学，（）：李伟，梅继霞，熊卫情绪智力、劳动策略与情感耗竭：有调节的中介模型科研管理，（）：刘小禹组织中情绪管理的文化视角与实证研 究北京：中国经济出版社，：，（）：，？，（）：彭艳君，张瀚文顾客感知的员工情绪劳动对其购买行为的影响：以家居零售企业为例中国流通经济，（）：杨琛，王婧倩员工情绪劳动策略影响消费者购买行为的机制研究：基于 理论模型的分析价格理论与实践，（）：，：，（上接第页）当历史数据有限时，除少数启发式算法外尚无有效的解决方法。本文在商品需求分布未知的前提下，将具有资源约束的多产品报童问题视作随机黑箱优化问题，在基于方向的直接搜索算法框架下设计了具有可变样本量的直接搜索算法，依据算法的迭代结果确定下一轮迭代所需的样本数量，通过重抽样方法从有限的历史数据中产生样本。本文提出的方法，不依赖于产品分布及产品成本结构等假设，数值实验结果表明，本文提出的算法可利用有限的历史数据求解具有资源约束的多产品报童问题，且求解效果整体上优于已有的方法。参考文献：刘开军，张子刚需求分布含未知参数时报童模型的实施方法系统管理学报，（）：，?，：，（）：，（）：，（）：，（）：，：，（）：，（）：上海管理科学 第 卷第期 年 月
