An exact algorithm for the home health care routing and scheduling problem with variable departure times

The added value of digitization has been recognized to help address the challenge of limited medical resources with the growing demand for home healthcare. This paper focuses on the home healthcare routing and scheduling problem (HHCRSP), which entails optimizing the assignment of caregivers and designing efficient service plans at patients’ homes. Compared with the existing studies, the time at which each caregiver departs from the service center is part of the decision-making process rather than an input parameter. This innovation can tackle the issue of potential resource waste caused by the fixed departure time, thereby considerably complicating the problem. The developed model comprehensively incorporates multiple critical factors, including caregiver qualifications, patient preferences, flexible time windows, and work hour limitations. Additionally, it accounts for the total working durations of care workers, which encompass their daily service times, waiting times, and traveling times. To address the problem in large-scale instances, a column-and-cut generation scheme is developed to provide a tight lower bound, in which a novel bounded bidirectional labeling algorithm incorporated with some computational enhancements is designed for solving the challenging pricing subproblems. Building on this scheme, we develop a branch-price-and-cut algorithm to exactly solve the problem. It utilizes the limited-node-memory subset row inequalities to further tighten the lower bound and employs several enhancement strategies to accelerate convergence. Numerical experiments are conducted using instances derived from the well-known Solomon benchmark dataset and realistic instances from an Italian HHC organization. The results demonstrate the effectiveness of the proposed approach, with optimal solutions achieved within reasonable computational time in most cases. Additionally, the study yields valuable managerial insights for enhancing the resilience and efficiency of home healthcare operations.