Home Care Routing and Appointment Scheduling with Stochastic Service Durations

Motivated by a practical problem arising from the home health care industry, we consider an integrated routing and appointment scheduling problem with random service durations. Given a set of patients with known locations and service duration distributions, the health care team is required to visit each location exactly once. The objective of the problem is to determine the visit route and appointment times to minimize the total cost of traveling and idling of the health care team and the cost of waiting of the patients. We formulate the problem as a stochastic mixed integer program (MIP). By exploiting structures of the problem, we propose using an integer L-shaped method to solve the sample average approximation (SAA) version of the problem. New optimality cuts are developed to improve the performance of the method, leading to a much more efficient algorithm than the traditional branch-and-cut algorithm. Furthermore, we propose two approximation methods for solving this problem. The first one uses an inventory approximation idea developed in the recent literature, which only requires the mean and variance information of the service durations. The second one is based on a "look-one-step-back" idea and approximates the appointment cost of each patient by only considering the randomness of the service duration at its predecessor. We also conduct numerical experiments to assess the performance of the proposed methods on problems of practical size. The computational results show that both the exact and the approximate methods work very well