Mostrar el registro sencillo del ítem

On the exact solution of vehicle routing problems with backhauls

hal.structure.identifierInstituto de Computação [Niteroi-Rio de Janeiro] [IC-UFF]
dc.contributor.authorQUEIROGA, Eduardo
hal.structure.identifierInstituto de Computação [Niteroi-Rio de Janeiro] [IC-UFF]
dc.contributor.authorFROTA, Yuri
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorSADYKOV, Ruslan
hal.structure.identifierUniversidade Federal da Paraiba / Federal University of Paraiba [UFPB]
dc.contributor.authorSUBRAMANIAN, Anand
hal.structure.identifierUniversidade Federal Fluminense [Rio de Janeiro] [UFF]
dc.contributor.authorUCHOA, Eduardo
hal.structure.identifierDepartamento de Informática = Department of Informatics [PUC-Rio]
dc.contributor.authorVIDAL, Thibaut
dc.date.accessioned2024-04-04T02:58:47Z
dc.date.available2024-04-04T02:58:47Z
dc.date.created2020
dc.date.issued2020
dc.identifier.issn0377-2217
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/192686
dc.description.abstractEnIn this paper, we are interested in the exact solution of the vehicle routing problem with back-hauls (VRPB), a classical vehicle routing variant with two types of customers: linehaul (delivery) and backhaul (pickup) ones. We propose two branch-cut-and-price (BCP) algorithms for the VRPB. The first of them follows the traditional approach with one pricing subproblem, whereas the second one exploits the linehaul/backhaul customer partitioning and defines two pricing sub-problems. The methods incorporate elements of state-of-the-art BCP algorithms, such as rounded capacity cuts, limited-memory rank-1 cuts, strong branching, route enumeration, arc elimination using reduced costs and dual stabilization. Computational experiments show that the proposed algorithms are capable of obtaining optimal solutions for all existing benchmark instances with up to 200 customers, many of them for the first time. It is observed that the approach involving two pricing subproblems is more efficient computationally than the traditional one. Moreover, new instances are also proposed for which we provide tight bounds. Also, we provide results for benchmark instances of the heterogeneous fixed fleet VRPB and the VRPB with time windows.
dc.language.isoen
dc.publisherElsevier
dc.subject.enRouting
dc.subject.enBackhauls
dc.subject.enBranch-cut-and-price
dc.subject.enInteger programming
dc.title.enOn the exact solution of vehicle routing problems with backhauls
dc.typeArticle de revue
dc.identifier.doi10.1016/j.ejor.2020.04.047
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalEuropean Journal of Operational Research
bordeaux.page76-89
bordeaux.volume287
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue1
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.type.institutionUniversidade Federal Fluminense
bordeaux.peerReviewedoui
bordeaux.type.reportrr
hal.identifierhal-02379008
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-02379008v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=European%20Journal%20of%20Operational%20Research&rft.date=2020&rft.volume=287&rft.issue=1&rft.spage=76-89&rft.epage=76-89&rft.eissn=0377-2217&rft.issn=0377-2217&rft.au=QUEIROGA,%20Eduardo&FROTA,%20Yuri&SADYKOV,%20Ruslan&SUBRAMANIAN,%20Anand&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