Lookahead policy and genetic algorithm for solving nurse rostering problems
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 repla...
| Main Authors: | , |
|---|---|
| Format: | Conference or Workshop Item |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/53343/ |
| _version_ | 1848798924417007616 |
|---|---|
| author | Shi, Peng Landa-Silva, Dario |
| author_facet | Shi, Peng Landa-Silva, Dario |
| author_sort | Shi, Peng |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T20:27:30Z |
| format | Conference or Workshop Item |
| id | nottingham-53343 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T20:27:30Z |
| publishDate | 2018 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-533432018-10-08T10:10:26Z https://eprints.nottingham.ac.uk/53343/ Lookahead policy and genetic algorithm for solving nurse rostering problems Shi, Peng Landa-Silva, Dario 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. 2018-09-16 Conference or Workshop Item PeerReviewed application/pdf en https://eprints.nottingham.ac.uk/53343/1/dls_lod2018.pdf Shi, Peng and Landa-Silva, Dario (2018) Lookahead policy and genetic algorithm for solving nurse rostering problems. In: 4th International Conference on Machine Learning, Optimization and Data Science (LOD 2018), 13-16 September, 2018, Volterra, Italy. hybrid algorithm genetic algorithm lookahead policy eval- uation dynamic programming nurse rostering problem |
| spellingShingle | hybrid algorithm genetic algorithm lookahead policy eval- uation dynamic programming nurse rostering problem Shi, Peng Landa-Silva, Dario Lookahead policy and genetic algorithm for solving nurse rostering problems |
| title | Lookahead policy and genetic algorithm for solving nurse rostering problems |
| title_full | Lookahead policy and genetic algorithm for solving nurse rostering problems |
| title_fullStr | Lookahead policy and genetic algorithm for solving nurse rostering problems |
| title_full_unstemmed | Lookahead policy and genetic algorithm for solving nurse rostering problems |
| title_short | Lookahead policy and genetic algorithm for solving nurse rostering problems |
| title_sort | lookahead policy and genetic algorithm for solving nurse rostering problems |
| topic | hybrid algorithm genetic algorithm lookahead policy eval- uation dynamic programming nurse rostering problem |
| url | https://eprints.nottingham.ac.uk/53343/ |