Path Reduced Costs for Eliminating Arcs

, , et

référence BibTeX

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

Axe de recherche

Application de recherche


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