On the exact solution of vehicle routing problems with backhauls
hal.structure.identifier | Instituto de Computação [Niteroi-Rio de Janeiro] [IC-UFF] | |
dc.contributor.author | QUEIROGA, Eduardo | |
hal.structure.identifier | Instituto de Computação [Niteroi-Rio de Janeiro] [IC-UFF] | |
dc.contributor.author | FROTA, Yuri | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
dc.contributor.author | SADYKOV, Ruslan | |
hal.structure.identifier | Universidade Federal da Paraiba / Federal University of Paraiba [UFPB] | |
dc.contributor.author | SUBRAMANIAN, Anand | |
hal.structure.identifier | Universidade Federal Fluminense [Rio de Janeiro] [UFF] | |
dc.contributor.author | UCHOA, Eduardo | |
hal.structure.identifier | Departamento de Informática = Department of Informatics [PUC-Rio] | |
dc.contributor.author | VIDAL, Thibaut | |
dc.date.accessioned | 2024-04-04T02:58:47Z | |
dc.date.available | 2024-04-04T02:58:47Z | |
dc.date.created | 2020 | |
dc.date.issued | 2020 | |
dc.identifier.issn | 0377-2217 | |
dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/192686 | |
dc.description.abstractEn | In 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.iso | en | |
dc.publisher | Elsevier | |
dc.subject.en | Routing | |
dc.subject.en | Backhauls | |
dc.subject.en | Branch-cut-and-price | |
dc.subject.en | Integer programming | |
dc.title.en | On the exact solution of vehicle routing problems with backhauls | |
dc.type | Article de revue | |
dc.identifier.doi | 10.1016/j.ejor.2020.04.047 | |
dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
bordeaux.journal | European Journal of Operational Research | |
bordeaux.page | 76-89 | |
bordeaux.volume | 287 | |
bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
bordeaux.issue | 1 | |
bordeaux.institution | Université de Bordeaux | |
bordeaux.institution | Bordeaux INP | |
bordeaux.institution | CNRS | |
bordeaux.type.institution | Universidade Federal Fluminense | |
bordeaux.peerReviewed | oui | |
bordeaux.type.report | rr | |
hal.identifier | hal-02379008 | |
hal.version | 1 | |
hal.popular | non | |
hal.audience | Internationale | |
hal.origin.link | https://hal.archives-ouvertes.fr//hal-02379008v1 | |
bordeaux.COinS | ctx_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 |
Fichier(s) constituant ce document
Fichiers | Taille | Format | Vue |
---|---|---|---|
Il n'y a pas de fichiers associés à ce document. |