The Prominence of Stabilization Techniques in Column Generation: the case of Freight Transportation
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | SADYKOV, Ruslan | |
| hal.structure.identifier | Trapeznikov Institute of Control Sciences [ICS RAS] | |
| dc.contributor.author | LAZAREV, Alexander A. | |
| hal.structure.identifier | Universidade Federal Fluminense [Rio de Janeiro] [UFF] | |
| dc.contributor.author | PESSOA, A | |
| hal.structure.identifier | Universidade Federal Fluminense [Rio de Janeiro] [UFF] | |
| dc.contributor.author | UCHOA, E | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | VANDERBECK, François | |
| dc.date.accessioned | 2024-04-04T03:16:35Z | |
| dc.date.available | 2024-04-04T03:16:35Z | |
| dc.date.issued | 2015-06 | |
| dc.date.conference | 2015-06 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/194226 | |
| dc.description.abstractEn | Routing and logistics applications are often viewed as intractable for exact optimization tools. Al- though such problems are naturally suited for a decomposition approach, branch-and-price-and-cut algorithms of the literature typically do not scale to the size of real-life instances. Some recent progress in stabilization techniques amongst other advances (such as diving heuristics, strong branching, and the combination with cutting plane approaches) generate new ambitions for column generation ap- proach in solving approximately very large scale instances. Let us for instance point to the new benchmarks for the Capacitated Vehicle Routing Problem (CVRP) in [2]. This paper illustrates this trend, showing exact results for freight transportation instances of a scale never considered before. Our column generation algorithm yields dual bounds and serves as the core procedure for a primal heuristic. The overal procedure is quite competitive in great part due to the convergence speed-ups resulting from efficient stabilization schemes. It typically provides optimal solutions as primal and dual bounds tend to be equal. The very large scale freight transportation instances (with up to 1,025 stations, 5,300 demands, and 12,651 rail cars) were submitted to us by our Russian partner Freight-One. | |
| dc.language.iso | en | |
| dc.subject.en | Column Generation | |
| dc.subject.en | Stabilization | |
| dc.subject.en | Freight Transportation | |
| dc.title.en | The Prominence of Stabilization Techniques in Column Generation: the case of Freight Transportation | |
| 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 | 6th International Workshop on Freight Transportation and Logistics Odysseus'2015 | |
| bordeaux.country | FR | |
| bordeaux.conference.city | Ajaccio | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01248323 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01248323v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2015-06&rft.au=SADYKOV,%20Ruslan&LAZAREV,%20Alexander%20A.&PESSOA,%20A&UCHOA,%20E&VANDERBECK,%20Fran%C3%A7ois&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||