Continuity of care in home services: a client-centered heuristic for the home health care routing and scheduling problem

The home health care routing and scheduling problem (HHCRSP) consists in assigning and routing care-workers to provide cares or services at clients' homes. It is often treated as a variant of the vehicle routing problem (VRP) with time windows, multiple depots and specific constraints. To solve this problem, we propose a heuristic combining a Mixed Integer Linear Programming (MILP) formulation and a greedy algorithm. Our main objective is to ensure the continuity of care while taking into account practical constraints that are hardly studied together in the literature. We are able to propose a good feasible solution in a few minutes for instances up to 35 care-workers, 200 clients and 742 services over a week.