A set partitioning heuristic for the home health care routing and scheduling problem

The home health care routing and scheduling problem comprises the assignment and routing of a set of home care visits over the duration of a week. These services allow patients to remain in their own homes, thereby reducing governmental costs by decentralizing the care. In this work, we present a set partitioning heuristic which takes into account most of the industry's practical constraints. The developed method is based on a set partitioning formulation and a large neighborhood search (LNS) framework. The algorithm solves a linear relaxation of a set partitioning model using the columns generated by the large neighborhood search. A constructive heuristic is then called to build an integer solution. This project is joint work with Alayacare, a start-up sited in Montral (Canada) developing an operations management platform for home health care agencies. They provide their clients with a flexible optimization module that solves real-life instances in no more than 10 minutes. Based on their real instances, the proposed method is able to provide a reduction in travel time by 37% and an increase by more than 16% in continuity of care. We also provide a public benchmark for this problem. (C) 2018 Elsevier B.V. All rights reserved.