Abstract
This paper proposes a local search method based on a large neighborhood to solve the static version of the problem defined for the Second International Nurse Rostering Competition (INRC-II). The search method, driven by a simulated annealing metaheuristic, uses a combination of neighborhoods that either change the assignments of a nurse or swap the assignments of two compatible nurses, for multiple consecutive days. Computational results on the set of competition instances show that our method has been able to improve on all previous approaches on some datasets, and to get close to the best ones in others. Best solutions, along with the datasets and the validation tool, are made available for future comparison.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahuja, R. K., Ergun, Ö., Orlin, J. B., & Punnen, A. P. (2002). A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics, 123(1), 75–102.
Arendt, J. (2010). Shift work: Co** with the biological clock. Occupational Medicine, 60(1), 10–20.
Birattari, M., Yuan, Z., Balaprakash, P., & Stützle, T. (2010). F-race and iterated F-race: An overview. In T. Bartz-Beielstein, M. Chiarandini, L. Paquete & M. Preuss (Eds.), Experimental methods for the analysis of optimization algorithms (pp. 311–336). Berlin: Springer.
Burke, E. K., De Causmaecker, P., Berghe, G. V., & Van Landeghem, H. (2004). The state of the art of nurse rostering. Journal of Scheduling, 7(6), 441–499.
Burke, E. K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., et al. (2013). Hyper-heuristics: A survey of the state of the art. Journal of the Operational Research Society, 64(12), 1695–1724.
Ceschia, S., Dang, N. T. T., De Causmaecker, P., Haspeslagh, S., & Schaerf, A. (2018). Second international nurse rostering competition: Mathematical model. Retrieved December 18, 2019, from http://mobiz.vives.be/inrc2/wp-content/uploads/2018/07/math_model-updated.pdf.
Ceschia, S., Dang, N. T. T., De Causmaecker, P., Haspeslagh, S., & Schaerf, A. (2019). The second international nurse rostering competition. Annals of Operations Research, 274(1–2), 171–186.
Dang, N. T. T., Ceschia, S., Schaerf, A., De Causmaecker, P., & Haspeslagh, S. (2016). Solving the multi-stage nurse rostering problem. In Proceedings of the 11th international conference on the practice and theory of automated timetabling (PATAT-2016) (pp. 473–475).
Della Croce, F., & Salassa, F. (2014). A variable neighborhood search based matheuristic for nurse rostering problems. Annals of Operations Research, 218(1), 185–199.
Franzin, A., & Stützle, T. (2019). Revisiting simulated annealing: A component-based analysis. Computers and Operations Research, 104, 191–206.
Glass, C. A., & Knight, R. A. (2010). The nurse rostering problem: A critical appraisal of the problem structure. European Journal of Operational Research, 202(2), 379–389.
Gomes, R., Toffolo, T., & Santos, H. G. (2017). Variable neighborhood search accelerated column generation for the nurse rostering problem. Electronic Notes in Discrete Mathematics, 58, 31–38.
Haspeslagh, S., De Causmaecker, P., Schaerf, A., & Stølevik, M. (2014). The first international nurse rostering competition 2010. Annals of Operations Research, 218, 221–236.
**, H., Post, G., & van der Veen, E. (2016). ORTECâ’s contribution to the second international nurse rostering competition. In Proceedings of the 11th international conference on the practice and theory of automated timetabling (PATAT-2016) (pp. 599–501).
Kheiri, A., Özcan, E., Lewis, R., & Thompson, J. (2016). A sequence-based selection hyper-heuristic: Case study in multi-stage nurse rostering problem. In Proceedings of the 11th international conference on the practice and theory of automated timetabling (PATAT-2016) (pp. 503–505).
Kirkpatrick, S., Gelatt, D., & Vecchi, M. (1983). Optimization by simulated annealing. Science, 220, 671–680.
Legrain, A., Omer, J., & Rosat, S. (2017). A rotation-based branch-and-price approach for the nurse scheduling problem. Working paper. Retrieved December 18, 2019, from https://hal.archives-ouvertes.fr/hal-01545421.
Legrain, A., Omer, J., & Rosat, S. (2018). An online stochastic algorithm for a dynamic nurse scheduling problem. European Journal of Operational Research, 2018. https://hal.archives-ouvertes.fr/hal-01763422/document.
Lü, Z., & Hao, J.-K. (2012). Adaptive neighborhood search for nurse rostering. European Journal of Operational Research, 218(3), 865–876.
Mischek, F., & Musliu, N. (2019). Integer programming model extensions for a multi-stage nurse rostering problem. Annals of Operations Research, 275(1), 123–143.
Rahimian, E., Akartunali, K., & Levine, J. (2017). A hybrid integer programming and variable neighbourhood search algorithm to solve nurse rostering problems. European Journal of Operational Research, 258(2), 411–423.
Römer, M., & Mellouli, T. (2016a). A direct MILP approach based on state-expanded network flows and anticipation for multi-stage nurse rostering under uncertainty. In Proceedings of the 11th international conference on the practice and theory of automated timetabling (PATAT-2016) (pp. 549–551).
Römer, M., & Mellouli, T. (2016b). Future demand uncertainty in personnel scheduling: Investigating deterministic lookahead policies using optimization and simulation. In Proceedings of the 30th European conference on modelling and simulation (ECMS 2016) (pp. 502–507).
Santos, H. G., Toffolo, T. A. M., Ribas, S., & Gomes, R. A. M. (2016). Integer programming techniques for the nurse rostering problem. Annals of Operations Research, 239(1), 225–251.
Smet, P., Salassa, F., & Berghe, G. V. (2017). Local and global constraint consistency in personnel rostering. International Transactions in Operational Research, 24(5), 1099–1117.
Tassopoulos, I. X., Solos, I. P., & Beligiannis, G. N. (2015). A two-phase adaptive variable neighborhood approach for nurse rostering. Computers & Operations Research, 60, 150–169.
Van den Bergh, J., Beliën, J., De Bruecker, P., Demeulemeester, E., & De Boeck, L. (2013). Personnel scheduling: A literature review. European Journal of Operational Research, 226(3), 367–385.
Wickert, T., Sartori, C., & Buriol, L. (2016). A fix-and-optimize VNS algorithm applied to the nurse rostering problem. In Proceedings of matheuristics.
Wickert, T. I., Smet, P., & Vanden Berghe, G. (2019). The nurse rerostering problem: Strategies for reconstructing disrupted schedules. Computers & Operations Research, 104, 319–337.
Acknowledgements
We would like to thank Nguyen Thi Thanh Dang, Patrick De Causmaecker, and Stefaan Haspeslagh, for their contribution to the organisation of INRC-II and for their collaboration with us on this subject. We also thank Antoine Legrain, Jérémy Omer, and Samuel Rosat for fruitful discussions and for their support in installing and configuring their code.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Ceschia, S., Guido, R. & Schaerf, A. Solving the static INRC-II nurse rostering problem by simulated annealing based on large neighborhoods. Ann Oper Res 288, 95–113 (2020). https://doi.org/10.1007/s10479-020-03527-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-020-03527-6