Vehicle Routing Problems with Synchronized Visits and Stochastic Travel and Service Times: Applications in Healthcare

Abstract

This paper, for the first time, studies vehicle routing problems with synchronized visits (VRPS) and stochastic travel and service times. In addition to considering a home healthcare scheduling problem, we introduce an operating room scheduling problem with stochastic durations as a novel application of VRPS. We formulate VRPS with stochastic times as a two-stage stochastic integer programming model that, unlike the deterministic models in the VRPS literature, does not have any big-M constraints. This advantage comes at the cost of a large number of second-stage integer variables. We prove that the integrality constraints on second-stage variables can be relaxed, and therefore, we can apply the L-shaped algorithm and its branch-and-cut implementation to solve the problem. We enhance the model by developing valid inequalities and a lower bounding functional. We analyze the subproblems of the L-shaped algorithm and devise a specialized algorithm for them that is significantly faster than standard linear programming algorithms. Computational results show that the branch-and-cut algorithm optimally solves stochastic home healthcare scheduling instances with 15 patients and 10%–30% of synchronized visits. It also finds solutions with an average optimality gap of 3.57% for instances with 20 patients. Furthermore, the branch-and-cut algorithm optimally solves stochastic operating room scheduling problems with 20 surgeries.