Near-Optimal Algorithms for the Assortment Planning Problem Under Dynamic Substitution and Stochastic Demand

Vineet Goyal (), Retsef Levi () and Danny Segev ()
Additional contact information
Vineet Goyal: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Retsef Levi: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Danny Segev: Department of Statistics, University of Haifa, Haifa 31905, Israel

Operations Research, 2016, vol. 64, issue 1, 219-235

Abstract: Assortment planning of substitutable products is a major operational issue that arises in many industries such as retailing, airlines, and consumer electronics. We consider a single-period joint assortment and inventory planning problem under dynamic substitution with stochastic demands, and provide complexity and algorithmic results as well as insightful structural characterizations of near-optimal solutions for important variants of the problem. First, we show that the assortment planning problem is NP-hard even for a very simple consumer choice model, where each consumer is willing to buy only two products. In fact, we show that the problem is hard to approximate within a factor better than 1 − 1/ e . Second, we show that for several interesting and practical customer choice models, one can devise a polynomial-time approximation scheme (PTAS), i.e., the problem can be solved efficiently to within any level of accuracy. To the best of our knowledge, this is the first efficient algorithm with provably near-optimal performance guarantees for assortment planning problems under dynamic substitution. Quite surprisingly, the algorithm we propose stocks only a constant number of different product types; this constant depends only on the desired accuracy level. This provides an important managerial insight that assortments with a relatively small number of product types can obtain almost all of the potential revenue. Furthermore, we show that our algorithm can be easily adapted for more general choice models, and we present numerical experiments to show that it performs significantly better than other known approaches.

Keywords: assortment planning; dynamic substitution; polynomial time approximation schemes (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2015.1450 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:64:y:2016:i:1:p:219-235

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().