A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation

Publication year: 2012
Source: Computers & Operations Research, Volume 39, Issue 2, February 2012, Pages 164-178

Xiaoyan, Zhu , Wilbert E., Wilhelm

This paper focuses on the common scenario in which the resource-constrained shortest path problem (RCSP) on an acyclic graph is a sub-problem in the context of column generation. It proposes a pseudo-polynomial time, three-stage solution approach. Stages 1 (preprocessing) and 2 (setup) are implemented one time to transform RCSP into a shortest path problem, which is solved by stage 3 (iterative solution) at each column generation iteration, each time with different arc costs. This paper analyzes certain properties related to each stage as well as algorithm complexity. Computational tests compare the performances of this method, a state-of-the-art label-setting algorithm, and…