Nonrobust Strong Knapsack Cuts for Capacitated Location Routing and Related Problems

Pedro Henrique Liguori (), A. Ridha Mahjoub (), Guillaume Marques (), Ruslan Sadykov () and Eduardo Uchoa ()
Additional contact information
Pedro Henrique Liguori: Laboratoire d’Analyse et de Modélisation de Systèmes pour l’Aide à la Décision, Université Paris-Dauphine (Paris Sciences & Lettres), Paris 75016, France
A. Ridha Mahjoub: Laboratoire d’Analyse et de Modélisation de Systèmes pour l’Aide à la Décision, Université Paris-Dauphine (Paris Sciences & Lettres), Paris 75016, France; Department of Statistics and Operations Research, College of Science, Kuwait University, Kuwait
Guillaume Marques: Institut National de Recherche en Sciences et Technologies du Numérique, Inria Centre at the University of Bordeaux, Talence 33405, France; Atoptima SAS, Bordeaux 33000, France
Ruslan Sadykov: Institut National de Recherche en Sciences et Technologies du Numérique, Inria Centre at the University of Bordeaux, Talence 33405, France
Eduardo Uchoa: Institut National de Recherche en Sciences et Technologies du Numérique, Inria Centre at the University of Bordeaux, Talence 33405, France; Departamento deEngenharia de Produção, Universidade Federal Fluminense, Niteroi-RJ 24210-240, Brazil

Operations Research, 2023, vol. 71, issue 5, 1577-1595

Abstract: The capacitated location-routing problem consists in, given a set of locations and a set of customers, determining in which locations one should install depots with limited capacity, and for each depot, design a number of routes to supply customer demands. We provide a formulation that includes depot variables, edge variables, assignment variables, and an exponential number of route variables, together with some new families of valid inequalities, leading to a branch-cut-and-price algorithm. The main original methodological contribution of the article is the route load knapsack cuts, a family of nonrobust cuts, defined over the route variables, devised to strengthen the depot capacity constraints. We explore the monotonicity and the superadditivity properties of those cuts to adapt the labeling algorithm, used in the pricing, for handling the additional dual variables efficiently. Computational experiments show that several capacitated location-routing previously unsolved instances from the literature can now be solved to optimality. Additional experiments with hard instances of the vehicle routing problem with capacitated multiple depots and with instances of the vehicle routing problem with time windows and shifts indicate that the newly proposed cuts are also effective for those problems.

Keywords: Transportation; location routing; cutting planes; column generation (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.2458 (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:71:y:2023:i:5:p:1577-1595

Access Statistics for this article

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