This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Irnich, S. Articles by Hadjar, A.

Path-Reduced Costs for Eliminating Arcs in Routing and Scheduling

Operations Research and Supply Chain Management, RWTH Aachen University, D-52056 Aachen, Germany
Ecole Polytechnique de Montréal and GERAD, Montréal, Québec H3C 3A7, Canada
HEC Montreal and GERAD, Montréal, Québec H3T 2A7, Canada
Kronos Canadian Systems Inc., Montréal, Québec H3V 1H8, Canada
sirnich{at}or.rwth-aachen.de
guy.desaulniers{at}gerad.ca
jacques.desrosiers{at}hec.ca
ahadjar{at}kronos.com

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.

Key words: integer programming; branch and bound; column generation and variable elimination; vehicle routing
History: received December 2007; revised January 2009; accepted April 2009.