Joint Assortment and Inventory Planning Under the Markov Chain Choice Model
针对在线零售商面临的可替代产品，研究如何同时决定品类和库存以最大化期望利润，提出基于样本平均近似的算法，在马尔可夫链选择模型下实现低遗憾，并有效处理长尾产品库存。
We address the joint assortment and inventory optimization problem for an online retailer facing a set of N substitutable products. The retailer must determine both the assortment and inventories of these products before the start of the selling season to maximize the expected profit. We consider a setting with dynamic SOBS, where consumers’ choices follow the Markov chain choice model. This is a challenging problem, and even computing the expected profit for a given assortment and inventory solution requires solving an intractable dynamic program. We present a sample average approximation-based algorithm for the problem that achieves a regret of [Formula: see text] with respect to an linear program (LP) upper bound. Our algorithm first selects an assortment by balancing the expected revenue (from a single consumer) and the inventory cost. We do this by identifying a subset of products that can pool demand from the universe of substitutable products without significantly cannibalizing the revenue in the presence of dynamic substitution behavior of consumers. We then use a sample average approximation-based LP to decide on the inventory level for each item in the selected assortment. We numerically show that our algorithm considerably improves the performance over standard approaches from the literature on a wide range of instances of the Markov chain choice model and demonstrate that it carefully handles the inventory of products in the long tail (i.e., products with small mean total demand). This paper was accepted by Chung Piaw Teo, optimization. Funding: This work was supported by Amazon [Research Award (V. Goyal and O. El Housni)] and the National Science Foundation [Grants CMMI 1636046 (V. Goyal) and 2226900 (O. El Housni)]. The research was partially supported by RGC from Hong Kong [Grant 16215820 (G. Gallego)]. Supplemental Material: The online appendices and data files are available at https://doi.org/10.1287/mnsc.2023.01322 .