a branch-and-price algorithm for the home-caregiver scheduling and routing problem with stochastic travel and service times

This paper addresses the solution methods for the stochastic home-caregiver scheduling and routing problem which arises in many service industries such as home care and home health care. in the problem, the caregiver’s travel times and service times for customers are stochastic. a chance constraint is introduced to ensure the on-time service probability for the customers. such stochastic travelling and service time and the chance constraint further complicate the problem. in this paper, a route-based mathematical model is introduced. a branch-and-price (b&p) algorithm and a discrete approximation method are combined to solve the problem. herein, effective label algorithms are designed to generate negative reduced cost routes. the efficiency of the algorithm are improved by employing three acceleration strategies. the experiments on test instances validate the performances of the proposed b&p algorithm and demonstrate the necessity of considering the stochasticity of travel times of home-caregiver and service times to the customers.