A branch-cut-and-price algorithm for the distance constrained multi-depot vehicle routing problem
| 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 | PESSOA, Artur Alves | |
| hal.structure.identifier | Universidade Federal Fluminense [Rio de Janeiro] [UFF] | |
| dc.contributor.author | UCHOA, Eduardo | |
| dc.date.accessioned | 2024-04-04T03:06:59Z | |
| dc.date.available | 2024-04-04T03:06:59Z | |
| dc.date.conference | 2017-07-17 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193391 | |
| dc.description.abstractEn | In this work we propose a new Branch-Cut-and-Price algorithm for the distance constrained multi-depot vehicle routing problem. The algorithm combines many state-of-the-art techniques known to be efficient for routing problems : bi-directional ng-path based labelling algorithm to solve the pricing problem, generation of limited memory rank-1 cuts with up to 5 rows, reduced cost fixing of arcs, enumeration of elementary routes, and multi-phase strong branching with pseudo-costs. The main contribution of this work is an improvement of the labelling algorithm for the resource constrained shortest path problem with two resources. The labels with similar resource consumption are stored in buckets which are organised in so-called bucket graph. This organisation allows one to significantly reduce the number of dominance checks, exploit route symmetry, and perform reduced cost fixing of bucket arcs. Experiments showed that our algorithm is able to solve to optimality several open instances of the problem with up to 216 customers within the 2 hours time limit. The improvement of the solution time over the recent state-of-the-art algorithm by Contardo and Martinelli (2014) is up to two-three orders of magnitude. | |
| dc.language.iso | en | |
| dc.title.en | A branch-cut-and-price algorithm for the distance constrained multi-depot vehicle routing problem | |
| dc.type | Communication dans un congrès | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | IFORS 2017 - 21st Conference of the International Federation of Operational Research Societies | |
| bordeaux.country | CA | |
| bordeaux.conference.city | Quebec City | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01676023 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | non | |
| hal.conference.end | 2017-07-21 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01676023v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=SADYKOV,%20Ruslan&PESSOA,%20Artur%20Alves&UCHOA,%20Eduardo&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||