An efficient two-phase heuristic for the home care routing and scheduling problem

This paper focuses on modeling and solving the home health care routing and scheduling problem (HHCRSP) with the consideration of skill requirements, multiple time windows, multiple services and caregivers’ duty length. A new mixed integer linear programming (MILP) model is proposed to build a daily schedule in order to minimize caregivers’ waiting times and to balance their workloads. The complexity of this problem, which is an extended version of the NP-hard VRPTW problem, emerges during the numerical resolution of random instances. To overcome these difficulties, we proposed a two-phase approach to solve the problem under study in a reasonable amount of computational time. The first phase consists of applying a simulated annealing (SA) based heuristic to generate caregivers’ routes and their assignment while the second one aims to select, for each patient, a time window, ensure the synchronization of simultaneous services and define the timetable of visits. Computational results show that the proposed two-phase approach is very efficient, fast and outperforms state-of-art heuristics and exacts methods in terms of CPU running time and solution quality.