Algoritmos genéticos aplicados ao problema de roteamento de veículos com múltiplos depósitos

Abstract

The Vehicle Routing Problem (VRP) has wide applications in logistics and transportation with great economic importance. VRP is a generalization of a large number of routing problems, which consist of finding the optimal number of routes, leaving a single depot, to serve a set of customers, minimizing routing costs and meeting a set of constraints. The Multi Depot Vehicle Routing Problem (MDVRP) is an extension of VRP, in which there is more than one depot distributed in a given geographic area. The rest of the problem is identical to VRP. There are several methods for solving MDVRP such as exact techniques, approximate algorithms and heuristics. Genetic Algorithms (GAs) are meta-heuristics widely used to find solutions to the MDVRP problem due to the stochastic characteristics of GAs and the efficiency in solving combinatorial problems and, for this reason, they were selected to be applied in this work. The developed algorithm was tested using instances present in the literature and compared with existing methodologies, in which the genetic algorithm found good results and the work contributed to the technique of selecting customers who can exchange between deposits. The results achieved show that this algorithm can be evaluated in real projects, making it possible to improve the operation of projects that face this type of problem, reducing transportation costs, distance, delivery time, services, among other benefits.