A model-based evolutionary algorithm for home health care scheduling

In this paper, for the first time a model-based evolutionary algorithm is presented for a real-life Home Health Care Routing and Scheduling Problem (HHCRSP). The algorithm generates routes consisting of care activities jointly with the underlying shift schedule, while taking into account the qualification levels. The performance is optimized in terms of travel time, time window waiting time and shift overtime. The algorithm is a novel extension of the permutation Gene-Pool Optimal Mixing Evolutionary Algorithm. Numerical experiments, using real-life data, show that the algorithm performs close to optimal for small instances, and outperforms schedules from a case study, leading to efficiency gains of 41%. Furthermore, it is shown that the model-based evolutionary algorithm performs better than a more traditional evolutionary algorithm, which demonstrates the importance of learning and exploiting a model to guide the optimization in HHCRSP.