Path Reduced Costs for Eliminating Arcs

, , , and

BibTeX reference

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.

, 36 pages

Research Axis

Research application


Path reduced costs for eliminating arcs in routing and scheduling
, , , and
INFORMS Journal on Computing, 22(2), 297–313, 2010 BibTeX reference