An Adaptive Large Neighbourhood Search algorithm for a real-world Home Care Scheduling Problem with time windows and dynamic breaks

Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG[Abstract]: This paper presents a Home Care Scheduling Problem (from now on HCSP) based on a real case of a care company for elderly and dependent people located in the North of Spain. The problem incorporates many of the common features addressed in the HCSP literature, such as soft and hard time windows for the services, available working time of the caregivers or affinity levels between users and caregivers. However, it also includes other novel characteristics that increase the difficulty of the problem significantly, since the breaks between services will play a key role in the quality of the solutions. To evaluate the solutions, the users welfare will be prioritized over the cost associated with the schedule. The problem has been formulated as a Mixed Integer Linear Programming (MILP) one but, due to the complexity of the model, it is not possible to solve it for real size instances. Therefore, we have designed a method that combines the Adaptive Large Neighbourhood Search (ALNS) methodology with a heuristic approach necessary to evaluate the objective functions. To analyse the behaviour of the algorithm, a set of computational experiments are carried out under different configurations. First, the MILP formulation and the algorithm have been compared over some standard instances from the literature. Finally, the performance of the algorithm is evaluated over a real case study based on the timetables of the company during some weeks from 2016 to 2017.This research was funded by MICINN/AEI/10.13039/501100011033/ and ERDF/EU through R+D+I project grants MTM2017-87197-C3-1-P and PID2021-124030NB-C31 and by Consellería de Cultura, Educación e Universidades, Xunta de Galicia (Grupos de Referencia Competitiva ED431C-2020/14 and Centro de Investigación del Sistema universitario de Galicia ED431G-2019/01). Funding for open access charge: Universidade da Coruña/CISUG. Constructive comments from several referees and the editor are also gratefully acknowledged.Xunta de Galicia; ED431C-2020/14Xunta de Galicia; ED431G-2019/0