Solving staff rostering problems with column generation Dominance cost functions, aggregate branching, neighbourhood pricing and other matheuristic improvements

Abstract

This thesis presents a methodology for modelling and solving generic staff rostering problems using column generation. We solve two difficult problem sets using column generation and demonstrate some novel exact and heuristic improvements to standard column generation, which are needed to solve these problem sets. The first problem set we solved was from the International Nurse Rostering Competition (INRC). The INRC was held in 2010 to identify novel approaches to solve staff-rostering problems. Although many of the INRC problems were too tricky to solve to proven optimality, since the competition in 2010, multiple research groups have reported improved solutions to the problems compared to those proposed during the competition. However, up until this thesis, optimal solutions had not been found for 11 out of the 30 hardest INRC problem instances. In this thesis, we report how we obtained optimal solutions for the 30 hardest INRC problem instances within a 4-hour time window. Some of the identified solutions are of a higher quality than those obtained previously in the literature. We identified these solutions by implementing a series of improvements to Genie++, a nested column generation algorithm capable of solving staff-rostering problems. These improvements include a new dominance technique (dominance cost functions), new branching techniques, an objective function perturbation technique, and a shift aggregation relaxation. The second set of problems were to create rosters for wards serviced by the Waikato District Health Board (DHB). The exact techniques used to solve the INRC problems were ineffective at finding solutions to the large and complex Waikato DHB problems. Thus, we developed some column-generation-based matheuristics to build high-quality rosters. We compare a suite of novel column-generation-based local search matheuristics for improving an incumbent roster solution. Our novel implementations of “fixed days" local search and “maximum shift changes per employee" local search were particularly effective at quickly improving an incumbent roster solution’s quality. We also compare a suite of novel column-generation subproblem heuristics that we integrated into a branch and price dive to find high-quality roster solutions quickly. Our novel “LP neighbourhood pricing" methodology was especially effective at producing high-quality roster solutions quickly. Many of the techniques developed in this thesis can be applied to other column generation problems, especially those with column generation subproblems which involve solving complex shortest path problems with resource constraints.