Uma abordagem híbrida de metaheurística para o problema de roteamento de veículos

Abstract

The Capacitated Vehicle Routing Problem (CVRP) is a classic problem in combinatorial optimization, aimed at optimizing the routes of vehicles with limited storage capacity to meet customer demands. The primary goal of the CVRP is to find a feasible solution that minimizes the total route cost in a weighted graph. This problem is widely studied due to its relevance in various practical applications, such as logistics and distribution. This research aims to develop a hybrid metaheuristic solution composed of Genetic Algorithms (GA), Ant Colony Optimization (ACO), and Tabu Search (TS) to find optimal or near-optimal solutions for the CVRP. The steps established to achieve this objective include the development of the hybrid algorithm ACO+TS combined with GA for the CVRP, conducting computational experiments using test instances, comparing the results obtained by the proposed algorithm with known optimal solutions or those obtained by other existing optimization methods, and analyzing the results to identify advantages, limitations, and potential improvements of the proposed algorithm. The results demonstrate that the GA, ACO, and TS are highly effective in solving complex instances of the CVRP. In several tested instances, the solutions found were close to or exceeded the reference optimal values, highlighting the high efficiency of the proposed method. In conclusion, the hybrid ACO+TS approach combined with GA has confirmed its effectiveness in solving complex vehicle routing problems, providing a solid foundation for future research. The hybrid combination of algorithms contributes to obtaining high-quality solutions and efficiently exploring the solution space.