Primal column generation framework for vehicle and crew scheduling problems

摘要

The primal adjacency-based algorithm and the multidirectional dynamic programming algorithm are two exact methods that have recently been developed to efficiently solve the shortest path problem with resource constraints (SPPRCs). 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 SPPRCs often appear as a subproblem (SP) in the solution of vehicle and crew scheduling problems (VCSP) using column generation (CG), we propose a new primal column generation framework that embeds these primal methods in a CG scheme. The primal column generation solves at each iteration a sequence of appropriate restricted SP and stops solving the SP when there is no need to continue. This approach introduces a large degree of flexibility, and allows performing good cost improvements in a very limited time. Computational experiments on VCSP instances show that the proposed approach is able to find optimal solutions while reducing the time spent solving the SP by factors of up to seven compared to the standard CG algorithm. This leads to significant improvements in the overall solution times, with an average reduction factor of 3.5.