Distributionally robust vehicle routing with crowdshipping and time windows

Last-mile delivery with crowdshipping has received much attention from large retailers, in which in-store customers (i.e., occasional drivers) supplement company drivers (i.e., regular drivers) and make deliveries on their way home. However, real-world uncertainty in travel times leads to delays, and the true distribution of travel times is inaccessible. Motivated by these challenges, this paper studies a Vehicle Routing Problem with Crowdshipping and Time Windows (VRPCTW) under uncertain travel times. We formulate an arc-based distributionally robust optimization model where the travel time distribution is described by a Wasserstein ambiguity set, and the risk of time window violation is measured by Conditional Value-at-Risk. We reformulate the distributionally robust time window constraints and establish their equivalence to sample average constraints with slightly advanced deadlines. We then formulate an equivalent route-based model and develop an exact branch-price-and-cut algorithm and a column-generation-based heuristic. Extensive computational studies on benchmark instances validate the computational efficiency of our algorithms. Compared with the deterministic VRPCTW, our model can more effectively meet the time windows with a slightly additional cost.