ICC   25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Unidad Ejecutora - UE
congresos y reuniones científicas
Título:
A Branch-and-cut Algorithm for the Prize-Collecting Capacitated Location Routing Problem
Autor/es:
NEGROTTO, DANIEL; LOISEAU, IRENE
Lugar:
Santa CruZ
Reunión:
Workshop; Land-TRANSLOG III; 2016
Resumen:
The Location RoutingProblem (LRP) is the combination of two well studied problems: the facilitylocation problem and the vehicle routing problem. In the logistics field, thesetwo problems are sometimes treated independently. However, this approach leadsto suboptimal solutions.  The CapacitatedLocation Routing Problem (CLRP) is the most studied variant of the LRP. Given aset of available locations, the aim is to find a subset of them to open depots,and to determine the routes to visit the customers in order to satisfy theirdemands. The objective is to minimize the cost of the opened depots, the fixedcost of the vehicles in use and the cost of the routes, satisfying vehicle anddepot capacity constraints.  Inthis work we present, a new variant of the problem named Prize-CollectingCapacitated Location Routing Problem (PC-CLRP). This  is a generalization of CLRP. In this case wehave the possibility toleave customers unvisited.If a customer isvisited it gives a prize or gain. Themaximization of these benefits is a new objective for this problem. As far weknow, PC-CLRP has not been studied before in literature. We proposed threeinteger linear programming formulations for the PC-CLRP (two-index andthree-index flow models). We implemented a Branch-and-Cut algorithm based onone of those models. The algorithm is implemented using the commercial integerlinear programming solver CPLEX 12.6 and coded in C++. Valid inequalitiesproposed at the literature for CLRP were analyzed and adapted for PC-CLRP. Thiswas complemented with the development of new valid inequalities and optimalitycuts, together with their corresponding separation algorithms.  Several separationstrategies were tested using an algorithmic parameterization approach and theauxiliary  configuration software IRACE (IteratedRacing for Automatic Algorithm Configuration Software) version1.06. A hierarchical branchingstrategy was also included. In some cases branching on variables is selectedwhile in the others branching on constraints is preferable.  The branch-and-cut algorithm includes apreprocessing phase and a primal heuristic. The initial solution was providedby an Ant Colony Optimization Algorithm we had previously developed.  In order to check ourbranch-and-cut algorithm, a new set of instances was specially generated forthe PC-CLRP based on the set of 30 Prodhon instances and a random generator algorithm. Computational resultsare promising. Optimal solutions were obtained for  the set of small size instances (20customers) and for two instances from the medium size instance set (50customers), whereas in the rest of the instances, the gaps obtained showed thatthe algorithm gives good results. Most of the instances were solved with gapsnot exceeding 10 percent to their optimal solutions.  We also compared ouralgorithm with  recent work for the CLRPon Prodhon instances. Our algorithm can be tested on those CLRP instances ifvirtual benefits are properly generated. The solutions obtained showed thatthis algorithm is competitive with previous branch-and-cut algorithms for theCLRP.