Variable Fixing for Two-Arc Sequences in Branch-Price-and-Cut Algorithms on Path-Based Models

Guy Desaulniers (), Timo Gschwind () and Stefan Irnich ()
Additional contact information
Guy Desaulniers: GERAD and Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montréal H3T 1J4, Canada
Timo Gschwind: Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, 55128 Mainz, Germany
Stefan Irnich: Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, 55128 Mainz, Germany

Transportation Science, 2020, vol. 54, issue 5, 1526-5447

Abstract: 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.

Keywords: integer programming; branch price and cut; variable fixing; vehicle routing; labeling algorithm (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: Track citations by RSS feed

Downloads: (external link)
https://doi.org/10.1287/trsc.2020.0988 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:54:y:2020:i:5:p:1526-5447

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Matthew Walls ().