We present an improved integer L-shaped method for the vehicle routing problem with stochastic demands. It exhibits speedups up to a factor of 325 compared with the current state-of-the-art, which allows us to solve 153 previously unsolved benchmark instances to optimality. The algorithm builds on the state-of-the-art in a few ways. First, we rectify a few technical issues found in the current literature. Second, we improve valid inequalities known as partial route inequalities. Finally, we introduce three new types of valid inequalities. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online appendices are available at https://doi.org/10.1287/ijoc.2023.1271 .

We introduce the driver assignment vehicle routing problem, DAVRP. In this problem, drivers are assigned to customers before demand is known, and after demand is known a routing schedule has to be made such that every driver visits at least a fraction α of its assigned customers. We present a solution procedure to investigate how much transportation costs increase by adhering to the driver assignments. Furthermore, we distinguish between the case in which customers that are not visited by their assigned driver are visited by backup drivers only, and the case in which slack capacity of regular drivers is utilized to visit these customers. We use randomly generated instances of the DAVRP to provide examples where the difference in transportation costs is substantial. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(3), 212–223 2016