An Exact Method for the Capacitated Location-Routing Problem

Roberto Baldacci (), Aristide Mingozzi () and Roberto Wolfler Calvo ()
Additional contact information
Roberto Baldacci: Department of Electronics, Computer Science and Systems, University of Bologna, 47521 Cesena, Italy
Aristide Mingozzi: Department of Mathematics, University of Bologna, 47521 Cesena, Italy
Roberto Wolfler Calvo: Laboratoire d'Informatique de Paris-Nord (LIPN, UMR 7030), 93430 Villetaneuse, France

Operations Research, 2011, vol. 59, issue 5, 1284-1296

Abstract: 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.

Keywords: location routing; set partitioning; dual ascent; dynamic programming (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (37)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1110.0989 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:59:y:2011:i:5:p:1284-1296

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().