A branch-and-price approach for the nurse rostering problem with multiple units

Abstract

In this paper, we study the nurse rostering problem that considers multiple units and many soft time-related constraints. An efficient branch and price solution approach that relies on a fast algorithm to solve the pricing subproblem of the column generation process is presented. For the nurse rostering problem, its pricing subproblem can be formulated as a shortest path problem with resource constraints, which has been the backbone of several solutions for several classical problems like vehicle routing problems. However, approaches that perform well on these problems cannot be used since most constraints in the nurse rostering problem are soft. Based on ideas borrowed from global constraints in constraint programming to model rostering problems, an efficient dynamic programming algorithm with novel label definitions and dominating rules specific to soft time-related constraints is proposed. In addition, several acceleration strategies are employed to improve the branch and price algorithm. Computational results on two sets of instances ranging from 2 to 4 units over a horizon of 2 or 4 weeks demonstrate the effectiveness of the proposed algorithms. The accelerated dynamic programming algorithm is able to solve pricing subproblems to optimality with the fewest extended labels. When contrasted with Cplex, the branch and price approach yields solutions that are either equivalent or superior across all instances.