Mostrar el registro sencillo del ítem

A Bucket Graph Based Labelling Algorithm for Vehicle Routing

hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorSADYKOV, Ruslan
hal.structure.identifierUniversidade Federal Fluminense [Rio de Janeiro] [UFF]
dc.contributor.authorPESSOA, Artur
hal.structure.identifierUniversidade Federal Fluminense [Rio de Janeiro] [UFF]
dc.contributor.authorUCHOA, Eduardo
dc.date.accessioned2024-04-04T02:48:59Z
dc.date.available2024-04-04T02:48:59Z
dc.date.issued2021
dc.identifier.issn0041-1655
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/191785
dc.description.abstractEnWe consider the Shortest Path Problem with Resource Constraints (SPPRC) arising as a subproblem in state-of-the-art Branch-Cut-and-Price algorithms for vehicle routing problems. We propose a variant of the bi-directional label correcting algorithm in which the labels are stored and extended according to the so-called bucket graph. Such organization of labels helps to decrease significantly the number of dominance checks and the running time of the algorithm. We also show how the forward/backward route symmetry can be exploited and how to eliminate arcs from the bucket graph using reduced costs. The proposed algorithm can be especially beneficial for vehicle routing instances with large vehicle capacity and/or with time window constraints. Computational experiments were performed on instances from the distance constrained vehicle routing problem, including multi-depot and site-dependent variants, on the vehicle routing problem with time windows, and on the "nightmare" instances of the heterogeneous fleet vehicle routing problem. Significant improvements over the best algorithms in the literature were achieved and many instances could be solved for the first time.
dc.language.isoen
dc.publisherINFORMS
dc.title.enA Bucket Graph Based Labelling Algorithm for Vehicle Routing
dc.typeArticle de revue
dc.identifier.doi10.1287/trsc.2020.0985
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalTransportation Science
bordeaux.page4-28
bordeaux.volume55
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue1
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-02378624
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-02378624v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Transportation%20Science&rft.date=2021&rft.volume=55&rft.issue=1&rft.spage=4-28&rft.epage=4-28&rft.eissn=0041-1655&rft.issn=0041-1655&rft.au=SADYKOV,%20Ruslan&PESSOA,%20Artur&UCHOA,%20Eduardo&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