Multi-Location Assortment Optimization Under Capacity Constraints

We study the assortment optimization problem in an online setting where a retailer uses multiple distribution centers to fulfill customer orders. Due to space, handling or other constraints, each distribution center can carry up to a pre-specified number of products. It is assumed that each distribution center is primarily responsible for a geographical region whose customers' choice is governed by a separate multinomial logit model. A distribution center can satisfy the demand from other regions, but this incurs an additional shipping cost for the retailer. The problem for the retailer is to determine which products to carry in each of its distribution centers and which products to offer for sale in each region so as to maximize its expected profit (revenue minus the shipping costs). We first show that the problem is NP-complete. We develop a conic quadratic mixed integer programming formulation and suggest a family of valid inequalities to strengthen this formulation. Numerical experiments show that our conic approach, combined with valid inequalities over-perform the mixed integer linear programming formulation and enables us to solve moderately sized instances optimally. We also study the effect of various factors such as the strength of the outside option, capacity constraint and shipping cost on company's profitability and assortment selection. Finally, we study the effect of not allowing cross-shipments or not considering them in assortment decisions and show that these may lead to substantial losses for an online retailer