Benders decomposition for a stochastic three-level lot sizing and replenishment problem with a distribution structure

We address a stochastic three-level lot sizing and replenishment problem with a distribution structure in a two-stage decision process. We consider one production plant that produces one type of item over a discrete and finite planning horizon. The items produced are transported to warehouses and then to retailers using direct shipments. Each retailer is linked to a unique warehouse and there are no transfers between warehouses nor between retailers. The stochasticity comes from the uncertainty in the demand at the retailer level and is modelled through scenarios. The setup decisions are made in the first stage and the production, transportation and inventory decisions are made in the second stage, once the demands are revealed. The objective is to minimize the sum of the fixed production and replenishment costs, and of the expected variable inventory holding costs among all scenarios. We also study an extension where we allow for lost sales at the retailer level. We use a Benders decomposition approach and develop a Benders-based branch-and-cut algorithm to efficiently solve the problem. We take advantage of the substructures identified in the decomposition and design efficient procedures to solve the subproblems obtained. We also propose computational enhancements to speed up the solution process. Finally, we perform extensive computational experiments to assess the performance of our decomposition approach and analyze the impact of the enhancements. The Benders-based branch-and-cut algorithm we propose clearly outperforms CPLEX.