Daily scheduling of caregivers with stochastic times

This paper addresses a daily caregiver scheduling and routing problem arising in home health care or home care service providers. The problem is quite challenging due to its uncertainties in terms of travel and service times derived from changes in road traffic conditions and customer health status in practice. We first model the problem as a stochastic programme with recourse, where the recourse action is to skip customers without services if the caregiver arrives later than their latest starting service time (i.e. hard time window requirements). Then, we formulate the problem as a set partitioning model and solve it with a branch-and-price (B&P) algorithm. Specifically, we devise an effective discrete approximation method to calculate the arrival time distribution of caregivers, incorporate it into a problem-specific label algorithm, and use a removal-and-insertion-based heuristic and the decremental state-space relaxation technique to accelerate the pricing process. Finally, we conduct numerical experiments on randomly generated instances to validate the effectiveness of the discrete approximation method and the proposed B&P algorithm.