A hybrid Integer Programming and Variable Neighbourhood Search algorithm to solve Nurse Rostering Problems
Erfan Rahimian,
Kerem Akartunalı and
John Levine
European Journal of Operational Research, 2017, vol. 258, issue 2, 411-423
Abstract:
The Nurse Rostering Problem (NRP) is defined as assigning a number of nurses to different shifts during a specified planning period, considering some regulations and preferences. This is often very difficult to solve in practice particularly by applying a sole approach. In this paper, we propose a novel hybrid algorithm combining the strengths of Integer Programming (IP) and Variable Neighbourhood Search (VNS) algorithms to design a hybrid method for solving the NRP. After generating the initial solution using a greedy heuristic, the solution is further improved by employing a Variable Neighbourhood Descent algorithm. Then IP, deeply embedded in the VNS algorithm, is employed within a ruin-and-recreate framework to assist the search process. Finally, IP is called again to further refine the solution during the remaining time. We utilise the strength of IP not only to diversify the search process, but also to intensify the search efforts. To identify the quality of the current solution, we use a new generic scoring scheme to mark the low-penalty parts of the solution. Based on the computational tests with 24 instances recently introduced in the literature, we obtain better results with our proposed algorithm, where the hybrid algorithm outperforms two state-of-the-art algorithms and Gurobi in most of the instances. Furthermore, we introduce 11 randomly generated instances to further evaluate the efficiency of the hybrid algorithm, and we make these computationally challenging instances publicly available to other researchers for benchmarking purposes.
Keywords: Timetabling; Nurse Rostering; Hybrid algorithm; Integer Programming; Variable Neighbourhood Search (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)
Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716307822
Full text for ScienceDirect subscribers only
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:258:y:2017:i:2:p:411-423
DOI: 10.1016/j.ejor.2016.09.030
Access Statistics for this article
European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati
More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().