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. Note to Practitioners-This article provides a decision support tool to HC managers, which appropriately assigns caregivers to clients and makes routing decisions over a long horizon. Chargeable overtimes and preference matching enclosed in this tool are rarely considered in the literature, despite matching is relevant in HC caregiver-to-client assignments and chargeable overtime has potential in tailoring the service level based on the specific client. We formulate the scheduling problem as a mathematical model. Then, we propose a matheuristic algorithm to efficiently solve the problem in real-size instances. The results show the applicability and efficiency of our method. Thus, HC managers can exploit it to efficiently make assignment and routing decisions and to analyze the impact on other operating costs when adjusting any of them.