Hybridizing Subgradient Optimization and Very Large Scale Neighborhood Search for Nurse Rostering

摘要

The nurse rostering problem (NRP) requires the production of a roster for a set of nurses subjected to a predefined set of requirements. NRP is computationally intractable for general instances. This article presents a hybrid algorithm that integrates a very large scale neighborhood (VLSN) search metaheuristic within a subgradient optimization framework. The use of a subgradient optimization technique enables better navigation during the local search process. Searching the exponential size neighborhood amounts to solve a very small binary program (BP). The solution method is tested on benchmark instances from NSPLib. Its effectiveness and competitiveness with three recent methods are shown.