Optimizing resource allocation in home care services using MaxSAT

Abstract

In large urban areas, enhancing the personal care and quality of life for elderly individuals poses a critical societal challenge. As the population ages and the amount of people requiring assistance grows, so does the demand for home care services. This will inevitably put tremendous pressure on a system that has historically struggled to provide high-quality assistance with limited resources, all while managing urgent, unforeseen additional demands. This scenario can be framed as a resource allocation problem, wherein caregivers must be efficiently matched with services based on availability, qualifications, and schedules. Given its scale and complexity, traditional computational approaches have struggled to address this problem effectively, leaving it largely unresolved. Currently, many European cities emphasize geographical and emotional proximity, offering a model for home care services based on reduced social urban sectors. This new paradigm provides opportunities for tackling the resource allocation problem while promoting desirable pairings between caregivers and elderly people. This paper presents a MaxSAT-based solution in this context. Our approach efficiently allocates services across various configurations, maximizing caregiver-user pairings’ similarity and consistency while minimizing costs. Moreover, we show that our method solves the resource allocation problem in a reasonable amount of time. Consequently, we can either provide an optimal allocation or highlight the limits of the available resources relative to the service demand.