Comparing the performance of state-of-the-art algorithms for the nurse rostering problem

The future prospect of healthcare workers in the Netherlands is worrisome, due to stressful working conditions and large expected personnel shortages. High quality personnel rosters have been shown to be able to alleviate this problem. The problem of creating personnel rosters that are of high quality in terms of how much they satisfy constraints regarding labor rules, work demand and personnel preferences, is denoted by the nurse rostering problem (NRP). This study aims to find an algorithm to solve the NRP that is suitable for implementation in a general automatic shift scheduler. 

Firstly, literature on the NRP is reviewed, from which we conclude that single-solution based meta-heuristics are most suitable for this purpose. A categorization is made of different algorithm components, that are varied among different methods, namely construction methods, neighborhood structures, overall frameworks and perturbation methods. Secondly, based on the conclusions from the literature review, two construction methods, i.e. Construction-per-shift and Construction-per-employee, and two overall frameworks, i.e. Simulated Annealing and Variable Neighborhood Search, are implemented. Experiments are performed on nine data instances from a Dutch hospital, for which the problem description, in terms of hard and soft constraints, is drawn up to reflect real-world target cases. Different variations within the implemented methods are tested, from which general conclusions are drawn, mostly on the use of neighborhood structures within the overall frameworks. 

Overall, Construction-per-shift greatly outperforms Construction-per-employee, Simulated Annealing slightly outperforms Variable Neighborhood Search, and the performance of the overall frameworks is largely independent of the preceding construction method. Based on the results, we conclude that both Simulated Annealing and Variable Neighborhood Search are stable and general methods, that can produce high quality rosters within a short time, making them suitable for implementation in a general automatic shift scheduler. 

Potential future improvements could be found in additional algorithm adjustments, such as adaptive neighborhood probabilities for Simulated Annealing, targeted perturbation for Variable Neighborhood Search, or hard constraint relaxations.