Mostrar el registro sencillo del ítem

Non-Robust Strong Knapsack Cuts for Capacitated Location-Routing and Related Problems

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLIGUORI, Pedro
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMAHJOUB, Ali Ridha
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorMARQUES, Guillaume
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierFormulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
dc.contributor.authorSADYKOV, Ruslan
hal.structure.identifierUniversidade Federal Fluminense [Rio de Janeiro] [UFF]
dc.contributor.authorUCHOA, Eduardo
dc.date.accessioned2024-04-04T02:37:06Z
dc.date.available2024-04-04T02:37:06Z
dc.date.issued2022-12-02
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/190776
dc.description.abstractEnThe 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 non-robust 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.
dc.language.isoen
dc.title.enNon-Robust Strong Knapsack Cuts for Capacitated Location-Routing and Related Problems
dc.typeRapport
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.type.institutionInria Centre at the University of Bordeaux
hal.identifierhal-03900804
hal.version1
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-03900804v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2022-12-02&rft.au=LIGUORI,%20Pedro&MAHJOUB,%20Ali%20Ridha&MARQUES,%20Guillaume&SADYKOV,%20Ruslan&UCHOA,%20Eduardo&rft.genre=unknown


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem