Path-Reduced Costs for Eliminating Arcs in Routing and Scheduling

In many branch-and-price algorithms, the column generation pricing problem consists of computing feasible paths in a network. In this paper, we show how, in this context, path-reduced costs can be used to remove some arcs from the underlying network without compromising optimality, and we introduce a bidirectional search technique to compute these reduced costs. This arc elimination method can lead to a substantial speedup of the pricing process and the overall branch-and-price algorithm. Special attention is given to variants of shortest-path problems with resource constraints. Computational results obtained for the vehicle routing problem with time windows show the efficiency of the proposed method.