Enhanced Branch-Cut-and-Price Algorithm for Heterogeneous Fleet Vehicle Routing Problems
hal.structure.identifier | Universidade Federal Fluminense [Rio de Janeiro] [UFF] | |
dc.contributor.author | PESSOA, Artur Alves | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
dc.contributor.author | SADYKOV, Ruslan | |
hal.structure.identifier | Universidade Federal Fluminense [Rio de Janeiro] [UFF] | |
dc.contributor.author | UCHOA, Eduardo | |
dc.date.accessioned | 2024-04-04T03:07:31Z | |
dc.date.available | 2024-04-04T03:07:31Z | |
dc.date.issued | 2018-10 | |
dc.identifier.issn | 0377-2217 | |
dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193453 | |
dc.description.abstractEn | This paper considers a family of Vehicle Routing Problem (VRP) variants that generalize the classical Capacitated VRP by taking into account the possibility that vehicles di↵er by capacity, costs, depot allocation, or even by the subset of customers that they can visit. This work proposes a branch- cut-and-price algorithm that adapts advanced features found in the best performing exact algorithms for homogeneous fleet VRPs. The original con- tributions include: (i) the use of Extended Capacity Cuts, defined over a pseudo-polynomially large extended formulation, together with Rank-1 Cuts, defined over the Set Partitioning Formulation; (ii) the concept of vehicle-type dependent memory for Rank-1 Cuts; and (iii) a new family of lifted Extended Capacity Cuts that takes advantage of the vehicle-type dependent route enumeration. The algorithm was extensively tested in in- stances of the literature and was shown to be significantly better than pre- vious exact algorithms, finding optimal solutions for many instances with up to 200 customers and also for some larger instances. A new set of set of benchmark instances is also proposed. | |
dc.language.iso | en | |
dc.publisher | Elsevier | |
dc.subject.en | Cutting Planes | |
dc.subject.en | Column Generation | |
dc.subject.en | Routing | |
dc.title.en | Enhanced Branch-Cut-and-Price Algorithm for Heterogeneous Fleet Vehicle Routing Problems | |
dc.type | Article de revue | |
dc.identifier.doi | 10.1016/j.ejor.2018.04.009 | |
dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
bordeaux.journal | European Journal of Operational Research | |
bordeaux.page | 530-543 | |
bordeaux.volume | 270 | |
bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
bordeaux.issue | 2 | |
bordeaux.institution | Université de Bordeaux | |
bordeaux.institution | Bordeaux INP | |
bordeaux.institution | CNRS | |
bordeaux.peerReviewed | oui | |
hal.identifier | hal-01664844 | |
hal.version | 1 | |
hal.popular | non | |
hal.audience | Internationale | |
hal.origin.link | https://hal.archives-ouvertes.fr//hal-01664844v1 | |
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=2018-10&rft.volume=270&rft.issue=2&rft.spage=530-543&rft.epage=530-543&rft.eissn=0377-2217&rft.issn=0377-2217&rft.au=PESSOA,%20Artur%20Alves&SADYKOV,%20Ruslan&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. |