A tabu search approach with embedded nurse preferences for solving nurse rostering problem

Abstract

This paper presents an intelligent tabu search (TS) approach for solving a complex real-world nurse rostering problem (NRP). Previous study has suggested that improvement on neighborhoods and smart intensification of a TS could produce faster and fitted solution. In order to enhance the TS, this paper introduces an improvement to the neighborhoods and explores on the neighborhoods exploitations of TS to solve the NRP. The methodology consists of two phases: initialization and neighborhood. The semi-random initialization is employed for finding a good initial solution during the initialization phase which avoids the violation of hard constraints, while the neighborhood phase is established for further improving the solution quality with a special representation and innovative neighborhood generations within TS algorithm. The aim is to move sample points towards a high-quality solution while avoiding local optima by utilising a calculated force value. It is observed that the enhancement strategy could improve the solution quality of the constructed roster. It is concluded that the TS with enhancements approach is able to assign effective and efficient shift duties for the NRP especially when related with real-world working regulations and nurses preferences.

Keywords

• nurse rostering problem
• heuristics
• nurse preference
• tabu search
• initial solution
• neighborhood generation