A Benders Decomposition Approach for the Two-Echelon Stochastic Multi-period Capacitated Location-Routing Problem

In the first echelon of the two-echelon stochastic multi-period capacitated location-routing problem (2E-SM-CLRP), one has to decide the number and location of warehouse platforms as well as the intermediate distribution platforms for each period; while fixing the capacity of the links between them. The system must be dimensioned to enable an efficient distribution of goods to customers under a stochastic and time-varying demand. In the second echelon of the 2E-SM-CLRP, the goal is to construct vehicle routes that visit customers from operating distribution platforms. The objective is to minimize the total expected cost. We model this hierarchical decision problem as a two-stage stochastic program with integer recourse. The first-stage includes location and capacity decisions to be fixed at each period over the planning horizon, while routing decisions of the second echelon are determined in the recourse problem. We propose a Benders decomposition approach to solve this model. In the proposed approach, the location and capacity decisions are taken by solving the Benders master problem. After these first-stage decisions are fixed, the resulting subproblem is a capacitated vehicle-routing problem with capacitated multi-depot (CVRP-CMD) that is solved by a branch-cut-and-price algorithm. Computational experiments show that instances of realistic size can be solved optimally within reasonable time, and that relevant managerial insights are derived on the behavior of the design decisions under the stochastic multi-period characterization of the planning horizon