Vehicle Routing Problem with Roaming Delivery Locations and Stochastic Travel Times (VRPRDL-S)

This paper presents an approach to model and solve the vehicle routing problem with random delivery locations and stochastic travel times (VRPRDL-S), a variant of the vehicle routing problem with random delivery locations that allows, for instance, the possibility of having a parcel delivered to the trunk of the customer’s vehicle, which can be in different locations during the same day. In the proposed model, the classical distance matrix is replaced by a matrix of probability distributions composed of the distribution of travel times between two points. Thus, the model integrates the fact that the travel time between two points is non-deterministic. This paper explores in detail a medium-sized problem and uses a combination of a Monte-Carlo method and an enhanced greedy randomized adaptive search procedure (GRASP) to find a pseudo-optimum. Moreover, the relevance of the approach is validated through a campaign test. This work intends to build on the current state of the art by proposing a new variant of the VRP and a heuristic method to solve it.