Paper Info
Title
An Exact Algorithm Based on Cut-and-Column Generation for the Capacitated Location-Routing Problem
Abstract
<P>In this paper we present an exact algorithm for the capacitated location-routing problem (CLRP) based on cut-and-column generation. The CLRP is formulated as a set-partitioning problem that also inherits all of the known valid inequalities for the flow formulations of the CLRP. We introduce five new families of inequalities that are shown to dominate some of the cuts from the two-index formulation. The problem is solved by column generation, where the subproblem consists in finding a shortest path of minimum reduced cost under capacity constraints. We first use the two-index formulation for enumerating all of the possible subsets of depot locations that could lead to an optimal solution of cost less than or equal to a given upper bound. For each of these subsets, the corresponding multiple depot vehicle routing problem is then solved by means of column generation. The results show that we can improve the bounds found in the literature, solve to optimality some previously open instances, and improve the upper bounds on some other instances.</P>
Year
DOI
Venue
2014
10.1287/ijoc.2013.0549
INFORMS Journal on Computing
Keywords
Field
DocType
branch-and-cut-and-price,column generation,location routing,vehicle routing
Discrete mathematics,Mathematical optimization,Column generation,Vehicle routing problem,Reduced cost,Exact algorithm,Shortest path problem,Upper and lower bounds,Mathematics
Journal
Volume
Issue
ISSN
26
1
1091-9856
Citations 
PageRank 
References 
33
0.89
25
Authors
3
Name
Order
Citations
PageRank
Claudio Contardo11858.73
Jean-François Cordeau22604127.77
Bernard Gendron368849.92