Afficher la notice abrégée

Branch-and-cut-and-price for the robust capacitated vehicle routing problem with knapsack uncertainty

hal.structure.identifierUniversidade Federal Fluminense [Rio de Janeiro] [UFF]
dc.contributor.authorPESSOA, Artur Alves
hal.structure.identifierMethods, Algorithms for Operations REsearch [MAORE]
dc.contributor.authorPOSS, Michael
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorVANDERBECK, François
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorSADYKOV, Ruslan
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorVANDERBECK, Francois
dc.date.accessioned2024-04-04T02:55:12Z
dc.date.available2024-04-04T02:55:12Z
dc.date.created2020-06
dc.date.issued2021
dc.identifier.issn0030-364X
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/192342
dc.description.abstractEnWe examine the robust counterpart of the classical Capacitated Vehicle Routing Problem (CVRP). We consider two types of uncertainty sets for the customer demands: the classical budget polytope introduced by Bertsimas and Sim (2003), and a partitioned budget polytope proposed by Gounaris et al. (2013). We show that using the set-partitioning formulation it is possible to reformulate our problem as a deterministic heterogeneous vehicle routing problem. Thus, many state-of-the-art techniques for exactly solving deterministic VRPs can be applied for the robust counterpart, and a modern branch-and-cut-and-price algorithm can be adapted to our setting by keeping the number of pricing subproblems strictly polynomial. More importantly, we introduce new techniques to significantly improve the efficiency of the algorithm. We present analytical conditions under which a pricing subproblem is infeasible. This result is general and can be applied to other combinatorial optimization problems with knapsack uncertainty. We also introduce robust capacity cuts which are provably stronger than the ones known in the literature. Finally, a fast iterated local search algorithm is proposed to obtain heuristic solutions for the problem. Using our branch-and-cut-and-price algorithm incorporating existing and new techniques, we are able to solve to optimality all but one open instances from the literature.
dc.description.sponsorshipOrdonancement robuste avec durée incertaines pour une incertitude de type budget - ANR-16-CE40-0018
dc.language.isoen
dc.publisherINFORMS
dc.subject.enCapacity inequalities
dc.subject.enBranch-cut-and-price
dc.subject.enLocal search
dc.subject.enBranch-and-cut-and-price
dc.subject.enRobust optimization
dc.title.enBranch-and-cut-and-price for the robust capacitated vehicle routing problem with knapsack uncertainty
dc.typeArticle de revue
dc.identifier.doi10.1287/opre.2020.2035
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalOperations Research
bordeaux.page739-754
bordeaux.volume69
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue3
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.type.institutionUniversidade Federal Fluminense
bordeaux.peerReviewedoui
bordeaux.type.reportrr
hal.identifierhal-01958184
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-01958184v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Operations%20Research&rft.date=2021&rft.volume=69&rft.issue=3&rft.spage=739-754&rft.epage=739-754&rft.eissn=0030-364X&rft.issn=0030-364X&rft.au=PESSOA,%20Artur%20Alves&POSS,%20Michael&VANDERBECK,%20Fran%C3%A7ois&SADYKOV,%20Ruslan&VANDERBECK,%20Francois&rft.genre=article


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée