Uma Abordagem Híbrida de Algoritmo Genético com Simulated Annealing na Solução do Problema do Roteamento de Veículos Capacitados

Abstract

The Capacitated Vehicle Routing Problem (CVRP) is an NP-hard combinatorial optimization challenge, fundamental to logistical efficiency, which seeks to minimize the costs of delivery routes while respecting vehicle load capacities. Given its computational complexity, the use of metaheuristics is an effective approach. This work proposes a two-phase hybrid methodology for solving the CVRP. First, a Genetic Algorithm (GA) is executed to perform a global search of the solution space, exploring diverse regions to generate a high-quality initial solution. Subsequently, the solution generated by the GA is used as the starting point for the Simulated Annealing (SA) algorithm, which applies an intensive local search process to refine the route, exploring its neighborhood and using its probabilistic mechanism to escape local optima. This hybridization aims to combine the exploratory power of the Genetic Algorithm with the intensification capability of Simulated Annealing, with the goal of finding higher-quality solutions than those obtained by the isolated application of each metaheuristic.