The classical Vehicle Routing Problem (VRP) is to determine optimal routes for$m$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.

The Traveling Car Renter Salesman Problem (CaRS) is a generalization of the Traveling Salesman Problem. A new variant of the Adaptive Local Search Procedure (ALSP) algorithm called Iterated Adaptive Local Search Procedure (IALSP) is presented in this work. Two mathematical formulations are presented to model the CaRS problem. These formulations are compared using a MIP solver. The formulation with the best result is used in the IALSP algorithm. To deal with the CaRS problem, we propose a hybrid algorithm composed of an evolutionary algorithm called Scientific Algorithm (ScA) and the IALSP algorithm. We call the proposed hybrid algorithm ScA + IALSP. We have carried out computational experiments on a set of 15 instances extracted from the literature. We have compared the proposed algorithm with the best-known algorithm in the literature. The results show that the IALSP algorithm is competitive. Six new best results are reported.