A Matheuristic Approach for the Home Care Scheduling Problem With Chargeable Overtime and Preference Matching

Home care (HC) services represent an effective solution to face the health issues related to population aging. However, several scheduling problems arise in HC, and the providers must make several scheduling and routing decisions, e.g., the assignment of caregivers to clients, in order to balance operating costs and client satisfaction. Starting from the analysis of a real HC provider operating in New York City, NY, USA, this article addresses a scheduling problem with chargeable overtime and preference matching and formulates it as an integer programming model. The objective is to minimize a cost function that includes traveling costs, the overtime cost paid by the provider, the preference mismatch, and a penalty related to the continuity of care violation. To solve this problem, we design a matheuristic algorithm that integrates a specific variable neighborhood search with a set covering model. The results demonstrate the applicability and efficiency of our approach to solving real-size instances. Sensitivity analyses are also performed to discuss practical insights.