The location and routing problem is an integrated problem, combining two problems of the supply chain, the location problem and the vehicle routing problem. The combination of these two important optimization problems to distribution networks can translate into considerable savings, given that a broader vision of costs is taken into account. We address a variant of this problem, the Location and Routing Problem with capacitated depots and vehicles, and Multiple routes (MLRP).

In this paper, we propose a network flow model for the MLRP, whose variables represent feasible vehicle routes. We then propose a variable neighborhood search algorithm, whose neighborhood structures contain neighborhoods for the routing and location problems. There is a compromise between routing configuration in the local search and the location of depots in the perturbation or shaking phase. During the exploration of the solution space, not only feasible solutions are considered, but also solutions that violate the capacity constraints of vehicles or depots. Finally, a hybrid approach that combines a column generation algorithm with variable neighborhood search is proposed. The variable neighborhood search is used in the column generation algorithm to generate “good” columns, in order to accelerate the convergence of the process. Computational experiments are conducted on a set of instances from the literature to validate our approaches.