Lookahead policy and genetic algorithm for solving nurse rostering problems

Peng, Shi; Dario, Landa-Silva

Abstract

Previous research has shown that value function approximation in dynamic programming does not perform too well when tackling difficult combinatorial optimisation problem such as multi-stage nurse rostering. This is because the large action space that need to be explored. This paper proposes to replace the value function approximation by a genetic algorithm in order to generate solutions to the stages before applying the lookahead policy to evaluate the future effect of decisions made in previous stages. Then, the paper proposes a hybrid approach that generates sets of weekly rosters through a genetic algorithm for consideration by the lookahead procedure that assembles a solution for the whole planning horizon of several weeks. Results indicate that this hybrid between an evolutionary algorithm and the lookahead policy mechanism from dynamic programming performs more competitive than the value function approximation dynamic programming investigated before. Results also show that the proposed algorithm is ranked well in respect of several other algorithms applied to the same set of problem instances. The intended contribution of this paper is towards a better understanding of how to successfully apply dynamic programming mechanisms to tackle difficult combinatorial optimisation problems.

Citation

Peng, S., & Dario, L. (2018). Lookahead policy and genetic algorithm for solving nurse rostering problems. In n/a

• Conference Name: 4th International Conference on Machine Learning, Optimization and Data Science (LOD 2018)
• Start Date: Sep 13, 2018
• End Date: Sep 16, 2018
• Acceptance Date: Jul 15, 2018
• Online Publication Date: Sep 16, 2018
• Publication Date: Sep 16, 2018
• Deposit Date: Oct 8, 2018
• Book Title: n/a
• Chapter Number: n/a
• ISBN: n/a
• Keywords: hybrid algorithm, genetic algorithm, lookahead policy evaluation, dynamic programming, nurse rostering problem
• Public URL: https://nottingham-repository.worktribe.com/output/1150326
• Related Public URLs: https://lod2018.icas.xyz/