供應(yīng)鏈｜MnSc論文解讀：面向即時(shí)零售品類規(guī)劃的整數(shù)規(guī)劃方法

來源：市場資訊

（來源：運(yùn)籌OR帷幄）

據(jù)MS官網(wǎng)顯示，來自上海交通大學(xué)安泰經(jīng)管學(xué)院的Yajing Chen、何濤濤、榮鷹、王云龍，合著的論文“ An Integer Programming Approach for Quick-Commerce Assortment Planning ”在國際管理學(xué)頂刊《Management Science》線上正式發(fā)表。

Title: An Integer Programming Approach for Quick-Commerce Assortment Planning

面向即時(shí)零售品類規(guī)劃的整數(shù)規(guī)劃方法

作者簡介

Yajing Chen

上海交通大學(xué)

何濤濤

上海交通大學(xué)

榮鷹

上海交通大學(xué)

王云龍

上海交通大學(xué)

摘要

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.

本文探討即時(shí)零售背景下的品類規(guī)劃問題，即時(shí)零售是一種旨在配送時(shí)效敏感型產(chǎn)品的快速增長商業(yè)模式。為實(shí)現(xiàn)快速配送以響應(yīng)鄰近地區(qū)線上消費(fèi)者的即時(shí)需求，企業(yè)需將個(gè)性化的線上品類納入實(shí)體門店的線下在售商品組合。在存在此類物理聯(lián)動(dòng)約束、且線上消費(fèi)群體服從差異化多項(xiàng)對數(shù)選擇模型的條件下，企業(yè)需為各區(qū)域門店選擇最優(yōu)品類集合，并為每一線上消費(fèi)群體定制個(gè)性化品類方案，以最大化整體收益。本文采用整數(shù)規(guī)劃方法求解該NP-hard問題至全局最優(yōu)，我們推導(dǎo)了凸包結(jié)果，以刻畫一般運(yùn)營約束下各線上消費(fèi)群體的消費(fèi)者選擇，并表征品類決策與產(chǎn)品選擇概率之間的關(guān)系。將所提出的凸包結(jié)果與修正的選擇概率順序分離算法相結(jié)合，本文構(gòu)建的模型相較于既有方法具有顯著的計(jì)算優(yōu)勢。最后，我們展示了該凸包結(jié)果在其他品類優(yōu)化問題中的推廣適用性。

介紹

近年來，即時(shí)零售作為一種以滿足消費(fèi)者即時(shí)需求為核心的新興商業(yè)模式迅速發(fā)展。與傳統(tǒng)的全渠道零售不同，即時(shí)零售要求線上訂單所涉及的商品必須在線下實(shí)體門店有現(xiàn)貨庫存，以實(shí)現(xiàn)分鐘級配送。這一“物理聯(lián)動(dòng)”約束使得品類規(guī)劃問題更為復(fù)雜：企業(yè)需在有限門店空間內(nèi)統(tǒng)一規(guī)劃線下在售品類，同時(shí)為不同線上消費(fèi)群體提供個(gè)性化推薦，以最大化整體期望收益。盡管多項(xiàng)對數(shù)模型及其變體在品類優(yōu)化領(lǐng)域已有廣泛應(yīng)用，但現(xiàn)有研究多聚焦于單一渠道或傳統(tǒng)線上線下互補(bǔ)場景，未能充分刻畫即時(shí)零售中線上品類須為線下子集、且不同消費(fèi)細(xì)分服從異質(zhì)性選擇模型的雙層決策結(jié)構(gòu)。此外，該問題被證明為NP-難問題，亟需兼具理論嚴(yán)謹(jǐn)性與計(jì)算可操作性的求解方法。

本文研究即時(shí)零售場景下的品類規(guī)劃問題，構(gòu)建了一個(gè)包含線下消費(fèi)者與多個(gè)線上消費(fèi)者細(xì)分的聯(lián)合優(yōu)化模型。假設(shè)線下消費(fèi)者與各線上細(xì)分均服從獨(dú)立的多項(xiàng)對數(shù)模型，且線上細(xì)分可享受個(gè)性化定價(jià)與個(gè)性化品類推薦。核心約束在于：任一線上細(xì)分可選購的商品必須同時(shí)在線下門店有貨，即線上品類為線下品類的子集。企業(yè)需決策線下門店的全局品類以及各線上細(xì)分的個(gè)性化品類，以最大化各渠道期望收益的加權(quán)和。研究首先指出，傳統(tǒng)兩步收益排序策略忽略線上需求對線下選品的影響，存在顯著最優(yōu)性差距。進(jìn)而，本文通過Charnes-Cooper變換將原分?jǐn)?shù)規(guī)劃問題轉(zhuǎn)化為混合整數(shù)雙線性規(guī)劃，并利用凸分析工具對問題的關(guān)鍵子結(jié)構(gòu)進(jìn)行凸包刻畫，為后續(xù)精確算法奠定理論基礎(chǔ)。

本文的核心方法論圍繞凸包刻畫與整數(shù)規(guī)劃展開。首先，對于每個(gè)消費(fèi)者類型，本文證明其選擇概率集的凸包等價(jià)于由可行品類凸包經(jīng)概率歸一化超平面截取所得，從而將復(fù)雜的選擇行為簡化為線性約束系統(tǒng)。該結(jié)果推廣了既有文獻(xiàn)中關(guān)于全幺模約束下的緊線性規(guī)劃表述，并延伸至兩階段Luce模型等更一般的選擇模型。其次，針對模型中最為關(guān)鍵的“品類-概率”雙線性約束，本文聚焦于單產(chǎn)品情形，推導(dǎo)出兩類指數(shù)族有效線性不等式（OVER與UNDER），并證明其恰好構(gòu)成該雙線性集的凸包。為克服不等式數(shù)量隨產(chǎn)品數(shù)指數(shù)增長的困難，本文設(shè)計(jì)了一個(gè)基于選擇概率排序的快速分離算法，時(shí)間復(fù)雜度為O(n log n)。在此基礎(chǔ)上，提出基于切割平面迭代的整數(shù)規(guī)劃框架（CH與CH-Chain），僅需兩輪切割即可獲得緊的松弛下界。該框架可靈活兼容品類容量、前序關(guān)系、覆蓋約束等多種運(yùn)營限制，并可擴(kuò)展至線上服從獨(dú)立需求模型、線下服從多項(xiàng)對數(shù)模型的混合場景。

本文通過大規(guī)模數(shù)值實(shí)驗(yàn)驗(yàn)證了所提方法的計(jì)算優(yōu)越性。在包含數(shù)百產(chǎn)品與上百消費(fèi)者細(xì)分的實(shí)例中，所提出的CH-2與CH-Chain-2方法在平均求解時(shí)間、穩(wěn)健性與可擴(kuò)展性上均顯著優(yōu)于基于錐優(yōu)化的整數(shù)規(guī)劃和基于大M法的混合整數(shù)線性規(guī)劃。敏感性分析表明：聯(lián)合優(yōu)化相較于分步啟發(fā)式可帶來可觀收益提升，且收益提升幅度隨線上渠道占比上升而擴(kuò)大；忽視線上消費(fèi)者偏好的異質(zhì)性或錯(cuò)誤假設(shè)選擇模型將導(dǎo)致顯著的收入損失。本文進(jìn)一步將模型擴(kuò)展至前端倉儲、庫存決策等衍生場景，并提出基于加權(quán)價(jià)格優(yōu)先級的庫存整數(shù)化整方法，仿真實(shí)驗(yàn)顯示流體近似收益與實(shí)際模擬收益的差距隨銷售周期延長而收斂?？傮w而言，本文為即時(shí)零售品類規(guī)劃提供了一套兼具理論深度與實(shí)用價(jià)值的整數(shù)規(guī)劃求解方案，其凸包刻畫技巧對于更廣泛的Luce型選擇模型與雙線性優(yōu)化問題亦具有推廣意義。