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.

Automated summary

This paper presents a model-based evolutionary algorithm for the Home Health Care Routing and Scheduling Problem (HHCRSP). The algorithm generates routes with care activities and shift schedules, considering qualification levels. Performance is optimized in terms of travel time, time window waiting time, and shift overtime. Numerical experiments using real-life data show close-to-optimal performance for small instances and a 41% efficiency gain compared to a case study. Furthermore, the model-based evolutionary algorithm outperforms a traditional evolutionary algorithm, emphasizing the importance of learning and exploiting a model in HHCRSP optimization.