Journal
TRANSPORTATION SCIENCE
Volume 54, Issue 5, Pages 1170-1188Publisher
INFORMS
DOI: 10.1287/trsc.2020.0988
Keywords
integer programming; branch price and cut; variable fixing; vehicle routing; labeling algorithm
Categories
Funding
- Deutsche Forschungsgemeinschaft [IR 122/10-1]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available