An exact method for the capacitated location-routing problem

The capacitated location-routing problem (LRP) consists of opening one or more depots on a given set of a-priori defined depot locations, and designing, for each opened depot, a number of routes in order to supply the demands of a given set of customers. With each depot are associated a fixed cost for opening it and a capacity that limits the quantity that can be delivered to the customers. The objective is to minimize the sum of the fixed costs for opening the depots and the costs of the routes operated from the depots. This paper describes a new exact method for solving the LRP based on a set-partitioning- like formulation of the problem. The lower bounds produced by different bounding procedures, based on dynamic programming and dual ascent methods, are used by an algorithm that decomposes the LRP into a limited set of multicapacitated depot vehicle-routing problems (MCDVRPs). Computational results on benchmark instances from the literature show that the proposed method outperforms the current best-known exact methods, both for the quality of the lower bounds achieved and the number and the dimensions of the instances solved to optimality. Subject classifications: location routing; set partitioning; dual ascent; dynamic programming. Area of review: Transportation. History: Received July 2009; revisions received July 2010, October 2010; accepted January 2011.