The primal adjacency-based algorithm and the multi-directional dynamic programming algorithm are two exact methods that have recently been developed to efficiently solve the shortest path problem with resource constraints. These methods are primal in the sense that they are able to produce sequences of feasible solutions using iterative exploration of the search space. Since the shortest path problem with resource constraints often appears as a subproblem in the solution of vehicle and crew scheduling problems using column generation, we propose a new Primal Column Generation framework that embeds these primal methods in a column generation scheme. The Primal Column Generation performs at each iteration a good cost improvement versus time by solving an appropriate restricted subproblem. The use of a primal approach introduces a self-acting ability and a large degree of flexibility. Computational experiments show that the proposed Primal Column Generation is able to find optimal solutions while reducing the time spent solving the subproblems by factors of up to 7 compared to the standard column generation algorithm. This leads to significant improvements in the overall solution times, with an average reduction factor of 3.5.
Published October 2018 , 21 pages