A stochastic vehicle routing problem with roaming customers under joint delivery

Our attention is directed toward addressing two stochastic variants of vehicle routing problems involving roaming customers under the context of joint delivery (SVRP-RC-JD). Specifically, one variant accounts for stochastic travel times, while the other incorporates stochastic time windows. The SVRP-RC-JD is conceptualized as a two-stage stochastic model with recourse. To tackle this problem effectively, we introduce an adaptive large neighborhood search heuristic, complemented by a late acceptance hill-climbing strategy, and integrate two distinct sampling strategies: fixed sample size sampling (FSS) and sample average approximation (SAA). Furthermore, we carry on a computational study to assess and analyze our approach. The results reveal that significant cost saving can be achieved under stochastic variants. There is no significant difference in cost between FSS and SAA in the case of small and medium-sized instances, conversely, the SAA outperforms the FSS in cost for large-sized instances.