IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v71y2023i5p1577-1595.html
   My bibliography  Save this article

Nonrobust Strong Knapsack Cuts for Capacitated Location Routing and Related Problems

Author

Listed:
  • 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)

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.

Suggested Citation

  • Pedro Henrique Liguori & A. Ridha Mahjoub & Guillaume Marques & Ruslan Sadykov & Eduardo Uchoa, 2023. "Nonrobust Strong Knapsack Cuts for Capacitated Location Routing and Related Problems," Operations Research, INFORMS, vol. 71(5), pages 1577-1595, September.
    • Handle: RePEc:inm:oropre:v:71:y:2023:i:5:p:1577-1595
    DOI: 10.1287/opre.2023.2458
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2023.2458
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2023.2458?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:71:y:2023:i:5:p:1577-1595. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.