Non-Robust Strong Knapsack Cuts for Capacitated Location-Routing and Related Problems
Sadykov, Ruslan; Pereira Vargas Liguori, Pedro; Mahjoub, Ali Ridha; Marques, Guillaume; Uchoa, Eduardo (2022-11), Non-Robust Strong Knapsack Cuts for Capacitated Location-Routing and Related Problems, Journée commune ROADEF / AIRO, 2022-11, Virtual, France
Type
Communication / ConférenceExternal document link
https://hal.archives-ouvertes.fr/hal-03899418Date
2022-11Conference title
Journée commune ROADEF / AIROConference date
2022-11Conference city
VirtualConference country
FrancePages
1-34
Metadata
Show full item recordAuthor(s)
Sadykov, Ruslan
Inria Bordeaux - Sud-Ouest
Pereira Vargas Liguori, Pedro
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mahjoub, Ali Ridha
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Marques, Guillaume
Atoptima
Uchoa, Eduardo
Federal University Fluminense [Rio de Janeiro, Brazil] [FUF]
Abstract (EN)
The Capacitated Location-Routing Problem consists in, given a set of locations and a set of customers, determine 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 this work is a family of non-robust cuts, which we call the Route Load Knapsack Cuts. They are 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.Related items
Showing items related by title and author.
-
Pereira Vargas Liguori, Pedro; Pereira Vargas Liguori, Pedro Henrique; Mahjoub, Ali Ridha; Marques, Guillaume; Uchoa, Eduardo (2022-12) Document de travail / Working paper
-
Pereira Vargas Liguori, Pedro Henrique; Mahjoub, Ali Ridha; Sadykov, Ruslan; Uchoa, Eduardo (2019) Communication / Conférence
-
A Branch-and-Cut Algorithm for the Alternative Fuel Refueling Station Location Problem with Routing Arslan, Okan; Karaşan, Oya Ekin; Mahjoub, Ali Ridha; Yaman, Hande (2019) Article accepté pour publication ou publié
-
Borne, Sylvie; Gourdin, Eric; Klopfenstein, Olivier; Mahjoub, Ali Ridha (2018) Article accepté pour publication ou publié
-
Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021) Document de travail / Working paper