Variable Fixing for Two-Arc Sequences in Branch-Price-and-Cut Algorithms on Path-Based Models
- Publikationstyp:
- Zeitschriftenaufsatz
- Metadaten:
-
- Autoren
- Guy Desaulniers
- Timo Gschwind
- Stefan Irnich
- Autoren-URL
- https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=fis-test-1&SrcAuth=WosAPI&KeyUT=WOS:000567549700002&DestLinkType=FullRecord&DestApp=WOS_CPL
- DOI
- 10.1287/trsc.2020.0988
- Externe Identifier
- Clarivate Analytics Document Solution ID: NL6VC
- ISSN
- 0041-1655
- Ausgabe der Veröffentlichung
- 5
- Zeitschrift
- TRANSPORTATION SCIENCE
- Schlüsselwörter
- integer programming
- branch price and cut
- variable fixing
- vehicle routing
- labeling algorithm
- Paginierung
- 1170 - 1188
- Datum der Veröffentlichung
- 2020
- Status
- Published
- Titel
- Variable Fixing for Two-Arc Sequences in Branch-Price-and-Cut Algorithms on Path-Based Models
- Sub types
- Article
- Ausgabe der Zeitschrift
- 54
Datenquelle: Web of Science (Lite)
- Andere Metadatenquellen:
-
- Abstract
- <jats:p> Variable fixing by reduced costs is a popular technique for accelerating the solution process of mixed-integer linear programs. For vehicle-routing problems solved by branch-price-and-cut algorithms, it is possible to fix to zero the variables associated with all routes containing at least one arc from a subset of arcs determined according to the dual solution of a linear relaxation. This is equivalent to removing these arcs from the network used to generate the routes. In this paper, we extend this technique to routes containing sequences of two arcs. Such sequences or their arcs cannot be removed directly from the network because routes traversing only one arc of a sequence might still be allowed. For some of the most common vehicle-routing problems, we show how this issue can be overcome by modifying the route-generation labeling algorithm in order to remove indirectly these sequences from the network. The proposed acceleration strategy is tested on benchmark instances of the vehicle-routing problem with time windows (VRPTW) and four variants of the electric VRPTW. The computational results show that it yields a significant speedup, especially for the most difficult instances. </jats:p>
- Autoren
- Guy Desaulniers
- Timo Gschwind
- Stefan Irnich
- DOI
- 10.1287/trsc.2020.0988
- eISSN
- 1526-5447
- ISSN
- 0041-1655
- Ausgabe der Veröffentlichung
- 5
- Zeitschrift
- Transportation Science
- Sprache
- en
- Paginierung
- 1170 - 1188
- Datum der Veröffentlichung
- 2020
- Status
- Published
- Herausgeber
- Institute for Operations Research and the Management Sciences (INFORMS)
- Herausgeber URL
- http://dx.doi.org/10.1287/trsc.2020.0988
- Datum der Datenerfassung
- 2023
- Titel
- Variable Fixing for Two-Arc Sequences in Branch-Price-and-Cut Algorithms on Path-Based Models
- Ausgabe der Zeitschrift
- 54
Datenquelle: Crossref
- Autoren
- Guy Desaulniers
- Timo Gschwind
- Stefan Irnich
- DOI
- 10.1287/trsc.2020.0988
- Zeitschrift
- Transp. Sci.
- Artikelnummer
- 5
- Paginierung
- 1170 - 1188
- Datum der Veröffentlichung
- 2020
- Titel
- Variable Fixing for Two-Arc Sequences in Branch-Price-and-Cut Algorithms on Path-Based Models.
- Ausgabe der Zeitschrift
- 54
Datenquelle: DBLP
- Beziehungen:
- Eigentum von