A Branch-and-Cut method for the Capacitated Location-Routing Problem

Recent researches in the design of logistic networks have shown that the overall distribution cost may be excessive if routing decisions are ignored when locating depots The Location-Routing Problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions The aim of this paper is to propose an exact approach based on a Branch-and-Cut algorithm for solving the LRP with capacity constraints on depots and vehicles The proposed method is based on a zero-one linear model strengthened by new families of valid inequalities The computational evaluation on three sets of instances (34 instances in total) with 5-10 potential depots and 20-88 customers shows that 26 instances with five depots are solved to optimality including all instances with up to 40 customers and three with 50 customers.