An efficient algorithm for capacitated assortment planning with stochastic demand and substitution

• Increasing product variety requires efficient assortments as shelf space is scarce.
• The stochastic model integrates out-of-assortment and out-of-stock substitution.
• Algorithm has been developed for practically relevant problem sizes.
• An optimal solution procedure and a time-efficient heuristic are presented.

The ever increasing product variety in grocery retailing is in conflict with the limited shelf space. Managing the assortment and regular order quantity for perishable and non-perishable products is therefore a core task for retailers. Retailers want to maximize profit by considering potential revenues, purchase costs, diminishing profits for products and opportunity costs for unfulfilled demand when determining assortment sizes and order volume to meet stochastic consumer demand.We considered a newsvendor-based decision model that jointly optimizes assortment size and the associated order volumes for listed items. The model considers out-of-assortment (OOA) and out-of-stock (OOS) substitution effects. The model is a structural equivalent to the model described in Kök and Fisher (2007) and solved there via a heuristic procedure. We develop an optimal solution procedure and a time-efficient heuristic that solves the model. The heuristic suggested is applicable for practically relevant, large-scale problem instances. Numerical tests reveal that the heuristic procedure produces close-to-optimal solutions and outperforms the Kök and Fisher heuristic with regard to both computational time and solution quality. A simulation study with discrete demand justifies our approach with using continuous demand distributions. The numerical analyses show that considering substitution effects in a decision-based model has a significant impact on the total profit and solution structure. Further managerial insights are presented with regard to assortment heterogeneity when shelf size, substitution and demand variability are varied.