An exact algorithm for the Prize-Collecting Capacitated Location Routing Problem

LOISEAU, IRENE; NEGROTTO, DANIEL

Santiago

Congreso; XVIII CLAIO, Latin-Iberoamerican Conference on Operations Research; 2016

Pontificia Universidad Católica de Chile, en conjunto con ALIO e ICHIO.

The Capacitated Location Routing Problem (CLRP) is the combination of two well studied problems: the facility location problem and the capacitated vehicle routing problem. The objective is to minimize the cost of the open depots, the fixed cost of the vehicles and the cost of the routes. We present here a new variant, the Prize-Collecting Capacitated Location Routing Problem (PC-CLRP).In this case it is possible to leave customers unvisited and if a customer is visited it gives a gain. We proposed three integer linear programming formulations for the PC-CLRP (two-index and three-index flow models). We implemented a Branch-and-Cut algorithm based on one of them. Valid inequalities for the CLRP were adapted for the PC-CLRP. Also new valid inequalities and optimality cuts were proposed, together with their separation algorithms. A hierarchical branching strategy was also included. The initial solution was provided by an Ant Colony Algorithm. Computational results showed very promising.