The service-centric Vehicle Routing Problem with Crowdshipping

Last-mile delivery services worldwide have embraced crowdshipping, which involves both regular and occasional drivers to reduce transportation costs and potentially ensure timely deliveries. However, real-world uncertainty in travel times leads to delays in deliveries. Motivated by empirical studies on customer impatience with late deliveries, this paper focuses on a service-centric Vehicle Routing Problem with Crowdshipping (VRPC) under uncertain travel times. Apart from traditional lateness measures, such as on-time arrival probability and expected lateness duration, we also consider scenarios where customers show exponential impatience towards lateness. We introduce a novel approach to calibrate the disutility, leading to salient managerial implications and probabilistic insights. We develop an exact branch-price-and-cut algorithm for the deterministic VRPC and a route enumeration-based exact algorithm for the non-convex and discontinuous service-centric VRPC. Numerical studies based on existing instances validate the computational efficiency of the developed algorithms and the efficacy of the newly proposed lateness measures in mitigating the risk of late deliveries.