An exact solution method for home health care scheduling with synchronized services

We study the home health care scheduling problem that considers the synchronized services of multiskilled caregivers necessitated by the simultaneous service requirements of patients. A characteristic feature of the problem is that there is a threshold on the maximum difference between the start times of the pairwise synchronized services at a patient, which enables flexible imposition of various synchronization constraints. We first derive some structural properties of the problem, based on which we provide a set-partitioning formulation of the problem and devise a branch-and-price-and-cut solution algorithm. We develop a column generation scheme to obtain lower bounds for the problem, in which we design a labeling algorithm together with some enhancement strategies to address the pricing subproblems, and use the 2-path inequalities and limited-node-memory subset row inequalities to strengthen the lower bounds. To test the algorithm, we apply it to solve the instances generated according to the well-known Solomon's benchmark data set and real-world instances. The results demonstrate that the algorithm can find the optimal solutions in most situations within reasonable computational times, confirming its efficacy. Finally, we perform sensitivity analysis of the optimal solution to some key model parameters and discuss the management implications of the results.