Subset-row inequalities and unreachability in path-based formulations for vehicle routing and scheduling problems

Abstract

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 SRIs 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 demonstrate 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 are minor.