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.

We present a natural probabilistic variation of the multi-depot vehicle routing problem with pickup and delivery (MDVRPPD).In this paper, we present a variation of this deterministic problem, where each pair of pickup and delivery points are present with some probability, and their realization are only known after the routes are computed.We denote this stochastic version by S-MDVRPPD.One route for each depot must be computed satisfying precedence constraints, where each pickup point must appear before its delivery pair in the route.The objective is to find a solution with minimum expected traveling distance.We present a closed-form expression to compute the expected length of an a priori route under general probabilistic assumptions.To solve the S-MDVRPPD we propose an Iterated Local Search (ILS) that uses the Variable Neighborhood Descent (VND) as local search procedure.The proposed heuristic was compared with a Tabu Search (TS) algorithm based on a previous work.We evaluate the performance of these heuristics on a data set adapted from TSPLIB instances.The results show that the ILS proposed is efficient and effective to solve S-MDVRPPD.

The Traveling Car Renter Problem (CaRS) is a generalization of the Traveling Salesman Problem. This paper presents a hybrid metaheuristic approach to deal with CaRS: an evolutionary algorithm (ScA) and the hybrid method Adaptive Local Search Procedure (ALSP), denoted by ScA+ALSP. A mixed integer programming model proposed for CaRS is corrected and used within the ALSP. The results of experimental studies using a suite of 21 instances taken from the literature indicated that the hybrid ScA+ALSP is competitive regarding the best known algorithm in literature for non-Euclidean CaRS instances. Three new best results are reported.