来源：市场资讯
（来源：运筹OR帷幄）
据MS官网显示，来自上海交通大学安泰经管学院的Yajing Chen、何涛涛、荣鹰、王云龙，合著的论文“ An Integer Programming Approach for Quick-Commerce Assortment Planning ”在国际管理学顶刊《Management Science》线上正式发表。
Title: An Integer Programming Approach for Quick-Commerce Assortment Planning
面向即时零售品类规划的整数规划方法
作者简介
Yajing Chen
上海交通大学
何涛涛
上海交通大学
荣鹰
上海交通大学
王云龙
上海交通大学
摘要
In this paper, we explore the challenge of assortment planning in the context of quick commerce, a rapidly growing business model that aims to deliver time-sensitive products. In order to achieve quick delivery to satisfy the immediate demands of online customers in close proximity, personalized online assortments need to be included in brick-and-mortar store offerings. With the presence of this physical linkage requirement and distinct multinomial logit choice models for online consumer segments, the firm seeks to maximize overall revenue by selecting an optimal assortment of products for local stores and by tailoring a personalized assortment for each online consumer segment. We employ an integer programming approach to solve this NP-hard problem to global optimality. In particular, we derive convex hull results to represent the consumer choice of each online segment under a general class of operational constraints, and to characterize the relation between assortment decisions and choice probabilities of products. Our convex hull results, coupled with a modified choice probability–ordered separation algorithm, yield formulations that provide a significant computational advantage over existing methods. Finally, we illustrate how our convex hull results can be used to address other assortment optimization problems.
本文探讨即时零售背景下的品类规划问题，即时零售是一种旨在配送时效敏感型产品的快速增长商业模式。为实现快速配送以响应邻近地区线上消费者的即时需求，企业需将个性化的线上品类纳入实体门店的线下在售商品组合。在存在此类物理联动约束、且线上消费群体服从差异化多项对数选择模型的条件下，企业需为各区域门店选择最优品类集合，并为每一线上消费群体定制个性化品类方案，以最大化整体收益。本文采用整数规划方法求解该NP-hard问题至全局最优，我们推导了凸包结果，以刻画一般运营约束下各线上消费群体的消费者选择，并表征品类决策与产品选择概率之间的关系。将所提出的凸包结果与修正的选择概率顺序分离算法相结合，本文构建的模型相较于既有方法具有显著的计算优势。最后，我们展示了该凸包结果在其他品类优化问题中的推广适用性。
介绍
近年来，即时零售作为一种以满足消费者即时需求为核心的新兴商业模式迅速发展。与传统的全渠道零售不同，即时零售要求线上订单所涉及的商品必须在线下实体门店有现货库存，以实现分钟级配送。这一“物理联动”约束使得品类规划问题更为复杂：企业需在有限门店空间内统一规划线下在售品类，同时为不同线上消费群体提供个性化推荐，以最大化整体期望收益。尽管多项对数模型及其变体在品类优化领域已有广泛应用，但现有研究多聚焦于单一渠道或传统线上线下互补场景，未能充分刻画即时零售中线上品类须为线下子集、且不同消费细分服从异质性选择模型的双层决策结构。此外，该问题被证明为NP-难问题，亟需兼具理论严谨性与计算可操作性的求解方法。
本文研究即时零售场景下的品类规划问题，构建了一个包含线下消费者与多个线上消费者细分的联合优化模型。假设线下消费者与各线上细分均服从独立的多项对数模型，且线上细分可享受个性化定价与个性化品类推荐。核心约束在于：任一线上细分可选购的商品必须同时在线下门店有货，即线上品类为线下品类的子集。企业需决策线下门店的全局品类以及各线上细分的个性化品类，以最大化各渠道期望收益的加权和。研究首先指出，传统两步收益排序策略忽略线上需求对线下选品的影响，存在显著最优性差距。进而，本文通过Charnes-Cooper变换将原分数规划问题转化为混合整数双线性规划，并利用凸分析工具对问题的关键子结构进行凸包刻画，为后续精确算法奠定理论基础。
本文的核心方法论围绕凸包刻画与整数规划展开。首先，对于每个消费者类型，本文证明其选择概率集的凸包等价于由可行品类凸包经概率归一化超平面截取所得，从而将复杂的选择行为简化为线性约束系统。该结果推广了既有文献中关于全幺模约束下的紧线性规划表述，并延伸至两阶段Luce模型等更一般的选择模型。其次，针对模型中最为关键的“品类-概率”双线性约束，本文聚焦于单产品情形，推导出两类指数族有效线性不等式（OVER与UNDER），并证明其恰好构成该双线性集的凸包。为克服不等式数量随产品数指数增长的困难，本文设计了一个基于选择概率排序的快速分离算法，时间复杂度为O(n log n)。在此基础上，提出基于切割平面迭代的整数规划框架（CH与CH-Chain），仅需两轮切割即可获得紧的松弛下界。该框架可灵活兼容品类容量、前序关系、覆盖约束等多种运营限制，并可扩展至线上服从独立需求模型、线下服从多项对数模型的混合场景。
本文通过大规模数值实验验证了所提方法的计算优越性。在包含数百产品与上百消费者细分的实例中，所提出的CH-2与CH-Chain-2方法在平均求解时间、稳健性与可扩展性上均显著优于基于锥优化的整数规划和基于大M法的混合整数线性规划。敏感性分析表明：联合优化相较于分步启发式可带来可观收益提升，且收益提升幅度随线上渠道占比上升而扩大；忽视线上消费者偏好的异质性或错误假设选择模型将导致显著的收入损失。本文进一步将模型扩展至前端仓储、库存决策等衍生场景，并提出基于加权价格优先级的库存整数化整方法，仿真实验显示流体近似收益与实际模拟收益的差距随销售周期延长而收敛。总体而言，本文为即时零售品类规划提供了一套兼具理论深度与实用价值的整数规划求解方案，其凸包刻画技巧对于更广泛的Luce型选择模型与双线性优化问题亦具有推广意义。
热门跟贴