A Branch & Cut algorithm for the prize-collecting capacitated location routing problem

Daniel Negrotto () and Irene Loiseau ()
Additional contact information
Daniel Negrotto: Universidad de Buenos Aires
Irene Loiseau: Universidad de Buenos Aires

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 2021, vol. 29, issue 1, No 3, 34-57

Abstract: Abstract The Capacitated location routing problem (CLRP) is the combination of two well-studied problems in Operations Research: the capacitated facility location problem (CFLP) and the multiple depots vehicle routing problem (MDVRP). Given a set of available locations and a fleet of vehicles, the aim is to determine a set of depots to open and routes of the vehicles to satisfy the customers demands. The objective of the CLRP is to minimize the total cost, that is the cost of the opened depots, the fixed cost of the vehicles and the cost of the routes while satisfying vehicle and depot capacity constraints. In this work the prize-collecting capacitated location routing problem (PC-CLRP), a new variant of the CLRP is presented. In this case it is possible to leave some customers unvisited and if a customer is visited it gives a gain. The objective is to maximize the overall benefit. A two-index formulation for the PC-CLRP and a Branch & Cut algorithm based on this model are proposed. Valid inequalities for the CLRP are adapted for the PC-CLRP. Also new valid inequalities and optimality cuts are proposed together with their corresponding separation algorithms. A hierarchical branching strategy is also included. The initial solution was provided by an Ant Colony Algorithm. The algorithm is tested on a set of instances specially designed for the new problem. Computational results showed very promising. We also compare the performance of the algorithm with recent work for CLRP on instances from the literature.

Keywords: Location-routing problem; Vehicle routing; Integer linear programming; Branch & Cut (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11750-020-00590-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:topjnl:v:29:y:2021:i:1:d:10.1007_s11750-020-00590-x

Ordering information: This journal article can be ordered from
http://link.springer.de/orders.htm

DOI: 10.1007/s11750-020-00590-x

Access Statistics for this article

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research is currently edited by Juan José Salazar González and Gustavo Bergantiños

More articles in TOP: An Official Journal of the Spanish Society of Statistics and Operations Research from Springer, Sociedad de Estadística e Investigación Operativa
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().