Large Neighborhood Search for the Nurse Rostering Problem

Abstract

Generating rosters for nurses in a hospital involves the assignment of nurses to shifts, taking into account their skills, preferences and contract types. This task is typically a very complex problem, not least because of the many restrictions that need to be taken into account. These constraints generally include hard constraints, such as forbidden shift successions and providing a minimum number of nurses for each shift. In addition, several soft constraints, representing a well-balanced schedule, should also be satisfied as far as possible. The actual real-world problem might deviate from hospital to hospital. However, the international nurse rostering competitions in 2010 and 2015 generated a common basis for research. They enhanced academic interchange by stating problem formulations and benchmark instances, that have been widely accepted and used by the research community since then. While for the first international nurse rostering competition, a formulation with many constraints was proposed, the second competition used a smaller number of constraints but extended the problem to a sequence of periods for which a roster has to be created successively. The first contribution of this thesis refers to the development of a mixed integer programming model for the problem formulation of the second competition. Due to the inherent complexity of the problem, heuristic approaches appear to be appropriate, if the problem has to be solved in reasonable time. Hence, I propose a metaheuristic based on large neighborhood search for the nurse rostering problem in this thesis. The algorithm repetitively destroys and re-builds relatively large parts of the incumbent solution by making use of several destroy and repair operators. Well-performing selection rates are precomputed by applying a modified version of the algorithm, in which selection probabilities are adjusted dynamically depending on the performance of the operators. These selection rates are then passed to the original algorithm. Within the proposed approach, a simulated annealing acceptance scheme is employed for deciding whether a generated solution is accepted as new incumbent. The algorithm is applied to the benchmark instances of the second international nurse rostering competition. The generated results are then compared with those of the finalists of the competition.