Subset-Row Inequalities and Unreachability in Path-based Formulations for Routing and Scheduling Problems

This work considers branch-price-and-cut algorithms for variants of the vehicle-routing problem in which subset-row inequalities (SRIs) are used to strengthen the linear relaxation. SRIs often help to substantially reduce the size of the branch-and-bound search tree. However, their use is computationally costly because they modify the structure of the respective column-generation subproblem which is a shortest-path problem with resource constraints (SPPRC). Each active SRI requires the addition of a resource to the labeling algorithm that is invoked for solving the SPPRC in every iteration. In the context of time-window constraints, the concept of unreachable customers has been used for preprocessing (time-window reduction, arc elimination, precedence identification) as well as for improving the dominance between labels in the elementary SPPRC and its relaxations. We show that the identification of unreachable customers can also help to improve the dominance due to a modified comparison of SRI-related resources. Computational experiments with a fully-fledged branch-price-and-cut algorithm for the (standard and electric) vehicle routing problem with time windows demonstrates the effectiveness of the approach: Overall computation times decrease, for some difficult instances they may even be cut in half, while the required modifications of a computer implementation for combining SRIs with unreachable customers is minor.