Large-Scale Home Care Crew Scheduling with a Parallel Evolutionary Algorithm

As the population ages, the demand for home health care services is increasing currently, and is expecting to keep growing in the future. To cope with this increasing demand, effective planning approaches for assigning caregivers to vistis at patients´ home are required. The aim of this paper is to address this planning problem with parallel a (1 + lambda) evolutionary algorithm. A master/worker parallel model has been used, but with enhanced mechanisms to enable the algorithm to efficiently involve a large number of workers in the computation. By using 4 different, large, real-world instances provided by a private company, different settings of lambda for an increasing number of workers have been evaluated. The baseline for the comparison is set by the solutions already implemented by the company. The results show, on the one hand, that the company´s solutions is clearly outperformed by our algorithmic proposal and, on the other hand, that the parallelization proposed allows the algorithm to properly address instances with more than 10000 services.