O&SCM运营与供应链管理知识库

LATEST RESEARCH FRONTIERS / 最新研究前沿

品类优化 · 缺货风险 · 替代推荐

首选商品缺货,
如何选好替代品?

Assortment Optimization with Replacement Options for Retail Platforms with Stockout Risk

替代选项与柔性 / Replacement Options and Flexibility站内同词论文 ↗站内同词论文 ↗站内同词论文 ↗学术网络 ↗
多项式 Logit 选择 / Multinomial Logit and Consumer Choice站内同词论文 ↗站内同词论文 ↗学术网络 ↗

506 个原生公式 13:11 视频 14:59 音频

CHINESE LECTURE VIDEO / 中文讲解视频

品类优化:缺货风险与替代选项

解析两阶段消费者选择、替代选项推荐、PTAS 与 FPTAS,以及收益和退款率之间的权衡。

13 分 11 秒 · 854×480
CHINESE AUDIO SUMMARY / 中文音频总结

生鲜电商缺货替代算法

从生鲜电商的缺货履约难题出发,讨论替代推荐、个性化选品和服务水平约束。

14 分 59 秒 · 单声道 AAC
FULL PAPER SUMMARY / 完整论文总结

考虑缺货风险与替代选项的零售平台品类优化:全文总结与模型解析

以下为所附 Word 总结全文,保留全文脉络、核心贡献、模型函数、命题定理与算例、实证结果、管理启示和参考文献。

《考虑缺货风险与替代选项的零售平台品类优化》
全文总结与深度解析

Assortment Optimization with Replacement Options for Retail Platforms with Stockout Risk

项目 (Attribute) 详细内容 (Details)
论文题目 (Title) Assortment Optimization with Replacement Options for Retail Platforms with Stockout Risk(考虑缺货风险与替代选项的零售平台品类优化)
作者 (Authors) Dmitry Mitrofanov (Carroll School of Management, Boston College)
Huseyin Topaloglu (School of Operations Research and Information Engineering, Cornell Tech)
Yuheng Wang (School of Operations Research and Information Engineering, Cornell Tech)
发表期刊 (Journal) Operations Research(运筹学国际顶级期刊,UTD-24 / INFORMS 旗舰期刊)
出版信息 (Publication) 2026年,第74卷,第5期(Vol. 74, No. 5, September–October 2026),页码:2460–2484,DOI: 10.1287/opre.2024.1074
研究领域与关键词 Markets, Platforms, and Revenue Management | online platforms(在线平台)、retail(零售)、assortment optimization(品类优化)、stockout risk(缺货风险)、replacement options(替代选项)

一、 论文基本信息与全文核心脉络总结

1. 作者与发表期刊交代:本文题为 Assortment Optimization with Replacement Options for Retail Platforms with Stockout Risk,由来自波士顿学院卡罗尔管理学院(Carroll School of Management, Boston College)的 Dmitry Mitrofanov,以及来自康奈尔大学科技校区运筹学与信息工程学院(School of Operations Research and Information Engineering, Cornell Tech)的 Huseyin Topaloglu 和 Yuheng Wang 共同撰写。文章发表于运筹学与管理科学领域的国际顶级学术期刊 Operations Research(2026年第74卷第5期,第2460–2484页)。

2. 研究背景与现实痛点:近年来,以 Instacart、Amazon Fresh 以及 Target.com 等为代表的在线即时零售与生活杂货配送平台迅速崛起。这类平台主要作为“市场撮合与配送服务商”(Market Facilitators)运作,本身并不直接拥有或控制线下合作零售商(如超市、杂货店)的门店库存。由于消费者在线上下单的时间与拣货员(Shopper)在实体门店实际拣货履约的时间之间存在显著的时间滞后(长达数小时甚至24小时),且线下货架受门店自然客流购买及后仓补货波动的影响,消费者下单时显示有货的商品在实际履约时面临显著的“缺货风险”(Stockout Risk)。为避免因首选商品缺货而直接取消订单造成收入流失与客户不满,各大零售平台普遍引入了一项交互机制:在消费者将首选商品(Preferred Option)加入购物车后,提示消费者同时指定一个备选的替代商品(Replacement Option)。当拣货履约时,若首选商品有货,则交付首选商品并收取相应费用;若首选商品缺货但替代商品有货,则用替代商品履约并收取替代商品的费用;若两者均缺货(或未选替代商品且首选缺货),则无法履约并触发退款。

3. 核心科学问题与两阶段决策框架:本文研究的核心问题是:当商品存在外生缺货风险且平台允许消费者指定替代选项时,平台应当如何优化展示给消费者的商品组合(Assortment Optimization),以最大化来自单个消费者的期望总收益?作者采用改进的多项式 Logit(Multinomial Logit, MNL)随机效用最大化模型刻画消费者的两阶段选择过程:在第一阶段,平台展示初始商品组合 𝑆0\mathit{S}_{\mathit{0}},消费者从中选择效用最大的商品 𝑖∈𝑆0\mathit{i}\text{∈}\mathit{S}_{\text{0}} 作为首选商品(若不购买选项效用最大则直接离开);在第二阶段,针对选择了首选商品 𝑖\mathit{i} 的消费者,平台展示替代商品组合 𝑆𝑖\mathit{S}_{\mathit{i}},消费者从中选择效用最大的商品 𝑗∈𝑆𝑖\mathit{j}\text{∈}\mathit{S}_{\mathit{i}} 作为替代商品。出于业务逻辑一致性与客户信任考虑,模型要求第二阶段展示的替代商品集合必须是第一阶段商品集合的子集且不包含已选的首选商品,即满足包含约束 𝑆𝑖⊆𝑆0∖{𝑖}\mathit{S}_{\mathit{i}}\text{⊆}\mathit{S}_{\text{0}}\text{∖}\left\{ \mathit{i} \right\}(确保不会出现第一阶段未展示却在第二阶段突然冒出的“意外商品”)。

4. 两种优化模式与全文研究脉络:围绕第二阶段替代组合 𝑆𝑖\mathit{S}_{\mathit{i}} 是否随消费者第一阶段的首选商品 𝑖\mathit{i} 动态调整,本文深入研究了两个问题变体:(1)非自适应变体(Nonadaptive Variant):平台仅计算一个统一的初始商品组合 𝑆0\mathit{S}_{\mathit{0}},当消费者选择首选商品 𝑖\mathit{i} 后,第二阶段直接展示 𝑆0\mathit{S}_{\mathit{0}} 中除 𝑖\mathit{i} 以外的所有剩余商品,即 𝑆𝑖=𝑆0∖{𝑖}\mathit{S}_{\mathit{i}}\text{=}\mathit{S}_{\text{0}}\text{∖}\left\{ \mathit{i} \right\};(2)自适应变体(Adaptive Variant):平台根据消费者在第一阶段挑选的具体首选商品 𝑖\mathit{i},针对性地裁剪并优化第二阶段展示的替代商品子集 𝑆𝑖⊆𝑆0∖{𝑖}\mathit{S}_{\mathit{i}}\text{⊆}\mathit{S}_{\text{0}}\text{∖}\left\{ \mathit{i} \right\}。文章首先证明了这两种变体均为 NP-hard 问题;随后在理论上刻画了自适应策略相对于非自适应策略的价值上下界(上界为 2,下界趋近于 43\frac{\text{4}}{\text{3}});接着分别为自适应变体设计了多项式时间近似方案(PTAS),为非自适应变体设计了完全多项式时间近似方案(FPTAS),并构建了混合整数规划(MIP)模型以供实际求解及添加业务约束;最后利用北美头部生鲜杂货配送平台 Instacart 的 1100 万笔真实订单数据开展实证案例研究,并验证了受 PTAS 启发的启发式算法在大规模算例上超越商业求解器 Gurobi 的优越性能。

二、 突出文章的核心贡献

本文在零售平台运筹优化与收益管理领域做出了开创性的理论、算法与实证贡献,具体体现在以下六个核心方面:

1. 首创带缺货风险与替代选项的两阶段品类优化理论模型及复杂性证明:现有文献大多研究无缺货风险下的单阶段或多阶段顺序推荐问题,或仅从实证角度分析缺货对消费者满意度的影响。本文首次将“外生商品缺货风险”与“消费者预先指定替代选项”结合起来构建品类优化模型。作者巧妙利用独立 Gumbel 随机变量的“最大值分布性质”与“条件排序独立于最大值的性质(Conditional Ranking)”,推导出了两阶段选择机制下平台期望总收益的闭式解析表达式,并严格证明了无论是非自适应变体还是自适应变体,寻找期望收益最大化商品组合的问题均为 NP-hard(这与经典无缺货 MNL 模型可由按收益排序在多项式时间内精确求解形成了鲜明对比)。

2. 严格界定自适应推荐相对于非自适应推荐的理论价值边界:作者从理论上回答了“根据顾客首选商品动态定制替代商品推荐列表究竟能带来多大收益提升”这一核心问题。通过数学推导,作者证明了自适应变体的最优期望收益至多是非自适应变体最优期望收益的 2 倍(即自适应价值上界为 2);同时构造了一个精巧的极限算例,证明自适应最优期望收益与非自适应最优期望收益之比可以任意逼近 43\frac{\text{4}}{\text{3}}(即下界为 43\frac{\text{4}}{\text{3}},约提升 33.3%)。此外,在证明上界的过程中,作者顺带证明了完全忽略替代选项、直接求解经典单阶段 MNL 最优组合可作为两类变体的快速 12\frac{\text{1}}{\text{2}}-近似解,并构造紧性算例证明了该 12\frac{\text{1}}{\text{2}} 近似比是紧的。

3. 攻克带补偿机制(Recourse)的自适应品类优化难题,设计出多项式时间近似方案(PTAS):自适应变体本质上是一个带有第二阶段补偿决策(Recourse Decision)的两阶段优化问题,目标函数求和项中嵌套了 𝑛\mathit{n} 个子优化问题,设计近似算法极具挑战。作者提出了极具创新性的两步构造法:第一步,定义商品权重为 𝑣𝑖𝑟𝑖=𝑣𝑖𝑞𝑖𝑓𝑖\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}}\text{=}\mathit{v}_{\mathit{i}}\mathit{q}_{\mathit{i}}\mathit{f}_{\mathit{i}},对最优解中高调整后收益商品集里权重最大的前 ⌈1𝜖⌉\left\lceil \frac{\text{1}}{\mathit{\epsilon}} \right\rceil 个商品(称为“关键集” 𝑀H\mathit{M}_{\text{H}})进行猜测,构造了一个“代理问题(Surrogate Problem)”——仅当顾客首选商品属于关键集 𝑀H\mathit{M}_{\text{H}} 时才在第二阶段采取自适应推荐,否则采取统一的非自适应推荐,并证明该代理问题在 11+𝜖\frac{\text{1}}{\text{1+}\mathit{\epsilon}} 因子内逼近原自适应问题;第二步,将代理问题等价转化为含 ⌈1𝜖⌉+3\left\lceil \frac{\text{1}}{\mathit{\epsilon}} \right\rceil\text{+3} 个约束的多维背包问题(含打包约束与覆盖约束),通过几何网格猜测关键聚合量并运用缩放到整数状态的动态规划求得允许约束轻微违背 1+𝜖\text{1+}\mathit{\epsilon} 倍的“超最优解(Superoptimal Solution)”,最终在 𝑂((𝑛𝜖)𝑂(1𝜖))\mathit{O}\left( \left( \frac{\mathit{n}}{\mathit{\epsilon}} \right)^{\mathit{O}\left( \frac{\text{1}}{\mathit{\epsilon}} \right)} \right) 运行时间内实现了 (1−𝜖)\left( \text{1−}\mathit{\epsilon} \right)-近似解。

4. 为非自适应变体设计完全多项式时间近似方案(FPTAS):针对非自适应变体,作者克服了直接猜测总偏好权重 𝑉(𝑆*)\mathit{V}\left( \mathit{S}^{\text{*}} \right) 和总商品权重 𝑊(𝑆*)\mathit{W}\left( \mathit{S}^{\text{*}} \right) 会在目标函数分子分母中产生减法项(𝑤−𝑣𝑖𝑟𝑖\mathit{w}\text{−}\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}} 与 1+𝑔−𝑣𝑖\text{1+}\mathit{g}\text{−}\mathit{v}_{\mathit{i}})从而导致相对误差失控的技术障碍,巧妙地引入最优解中偏好权重最大的商品 𝑖*\mathit{i}^{\mathit{*}} 和商品权重最大的商品 𝑗*\mathit{j}^{\mathit{*}},改为猜测剔除这两个锚点商品后的剩余权重 𝑉(𝑆*∖{𝑖*})\mathit{V}\left( \mathit{S}^{\text{*}}\text{∖}\left\{ \mathit{i}^{\text{*}} \right\} \right) 与 𝑊(𝑆*∖{𝑗*})\mathit{W}\left( \mathit{S}^{\text{*}}\text{∖}\left\{ \mathit{j}^{\text{*}} \right\} \right),使分子分母全部转化为非负加法项,进而通过二维背包动态规划在 𝑂(𝑛7(log 𝑛)2𝜖4)\mathit{O}\left( \frac{\mathit{n}^{\text{7}}\left( \text{log }\mathit{n} \right)^{\text{2}}}{\mathit{\epsilon}^{\text{4}}} \right) 多项式时间内获得 (1−𝜖)\left( \text{1−}\mathit{\epsilon} \right)-近似解。

5. 构建精确等价的混合整数规划(MIP)模型与高效启发式算法:作者通过引入代表各阶段选择概率的连续变量与指示商品入选的二元变量,利用 Charnes-Cooper 类分式线性化技巧建立了自适应与非自适应变体的精确混合整数规划模型,并证明在无额外二阶段约束时可消去二阶段二元变量 𝑧𝑖𝑗\mathit{z}_{\mathit{ij}} 仅保留一阶段二元变量 𝑥𝑖\mathit{x}_{\mathit{i}}。该 MIP 模型不仅支持直接调用商业求解器,还能灵活嵌入“最高退款率上限”等现实业务约束。同时,作者受 PTAS 理论结构启发,将关键集 𝑀H\mathit{M}_{\text{H}} 简化为单元素集(Singleton),设计出一种兼具理论根基与极高计算速度的实用启发式算法:在 𝑛=200\mathit{n}\text{=200} 的大规模测试算例中,该启发式仅耗时约 0.41 秒,在 50 倍运行时间限制下击败 Gurobi 达 333/360 次,平均收益超越 Gurobi 1.40%(最高达 5.70%)。

6. 基于 Instacart 海量交易数据的实证检验与管理洞见:作者利用 Instacart 跨越 21 周的 1100 万笔真实订单数据(涵盖 12 个核心生鲜杂货品类及多家合作零售商)进行了系统实证分析。实证结果表明:(1)与忽略替代选项的朴素 MNL 策略相比,显式建模替代选项(非自适应策略)平均可提升平台期望收益 3.39%(部分品类与零售商组合超过 18%),同时将净市场份额(实际履约率)平均提升 1.36%(鸡蛋品类提升达 3.42%);(2)从非自适应策略升级为自适应策略可在此基础上进一步带来平均 0.94% 的期望收益增长(部分组合超过 4%),若保持历史第一阶段展示商品不变而仅在第二阶段采用自适应优化,期望收益平均增幅高达 8.93%;(3)揭示了扩大展示规模虽能提升总收益与履约率,但也会因引入高缺货风险商品而推高退款率(Refund Rate)的现象,并证明了通过 MIP 施加退款率上限约束可在仅增加约 1% 退款率的代价下实现约 1% 的净收益提升。

三、 模型中的数学符号与核心函数详解

为了清晰呈现论文的数学建模逻辑,本节首先汇总模型的基础参数与衍生变量定义,随后按照论文推进顺序,对模型中的每一个核心函数、选择概率表达式及优化目标函数进行逐一拆解与物理意义阐释。

3.1 基础集合、参数与随机效用变量汇总

数学符号 名称与定义 经济与物理含义详解
𝑁\mathit{N} = \text{ = }{1, 2, …, 𝑛}\left\{ \text{1, 2, …, }\mathit{n} \right\} 全集商品集合 平台上可供展示的全部候选商品集合,共有 n 种商品。
𝑓𝑖\mathit{f}_{\mathit{i}} 商品原始收益(价格) 当商品 𝑖\mathit{i} 被成功交付给消费者时,平台或零售商获得的单位销售收入(Unit Revenue)。
𝑞𝑖\mathit{q}_{\mathit{i}} ∈ [0, 1]\text{ ∈ [0, 1]} 商品有货概率(Availability Probability) 在订单拣货履约时刻,商品 𝑖\mathit{i} 在门店货架上处于有货可售状态的概率(外生参数)。
𝑝𝑖\mathit{p}_{\mathit{i}} = 1 − \text{ = 1 − }𝑞𝑖\mathit{q}_{\mathit{i}} 商品缺货概率(Unavailability Probability) 在订单拣货履约时刻,商品 𝑖\mathit{i} 发生缺货(Out of Stock)的概率。
𝑟𝑖\mathit{r}_{\mathit{i}} = \text{ = }𝑞𝑖\mathit{q}_{\mathit{i}}𝑓𝑖\mathit{f}_{\mathit{i}} 可用性调整后收益(Adjusted Revenue) 商品 𝑖\mathit{i} 考虑自身有货概率后的单次期望有效收益,是全文衡量商品直接收益贡献的核心指标。
𝑈𝑖\mathit{U}_{\mathit{i}}, \text{, }𝑈0\mathit{U}_{\text{0}} 随机效用变量(Random Utilities) 消费者赋予商品 𝑖\mathit{i} 的随机效用 𝑈𝑖\mathit{U}_{\mathit{i}} 服从位置与尺度参数为 (𝜇𝑖, 1)\left( \mathit{\mu}_{\mathit{i}}\text{, 1} \right) 的独立 Gumbel 分布;不购买选项(No-purchase option)的随机效用 𝑈0\mathit{U}_{\text{0}} 服从参数为 (0, 1)\left( \text{0, 1} \right) 的 Gumbel 分布。
𝑣𝑖\mathit{v}_{\mathit{i}} = \text{ = }exp\text{exp}(𝜇𝑖)\left( \mathit{\mu}_{\mathit{i}} \right) 商品偏好权重(Preference Weight) 衡量消费者对商品 𝑖\mathit{i} 的平均喜爱程度;不购买选项的偏好权重归一化为 𝑣0 = exp(0) = 1\mathit{v}_{\text{0}}\text{ = }\text{exp(0) = 1}。
𝑣𝑖\mathit{v}_{\mathit{i}}𝑟𝑖\mathit{r}_{\mathit{i}} = \text{ = }𝑣𝑖\mathit{v}_{\mathit{i}}𝑞𝑖\mathit{q}_{\mathit{i}}𝑓𝑖\mathit{f}_{\mathit{i}} 商品综合权重(Weight of Product) 将商品的偏好权重 𝑣𝑖\mathit{v}_{\mathit{i}}、有货概率 𝑞𝑖\mathit{q}_{\mathit{i}} 与销售收益 𝑓𝑖\mathit{f}_{\mathit{i}} 三者相乘得到的综合贡献指标,在设计近似算法(PTAS/FPTAS)时用于筛选核心商品。

3.2 集合聚合函数与两阶段选择概率函数(公式 1–2)

(1)子集总偏好权重函数 𝑉(𝑆)\mathit{V}\left( \mathit{S} \right) 与子集总商品权重函数 𝑊(𝑆)\mathit{W}\left( \mathit{S} \right):

𝑉(𝑆) = ∑𝑖∈𝑆𝑣𝑖 , 𝑊(𝑆) = ∑𝑖∈𝑆𝑣𝑖𝑟𝑖\mathit{V}\left( \mathit{S} \right)\text{ = }\sum_{\mathit{i}\text{∈}\mathit{S}}^{}\mathit{v}_{\mathit{i}}\text{ , }\mathit{W}\left( \mathit{S} \right)\text{ = }\sum_{\mathit{i}\text{∈}\mathit{S}}^{}{\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}}}

函数解释:对于任意商品子集 𝑆⊆𝑁\mathit{S}\text{⊆}\mathit{N},函数 𝑉(𝑆)\mathit{V}\left( \mathit{S} \right) 将集合 𝑆\mathit{S} 内所有展示商品的偏好权重 𝑣𝑖\mathit{v}_{\mathit{i}} 相加,反映了该商品组合对消费者的整体吸引力总和(分母 1+𝑉(𝑆)\text{1+}\mathit{V}\left( \mathit{S} \right) 则包含了权重为 1 的不购买选项);函数 𝑊(𝑆)\mathit{W}\left( \mathit{S} \right)(见第 5 节)则将集合 𝑆\mathit{S} 内所有商品的综合权重 𝑣𝑖𝑟𝑖\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}} 相加,代表该商品组合在未经分母归一化前的总期望收益分子项。

(2)Gumbel 随机变量的最大值概率与条件排序同分布函数(公式 1 与公式 2):

ℙ{𝑋1 ≥ max{𝑋2, 𝑋3, …, 𝑋𝑛}} = 𝑒𝜇1𝑒𝜇1 + ⋯ + 𝑒𝜇𝑛 (1)\text{ℙ}\left\{ \mathit{X}_{\text{1}}\text{ ≥ }\text{max}\left\{ \mathit{X}_{\text{2}}\text{, }\mathit{X}_{\text{3}}\text{, …, }\mathit{X}_{\mathit{n}} \right\} \right\}\text{ = }\frac{\mathit{e}^{\mathit{\mu}_{\text{1}}}}{\mathit{e}^{\mathit{\mu}_{\text{1}}}\text{ + ⋯ + }\mathit{e}^{\mathit{\mu}_{\mathit{n}}}}\text{ (1)}

ℙ{𝑋2 ≥ 𝑋3 ≥ ⋯ ≥ 𝑋𝑛 ∣ 𝑋1 ≥ max{𝑋2, 𝑋3, …, 𝑋𝑛}} = ℙ{𝑋2 ≥ 𝑋3 ≥ ⋯ ≥ 𝑋𝑛} (2)\text{ℙ}\left\{ \mathit{X}_{\text{2}}\text{ ≥ }\mathit{X}_{\text{3}}\text{ ≥ ⋯ ≥ }\mathit{X}_{\mathit{n}}\text{ ∣ }\mathit{X}_{\text{1}}\text{ ≥ }\text{max}\left\{ \mathit{X}_{\text{2}}\text{, }\mathit{X}_{\text{3}}\text{, …, }\mathit{X}_{\mathit{n}} \right\} \right\}\text{ = }\text{ℙ}\left\{ \mathit{X}_{\text{2}}\text{ ≥ }\mathit{X}_{\text{3}}\text{ ≥ ⋯ ≥ }\mathit{X}_{\mathit{n}} \right\}\text{ (2)}

函数解释:公式 (1) 给出了独立 Gumbel 随机变量序列中某一项取得最大值的概率,由此直接导出第一阶段展示商品组合 𝑆0\mathit{S}_{\mathit{0}} 时,消费者挑选商品 𝑖∈𝑆0\mathit{i}\text{∈}\mathit{S}_{\text{0}} 作为首选商品的概率为 𝑣𝑖1+𝑉(𝑆0)\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\text{0}} \right)}。公式 (2) 是整个两阶段模型得以简洁求解的核心概率基石:它表明在已知 𝑋1\mathit{X}_{\text{1}} 是全局最大值的条件下,其余剩余随机变量 {𝑋2, …, 𝑋𝑛}\left\{ \mathit{X}_{\text{2}}\text{, …, }\mathit{X}_{\mathit{n}} \right\} 的条件大小排序分布与它们无条件时的排序分布完全一致!由于第二阶段展示的商品集满足 𝑆𝑖⊆𝑆0∖{𝑖}\mathit{S}_{\mathit{i}}\text{⊆}\mathit{S}_{\text{0}}\text{∖}\left\{ \mathit{i} \right\},且消费者在第一阶段已经对所有商品抽样生成了效用值,已知商品 𝑖\mathit{i} 在第一阶段效用最大并不会改变 𝑆𝑖∪{0}\mathit{S}_{\mathit{i}}\text{∪}\left\{ \text{0} \right\} 中各选项的相对排序概率分布。因此,在第一阶段选定 𝑖\mathit{i} 的条件下,消费者在第二阶段从 𝑆𝑖\mathit{S}_{\mathit{i}} 中挑选商品 𝑗∈𝑆𝑖\mathit{j}\text{∈}\mathit{S}_{\mathit{i}} 作为替代选项的条件概率依然保持标准 MNL 形式 𝑣𝑗1+𝑉(𝑆𝑖)\frac{\mathit{v}_{\mathit{j}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\mathit{i}} \right)},而选择不指定任何替代商品(即在第二阶段选择不购买选项 0)的条件概率为 11+𝑉(𝑆𝑖)\frac{\text{1}}{\text{1+}\mathit{V}\left( \mathit{S}_{\mathit{i}} \right)}。

3.3 两阶段期望总收益函数与总体优化模型(公式 3–5)

(1)原始两阶段期望收益函数 𝑅(𝑆0, 𝑆1, …, 𝑆𝑛)\mathit{R}\left( \mathit{S}_{\text{0}}\text{, }\mathit{S}_{\text{1}}\text{, …, }\mathit{S}_{\mathit{n}} \right)(公式 3)及其精简形式(公式 5):

𝑅(𝑆0, 𝑆1, …, 𝑆𝑛) = ∑𝑖∈𝑆0∑𝑗∈𝑆𝑖𝑣𝑖1+𝑉(𝑆0)𝑣𝑗1+𝑉(𝑆𝑖)[𝑞𝑖𝑓𝑖 + (1−𝑞𝑖)𝑞𝑗𝑓𝑗] + ∑𝑖∈𝑆0𝑣𝑖1+𝑉(𝑆0)11+𝑉(𝑆𝑖)𝑞𝑖𝑓𝑖\mathit{R}\left( \mathit{S}_{\text{0}}\text{, }\mathit{S}_{\text{1}}\text{, …, }\mathit{S}_{\mathit{n}} \right)\text{ = }\sum_{\mathit{i}\text{∈}\mathit{S}_{\text{0}}}^{}{\sum_{\mathit{j}\text{∈}\mathit{S}_{\mathit{i}}}^{}{\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\text{0}} \right)}\frac{\mathit{v}_{\mathit{j}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\mathit{i}} \right)}\left\lbrack \mathit{q}_{\mathit{i}}\mathit{f}_{\mathit{i}}\text{ + }\left( \text{1−}\mathit{q}_{\mathit{i}} \right)\mathit{q}_{\mathit{j}}\mathit{f}_{\mathit{j}} \right\rbrack}}\text{ + }\sum_{\mathit{i}\text{∈}\mathit{S}_{\text{0}}}^{}{\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\text{0}} \right)}\frac{\text{1}}{\text{1+}\mathit{V}\left( \mathit{S}_{\mathit{i}} \right)}\mathit{q}_{\mathit{i}}\mathit{f}_{\mathit{i}}}

= ∑𝑖∈𝑆0𝑣𝑖1+𝑉(𝑆0)(𝑞𝑖𝑓𝑖 + (1−𝑞𝑖)∑𝑗∈𝑆𝑖𝑣𝑗1+𝑉(𝑆𝑖)𝑞𝑗𝑓𝑗) (3)\text{= }\sum_{\mathit{i}\text{∈}\mathit{S}_{\text{0}}}^{}{\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\text{0}} \right)}\left( \mathit{q}_{\mathit{i}}\mathit{f}_{\mathit{i}}\text{ + }\left( \text{1−}\mathit{q}_{\mathit{i}} \right)\sum_{\mathit{j}\text{∈}\mathit{S}_{\mathit{i}}}^{}{\frac{\mathit{v}_{\mathit{j}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\mathit{i}} \right)}\mathit{q}_{\mathit{j}}\mathit{f}_{\mathit{j}}} \right)}\text{ (3)}

引入调整后收益 𝑟𝑖=𝑞𝑖𝑓𝑖\mathit{r}_{\mathit{i}}\text{=}\mathit{q}_{\mathit{i}}\mathit{f}_{\mathit{i}} 和缺货概率 𝑝𝑖=1−𝑞𝑖\mathit{p}_{\mathit{i}}\text{=1−}\mathit{q}_{\mathit{i}} 后,公式 (3) 等价改写为精简形式(公式 5):

𝑅(𝑆0, 𝑆1, …, 𝑆𝑛) = ∑𝑖∈𝑆0𝑣𝑖1+𝑉(𝑆0)(𝑟𝑖 + 𝑝𝑖∑𝑗∈𝑆𝑖𝑣𝑗𝑟𝑗1+𝑉(𝑆𝑖)) (5)\mathit{R}\left( \mathit{S}_{\text{0}}\text{, }\mathit{S}_{\text{1}}\text{, …, }\mathit{S}_{\mathit{n}} \right)\text{ = }\sum_{\mathit{i}\text{∈}\mathit{S}_{\text{0}}}^{}{\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\text{0}} \right)}\left( \mathit{r}_{\mathit{i}}\text{ + }\mathit{p}_{\mathit{i}}\frac{\sum_{\mathit{j}\text{∈}\mathit{S}_{\mathit{i}}}^{}{\mathit{v}_{\mathit{j}}\mathit{r}_{\mathit{j}}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\mathit{i}} \right)} \right)}\text{ (5)}

函数解释:该函数刻画了平台给定决策向量 (𝑆0, 𝑆1, …, 𝑆𝑛)\left( \mathit{S}_{\text{0}}\text{, }\mathit{S}_{\text{1}}\text{, …, }\mathit{S}_{\mathit{n}} \right) 时从单个顾客处获得的期望总收入。第一行展开式分为两部分:第一部分对应顾客既选了首选商品 𝑖∈𝑆0\mathit{i}\text{∈}\mathit{S}_{\text{0}} 又选了替代商品 𝑗∈𝑆𝑖\mathit{j}\text{∈}\mathit{S}_{\mathit{i}}(联合选择概率为 𝑣𝑖1+𝑉(𝑆0)×𝑣𝑗1+𝑉(𝑆𝑖)\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\text{0}} \right)}\text{×}\frac{\mathit{v}_{\mathit{j}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\mathit{i}} \right)}),此时若 𝑖\mathit{i} 有货(概率 𝑞𝑖\mathit{q}_{\mathit{i}})则获益 𝑓𝑖\mathit{f}_{\mathit{i}},若 𝑖\mathit{i} 缺货但 𝑗\mathit{j} 有货(概率 (1−𝑞𝑖)𝑞𝑗\left( \text{1−}\mathit{q}_{\mathit{i}} \right)\mathit{q}_{\mathit{j}})则获益 𝑓𝑗\mathit{f}_{\mathit{j}};第二部分对应顾客选了首选商品 𝑖\mathit{i} 但在第二阶段未选任何替代商品(概率为 𝑣𝑖1+𝑉(𝑆0)×11+𝑉(𝑆𝑖)\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\text{0}} \right)}\text{×}\frac{\text{1}}{\text{1+}\mathit{V}\left( \mathit{S}_{\mathit{i}} \right)}),此时唯有 𝑖\mathit{i} 有货才能获得期望收入 𝑞𝑖𝑓𝑖\mathit{q}_{\mathit{i}}\mathit{f}_{\mathit{i}}。合并同类项后得到公式 (3) 第二行及公式 (5):括号内的第一项 𝑟𝑖\mathit{r}_{\mathit{i}} 是首选商品 𝑖\mathit{i} 直接带来的期望收益,第二项 𝑝𝑖∑𝑗∈𝑆𝑖𝑣𝑗𝑟𝑗1+𝑉(𝑆𝑖)\mathit{p}_{\mathit{i}}\frac{\sum_{\mathit{j}\text{∈}\mathit{S}_{\mathit{i}}}^{}{\mathit{v}_{\mathit{j}}\mathit{r}_{\mathit{j}}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\mathit{i}} \right)} 则是在首选商品 𝑖\mathit{i} 发生缺货(以概率 𝑝𝑖\mathit{p}_{\mathit{i}} 触发)时,由第二阶段替代商品组合 𝑆𝑖\mathit{S}_{\mathit{i}} 发挥“兜底补偿(Recourse)”作用所挽回的期望收益。

(2)统一品类优化主问题目标函数(公式 4):

max(𝑆0, 𝑆1, …, 𝑆𝑛)∈2𝑁×⋯×2𝑁, 𝑆𝑖∈ℱ𝑖(𝑆0) ∀𝑖∈𝑁 𝑅(𝑆0, 𝑆1, …, 𝑆𝑛) (4)\underset{\left( \mathit{S}_{\text{0}}\text{, }\mathit{S}_{\text{1}}\text{, …, }\mathit{S}_{\mathit{n}} \right)\text{∈}\text{2}^{\mathit{N}}\text{×⋯×}\text{2}^{\mathit{N}}\text{, }\mathit{S}_{\mathit{i}}\text{∈}\mathit{\mathcal{F}}_{\mathit{i}}\left( \mathit{S}_{\text{0}} \right)\text{ ∀}\mathit{i}\text{∈}\mathit{N}}{\text{max}}\text{ }\mathit{R}\left( \mathit{S}_{\text{0}}\text{, }\mathit{S}_{\text{1}}\text{, …, }\mathit{S}_{\mathit{n}} \right)\text{ (4)}

函数解释:其中可行域映射 ℱ𝑖(𝑆0)\mathit{\mathcal{F}}_{\mathit{i}}\left( \mathit{S}_{\text{0}} \right) 统一刻画了两种业务模式:当令 ℱ𝑖(𝑆0) = {𝑆⊆𝑁 : 𝑆⊆𝑆0∖{𝑖}}\mathit{\mathcal{F}}_{\mathit{i}}\left( \mathit{S}_{\text{0}} \right)\text{ = }\left\{ \mathit{S}\text{⊆}\mathit{N}\text{ : }\mathit{S}\text{⊆}\mathit{S}_{\text{0}}\text{∖}\left\{ \mathit{i} \right\} \right\} 时,公式 (4) 即为自适应变体(Adaptive Variant),最优目标值记为 𝑍AD*\mathit{Z}_{\text{AD}}^{\text{*}};当令 ℱ𝑖(𝑆0) = {𝑆0∖{𝑖}}\mathit{\mathcal{F}}_{\mathit{i}}\left( \mathit{S}_{\text{0}} \right)\text{ = }\left\{ \mathit{S}_{\text{0}}\text{∖}\left\{ \mathit{i} \right\} \right\}(单元素集合族)时,公式 (4) 即为非自适应变体(Nonadaptive Variant),最优目标值记为 𝑍NA*\mathit{Z}_{\text{NA}}^{\text{*}}。

3.4 单阶段基准函数、自适应简化函数与代理问题函数(公式 7–10)

(1)单阶段无二次替代期望收益函数 𝑅¯(𝑆)\overline{\mathit{R}}\left( \mathit{S} \right) 与子全集最优单阶段收益函数 𝐹¯(𝑆)\overline{\mathit{F}}\left( \mathit{S} \right):

𝑅¯(𝑆) = ∑𝑖∈𝑆𝑣𝑖𝑟𝑖1+𝑉(𝑆) , 𝐹¯(𝑆) = max𝑄⊆𝑆 𝑅¯(𝑄)\overline{\mathit{R}}\left( \mathit{S} \right)\text{ = }\frac{\sum_{\mathit{i}\text{∈}\mathit{S}}^{}{\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}}}}{\text{1+}\mathit{V}\left( \mathit{S} \right)}\text{ , }\overline{\mathit{F}}\left( \mathit{S} \right)\text{ = }\underset{\mathit{Q}\text{⊆}\mathit{S}}{\text{max}}\text{ }\overline{\mathit{R}}\left( \mathit{Q} \right)

函数解释:𝑅¯(𝑆)\overline{\mathit{R}}\left( \mathit{S} \right) 表示在只进行单阶段选择(或者等价地,没有第二阶段替代机会、仅凭商品自身调整后收益 𝑟𝑖\mathit{r}_{\mathit{i}} 创收)时,提供商品组合 𝑆\mathit{S} 所能获得的期望收益。借助 𝑅¯(𝑆)\overline{\mathit{R}}\left( \mathit{S} \right),公式 (5) 可以极具洞察力地改写为 𝑅(𝑆0, 𝑆1, …, 𝑆𝑛) = 𝑅¯(𝑆0) + ∑𝑖∈𝑆0𝑣𝑖1+𝑉(𝑆0)𝑝𝑖𝑅¯(𝑆𝑖)\mathit{R}\left( \mathit{S}_{\text{0}}\text{, }\mathit{S}_{\text{1}}\text{, …, }\mathit{S}_{\mathit{n}} \right)\text{ = }\overline{\mathit{R}}\left( \mathit{S}_{\text{0}} \right)\text{ + }\sum_{\mathit{i}\text{∈}\mathit{S}_{\text{0}}}^{}{\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\text{0}} \right)}\mathit{p}_{\mathit{i}}\overline{\mathit{R}}\left( \mathit{S}_{\mathit{i}} \right)}。而 𝐹¯(𝑆)\overline{\mathit{F}}\left( \mathit{S} \right) 则表示当可用候选商品的范围被限制在子集 𝑆\mathit{S} 之内时,从中挑选一个最优子集 𝑄⊆𝑆\mathit{Q}\text{⊆}\mathit{S} 所能实现的最大单阶段期望收益。根据 Talluri and van Ryzin (2004) 的经典结论,𝐹¯(𝑆)\overline{\mathit{F}}\left( \mathit{S} \right) 可以通过将 𝑆\mathit{S} 中的商品按 𝑟𝑖\mathit{r}_{\mathit{i}} 从大到小排序并依次检验前缀子集在 𝑂(𝑛)\mathit{O}\left( \mathit{n} \right) 时间内轻松求出。

(2)自适应变体的单集合变量简化目标函数 ℛAD(𝑆)\mathit{\mathcal{R}}_{\text{AD}}\left( \mathit{S} \right)(公式 7):

𝑍AD* = max𝑆0⊆𝑁{∑𝑖∈𝑆0𝑣𝑖1+𝑉(𝑆0)(𝑟𝑖 + 𝑝𝑖max𝑆𝑖⊆𝑆0∖{𝑖} 𝑅¯(𝑆𝑖))} = max𝑆⊆𝑁{∑𝑖∈𝑆𝑣𝑖1+𝑉(𝑆)(𝑟𝑖 + 𝑝𝑖𝐹¯(𝑆∖{𝑖}))} (7)\mathit{Z}_{\text{AD}}^{\text{*}}\text{ = }\underset{\mathit{S}_{\text{0}}\text{⊆}\mathit{N}}{\text{max}}\left\{ \sum_{\mathit{i}\text{∈}\mathit{S}_{\text{0}}}^{}{\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\text{0}} \right)}\left( \mathit{r}_{\mathit{i}}\text{ + }\mathit{p}_{\mathit{i}}\underset{\mathit{S}_{\mathit{i}}\text{⊆}\mathit{S}_{\text{0}}\text{∖}\left\{ \mathit{i} \right\}}{\text{max}}\text{ }\overline{\mathit{R}}\left( \mathit{S}_{\mathit{i}} \right) \right)} \right\}\text{ = }\underset{\mathit{S}\text{⊆}\mathit{N}}{\text{max}}\left\{ \sum_{\mathit{i}\text{∈}\mathit{S}}^{}{\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S} \right)}\left( \mathit{r}_{\mathit{i}}\text{ + }\mathit{p}_{\mathit{i}}\overline{\mathit{F}}\left( \mathit{S}\text{∖}\left\{ \mathit{i} \right\} \right) \right)} \right\}\text{ (7)}

函数解释:在自适应变体中,一旦第一阶段展示集合 𝑆0=𝑆\mathit{S}_{\text{0}}\text{=}\mathit{S} 确定,对于每一个首选商品 𝑖∈𝑆\mathit{i}\text{∈}\mathit{S},第二阶段的最优替代集合 𝑆𝑖⊆𝑆∖{𝑖}\mathit{S}_{\mathit{i}}\text{⊆}\mathit{S}\text{∖}\left\{ \mathit{i} \right\} 相互独立,必然应当取能够最大化第二阶段期望收益 𝑅¯(𝑆𝑖)\overline{\mathit{R}}\left( \mathit{S}_{\mathit{i}} \right) 的子集,其最大收益恰好就是 𝐹¯(𝑆∖{𝑖})\overline{\mathit{F}}\left( \mathit{S}\text{∖}\left\{ \mathit{i} \right\} \right)。因此,公式 (7) 将原本含有 𝑛+1\mathit{n}\text{+1} 个集合决策变量 (𝑆0, 𝑆1, …, 𝑆𝑛)\left( \mathit{S}_{\text{0}}\text{, }\mathit{S}_{\text{1}}\text{, …, }\mathit{S}_{\mathit{n}} \right) 的自适应问题,精确压缩为仅含单个集合决策变量 𝑆⊆𝑁\mathit{S}\text{⊆}\mathit{N} 的优化问题,大括号内的目标函数记为 ℛAD(𝑆)\mathit{\mathcal{R}}_{\text{AD}}\left( \mathit{S} \right)。

(3)代理问题(Surrogate Problem)目标函数 ℛSR(𝑆)\mathit{\mathcal{R}}_{\text{SR}}\left( \mathit{S} \right)(公式 8):

𝑍SR* = max𝑆⊆𝑁 : 𝑀H⊆𝑆⊆𝑁H∪𝑁L{∑𝑖∈𝑀H𝑣𝑖1+𝑉(𝑆)(𝑟𝑖 + 𝑝𝑖𝐹¯(𝑆∖{𝑖})) + ∑𝑖∈𝑆∖𝑀H𝑣𝑖1+𝑉(𝑆)(𝑟𝑖 + 𝑝𝑖𝑅¯(𝑆∩𝑁H))} (8)\mathit{Z}_{\text{SR}}^{\text{*}}\text{ = }\underset{\mathit{S}\text{⊆}\mathit{N}\text{ : }\mathit{M}_{\text{H}}\text{⊆}\mathit{S}\text{⊆}\mathit{N}_{\text{H}}\text{∪}\mathit{N}_{\text{L}}}{\text{max}}\left\{ \sum_{\mathit{i}\text{∈}\mathit{M}_{\text{H}}}^{}{\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S} \right)}\left( \mathit{r}_{\mathit{i}}\text{ + }\mathit{p}_{\mathit{i}}\overline{\mathit{F}}\left( \mathit{S}\text{∖}\left\{ \mathit{i} \right\} \right) \right)}\text{ + }\sum_{\mathit{i}\text{∈}\mathit{S}\text{∖}\mathit{M}_{\text{H}}}^{}{\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S} \right)}\left( \mathit{r}_{\mathit{i}}\text{ + }\mathit{p}_{\mathit{i}}\overline{\mathit{R}}\left( \mathit{S}\text{∩}\mathit{N}_{\text{H}} \right) \right)} \right\}\text{ (8)}

函数解释:在公式 (7) 中,第二阶段收益项 𝐹¯(𝑆∖{𝑖})\overline{\mathit{F}}\left( \mathit{S}\text{∖}\left\{ \mathit{i} \right\} \right) 随每一个 𝑖∈𝑆\mathit{i}\text{∈}\mathit{S} 变化,最多有 𝑛\mathit{n} 个不同项,难以直接用动态规划求解。为此,作者令 𝑧* = max𝑆⊆𝑆*𝑅¯(𝑆)\mathit{z}^{\text{*}}\text{ = }\underset{\mathit{S}\text{⊆}\mathit{S}^{\text{*}}}{\text{max}}\overline{\mathit{R}}\left( \mathit{S} \right),将最优解 𝑆*\mathit{S}^{\mathit{*}} 划分为高收益子集 𝑆H* = {𝑖∈𝑆* : 𝑟𝑖≥𝑧*}\mathit{S}_{\text{H}}^{\text{*}}\text{ = }\left\{ \mathit{i}\text{∈}\mathit{S}^{\text{*}}\text{ : }\mathit{r}_{\mathit{i}}\text{≥}\mathit{z}^{\text{*}} \right\} 与低收益子集 𝑆L* = {𝑖∈𝑆* : 𝑟𝑖<𝑧*}\mathit{S}_{\text{L}}^{\text{*}}\text{ = }\left\{ \mathit{i}\text{∈}\mathit{S}^{\text{*}}\text{ : }\mathit{r}_{\mathit{i}}\text{<}\mathit{z}^{\text{*}} \right\},并构造关键集合:𝑀H\mathit{M}_{\text{H}} 为 𝑆H*\mathit{S}_{\text{H}}^{\text{*}} 中综合权重 𝑣𝑖𝑟𝑖\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}} 最大的前 ⌈1𝜖⌉\left\lceil \frac{\text{1}}{\mathit{\epsilon}} \right\rceil 个商品(Critical Set),𝑄H = {𝑖∈𝑈∖𝑀H : 𝑣𝑖𝑟𝑖 ≤ min𝑗∈𝑀H𝑣𝑗𝑟𝑗}\mathit{Q}_{\text{H}}\text{ = }\left\{ \mathit{i}\text{∈}\mathit{U}\text{∖}\mathit{M}_{\text{H}}\text{ : }\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}}\text{ ≤ }\underset{\mathit{j}\text{∈}\mathit{M}_{\text{H}}}{\text{min}}\mathit{v}_{\mathit{j}}\mathit{r}_{\mathit{j}} \right\}(其中 𝑈 = {𝑖∈𝑁 : 𝑟𝑖≥𝑧*}\mathit{U}\text{ = }\left\{ \mathit{i}\text{∈}\mathit{N}\text{ : }\mathit{r}_{\mathit{i}}\text{≥}\mathit{z}^{\text{*}} \right\}),令候选高收益集 𝑁H = 𝑀H∪𝑄H\mathit{N}_{\text{H}}\text{ = }\mathit{M}_{\text{H}}\text{∪}\mathit{Q}_{\text{H}},候选低收益集 𝑁L = 𝑁∖𝑈\mathit{N}_{\text{L}}\text{ = }\mathit{N}\text{∖}\mathit{U}。公式 (8) 定义的代理问题目标函数 ℛSR(𝑆)\mathit{\mathcal{R}}_{\text{SR}}\left( \mathit{S} \right) 代表一种“半自适应(混合)策略”:只有当顾客第一阶段选中的首选商品 𝑖\mathit{i} 属于核心关键集 𝑀H\mathit{M}_{\text{H}}(至多 ⌈1𝜖⌉\left\lceil \frac{\text{1}}{\mathit{\epsilon}} \right\rceil 项)时,平台才为她定制最优第二阶段替代集并获得 𝐹¯(𝑆∖{𝑖})\overline{\mathit{F}}\left( \mathit{S}\text{∖}\left\{ \mathit{i} \right\} \right);若顾客选中的 𝑖\mathit{i} 属于普通商品 𝑆∖𝑀H\mathit{S}\text{∖}\mathit{M}_{\text{H}},平台不再随 𝑖\mathit{i} 调整,而是统一提供高收益交集 𝑆∩𝑁H\mathit{S}\text{∩}\mathit{N}_{\text{H}} 作为替代集,获得统一收益 𝑅¯(𝑆∩𝑁H)\overline{\mathit{R}}\left( \mathit{S}\text{∩}\mathit{N}_{\text{H}} \right)。

(4)自适应代理问题的多维背包重构函数 𝑍KS*(𝑓, 𝑔, h, 𝑤)\mathit{Z}_{\text{KS}}^{\text{*}}\left( \mathit{f}\text{, }\mathit{g}\text{, }\mathit{h}\text{, }\mathit{w} \right)(公式 9)与超最优解条件(公式 10):

𝑍KS*(𝑓, 𝑔, h, 𝑤) = max𝑀H⊆𝑆⊆𝑁H∪𝑁L{∑𝑖∈𝑀H𝑣𝑖1+𝑔+h(𝑟𝑖 + 𝑝𝑖𝑓𝑖) + ∑𝑖∈𝑆∖𝑀H𝑣𝑖1+𝑔+h(𝑟𝑖 + 𝑝𝑖𝑤1+𝑔)\mathit{Z}_{\text{KS}}^{\text{*}}\left( \mathit{f}\text{, }\mathit{g}\text{, }\mathit{h}\text{, }\mathit{w} \right)\text{ = }\underset{\mathit{M}_{\text{H}}\text{⊆}\mathit{S}\text{⊆}\mathit{N}_{\text{H}}\text{∪}\mathit{N}_{\text{L}}}{\text{max}}\left\{ \sum_{\mathit{i}\text{∈}\mathit{M}_{\text{H}}}^{}{\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{g}\text{+}\mathit{h}}\left( \mathit{r}_{\mathit{i}}\text{ + }\mathit{p}_{\mathit{i}}\mathit{f}_{\mathit{i}} \right)}\text{ + }\sum_{\mathit{i}\text{∈}\mathit{S}\text{∖}\mathit{M}_{\text{H}}}^{}{\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{g}\text{+}\mathit{h}}\left( \mathit{r}_{\mathit{i}}\text{ + }\mathit{p}_{\mathit{i}}\frac{\mathit{w}}{\text{1+}\mathit{g}} \right)} \right.\

s.t. ∑𝑗∈𝑆∖{𝑖}𝑣𝑗[𝑟𝑗−𝑓𝑖]+ ≥ 𝑓𝑖 ∀𝑖∈𝑀H , ∑𝑗∈𝑆∩𝑁H𝑣𝑗 ≤ 𝑔 , ∑𝑗∈𝑆∩𝑁L𝑣𝑗 ≤ h , ∑𝑗∈𝑆∩𝑁H𝑣𝑗𝑟𝑗 ≥ 𝑤 } (9)\text{s.t. }\sum_{\mathit{j}\text{∈}\mathit{S}\text{∖}\left\{ \mathit{i} \right\}}^{}{\mathit{v}_{\mathit{j}}\left\lbrack \mathit{r}_{\mathit{j}}\text{−}\mathit{f}_{\mathit{i}} \right\rbrack^{\text{+}}}\text{ ≥ }\mathit{f}_{\mathit{i}}\text{ ∀}\mathit{i}\text{∈}\mathit{M}_{\text{H}}\text{ , }\sum_{\mathit{j}\text{∈}\mathit{S}\text{∩}\mathit{N}_{\text{H}}}^{}\mathit{v}_{\mathit{j}}\text{ ≤ }\mathit{g}\text{ , }\sum_{\mathit{j}\text{∈}\mathit{S}\text{∩}\mathit{N}_{\text{L}}}^{}\mathit{v}_{\mathit{j}}\text{ ≤ }\mathit{h}\text{ , }\sum_{\mathit{j}\text{∈}\mathit{S}\text{∩}\mathit{N}_{\text{H}}}^{}{\mathit{v}_{\mathit{j}}\mathit{r}_{\mathit{j}}}\text{ ≥ }\mathit{w}\text{ \}}\text{ (9)}

函数解释:在公式 (9) 中,作者对代理问题中的 ⌈1𝜖⌉+3\left\lceil \frac{\text{1}}{\mathit{\epsilon}} \right\rceil\text{+3} 个未知耦合量给出猜测常数向量 (𝑓, 𝑔, h, 𝑤)\left( \mathit{f}\text{, }\mathit{g}\text{, }\mathit{h}\text{, }\mathit{w} \right):其中 𝑓𝑖\mathit{f}_{\mathit{i}} 是对 𝐹¯(𝑆∖{𝑖})\overline{\mathit{F}}\left( \mathit{S}\text{∖}\left\{ \mathit{i} \right\} \right) 的下界猜测(利用等价性质 𝐹¯(𝑆∖{𝑖}) ≥ 𝑓𝑖 ⟺ ∑𝑗∈𝑆∖{𝑖}𝑣𝑗[𝑟𝑗−𝑓𝑖]+ ≥ 𝑓𝑖\overline{\mathit{F}}\left( \mathit{S}\text{∖}\left\{ \mathit{i} \right\} \right)\text{ ≥ }\mathit{f}_{\mathit{i}}\text{ ⟺ }\sum_{\mathit{j}\text{∈}\mathit{S}\text{∖}\left\{ \mathit{i} \right\}}^{}{\mathit{v}_{\mathit{j}}\left\lbrack \mathit{r}_{\mathit{j}}\text{−}\mathit{f}_{\mathit{i}} \right\rbrack^{\text{+}}}\text{ ≥ }\mathit{f}_{\mathit{i}} 转化为线性覆盖约束),𝑔\mathit{g} 和 h\mathit{h} 分别是 𝑉(𝑆∩𝑁H)\mathit{V}\left( \mathit{S}\text{∩}\mathit{N}_{\text{H}} \right) 和 𝑉(𝑆∩𝑁L)\mathit{V}\left( \mathit{S}\text{∩}\mathit{N}_{\text{L}} \right) 的上界猜测(打包约束),𝑤\mathit{w} 是 𝑊(𝑆∩𝑁H)\mathit{W}\left( \mathit{S}\text{∩}\mathit{N}_{\text{H}} \right) 的下界猜测(覆盖约束)。固定 (𝑓, 𝑔, h, 𝑤)\left( \mathit{f}\text{, }\mathit{g}\text{, }\mathit{h}\text{, }\mathit{w} \right) 后,目标函数关于各个商品 𝑖∈𝑆\mathit{i}\text{∈}\mathit{S} 完全线性可加,从而转化为标准的多维背包问题。公式 (10) 则定义了该背包问题的“超最优解(Superoptimal Solution)”:即目标函数值不低于 𝑍KS*(𝑓, 𝑔, h, 𝑤)\mathit{Z}_{\text{KS}}^{\text{*}}\left( \mathit{f}\text{, }\mathit{g}\text{, }\mathit{h}\text{, }\mathit{w} \right),且对打包上界约束放宽至 (1+𝜖)𝑔\left( \text{1+}\mathit{\epsilon} \right)\mathit{g}、(1+𝜖)h\left( \text{1+}\mathit{\epsilon} \right)\mathit{h},对覆盖下界约束放宽至 11+𝜖𝑓𝑖\frac{\text{1}}{\text{1+}\mathit{\epsilon}}\mathit{f}_{\mathit{i}} 和 11+𝜖𝑤\frac{\text{1}}{\text{1+}\mathit{\epsilon}}\mathit{w}。

3.5 非自适应变体函数、MIP 线性化函数与实证评估指标(公式 11–14)

(1)非自适应变体目标函数(公式 11)及其二维背包重构函数(公式 12):

𝑍NA* = max𝑆⊆𝑁{∑𝑖∈𝑆𝑣𝑖1+𝑉(𝑆)(𝑟𝑖 + 𝑝𝑖∑𝑗∈𝑆∖{𝑖}𝑣𝑗𝑟𝑗1+𝑉(𝑆∖{𝑖}))} (11)\mathit{Z}_{\text{NA}}^{\text{*}}\text{ = }\underset{\mathit{S}\text{⊆}\mathit{N}}{\text{max}}\left\{ \sum_{\mathit{i}\text{∈}\mathit{S}}^{}{\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S} \right)}\left( \mathit{r}_{\mathit{i}}\text{ + }\mathit{p}_{\mathit{i}}\frac{\sum_{\mathit{j}\text{∈}\mathit{S}\text{∖}\left\{ \mathit{i} \right\}}^{}{\mathit{v}_{\mathit{j}}\mathit{r}_{\mathit{j}}}}{\text{1+}\mathit{V}\left( \mathit{S}\text{∖}\left\{ \mathit{i} \right\} \right)} \right)} \right\}\text{ (11)}

𝑍KS*(𝑔, 𝑤) = max{𝑖*, 𝑗*}⊆𝑆⊆{𝑖*, 𝑗*}∪𝑁L{∑𝑖∈𝑆𝑣𝑖1+𝑔+𝑣𝑖*(𝑟𝑖 + 𝑝𝑖𝑤 + 𝑣𝑗*𝑟𝑗* − 𝑣𝑖𝑟𝑖1 + 𝑔 + 𝑣𝑖* − 𝑣𝑖) : ∑𝑖∈𝑆∖{𝑖*}𝑣𝑖 ≤ 𝑔 , ∑𝑖∈𝑆∖{𝑗*}𝑣𝑖𝑟𝑖 ≥ 𝑤} (12)\mathit{Z}_{\text{KS}}^{\text{*}}\left( \mathit{g}\text{, }\mathit{w} \right)\text{ = }\underset{\left\{ \mathit{i}^{\text{*}}\text{, }\mathit{j}^{\text{*}} \right\}\text{⊆}\mathit{S}\text{⊆}\left\{ \mathit{i}^{\text{*}}\text{, }\mathit{j}^{\text{*}} \right\}\text{∪}\mathit{N}_{\text{L}}}{\text{max}}\left\{ \sum_{\mathit{i}\text{∈}\mathit{S}}^{}{\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{g}\text{+}\mathit{v}_{\mathit{i}^{\text{*}}}}\left( \mathit{r}_{\mathit{i}}\text{ + }\mathit{p}_{\mathit{i}}\frac{\mathit{w}\text{ + }\mathit{v}_{\mathit{j}^{\text{*}}}\mathit{r}_{\mathit{j}^{\text{*}}}\text{ − }\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}}}{\text{1 + }\mathit{g}\text{ + }\mathit{v}_{\mathit{i}^{\text{*}}}\text{ − }\mathit{v}_{\mathit{i}}} \right)}\text{ : }\sum_{\mathit{i}\text{∈}\mathit{S}\text{∖}\left\{ \mathit{i}^{\text{*}} \right\}}^{}\mathit{v}_{\mathit{i}}\text{ ≤ }\mathit{g}\text{ , }\sum_{\mathit{i}\text{∈}\mathit{S}\text{∖}\left\{ \mathit{j}^{\text{*}} \right\}}^{}{\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}}}\text{ ≥ }\mathit{w} \right\}\text{ (12)}

函数解释:公式 (11) 将非自适应规则 𝑆𝑖 = 𝑆∖{𝑖}\mathit{S}_{\mathit{i}}\text{ = }\mathit{S}\text{∖}\left\{ \mathit{i} \right\} 代入期望收益函数,此时第二阶段的期望收益直接等于剔除首选商品 𝑖\mathit{i} 后的剩余集合 𝑆∖{𝑖}\mathit{S}\text{∖}\left\{ \mathit{i} \right\} 的单阶段收益。在公式 (12) 中,𝑖* = arg max𝑖∈𝑆*𝑣𝑖\mathit{i}^{\text{*}}\text{ = }\text{arg max}_{\mathit{i}\text{∈}\mathit{S}^{\text{*}}}\mathit{v}_{\mathit{i}} 是最优解中偏好权重最大的商品,𝑗* = arg max𝑖∈𝑆*𝑣𝑖𝑟𝑖\mathit{j}^{\text{*}}\text{ = }\text{arg max}_{\mathit{i}\text{∈}\mathit{S}^{\text{*}}}\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}} 是最优解中综合权重最大的商品,𝑔\mathit{g} 和 𝑤\mathit{w} 分别猜测 𝑉(𝑆*∖{𝑖*})\mathit{V}\left( \mathit{S}^{\text{*}}\text{∖}\left\{ \mathit{i}^{\text{*}} \right\} \right) 和 𝑊(𝑆*∖{𝑗*})\mathit{W}\left( \mathit{S}^{\text{*}}\text{∖}\left\{ \mathit{j}^{\text{*}} \right\} \right)。由于对任意候选商品 𝑖\mathit{i} 均有 𝑣𝑖* − 𝑣𝑖 ≥ 0\mathit{v}_{\mathit{i}^{\text{*}}}\text{ − }\mathit{v}_{\mathit{i}}\text{ ≥ 0} 以及 𝑣𝑗*𝑟𝑗* − 𝑣𝑖𝑟𝑖 ≥ 0\mathit{v}_{\mathit{j}^{\text{*}}}\mathit{r}_{\mathit{j}^{\text{*}}}\text{ − }\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}}\text{ ≥ 0},公式 (12) 分式中的分子与分母均由正数项相加构成,从而保证了误差的可控性。

(2)混合整数规划(MIP)线性化目标与约束系统(公式 13):

max ∑𝑖∈𝑁𝑟𝑖𝑦𝑖 + ∑𝑖∈𝑁∑𝑗∈𝑁∖{𝑖}𝑝𝑖𝑟𝑗𝑤𝑖𝑗 (13)\text{max }\sum_{\mathit{i}\text{∈}\mathit{N}}^{}{\mathit{r}_{\mathit{i}}\mathit{y}_{\mathit{i}}}\text{ + }\sum_{\mathit{i}\text{∈}\mathit{N}}^{}{\sum_{\mathit{j}\text{∈}\mathit{N}\text{∖}\left\{ \mathit{i} \right\}}^{}{\mathit{p}_{\mathit{i}}\mathit{r}_{\mathit{j}}\mathit{w}_{\mathit{i}\mathit{j}}}}\text{ (13)}

函数解释:在公式 (13) 中,二元变量 𝑥𝑖 = 1(𝑖∈𝑆0)\mathit{x}_{\mathit{i}}\text{ = }\text{1}\left( \mathit{i}\text{∈}\mathit{S}_{\text{0}} \right) 表示商品 𝑖\mathit{i} 是否入选第一阶段商品集,二元变量 𝑧𝑖𝑗 = 1(𝑗∈𝑆𝑖)\mathit{z}_{\mathit{i}\mathit{j}}\text{ = }\text{1}\left( \mathit{j}\text{∈}\mathit{S}_{\mathit{i}} \right) 表示当顾客首选 𝑖\mathit{i} 时商品 𝑗\mathit{j} 是否入选第二阶段替代集(若添加约束 𝑧𝑖𝑗 = 𝑥𝑗\mathit{z}_{\mathit{i}\mathit{j}}\text{ = }\mathit{x}_{\mathit{j}} 则退化为非自适应模型)。连续变量 𝑦0 = 11+𝑉(𝑆0)\mathit{y}_{\text{0}}\text{ = }\frac{\text{1}}{\text{1+}\mathit{V}\left( \mathit{S}_{\text{0}} \right)} 与 𝑦𝑖 = 𝑥𝑖𝑣𝑖1+𝑉(𝑆0)\mathit{y}_{\mathit{i}}\text{ = }\frac{\mathit{x}_{\mathit{i}}\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\text{0}} \right)} 分别代表第一阶段不购买概率与选择商品 𝑖\mathit{i} 的概率;连续变量 𝑤𝑖0 = 𝑦𝑖1+𝑉(𝑆𝑖)\mathit{w}_{\mathit{i}\text{0}}\text{ = }\frac{\mathit{y}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\mathit{i}} \right)} 与 𝑤𝑖𝑗 = 𝑦𝑖𝑧𝑖𝑗𝑣𝑗1+𝑉(𝑆𝑖)\mathit{w}_{\mathit{i}\mathit{j}}\text{ = }\frac{\mathit{y}_{\mathit{i}}\mathit{z}_{\mathit{i}\mathit{j}}\mathit{v}_{\mathit{j}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\mathit{i}} \right)} 分别代表顾客第一阶段选 𝑖\mathit{i} 且第二阶段不选替代商品或选择替代商品 𝑗\mathit{j} 的联合概率。通过七组 Big-M 线性不等式约束:𝑦0 + ∑𝑖∈𝑁𝑦𝑖 = 1\mathit{y}_{\text{0}}\text{ + }\sum_{\mathit{i}\text{∈}\mathit{N}}^{}\mathit{y}_{\mathit{i}}\text{ = 1}、𝑦0 − (1−𝑥𝑖) ≤ 𝑦𝑖𝑣𝑖 ≤ 𝑦0\mathit{y}_{\text{0}}\text{ − }\left( \text{1−}\mathit{x}_{\mathit{i}} \right)\text{ ≤ }\frac{\mathit{y}_{\mathit{i}}}{\mathit{v}_{\mathit{i}}}\text{ ≤ }\mathit{y}_{\text{0}}、𝑦𝑖 ≤ 𝑥𝑖\mathit{y}_{\mathit{i}}\text{ ≤ }\mathit{x}_{\mathit{i}}、𝑤𝑖0 + ∑𝑗∈𝑁∖{𝑖}𝑤𝑖𝑗 = 𝑦𝑖\mathit{w}_{\mathit{i}\text{0}}\text{ + }\sum_{\mathit{j}\text{∈}\mathit{N}\text{∖}\left\{ \mathit{i} \right\}}^{}\mathit{w}_{\mathit{i}\mathit{j}}\text{ = }\mathit{y}_{\mathit{i}}、𝑤𝑖0 − (1−𝑧𝑖𝑗) ≤ 𝑤𝑖𝑗𝑣𝑗 ≤ 𝑤𝑖0\mathit{w}_{\mathit{i}\text{0}}\text{ − }\left( \text{1−}\mathit{z}_{\mathit{i}\mathit{j}} \right)\text{ ≤ }\frac{\mathit{w}_{\mathit{i}\mathit{j}}}{\mathit{v}_{\mathit{j}}}\text{ ≤ }\mathit{w}_{\mathit{i}\text{0}}、𝑤𝑖𝑗 ≤ 𝑧𝑖𝑗 ≤ 𝑥𝑗\mathit{w}_{\mathit{i}\mathit{j}}\text{ ≤ }\mathit{z}_{\mathit{i}\mathit{j}}\text{ ≤ }\mathit{x}_{\mathit{j}},非线性分式目标被完全等价地转化为线性混合整数规划。

(3)市场份额与服务水平评估函数(公式 14):总市场份额 FMS\text{FMS}、净市场份额 NMS\text{NMS} 与退款率 RFR\text{RFR}:

FMS(𝑆0) = 100 × ∑𝑖∈𝑆0𝑣𝑖1+𝑉(𝑆0) , NMS(𝑆0, 𝑆1, …, 𝑆𝑛) = 100 × ∑𝑖∈𝑆0𝑣𝑖1+𝑉(𝑆0)(𝑞𝑖 + (1−𝑞𝑖)∑𝑗∈𝑆𝑖𝑣𝑗1+𝑉(𝑆𝑖)𝑞𝑗)\text{FMS}\left( \mathit{S}_{\text{0}} \right)\text{ = 100 × }\frac{\sum_{\mathit{i}\text{∈}\mathit{S}_{\text{0}}}^{}\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\text{0}} \right)}\text{ , }\text{NMS}\left( \mathit{S}_{\text{0}}\text{, }\mathit{S}_{\text{1}}\text{, …, }\mathit{S}_{\mathit{n}} \right)\text{ = 100 × }\sum_{\mathit{i}\text{∈}\mathit{S}_{\text{0}}}^{}{\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\text{0}} \right)}\left( \mathit{q}_{\mathit{i}}\text{ + }\left( \text{1−}\mathit{q}_{\mathit{i}} \right)\sum_{\mathit{j}\text{∈}\mathit{S}_{\mathit{i}}}^{}{\frac{\mathit{v}_{\mathit{j}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\mathit{i}} \right)}\mathit{q}_{\mathit{j}}} \right)}

RFR(𝑆0, 𝑆1, …, 𝑆𝑛) = FMS(𝑆0) − NMS(𝑆0, 𝑆1, …, 𝑆𝑛) (14)\text{RFR}\left( \mathit{S}_{\text{0}}\text{, }\mathit{S}_{\text{1}}\text{, …, }\mathit{S}_{\mathit{n}} \right)\text{ = }\text{FMS}\left( \mathit{S}_{\text{0}} \right)\text{ − }\text{NMS}\left( \mathit{S}_{\text{0}}\text{, }\mathit{S}_{\text{1}}\text{, …, }\mathit{S}_{\mathit{n}} \right)\text{ (14)}

函数解释:这三个函数从客户服务与运营履约维度评估品类方案:总市场份额(Full Market Share, FMS)衡量进入平台的顾客中下单挑选了首选商品(而非直接空手离开)的百分比;净市场份额(Net Market Share, NMS)即令公式 (3) 中所有商品价格 𝑓𝑖=1\mathit{f}_{\mathit{i}}\text{=1} 时的期望值乘以 100,衡量最终通过首选商品或替代商品成功收到货物的顾客占全体访问顾客的百分比(即订单成功履约率);退款率(Refund Rate, RFR)则是下单顾客中因首选商品与替代商品双双缺货(或未选替代商品且首选缺货)而最终两手空空、被迫接受退款的顾客占全体访问顾客的百分比。此外,在第 8.1 节验证 MNL 模型样本外预测精度时,作者还定义了 𝑘-hit rate\mathit{k}\text{-hit rate}(顾客实际首选商品落入模型预测偏好概率前 𝑘\mathit{k} 名商品集合 𝑆𝑡(𝑘)\mathit{S}_{\mathit{t}}\left( \mathit{k} \right) 的比例:100 × ∑𝑡∈𝒯(𝑐,𝑟)1(𝑖𝑡∈𝑆𝑡(𝑘))∑𝑡∈𝒯(𝑐,𝑟)1(𝑖𝑡≠∅)\text{100 × }\frac{\sum_{\mathit{t}\text{∈}\mathit{\mathcal{T}}_{\left( \mathit{c}\text{,}\mathit{r} \right)}}^{}{\text{1}\left( \mathit{i}_{\mathit{t}}\text{∈}\mathit{S}_{\mathit{t}}\left( \mathit{k} \right) \right)}}{\sum_{\mathit{t}\text{∈}\mathit{\mathcal{T}}_{\left( \mathit{c}\text{,}\mathit{r} \right)}}^{}{\text{1}\left( \mathit{i}_{\mathit{t}}\text{≠∅} \right)}})以及平均绝对误差 MAE(观测首选频率与模型预测概率 𝜓𝑖(𝑆𝑡) = 𝑣𝑖1+𝑉(𝑆𝑡)\mathit{\psi}_{\mathit{i}}\left( \mathit{S}_{\mathit{t}} \right)\text{ = }\frac{\mathit{v}_{\mathit{i}}}{\text{1+}\mathit{V}\left( \mathit{S}_{\mathit{t}} \right)} 之间的平均绝对偏差)。

四、 命题、引理、定理与推论的通俗举例解析(不含证明过程)

本节对全文所有的核心命题(Propositions)、引理(Lemmas)、定理(Theorems)以及重要推论与界限结论进行系统梳理。遵照要求,本节略去繁琐的数学证明推导过程,重点通过直观的商业场景与具体数值算例(Numerical Examples)来阐明每一条结论的内在逻辑与实际含义。

4.1 计算复杂性结论(第 2 节 & Online Appendix A):两类变体均为 NP-Hard

【结论陈述】在商品存在缺货风险且允许指定替代选项的品类优化问题 (4) 中,无论是非自适应变体(𝑆𝑖 = 𝑆0∖{𝑖}\mathit{S}_{\mathit{i}}\text{ = }\mathit{S}_{\text{0}}\text{∖}\left\{ \mathit{i} \right\})还是自适应变体(𝑆𝑖 ⊆ 𝑆0∖{𝑖}\mathit{S}_{\mathit{i}}\text{ ⊆ }\mathit{S}_{\text{0}}\text{∖}\left\{ \mathit{i} \right\}),寻找最大化期望收益的商品组合均为 NP-hard 问题。

【通俗举例解析:为什么加入替代选项后,原本简单的按价格排序规则失效了?】

在传统的无缺货单阶段 MNL 模型中,Talluri and van Ryzin (2004) 证明了最优组合必然满足“按收益排序(Revenue-Ordered)”性质——只需把所有商品按收益从高到低排列,选取前 𝑘\mathit{k} 个高收益商品即可,绝对不会跳过某个高收益商品去选低收益商品。然而,一旦引入“缺货与替代选项”,每个商品在组合中同时扮演双重角色:第一阶段的首选引流角色与第二阶段的替补兜底角色。

具体数值例子:假设生鲜平台上有 3 种牛奶:商品 1(有机鲜奶:售价 𝑓1=10\mathit{f}_{\text{1}}\text{=10} 元,有货率 𝑞1=0.5\mathit{q}_{\text{1}}\text{=0.5},调整后收益 𝑟1=5\mathit{r}_{\text{1}}\text{=5} 元,偏好权重 𝑣1=2\mathit{v}_{\text{1}}\text{=2})、商品 2(网红鲜奶:售价 𝑓2=9\mathit{f}_{\text{2}}\text{=9} 元,极易缺货 𝑞2=0.5\mathit{q}_{\text{2}}\text{=0.5},调整后收益 𝑟2=4.5\mathit{r}_{\text{2}}\text{=4.5} 元,但偏好权重极高 𝑣2=10\mathit{v}_{\text{2}}\text{=10})、商品 3(常青基础鲜奶:售价 𝑓3=4.2\mathit{f}_{\text{3}}\text{=4.2} 元,永远有货 𝑞3=1.0\mathit{q}_{\text{3}}\text{=1.0},调整后收益 𝑟3=4.2\mathit{r}_{\text{3}}\text{=4.2} 元,偏好权重 𝑣3=2\mathit{v}_{\text{3}}\text{=2})。按调整后收益排序为 𝑟1(5) > 𝑟2(4.5) > 𝑟3(4.2)\mathit{r}_{\text{1}}\text{(5) > }\mathit{r}_{\text{2}}\text{(4.5) > }\mathit{r}_{\text{3}}\text{(4.2)}。如果我们在第一阶段展示 {1, 2}\left\{ \text{1, 2} \right\},大部分顾客会被高权重的网红奶(商品 2)吸引,但在商品 1 缺货时,替补的商品 2 也有 50% 概率缺货;反之,如果我们跳过商品 2 而选择展示 {1, 3}\left\{ \text{1, 3} \right\},虽然商品 3 的调整后收益(4.2 元)低于商品 2(4.5 元),但商品 3 不会在第一阶段过度分流商品 1 的高价客源,且当商品 1 缺货(50% 概率)时,商品 3 能以 100% 的有货率稳稳兜底!这种“第一阶段防分流”与“第二阶段保履约”之间的复杂权衡打破了单调排序性质,使得问题在组合爆炸下成为 NP-hard。

4.2 命题 3.1(Proposition 3.1):自适应价值的上界(Upper Bound on Value of Adaptivity)

【命题陈述】记 𝑍AD*\mathit{Z}_{\text{AD}}^{\text{*}} 和 𝑍NA*\mathit{Z}_{\text{NA}}^{\text{*}} 分别为优化问题 (4) 在自适应变体和非自适应变体下的最优期望收益目标值,则恒有:

𝑍NA* ≤ 𝑍AD* ≤ 2 𝑍NA*\mathit{Z}_{\text{NA}}^{\text{*}}\text{ ≤ }\mathit{Z}_{\text{AD}}^{\text{*}}\text{ ≤ 2 }\mathit{Z}_{\text{NA}}^{\text{*}}

【通俗举例解析:为什么动态定制替代列表最多只能让收益翻倍?】

核心意思:第一重不等式 𝑍NA* ≤ 𝑍AD*\mathit{Z}_{\text{NA}}^{\text{*}}\text{ ≤ }\mathit{Z}_{\text{AD}}^{\text{*}} 表明自适应策略因为允许根据顾客的首选商品灵活定制第二阶段替代列表,其收益必然不低于一刀切的非自适应策略;第二重不等式 𝑍AD* ≤ 2 𝑍NA*\mathit{Z}_{\text{AD}}^{\text{*}}\text{ ≤ 2 }\mathit{Z}_{\text{NA}}^{\text{*}} 则指出,无论平台如何精妙地针对每个首选商品定制第二阶段替代列表,它带来的期望总收益绝对不会超过非自适应最优收益的 2 倍。

具体数值例子:为什么上界恰好是 2?因为一位顾客最多只在两个阶段各产生一次购买机会(首选商品履约,或者首选缺货时由替代商品履约)。假设单阶段无替代情况下,平台上最优商品组合 𝑆*\mathit{S}^{\mathit{*}} 能创造的最大单阶段期望收益为 𝑅¯(𝑆*) = 10\overline{\mathit{R}}\left( \mathit{S}^{\text{*}} \right)\text{ = 10} 元。在自适应策略下,哪怕平台遇到了最理想的情况:(1)第一阶段获得的期望收益达到了单阶段理论天花板 10 元;(2)第一阶段所有商品恰好 100% 缺货触发第二阶段(实际上如果 100% 缺货,第一阶段收益就会是 0,这里做最宽松的极限叠加),且第二阶段针对每个商品定制的替代组合又赚到了单阶段理论天花板 10 元。即便把这两个阶段的天花板强行相加,自适应策略的总期望收益至多也只能达到 10 + 10 = 20\text{10 + 10 = 20} 元。与此同时,如果平台在非自适应模式下直接把 𝑆*\mathit{S}^{\mathit{*}} 拿出来展示,单靠第一阶段就已经稳拿至少 10 元(加上第二阶段自然替补还会高于 10 元),即 𝑍NA* ≥ 10\mathit{Z}_{\text{NA}}^{\text{*}}\text{ ≥ 10} 元。因此,自适应策略的最优收益(至多 20 元)绝不可能超过非自适应最优收益(至少 10 元)的 2 倍。

4.3 推论 3.1 与紧性结论(第 3 节):朴素单阶段解的 1/2 近似保证及其紧性算例

【推论陈述】令 𝑆* = arg max𝑆⊆𝑁𝑅¯(𝑆)\mathit{S}^{\text{*}}\text{ = }\text{arg max}_{\mathit{S}\text{⊆}\mathit{N}}\overline{\mathit{R}}\left( \mathit{S} \right) 为完全忽略替代选项、仅最大化单阶段期望收益 𝑅¯(𝑆)\overline{\mathit{R}}\left( \mathit{S} \right) 的最优商品组合(可通过按 𝑟𝑖\mathit{r}_{\mathit{i}} 从高到低排序在 𝑂(𝑛 log 𝑛)\mathit{O}\left( \mathit{n}\text{ log }\mathit{n} \right) 时间内求出)。将 (𝑆*, 𝑆*∖{1}, …, 𝑆*∖{𝑛})\left( \mathit{S}^{\text{*}}\text{, }\mathit{S}^{\text{*}}\text{∖}\left\{ \text{1} \right\}\text{, …, }\mathit{S}^{\text{*}}\text{∖}\left\{ \mathit{n} \right\} \right) 作为两阶段品类决策(称为朴素解 Naive Solution),则该解对自适应变体和非自适应变体均构成 12\frac{\text{1}}{\text{2}}-近似解,即 𝑅(𝑆*, 𝑆*∖{1}, …, 𝑆*∖{𝑛}) ≥ 12𝑍AD* ≥ 12𝑍NA*\mathit{R}\left( \mathit{S}^{\text{*}}\text{, }\mathit{S}^{\text{*}}\text{∖}\left\{ \text{1} \right\}\text{, …, }\mathit{S}^{\text{*}}\text{∖}\left\{ \mathit{n} \right\} \right)\text{ ≥ }\frac{\text{1}}{\text{2}}\mathit{Z}_{\text{AD}}^{\text{*}}\text{ ≥ }\frac{\text{1}}{\text{2}}\mathit{Z}_{\text{NA}}^{\text{*}},且该 12\frac{\text{1}}{\text{2}} 近似比是紧的(Tight)。

【通俗举例解析:为什么忽略替代选项的朴素算法会损失整整一半的收益?】

具体数值例子(基于论文第 2468 页构造的实例):假设平台上有 2 种商品,取极小正数 𝜖 = 0.01\mathit{\epsilon}\text{ = 0.01}:
• 商品 1(高价稳定款):调整后收益 𝑟1 = 1\mathit{r}_{\text{1}}\text{ = 1} 元,偏好权重 𝑣1 = 1\mathit{v}_{\text{1}}\text{ = 1},缺货概率 𝑝1 = 0\mathit{p}_{\text{1}}\text{ = 0}(100% 有货,售价 𝑓1=1\mathit{f}_{\text{1}}\text{=1} 元);
• 商品 2(网红易缺货引流款):调整后收益 𝑟2 = 12 − 𝜖 = 0.49\mathit{r}_{\text{2}}\text{ = }\frac{\text{1}}{\text{2}}\text{ − }\mathit{\epsilon}\text{ = 0.49} 元,偏好权重极高 𝑣2 = 1𝜖 = 100\mathit{v}_{\text{2}}\text{ = }\frac{\text{1}}{\mathit{\epsilon}}\text{ = 100},但缺货概率极高 𝑝2 = 1 − 𝜖 = 0.99\mathit{p}_{\text{2}}\text{ = 1 − }\mathit{\epsilon}\text{ = 0.99}(有货率仅 1%)。

(1)朴素算法的决策:朴素算法只看单阶段收益 𝑅¯(𝑆)\overline{\mathit{R}}\left( \mathit{S} \right)。如果只摆商品 1,单阶段期望收益为 𝑅¯({1}) = 1×11+1 = 0.50\overline{\mathit{R}}\left( \left\{ \text{1} \right\} \right)\text{ = }\frac{\text{1×1}}{\text{1+1}}\text{ = 0.50} 元;如果同时摆商品 1 和商品 2,由于商品 2 权重高达 100,会把几乎所有顾客吸走,单阶段期望收益降为 𝑅¯({1, 2}) = 1×1 + 100×0.491+1+100 = 50102 ≈ 0.4902 < 0.50\overline{\mathit{R}}\left( \left\{ \text{1, 2} \right\} \right)\text{ = }\frac{\text{1×1 + 100×0.49}}{\text{1+1+100}}\text{ = }\frac{\text{50}}{\text{102}}\text{ ≈ 0.4902 < 0.50} 元。因此,朴素算法果断剔除商品 2,令 𝑆* = {1}\mathit{S}^{\text{*}}\text{ = }\left\{ \text{1} \right\}。由于只展示了 1 种商品,第二阶段替代集为空集,平台最终获得的期望总收益就是 0.50 元。

(2)考虑替代选项的最优决策:如果我们把商品 1 和商品 2 同时摆上货架(𝑆0 = {1, 2}\mathit{S}_{\text{0}}\text{ = }\left\{ \text{1, 2} \right\}),奇迹发生了!第一阶段高达 100102 ≈ 98.04%\frac{\text{100}}{\text{102}}\text{ ≈ 98.04\%} 的顾客会被网红款商品 2 吸引而下单(不会空手离开),不仅直接贡献了 𝑟2 = 0.49\mathit{r}_{\text{2}}\text{ = 0.49} 元的首选期望收益,更重要的是:当商品 2 以 99% 的概率发生缺货时,这部分已被锁定在购物车里的顾客在第二阶段面对唯一替代品——商品 1 时,有 𝑣11+𝑣1 = 12 = 50%\frac{\mathit{v}_{\text{1}}}{\text{1+}\mathit{v}_{\text{1}}}\text{ = }\frac{\text{1}}{\text{2}}\text{ = 50\%} 的概率接受商品 1 作为替代并再贡献 0.99 × 0.5 × 1 ≈ 0.495\text{0.99 × 0.5 × 1 ≈ 0.495} 元的替补收益!两者合计,展示 {1, 2}\left\{ \text{1, 2} \right\} 的两阶段期望总收益高达 0.975 元(当 𝜖→0\mathit{\epsilon}\text{→0} 时趋近于 1.00 元)。可见,忽略替代选项的朴素算法因为害怕商品 2 分流而将其剔除,白白损失了将近 50%(即 1/2) 的总收益!

4.4 结论 3.1(第 3.1 节):自适应价值的下界算例(Lower Bound of 4/3 on Value of Adaptivity)

【结论陈述】存在一类包含 𝑛+1\mathit{n}\text{+1} 个商品的品类优化问题实例,使得自适应变体的最优期望收益 𝑍AD*\mathit{Z}_{\text{AD}}^{\text{*}} 与非自适应变体的最优期望收益 𝑍NA*\mathit{Z}_{\text{NA}}^{\text{*}} 之比满足 lim𝑛→∞𝑍AD*𝑍NA* = 43\underset{\mathit{n}\text{→∞}}{\text{lim}}\frac{\mathit{Z}_{\text{AD}}^{\text{*}}}{\mathit{Z}_{\text{NA}}^{\text{*}}}\text{ = }\frac{\text{4}}{\text{3}}。即自适应价值的理论下界为 43\frac{\text{4}}{\text{3}}(结合命题 3.1,自适应价值的最坏情况上界介于 [43, 2]\left\lbrack \frac{\text{4}}{\text{3}}\text{, 2} \right\rbrack 之间)。

【通俗举例解析:为什么非自适应模式会被“同类低价引流品互相替补”拖累,而自适应模式能多赚 1/3?】

具体算例构造(基于论文第 3.1 节):假设平台上有 𝑛 = 100\mathit{n}\text{ = 100} 个“低价高缺货引流盲盒商品”(编号 1, …, 100\text{1, …, 100}),每个商品的调整后收益均为 𝑟𝑖 = 14 = 0.25\mathit{r}_{\mathit{i}}\text{ = }\frac{\text{1}}{\text{4}}\text{ = 0.25} 元,偏好权重 𝑣𝑖 = 𝜖 = 0.1\mathit{v}_{\mathit{i}}\text{ = }\mathit{\epsilon}\text{ = 0.1},缺货概率高达 𝑝𝑖 = 1 − 𝜖 = 0.9\mathit{p}_{\mathit{i}}\text{ = 1 − }\mathit{\epsilon}\text{ = 0.9};此外还有 1 个“高价全勤王牌商品”(编号 𝑛+1 = 101\mathit{n}\text{+1 = 101}),其调整后收益 𝑟101 = 1.00\mathit{r}_{\text{101}}\text{ = 1.00} 元,偏好权重 𝑣101 = 1\mathit{v}_{\text{101}}\text{ = 1},缺货概率 𝑝101 = 0\mathit{p}_{\text{101}}\text{ = 0}(100% 有货)。

(1)自适应策略的聪明做法:平台在第一阶段把全部 101 个商品都摆出来(总引流权重 100×0.1 + 1 = 11\text{100×0.1 + 1 = 11}),极大降低了顾客空手离开的概率。当顾客在第一阶段选中了任意一个低价引流商品 𝑖 ∈ {1, …, 100}\mathit{i}\text{ ∈ \{1, …, 100\}} 时,平台在第二阶段把其余 99 个低价引流商品全部隐藏,只展示唯一的高价全勤王牌商品 101 作为替代选项(即 𝑆𝑖 = {101}\mathit{S}_{\mathit{i}}\text{ = \{101\}})!这样一来,引流商品既在第一阶段完成了吸客任务,一旦它以 90% 的概率缺货,顾客在第二阶段只能选高价商品 101(以 11+1 = 50%\frac{\text{1}}{\text{1+1}}\text{ = 50\%} 概率接受并创造 1 元高额收益)。当 𝑛\mathit{n} 很大且 𝜖 = 1𝑛\mathit{\epsilon}\text{ = }\frac{\text{1}}{\sqrt{\mathit{n}}} 时,自适应策略的期望收益逼近 34 = 0.75\frac{\text{3}}{\text{4}}\text{ = 0.75} 元。

(2)非自适应策略的两难困境:非自适应策略规定第二阶段必须展示 𝑆0∖{𝑖}\mathit{S}_{\text{0}}\text{∖}\left\{ \mathit{i} \right\}。如果平台在第一阶段摆出太多低价引流商品(使它们的总权重 𝑥 = 𝑘𝜖\mathit{x}\text{ = }\mathit{k}\mathit{\epsilon} 很大),那么当顾客首选某个低价商品 𝑖\mathit{i} 后,第二阶段替代列表里仍然挤满了其余 𝑘−1\mathit{k}\text{−1} 个低价商品!顾客在第二阶段又会大概率挑中另一个低价高缺货商品作为替代,而不会去选高价商品 101(即“劣币在第二阶段继续驱逐良币”);反之,如果平台为了保护第二阶段而少摆低价引流商品,第一阶段的总客流又会大幅萎缩。经求导计算,非自适应策略只能折中挑选使总权重 𝑥 = 𝑘𝜖 = 2\mathit{x}\text{ = }\mathit{k}\mathit{\epsilon}\text{ = 2} 的低价商品数量,其最大期望收益被死死卡在 𝑔(2) = 916 = 0.5625\mathit{g}\left( \text{2} \right)\text{ = }\frac{\text{9}}{\text{16}}\text{ = 0.5625} 元。两者相比,3/49/16 = 43 ≈ 1.3333\frac{\text{3/4}}{\text{9/16}}\text{ = }\frac{\text{4}}{\text{3}}\text{ ≈ 1.3333},自适应策略整整多赚了 33.33%!

4.5 定理 4.1、引理 4.2 与引理 4.3(第 4 节):自适应变体的 PTAS 与代理问题上下界

【定理与引理陈述】
• 定理 4.1(自适应变体的 PTAS):对于任意给定精度 𝜖 > 0\mathit{\epsilon}\text{ > 0},存在一个运行时间为 𝑂((𝑛𝜖)𝑂(1𝜖))\mathit{O}\left( \left( \frac{\mathit{n}}{\mathit{\epsilon}} \right)^{\mathit{O}\left( \frac{\text{1}}{\mathit{\epsilon}} \right)} \right) 的多项式时间近似方案(PTAS),能够为自适应变体 (7) 提供 (1−𝜖)\left( \text{1−}\mathit{\epsilon} \right)-近似解。
• 引理 4.2(代理问题提供上界):代理问题 (8) 的最优目标值 𝑍SR*\mathit{Z}_{\text{SR}}^{\text{*}} 不低于原自适应问题 (7) 的最优目标值 𝑍AD*\mathit{Z}_{\text{AD}}^{\text{*}},即 𝑍SR* ≥ 𝑍AD*\mathit{Z}_{\text{SR}}^{\text{*}}\text{ ≥ }\mathit{Z}_{\text{AD}}^{\text{*}}。
• 引理 4.3(代理问题提供下界):对于任意满足 𝑀H ⊆ 𝑆 ⊆ 𝑁H ∪ 𝑁L\mathit{M}_{\text{H}}\text{ ⊆ }\mathit{S}\text{ ⊆ }\mathit{N}_{\text{H}}\text{ ∪ }\mathit{N}_{\text{L}} 的商品子集 𝑆\mathit{S},原自适应目标函数 ℛAD(𝑆)\mathit{\mathcal{R}}_{\text{AD}}\left( \mathit{S} \right) 与代理问题目标函数 ℛSR(𝑆)\mathit{\mathcal{R}}_{\text{SR}}\left( \mathit{S} \right) 满足 ℛAD(𝑆) ≥ 11+𝜖ℛSR(𝑆)\mathit{\mathcal{R}}_{\text{AD}}\left( \mathit{S} \right)\text{ ≥ }\frac{\text{1}}{\text{1+}\mathit{\epsilon}}\mathit{\mathcal{R}}_{\text{SR}}\left( \mathit{S} \right)。
• 推论(由引理 4.2 与 4.3 合并导出):若 𝑆APP\mathit{S}_{\text{APP}} 是代理问题 (8) 的 𝛼\mathit{\alpha}-近似解,则它在原自适应问题 (7) 中至少是 𝛼1+𝜖\frac{\mathit{\alpha}}{\text{1+}\mathit{\epsilon}}-近似解,即 ℛAD(𝑆APP) ≥ 𝛼1+𝜖𝑍AD*\mathit{\mathcal{R}}_{\text{AD}}\left( \mathit{S}_{\text{APP}} \right)\text{ ≥ }\frac{\mathit{\alpha}}{\text{1+}\mathit{\epsilon}}\mathit{Z}_{\text{AD}}^{\text{*}}。

【通俗举例解析:为什么只给前 ⌈1/ϵ⌉ 个“核心大权重商品”定制替代列表就足够精确了?】

核心机制与数字例子:假设平台要在 𝑛 = 100\mathit{n}\text{ = 100} 种商品中优化组合,要求误差参数 𝜖 = 0.25\mathit{\epsilon}\text{ = 0.25},则关键集大小 𝜅 = ⌈10.25⌉ = 4\mathit{\kappa}\text{ = }\left\lceil \frac{\text{1}}{\text{0.25}} \right\rceil\text{ = 4}。假设最优解 𝑆*\mathit{S}^{\mathit{*}} 中高调整后收益子集 𝑆H*\mathit{S}_{\text{H}}^{\text{*}} 包含 10 种商品,其中前 4 大综合权重商品构成的“关键集” 𝑀H\mathit{M}_{\text{H}} 每个商品的权重 𝑣𝑗𝑟𝑗 = 10\mathit{v}_{\mathit{j}}\mathit{r}_{\mathit{j}}\text{ = 10}(合计 4×10 = 40\text{4×10 = 40}),而其余 6 个非关键高收益商品 𝑖 ∈ 𝑆H*∖𝑀H\mathit{i}\text{ ∈ }\mathit{S}_{\text{H}}^{\text{*}}\text{∖}\mathit{M}_{\text{H}} 的权重最多不超过 𝑣𝑖𝑟𝑖 ≤ 10\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}}\text{ ≤ 10}(比如为 8)。

• 为什么引理 4.2 成立(代理问题上界 𝑍SR* ≥ 𝑍AD*\mathit{Z}_{\text{SR}}^{\text{*}}\text{ ≥ }\mathit{Z}_{\text{AD}}^{\text{*}})? 在最优解 𝑆*\mathit{S}^{\mathit{*}} 上,如果顾客选了某个非关键商品 𝑖 ∈ 𝑆*∖𝑀H\mathit{i}\text{ ∈ }\mathit{S}^{\text{*}}\text{∖}\mathit{M}_{\text{H}},真实自适应模型在第二阶段不能再提供 𝑖\mathit{i},只能从 𝑆*∖{𝑖}\mathit{S}^{\text{*}}\text{∖}\left\{ \mathit{i} \right\} 中拿收益 𝐹¯(𝑆*∖{𝑖})\overline{\mathit{F}}\left( \mathit{S}^{\text{*}}\text{∖}\left\{ \mathit{i} \right\} \right);而在代理问题 (8) 的计算公式中,作者故意大方地把整个完整的高收益集 𝑆*∩𝑁H = 𝑆H*\mathit{S}^{\text{*}}\text{∩}\mathit{N}_{\text{H}}\text{ = }\mathit{S}_{\text{H}}^{\text{*}}(没有剔除 𝑖\mathit{i}!)的收益 𝑅¯(𝑆H*)\overline{\mathit{R}}\left( \mathit{S}_{\text{H}}^{\text{*}} \right) 赋给了它。因为 𝑅¯(𝑆H*)\overline{\mathit{R}}\left( \mathit{S}_{\text{H}}^{\text{*}} \right) 本身就是 𝑆*\mathit{S}^{\mathit{*}} 内所有子集的最大单阶段收益,自然大于等于剔除 𝑖\mathit{i} 后的 𝐹¯(𝑆*∖{𝑖})\overline{\mathit{F}}\left( \mathit{S}^{\text{*}}\text{∖}\left\{ \mathit{i} \right\} \right),所以代理问题在 𝑆*\mathit{S}^{\mathit{*}} 处算出来的分数必然高于真实最优值!

• 为什么引理 4.3 成立(真实收益至少是代理分数的 11+𝜖\frac{\text{1}}{\text{1+}\mathit{\epsilon}})? 反过来,在任意可行解 𝑆\mathit{S} 下,代理问题虽然在顧客选非关键高收益商品 𝑖 ∈ (𝑆∩𝑁H)∖𝑀H\mathit{i}\text{ ∈ }\left( \mathit{S}\text{∩}\mathit{N}_{\text{H}} \right)\text{∖}\mathit{M}_{\text{H}} 时多算了一个商品 𝑖\mathit{i} 的权重(真实情况必须剔除 𝑖\mathit{i}),但因为关键集 𝑀H\mathit{M}_{\text{H}} 里已经稳稳坐着 4 个权重至少为 10 的巨无霸商品(总重至少 40),被剔除的非关键商品 𝑖\mathit{i} 权重至多为 8,剔除 𝑖\mathit{i} 后剩余高收益商品集 (𝑆∩𝑁H)∖{𝑖}\left( \mathit{S}\text{∩}\mathit{N}_{\text{H}} \right)\text{∖}\left\{ \mathit{i} \right\} 的总权重至少保留了 4040+8 ≥ 𝜅1+𝜅 = 11+𝜖 = 80%\frac{\text{40}}{\text{40+8}}\text{ ≥ }\frac{\mathit{\kappa}}{\text{1+}\mathit{\kappa}}\text{ = }\frac{\text{1}}{\text{1+}\mathit{\epsilon}}\text{ = 80\%}!因此,只给前 ⌈1𝜖⌉\left\lceil \frac{\text{1}}{\mathit{\epsilon}} \right\rceil 个头部商品做定制化推荐、对其余普通商品统一推荐 (𝑆∩𝑁H)∖{𝑖}\left( \mathit{S}\text{∩}\mathit{N}_{\text{H}} \right)\text{∖}\left\{ \mathit{i} \right\},损失的收益比例最多不超过 𝜖1+𝜖\frac{\mathit{\epsilon}}{\text{1+}\mathit{\epsilon}}。

4.6 引理 5.1(Lemma 5.1):从多维背包超最优解到代理问题 (1−6ϵ)-近似解

【引理陈述】设 𝑆*\mathit{S}^{\mathit{*}} 为代理问题 (8) 的最优解。若猜测向量 (𝑓̂, 𝑔̂, ĥ, 𝑤̂)\left( \widehat{\mathit{f}}\text{, }\widehat{\mathit{g}}\text{, }\widehat{\mathit{h}}\text{, }\widehat{\mathit{w}} \right) 满足精度条件:𝑓̂𝑖 ≤ 𝐹¯(𝑆*∖{𝑖}) ≤ (1+𝜖)𝑓̂𝑖{\widehat{\mathit{f}}}_{\mathit{i}}\text{ ≤ }\overline{\mathit{F}}\left( \mathit{S}^{\text{*}}\text{∖}\left\{ \mathit{i} \right\} \right)\text{ ≤ }\left( \text{1+}\mathit{\epsilon} \right){\widehat{\mathit{f}}}_{\mathit{i}}(∀𝑖∈𝑀H\text{∀}\mathit{i}\text{∈}\mathit{M}_{\text{H}})、11+𝜖𝑔̂ ≤ 𝑉(𝑆*∩𝑁H) ≤ 𝑔̂\frac{\text{1}}{\text{1+}\mathit{\epsilon}}\widehat{\mathit{g}}\text{ ≤ }\mathit{V}\left( \mathit{S}^{\text{*}}\text{∩}\mathit{N}_{\text{H}} \right)\text{ ≤ }\widehat{\mathit{g}}、11+𝜖ĥ ≤ 𝑉(𝑆*∩𝑁L) ≤ ĥ\frac{\text{1}}{\text{1+}\mathit{\epsilon}}\widehat{\mathit{h}}\text{ ≤ }\mathit{V}\left( \mathit{S}^{\text{*}}\text{∩}\mathit{N}_{\text{L}} \right)\text{ ≤ }\widehat{\mathit{h}} 以及 𝑤̂ ≤ 𝑊(𝑆*∩𝑁H) ≤ (1+𝜖)𝑤̂\widehat{\mathit{w}}\text{ ≤ }\mathit{W}\left( \mathit{S}^{\text{*}}\text{∩}\mathit{N}_{\text{H}} \right)\text{ ≤ }\left( \text{1+}\mathit{\epsilon} \right)\widehat{\mathit{w}},且集合 𝑆̂\widehat{\mathit{S}} 是多维背包问题 (9) 在该猜测向量下的超最优解(满足公式 10),则 𝑆̂\widehat{\mathit{S}} 是代理问题 (8) 的一个 (1−6𝜖)\left( \text{1−6}\mathit{\epsilon} \right)-近似解。

【通俗举例解析:网格猜测与允许轻微越界的“超最优解”如何协同工作?】

核心意思与数值例子:在求解代理问题时,我们事先不知道最优解 𝑆*\mathit{S}^{\mathit{*}} 的真实总偏好权重 𝑉(𝑆*∩𝑁H)\mathit{V}\left( \mathit{S}^{\text{*}}\text{∩}\mathit{N}_{\text{H}} \right)(假设真实值为 10.0)和真实总收益权重 𝑊(𝑆*∩𝑁H)\mathit{W}\left( \mathit{S}^{\text{*}}\text{∩}\mathit{N}_{\text{H}} \right)(假设真实值为 50.0)。但我们可以按公比 1+𝜖\text{1+}\mathit{\epsilon}(设 𝜖 = 0.02\mathit{\epsilon}\text{ = 0.02},即 2% 步长)建立几何网格尺子:必然存在某个网格刻度 𝑔̂ = 10.1\widehat{\mathit{g}}\text{ = 10.1} 恰好从上方卡住 10.0(误差不超过 2%),以及某个网格刻度 𝑤̂ = 49.5\widehat{\mathit{w}}\text{ = 49.5} 恰好从下方托住 50.0(误差不超过 2%)。

随后,我们把 (𝑓̂, 𝑔̂, ĥ, 𝑤̂)\left( \widehat{\mathit{f}}\text{, }\widehat{\mathit{g}}\text{, }\widehat{\mathit{h}}\text{, }\widehat{\mathit{w}} \right) 当作背包问题的容量目标,用系数离散化后的动态规划去找商品组合 𝑆̂\widehat{\mathit{S}}。由于离散化取整,找到的超最优解 𝑆̂\widehat{\mathit{S}} 可能会轻微违背背包约束达 1+𝜖\text{1+}\mathit{\epsilon} 倍(例如实际选出的 𝑉(𝑆̂∩𝑁H)\mathit{V}\left( \widehat{\mathit{S}}\text{∩}\mathit{N}_{\text{H}} \right) 达到了 1.02 × 10.1 ≈ 10.3\text{1.02 × 10.1 ≈ 10.3},实际 𝑊(𝑆̂∩𝑁H)\mathit{W}\left( \widehat{\mathit{S}}\text{∩}\mathit{N}_{\text{H}} \right) 略降至 49.51.02 ≈ 48.5\frac{\text{49.5}}{\text{1.02}}\text{ ≈ 48.5})。引理 5.1 告诉我们:把“网格猜测本身的 1+𝜖\text{1+}\mathit{\epsilon} 误差”与“动态规划取整导致的 1+𝜖\text{1+}\mathit{\epsilon} 轻微越界误差”在分子分母中层层累积起来,总误差依然高度可控,最多只会折损 6𝜖\text{6}\mathit{\epsilon}(如 6 × 2%= 12%\text{6 × 2\% = 12\%}),从而保证 𝑆̂\widehat{\mathit{S}} 至少能拿到代理问题最优收益的 1−6𝜖\text{1−6}\mathit{\epsilon} 倍(结合引理 4.3,令 𝜖 = 𝛿7\mathit{\epsilon}\text{ = }\frac{\mathit{\delta}}{\text{7}} 即可拿到原问题 1−𝛿\text{1−}\mathit{\delta} 近似解)。

4.7 引理 6.1 与定理 6.2(第 6 节):非自适应变体的二维背包逼近与 FPTAS

【引理与定理陈述】
• 引理 6.1(二维背包超最优解到非自适应变体):设 𝑆*\mathit{S}^{\mathit{*}} 为非自适应变体 (11) 的最优解,𝑖*\mathit{i}^{\mathit{*}} 和 𝑗*\mathit{j}^{\mathit{*}} 分别为 𝑆*\mathit{S}^{\mathit{*}} 中 𝑣𝑖\mathit{v}_{\mathit{i}} 最大和 𝑣𝑖𝑟𝑖\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}} 最大的商品。若猜测值 (𝑔̂, 𝑤̂)\left( \widehat{\mathit{g}}\text{, }\widehat{\mathit{w}} \right) 满足 11+𝜖𝑔̂ ≤ 𝑉(𝑆*∖{𝑖*}) ≤ 𝑔̂\frac{\text{1}}{\text{1+}\mathit{\epsilon}}\widehat{\mathit{g}}\text{ ≤ }\mathit{V}\left( \mathit{S}^{\text{*}}\text{∖}\left\{ \mathit{i}^{\text{*}} \right\} \right)\text{ ≤ }\widehat{\mathit{g}} 且 𝑤̂ ≤ 𝑊(𝑆*∖{𝑗*}) ≤ (1+𝜖)𝑤̂\widehat{\mathit{w}}\text{ ≤ }\mathit{W}\left( \mathit{S}^{\text{*}}\text{∖}\left\{ \mathit{j}^{\text{*}} \right\} \right)\text{ ≤ }\left( \text{1+}\mathit{\epsilon} \right)\widehat{\mathit{w}},且 𝑆̂\widehat{\mathit{S}} 是二维背包问题 (12) 在 (𝑔̂, 𝑤̂)\left( \widehat{\mathit{g}}\text{, }\widehat{\mathit{w}} \right) 下的超最优解,则 𝑆̂\widehat{\mathit{S}} 是非自适应变体 (11) 的 (1−4𝜖)\left( \text{1−4}\mathit{\epsilon} \right)-近似解。
• 定理 6.2(非自适应变体的 FPTAS):对于任意 𝜖 > 0\mathit{\epsilon}\text{ > 0},存在一个运行时间为 𝑂(𝑛7(log 𝑛)2𝜖4)\mathit{O}\left( \frac{\mathit{n}^{\text{7}}\left( \text{log }\mathit{n} \right)^{\text{2}}}{\mathit{\epsilon}^{\text{4}}} \right) 的完全多项式时间近似方案(FPTAS),为非自适应变体提供 (1−𝜖)\left( \text{1−}\mathit{\epsilon} \right)-近似解。

【通俗举例解析:为什么非自适应变体必须“先扣除最大锚点商品 i* 和 j*”再做猜测?】

具体数值例子:在非自适应变体中,当顾客首选商品 𝑖\mathit{i} 缺货时,第二阶段的替代收益分子是 𝑊(𝑆∖{𝑖}) = 𝑊(𝑆) − 𝑣𝑖𝑟𝑖\mathit{W}\left( \mathit{S}\text{∖}\left\{ \mathit{i} \right\} \right)\text{ = }\mathit{W}\left( \mathit{S} \right)\text{ − }\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}}。假设最优组合 𝑆*\mathit{S}^{\mathit{*}} 的总权重 𝑊(𝑆*) = 100\mathit{W}\left( \mathit{S}^{\text{*}} \right)\text{ = 100},其中某个爆款商品 1\mathit{1} 的权重占了绝大多数:𝑣1𝑟1 = 99\mathit{v}_{\text{1}}\mathit{r}_{\text{1}}\text{ = 99},其余小商品合计权重只有 100 − 99 = 1\text{100 − 99 = 1}。

• 如果直接猜测整个集合的总权重 𝑊(𝑆*)\mathit{W}\left( \mathit{S}^{\text{*}} \right): 哪怕我们的猜测值 𝑤̂ = 98\widehat{\mathit{w}}\text{ = 98} 相对于 100 只有 2% 的微小误差,一旦在公式里做减法计算商品 1 缺货后的替补分子 𝑤̂ − 𝑣1𝑟1 = 98 − 99 = −1\widehat{\mathit{w}}\text{ − }\mathit{v}_{\text{1}}\mathit{r}_{\text{1}}\text{ = 98 − 99 = −1}(真实值是 100 − 99 = +1\text{100 − 99 = +1}),两个相近大数相减会导致相对误差瞬间爆炸甚至变成负数!
• 作者的精妙解决之道(锚点置换法): 先直接枚举找出权重最大的锚点商品 𝑗* = 1\mathit{j}^{\text{*}}\text{ = 1}(精准知道 𝑣1𝑟1 = 99\mathit{v}_{\text{1}}\mathit{r}_{\text{1}}\text{ = 99}),只去猜测“除去商品 1 以外的剩余商品总权重” 𝑊(𝑆*∖{1}) = 1\mathit{W}\left( \mathit{S}^{\text{*}}\text{∖}\left\{ \text{1} \right\} \right)\text{ = 1}(设猜测值 𝑤̂ = 0.98\widehat{\mathit{w}}\text{ = 0.98})。此时,对于任意商品 𝑖\mathit{i},替补分子改写为 𝑤̂ + (𝑣𝑗*𝑟𝑗* − 𝑣𝑖𝑟𝑖)\widehat{\mathit{w}}\text{ + }\left( \mathit{v}_{\mathit{j}^{\text{*}}}\mathit{r}_{\mathit{j}^{\text{*}}}\text{ − }\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}} \right)。因为 𝑗*\mathit{j}^{\mathit{*}} 是权重冠军,括号里的差值 𝑣𝑗*𝑟𝑗* − 𝑣𝑖𝑟𝑖\mathit{v}_{\mathit{j}^{\text{*}}}\mathit{r}_{\mathit{j}^{\text{*}}}\text{ − }\mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}} 永远是非负正数(当 𝑖=1\mathit{i}\text{=1} 时差值为 0,分子直接等于 𝑤̂ = 0.98\widehat{\mathit{w}}\text{ = 0.98},与真实值 1.00 误差仅 2%)。正是这一巧妙变形消除了减法误差放大,而且因为非自适应变体无需猜测关键集 𝑀H\mathit{M}_{\text{H}},背包约束个数固定为 2 个(与 𝜖\mathit{\epsilon} 无关),从而使运行时间对 𝑛\mathit{n} 和 1𝜖\frac{\text{1}}{\mathit{\epsilon}} 均为多项式阶,升级为完全多项式时间近似方案(FPTAS)!

4.8 混合整数规划等价性与二元变量消去结论(第 7 节 & Online Appendix D)

【结论陈述】混合整数规划模型 (13) 的最优目标值与原自适应品类优化问题完全等价;若附加约束 𝑧𝑖𝑗 = 𝑥𝑗\mathit{z}_{\mathit{i}\mathit{j}}\text{ = }\mathit{x}_{\mathit{j}}(∀𝑖≠𝑗\text{∀}\mathit{i}\text{≠}\mathit{j}),则与非自适应品类优化问题完全等价。进一步地,在自适应变体且第二阶段无额外业务约束时,可以将表示第二阶段选品的 𝑛(𝑛−1)\mathit{n}\left( \mathit{n}\text{−1} \right) 个二元变量 𝑧𝑖𝑗 ∈ {0, 1}\mathit{z}_{\mathit{i}\mathit{j}}\text{ ∈ \{0, 1\}} 全部松弛/消去,仅保留第一阶段的 𝑛\mathit{n} 个二元变量 𝑥𝑖 ∈ {0, 1}\mathit{x}_{\mathit{i}}\text{ ∈ \{0, 1\}} 而不改变最优解。

【通俗举例解析:为什么在求解器里可以删掉成千上万个第二阶段整数变量 zij?】

具体数值例子:假设有 𝑛 = 200\mathit{n}\text{ = 200} 种商品,一阶段二元变量 𝑥𝑖\mathit{x}_{\mathit{i}} 只有 200 个,而二阶段二元变量 𝑧𝑖𝑗\mathit{z}_{\mathit{ij}} 却多达 200 × 199 = 39,800\text{200 × 199 = 39,800} 个!为什么可以把这 39,800 个二元变量 𝑧𝑖𝑗\mathit{z}_{\mathit{ij}} 直接松弛为连续变量甚至删掉?因为当第一阶段展示集合 𝑆0\mathit{S}_{\mathit{0}}(由 𝑥𝑖 ∈ {0, 1}\mathit{x}_{\mathit{i}}\text{ ∈ \{0, 1\}} 决定)固定后,对于每一个首选商品 𝑖\mathit{i},寻找第二阶段替代集 𝑆𝑖 ⊆ 𝑆0∖{𝑖}\mathit{S}_{\mathit{i}}\text{ ⊆ }\mathit{S}_{\text{0}}\text{∖}\left\{ \mathit{i} \right\} 本质上是一个无约束的单阶段 MNL 品类优化子问题。众所周知,无约束单阶段 MNL 品类优化问题的线性规划松弛(LP Relaxation)天然具有整数极点性质(不会出现把某个商品选半个的情况)。因此,只要一阶段变量 𝑥𝑖\mathit{x}_{\mathit{i}} 取 0 或 1,二阶段子问题在连续概率变量 𝑤𝑖𝑗\mathit{w}_{\mathit{ij}} 下会自动收敛到非 0 即 1 的纯整数选品方案,从而大幅减轻了整数规划求解器的分支定界负担!

五、 实证案例研究(Instacart)与数值实验总结

作者在第 8 节和第 9 节分别开展了基于 Instacart 真实交易数据的实证研究和针对大规模随机算例的算法性能测试,核心实验设计与数据结果总结如下:

5.1 Instacart 数据集特征与 MNL 模型拟合表现

研究团队采集了 Instacart 平台上跨越 21 周的 1100 万笔订单样本,选取交易量最大的 12 个核心品类(苹果 Apples、浆果 Berries、糖果 Candy、鸡肉 Chicken、薯片 Chips、希腊酸奶 Greek yogurt、叶菜类 Leafy vegetables、纯牛奶 Plain milk、调味品 Seasonings、气泡水 Sparkling water、番茄 Tomatoes、整蛋 Whole eggs),并在每个“品类—零售商”组合中截取累计贡献 90% 销量的头部商品(包含 10 至 60 种商品)构建商品全集。以前 16 周数据作为训练集(通过极大似然估计拟合偏好权重 𝑣𝑖\mathit{v}_{\mathit{i}}),后 5 周数据作为样本外测试集。模型样本外平均绝对误差(MAE)低至 0.90%(远低于均匀随机猜测的基准),平均 1-hit、2-hit 和 3-hit 命中率分别达到 16.12%、27.44% 和 36.08%(相比 20 个商品下随机盲猜的 5%、10% 和 15% 提升了两倍以上),验证了带替代选项的 MNL 模型能够极其精准地刻画真实消费者的首选与替补偏好。

5.2 朴素策略、非自适应策略与自适应策略的实证绩效对比

作者对比了三种递进策略的表现:(1)朴素策略 𝑆̂ML{\widehat{\mathit{S}}}_{\text{ML}}(忽略替代选项,按单阶段 MNL 最优解展示);(2)非自适应策略 𝑆̂NA{\widehat{\mathit{S}}}_{\text{NA}}(显式考虑替代选项,求解非自适应模型);(3)自适应策略 𝑆̂AD{\widehat{\mathit{S}}}_{\text{AD}}(根据顾客首选商品动态优化第二阶段替代列表)。核心对比数据汇总如下表:

对比维度 / 实验场景 展示商品数量变化 期望收益提升 (Exp. Rev.) 市场份额与退款率变化
显式纳入替代选项的价值
(𝑆̂NA{\widehat{\mathit{S}}}_{\text{NA}} 对比 𝑆̂ML{\widehat{\mathit{S}}}_{\text{ML}},表 3)
平均从 8.13 个增至 10.63 个(倾向于提供更宽的初始选品) 全品类平均提升 3.39%;95分位数提升 7.36%,最高组合提升达 18.87%(浆果类) 总市场份额(FMS)平均提升 +5.84%;净市场份额/履约率(NMS)平均提升 +1.36%(鸡蛋类最高 +3.42%);退款率(RFR)平均上升 +4.48%
升级为自适应推荐的价值
(𝑆̂AD{\widehat{\mathit{S}}}_{\text{AD}} 对比 𝑆̂NA{\widehat{\mathit{S}}}_{\text{NA}},表 4)
一阶段平均从 10.63 个进一步增至 12.07 个 在非自适应基础上进一步平均提升 0.94%;最高组合提升达 4.12%(番茄类) 总市场份额进一步提升 +2.36%;净市场份额(NMS)进一步提升 +0.60%;退款率微升 +1.77%
固定历史一阶段商品集下
仅二阶段自适应(表 5)
一阶段固定为历史实际展示集合 𝑆̂HS{\widehat{\mathit{S}}}_{\text{HS}} 全品类期望收益平均大幅提升 8.93%(最高达 24.30%,叶菜类) 证明当一阶段现有商品结构不够理想时,仅靠二阶段精准过滤低价值替补品即可创造近 9% 的惊人收益增幅
施加退款率上限约束
(MIP 扩展实验,图 3)
随退款率上限 𝛿\mathit{\delta} 动态调节高风险引流品数量 在严格限制退款率增幅的前提下仍保持显著正收益增长 存在理想折中点:仅允许平均退款率增加约 1%,即可换取平均期望收益增长约 1%

5.3 受 PTAS 启发的启发式算法与商业求解器 Gurobi 对比(第 9 节)

在大规模自适应品类优化问题(𝑛 = 200\mathit{n}\text{ = 200} 种商品,18 组参数配置共 360 个测试算例)中,作者将 PTAS 中的关键集 𝑀H\mathit{M}_{\text{H}} 简化为单元素集 {𝑗*}\left\{ \mathit{j}^{\text{*}} \right\}(其中 𝑗* = arg max𝑖∈𝑁{𝑣𝑖𝑟𝑖 : 𝑟𝑖 ≥ 34𝑧¯}\mathit{j}^{\text{*}}\text{ = }\text{arg max}_{\mathit{i}\text{∈}\mathit{N}}\left\{ \mathit{v}_{\mathit{i}}\mathit{r}_{\mathit{i}}\text{ : }\mathit{r}_{\mathit{i}}\text{ ≥ }\frac{\text{3}}{\text{4}}\overline{\mathit{z}} \right\},𝑧¯ = max𝑆⊆𝑁𝑅¯(𝑆)\overline{\mathit{z}}\text{ = }\underset{\mathit{S}\text{⊆}\mathit{N}}{\text{max}}\overline{\mathit{R}}\left( \mathit{S} \right)),无需枚举 𝑂(𝑛⌈1𝜖⌉)\mathit{O}\left( \mathit{n}^{\left\lceil \frac{\text{1}}{\mathit{\epsilon}} \right\rceil} \right) 种组合。实验显示:该启发式算法平均仅需 0.41 秒 即可求得高质量解;而商业求解器 Gurobi 12.0 求解 MIP 模型 (13) 在 20 倍运行时间内几乎找不到任何可行解,即便给予 Gurobi 50 倍运行时间(约 20 秒),PTAS 启发式依然在 360 个算例中的 333 个算例上击败 Gurobi,平均期望收益高出 1.40%(最高高出 5.70%);即便给予 Gurobi 200 倍运行时间,启发式算法仍在近半数算例(178/360)上占优且平均收益领先 0.37%。

六、 全文结论的经济与管理学启示总结

本文的理论模型与 Instacart 实证研究为在线零售平台、即时配送企业(如美团闪购、京东到家、盒马、Instacart 等)以及无自营库存的撮合电商提供了深刻且可直接落地的经济与管理学启示:

1. 摒弃“孤立单阶段选品”思维,将“替代选项机制”纳入品类规划底层算法:传统零售品类管理往往假定展示商品 100% 有货,或者在缺货发生后才被动提示替代品。本文证明,如果在规划第一阶段展示货架时忽略消费者拥有指定替代品的权利(即采用朴素策略),平台会因为害怕“高人气但易缺货商品”分流高毛利商品而错误地将其下架,导致平台在生鲜杂货全品类上平均白白流失 3.39% 的期望收入(特定品类高达 18% 以上)。由于零售行业净利润率通常较薄(仅数个百分点),3% 以上的顶线收入提升将直接转化为极为可观的净利润增长。

2. 善用“引流款 + 全勤兜底款”的互补协同效应,适度扩大首阶段展示宽度:当平台拥有替代选项作为第二道防线时,最优品类策略会发生结构性转变:平台应当比传统单阶段模型更加大胆地展示更多商品(实证中平均展示商品数从 8.13 个增加到 10.63–12.07 个)。具体而言,平台可以将“高消费者偏好但库存不稳定的网红/爆款商品”作为第一阶段的引流钩子(防止顾客因找不到心仪商品而直接流失),同时在组合中配置“货源充足、利润率高的常青商品”作为第二阶段的履约稳定器。这种跨阶段互补机制不仅推高了期望总收入,还将订单净履约率(Net Market Share)平均提升了 1.36% 至 1.96%。

3. 推进“第二阶段个性化自适应推荐”,以极低改造成本撬动存量收益:许多平台出于前后端工程实现简便,在消费者点击“选择替代品”时,只是简单地把第一阶段列表里剩下的商品原样展示出来(非自适应模式)。本文证明,哪怕平台由于商业协议或界面规范无法轻易改动第一阶段的常规展示列表(如历史固定货架),仅仅在消费者选定首选商品后,利用自适应算法对第二阶段的替代候选弹窗进行智能裁剪(剔除那些低毛利或同样极易缺货的干扰项,精准保留高调整后收益的替代品),就能带来平均高达 8.93% 的期望收益跃升!这为平台产品经理提供了一条“高投资回报率(High ROI)、低业务阻力”的渐进式算法升级路径。

4. 警惕“高期望收益与高退款率并存”的运营悖论,实施带服务水平约束的稳健优化:本文揭示了一个极具价值的运营管理权衡(Trade-off):显式利用替代选项来最大化期望收入时,算法往往会引入更多高吸引力但高缺货率的商品,这虽然让更多顾客成功买到了首选或替代商品(净市场份额上升),但同时也使另一部分倒霉的顾客遭遇“首选与替代双双缺货”,导致整体退款率(Refund Rate)上升了 4.48%。频繁退款会损害消费者长期留存与平台商誉。管理者不应盲目追求无约束的期望收入最大化,而应利用本文提出的混合整数规划(MIP)框架设置“退款率红线约束(RFR ≤ 𝛿\text{RFR ≤ }\mathit{\delta})”——实证表明,将退款率增幅严格控制在 1% 以内,依然能够稳健捕获显著的净收入增长。

5. 聚焦“头部核心单品(Critical Set)”抓大放小,兼顾算法实时性与最优性:本文 PTAS 算法与启发式实验在管理方法论上印证了“二八定律”的深刻威力:面对数百种候选商品的复杂两阶段随机优化,平台无需对每一个长尾商品都耗费算力去定制替代策略,只需精准识别出调整后收益与偏好权重乘积最大的前几个“关键商品(Critical Set,甚至仅锁定排名第一的核心锚点商品)”进行自适应精细化匹配,对其余商品采用统一规则,即可在 0.4 秒 内获得超越大型商业求解器运行数十秒的卓越方案,完美契合在线零售平台高并发、毫秒级响应的工程部署需求。

6. 针对高缺货风险品类与门店优先部署智能替代引擎:敏感性分析(表 6)表明,替代选项建模与自适应推荐的收益增幅与商品的缺货风险呈显著正相关。对于标准化程度高、库存极其充裕的常温和耐用品类,传统单阶段算法已基本够用;但对于生鲜果蔬(如浆果、叶菜、苹果、番茄)、烘焙、鲜奶及晚间高峰时段等库存波动剧烈、缺货频发的品类与门店,部署本文的两阶段品类与替代推荐优化模型能够释放出最大的商业潜能。

七、 参考文献 (References)

以下完整列出本文目标文献及文中所引用的全部学术参考文献(按作者姓氏字母顺序排列):

目标主文献:Mitrofanov D, Topaloglu H, Wang Y (2026) Assortment optimization with replacement options for retail platforms with stockout risk. Operations Research 74(5):2460–2484. https://doi.org/10.1287/opre.2024.1074.

1. Akchen Y-C, Misic VV (2025) Assortment optimization under the decision forest model. Preprint, submitted March 25, https://arxiv.org/abs/2103.14067.

2. Akchen Y-C, Mitrofanov D (2025) Consider or choose? The role and power of consideration sets. Management Sci. Forthcoming.

3. Alfandari L, Hassanzadeh A, Ljubic I (2021) An exact method for assortment optimization under the nested logit model. Eur. J. Oper. Res. 291(3):830–845.

4. Anderson ET, Fitzsimons GJ, Simester D (2006) Measuring and mitigating the costs of stockouts. Management Sci. 52(11):1751–1763.

5. Aouad A, Feldman J, Segev D, Zhang DJ (2018) Click-based MNL: Algorithmic frameworks for modeling click data in assortment optimization. Technical report, Washington University, St. Louis.

6. Bai Y, Feldman J, Segev D, Topaloglu H, Wagner L (2023) Assortment optimization under the multi-purchase multinomial logit choice model. Oper. Res. 72(6):2631–2664.

7. Bront JJM, Méndez-Díaz I, Vulcano G (2009) A column generation algorithm for choice-based network revenue management. Oper. Res. 57(3):769–784.

8. Chen Y, He T, Rong Y, Wang Y (2025) An integer programming approach for quick-commerce assortment planning. Preprint, submitted May 4, https://arxiv.org/abs/2405.02553.

9. Desir A, Goyal V, Zhang J (2022) Capacitated assortment optimization: Hardness and approximation. Oper. Res. 70(2):893–904.

10. El Housni O, Topaloglu H (2023) Joint assortment optimization and customization under a mixture of multinomial logit models: On the value of personalized assortments. Oper. Res. 71(4):1197–1215.

11. Feldman J, Segev D (2022) Technical note—The multinomial logit model with sequential offerings: Algorithmic frameworks for product recommendation displays. Oper. Res. 70(4):2162–2184.

12. Feldman J, Topaloglu H (2018) Technical note: Capacitated assortment optimization under the multinomial logit model with nested consideration sets. Oper. Res. 66(2):380–391.

13. Fitzsimons GJ (2000) Consumer response to stockouts. J. Consumer Res. 27(2):249–266.

14. Flores A, Berbeglia G, van Hentenryck P (2019) Assortment optimization under the sequential multinomial logit model. Eur. J. Oper. Res. 273(3):1052–1064.

15. Gallego G, Topaloglu H (2019) Revenue Management and Pricing Analytics, International Series in Operations Research & Management Science, vol. 209 (Springer, New York).

16. Gao P, Ma Y, Chen N, Gallego G, Li A, Rusmevichientong P, Topaloglu H (2021) Assortment optimization and pricing under the multinomial logit model with impatient customers: Sequential recommendation and selection. Oper. Res. 69(5):1509–1532.

17. Jagabathula S, Rusmevichientong P (2019) The limit of rationality in choice modeling: Formulation, computation, and implications. Management Sci. 65(5):2196–2215.

18. Jagabathula S, Vulcano G (2018) A partial-order-based model to estimate individual preferences using panel data. Management Sci. 64(4):1609–1628.

19. Jagabathula S, Mitrofanov D, Vulcano G (2022) Personalized retail promotions through a directed acyclic graph-based representation of customer preferences. Oper. Res. 70(2):641–665.

20. Knight B, Mitrofanov D (2026) Disclosing low product availability: An online platform's strategy for mitigating stockout risk. Management Sci. 72(2):1560–1578.

21. Liu N, Ma Y, Topaloglu H (2020) Assortment optimization under the multinomial logit model with sequential offerings. INFORMS J. Comput. 32(3):835–853.

22. Musalem A, Olivares M, Bradlow ET, Terwiesch C, Corsten D (2010) Structural estimation of the effect of out-of-stocks. Management Sci. 56(7):1180–1197.

23. Rusmevichientong P, Shen Z-JM, Shmoys DB (2010) Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Oper. Res. 58(6):1666–1680.

24. Rusmevichientong P, Shmoys D, Tong C, Topaloglu H (2014) Assortment optimization under the multinomial logit model with random choice parameters. Production Oper. Management 23(11):2023–2039.

25. Sen A, Atamturk A, Kaminsky P (2018) Technical note—A conic integer optimization approach to the constrained assortment problem under the mixed multinomial logit model. Oper. Res. 66(4):994–1003.

26. Sumida M, Gallego G, Rusmevichientong P, Topaloglu H, Davis J (2021) Revenue-utility tradeoff in assortment optimization under the multinomial logit model with totally unimodular constraints. Management Sci. 67(5):2845–2869.

27. Talluri K, van Ryzin G (2004) Revenue management under a general discrete choice model of consumer behavior. Management Sci. 50(1):15–33.

28. Wagner L, Martinez-de-Albeniz V (2020) Pricing and assortment strategies with product exchanges. Oper. Res. 68(2):453–466.