供應鏈｜MnSc論文解讀：面向即時零售品類規劃的整數規劃方法

來源：市場資訊

（來源：運籌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型選擇模型與雙線性優化問題亦具有推廣意義。