An integer programming based ant colony optimisation method for nurse rostering

Joe D. Bunton, Andreas T. Ernst, Mohan Krishnamoorthy

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

6 Citations (Scopus)

Abstract

Nurse rostering problems are typically too large and hard to be solved exactly. In order to achieve quality solutions to these difficult problems, meta-heuristics are often employed. One such meta-heuristic is Ant Colony Optimisation (ACO), inspired by the pheromone trails left by ants. ACO works by guiding a heuristic solution construction by using these pheromones to direct weighted random choices. When the problem to be solved is highly constrained, finding feasible solutions is difficult, which can result in poor performance for ACO. To address this, we propose an ACO algorithm using an integer programming based solution construction method to ensure feasibility and select from a collection of schedules. The approach also uses a novel solution merging step that combines the information from multiple ants to generate a better final roster. We discuss several challenges inherent in this approach, and how they may be overcome. Computational results on highly constrained nurse rostering problem instances from the literature demonstrate the effectiveness of our proposed new hybrid metaheuristic.

Original languageEnglish
Title of host publicationProceedings of the 2017 Federated Conference on Computer Science and Information Systems, FedCSIS 2017
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages407-414
Number of pages8
Volume11
ISBN (Electronic)9788394625375, 9788394625382, 9788394625399
DOIs
Publication statusPublished - 10 Nov 2017
EventInternational Workshop on Computational Optimization, 2017 - Prague, Czech Republic
Duration: 3 Sep 20176 Sep 2017
Conference number: 10th
https://fedcsis.org/2017/wco

Workshop

WorkshopInternational Workshop on Computational Optimization, 2017
Abbreviated titleWCO 2017
CountryCzech Republic
CityPrague
Period3/09/176/09/17
Internet address

Cite this