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

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.