A scenario-based approach for the vehicle routing problem with roaming delivery locations under stochastic travel times

We address a stochastic variant of the Vehicle Routing Problem with Roaming Delivery Locations. In this model, direct-to-consumer deliveries can be made in the trunk of the customer’s car, while the vehicle is parked at a location along the customer’s itinerary. The stochasticity arises from the uncertainty in travel times and the problem is formulated as a two-stage stochastic model. We propose a scenario-based sample average approximation to obtain a heuristic solution. Several experiments to assess the effect of our solution approach compared to a pure deterministic solution approach using expected travel times,show that a cost savings of on average more than 30% can be obtained. Furthermore, it is shown that the flexibility provided by using alternative roaming delivery locations as a recourse to avoid missed deliveries can provide, on average, costs savings of 25% compared to a recourse staying with the locations chosen in the a priori first stage plan.\u3cbr/\u3e\u3cbr/\u3