An Adaptive Large Neighbourhood Search algorithm for a real-world Home Care Scheduling Problem with time windows and dynamic breaks
Use this link to cite
http://hdl.handle.net/2183/34267
Except where otherwise noted, this item's license is described as Atribución 4.0 Internacional (CC BY 4.0)
Collections
- GI-MODES - Artigos [137]
Metadata
Show full item recordTitle
An Adaptive Large Neighbourhood Search algorithm for a real-world Home Care Scheduling Problem with time windows and dynamic breaksDate
2023-11Citation
I. Méndez-Fernández, S. Lorenzo-Freire, and Á.M. González-Rueda, "An Adaptive Large Neighbourhood Search algorithm for a real-world Home Care Scheduling Problem with time windows and dynamic breaks", Computers and Operations Research, Vol. 159, November 2023, article 106351, doi: 10.1016/j.cor.2023.106351
Abstract
[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.
Keywords
Adaptive large neighbourhood search
Home care
Mixed integer linear programming
Scheduling
Home care
Mixed integer linear programming
Scheduling
Description
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG
Editor version
Rights
Atribución 4.0 Internacional (CC BY 4.0)