A Generic Exact Solver for Vehicle Routing and Related Problems
| hal.structure.identifier | Universidade Federal Fluminense [Rio de Janeiro] [UFF] | |
| dc.contributor.author | PESSOA, Artur | |
| 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 | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Atoptima | |
| dc.contributor.author | VANDERBECK, François | |
| dc.date.accessioned | 2024-04-04T02:49:00Z | |
| dc.date.available | 2024-04-04T02:49:00Z | |
| dc.date.issued | 2020 | |
| dc.identifier.issn | 0025-5610 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/191786 | |
| dc.description.abstractEn | Major advances were recently obtained in the exact solution of Vehicle Routing Problems (VRPs). Sophisticated Branch-Cut-and-Price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However , adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This work proposes a BCP solver for a generic model that encompasses a wide class of VRPs. It incorporates the key elements found in the best recent VRP algorithms: ng-path relaxation, rank-1 cuts with limited memory, and route enumeration; all generalized through the new concept of "packing set". This concept is also used to derive a new branch rule based on accumulated resource consumption and to generalize the Ryan and Foster branch rule. Extensive experiments on several variants show that the generic solver has an excellent overall performance, in many problems being better than the best existing specific algorithms. Even some non-VRPs, like bin packing, vector packing and generalized assignment, can be modeled and effectively solved. | |
| dc.language.iso | en | |
| dc.publisher | Springer Verlag | |
| dc.subject.en | Routing | |
| dc.subject.en | Column generation | |
| dc.subject.en | Integer programming | |
| dc.title.en | A Generic Exact Solver for Vehicle Routing and Related Problems | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1007/s10107-020-01523-z | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.journal | Mathematical Programming | |
| bordeaux.page | 483-523 | |
| bordeaux.volume | 183 | |
| 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.peerReviewed | oui | |
| hal.identifier | hal-02178171 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-02178171v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Mathematical%20Programming&rft.date=2020&rft.volume=183&rft.spage=483-523&rft.epage=483-523&rft.eissn=0025-5610&rft.issn=0025-5610&rft.au=PESSOA,%20Artur&SADYKOV,%20Ruslan&UCHOA,%20Eduardo&VANDERBECK,%20Fran%C3%A7ois&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||