Mostrar el registro sencillo del ítem

An improved branch-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem

hal.structure.identifierLaboratoire de l'intégration, du matériau au système [IMS]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorMARQUES, Guillaume
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorSADYKOV, Ruslan
hal.structure.identifierLaboratoire de l'intégration, du matériau au système [IMS]
dc.contributor.authorDESCHAMPS, Jean-Christophe
hal.structure.identifierLaboratoire de l'intégration, du matériau au système [IMS]
dc.contributor.authorDUPAS, Rémy
dc.date.accessioned2024-04-04T02:48:59Z
dc.date.available2024-04-04T02:48:59Z
dc.date.issued2020
dc.identifier.issn0305-0548
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/191784
dc.description.abstractEnIn the paper, we propose a branch-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem in which delivery of products from a depot to customers is performed using intermediate depots called satellites. Our algorithm incorporates significant improvements recently proposed in the literature for the standard capacitated vehicle routing problem such as bucket graph based labeling algorithm for the pricing problem, automatic stabilization, limited memory rank-1 cuts, and strong branching. In addition, we make some specific problem contributions. First, we introduce a new route based formulation for the problem which does not use variables to determine product flows in satellites. Second, we introduce a new branching strategy which significantly decreases the size of the branch-and-bound tree. Third, we introduce a new family of satellite supply inequalities, and we empirically show that it improves the quality of the dual bound at the root node of the branch-and-bound tree. Finally, extensive numerical experiments reveal that our algorithm can solve to optimality all literature instances with up to 200 customers and 10 satellites for the first time and thus double the size of instances which could be solved to optimality.
dc.language.isoen
dc.publisherElsevier
dc.title.enAn improved branch-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem
dc.typeArticle de revue
dc.identifier.doi10.1016/j.cor.2019.104833
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalComputers and Operations Research
bordeaux.page104833
bordeaux.volume114
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-02112287
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-02112287v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Computers%20and%20Operations%20Research&rft.date=2020&rft.volume=114&rft.spage=104833&rft.epage=104833&rft.eissn=0305-0548&rft.issn=0305-0548&rft.au=MARQUES,%20Guillaume&SADYKOV,%20Ruslan&DESCHAMPS,%20Jean-Christophe&DUPAS,%20R%C3%A9my&rft.genre=article


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