The Capacitated Multi-Depot Vehicle Routing Problem with Stochastic Pickups and Deliveries

The classical Vehicle Routing Problem (VRP) is to determine optimal routes for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m$</tex> identical vehicles that must visit a set of costumers, departing and returning from a depot. The following restrictions must be satisfied: (1) each vehicle begins and ends at the depot and (2) each customer is visited exactly once. We consider a novel variant of the VRP that incorporates multiple depots, vehicle capacity and stochastic information about future incoming of costumers. We denote this problem as the capacitated multi-depot VRP with stochastic pickup and delivery (CMVRPSPD). The CMVRPSPD is an extension of the capacitated VRP with pickup and delivery, in which there is a different depot for each vehicle and the pickup and delivery points (each pair associated with a costumer) are stochastic. The problem is to compute routes visiting all pairs of pickup and delivery minimizing the expected total cost of routes, since the real occurrence of each pair of pickup/delivery is random. In this case, some of the a priori designed routes can fail. We propose strategies to correct routes with failures. We introduce a method to efficiently compute the expected cost of a solution. We evaluate the performance of these strategies on a data set adapted from VRP instances. The results show that the proposed method is efficient to compute the expected cost of a route.