Picture map of Europe with pins indicating European capital cities

Open Access research with a European policy impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by Strathclyde researchers, including by researchers from the European Policies Research Centre (EPRC).

EPRC is a leading institute in Europe for comparative research on public policy, with a particular focus on regional development policies. Spanning 30 European countries, EPRC research programmes have a strong emphasis on applied research and knowledge exchange, including the provision of policy advice to EU institutions and national and sub-national government authorities throughout Europe.

Explore research outputs by the European Policies Research Centre...

A hybrid integer programming and variable neighborhood search algorithm to solve Nurse Rostering Problems

Rahimian, Erfan and Akartunali, Kerem and Levine, John (2017) A hybrid integer programming and variable neighborhood search algorithm to solve Nurse Rostering Problems. European Journal of Operational Research, 258 (2). 411–423. ISSN 0377-2217

[img] Text (Rahimian-etal-EJOR-2016-Hybrid-integer-programming-and-variable-neighborhood-search-algorithm)
Rahimian_etal_EJOR_2016_Hybrid_integer_programming_and_variable_neighborhood_search_algorithm.pdf - Accepted Author Manuscript
Restricted to Repository staff only until 22 September 2018.
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (487kB) | Request a copy from the Strathclyde author


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 utilize 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.