Memorial de projetos : aplicação do problema caixeiro viajante para na solução de problemas de otimização de rotas utilizando algoritmos gentéticos K-Means

Abstract

Resumo: O Problema do Caixeiro Viajante (PCV) é um problema clássico de otimização combinatória que é intensamente investigado em matemática computacional devido a sua complexidade de obtenção de uma solução ideal. O presente trabalho utiliza-se da estratégia de agrupamento de clusterização utilizando K-means e Algoritmo Genético para tratar um problema de alta complexidade com o objetivo de otimização de rotas turísticas. Utilizando pontos de interesses da cidade do Rio de Janeiro como exemplo para geração de um roteiro com pontos turísticos de interesse do usuário, o uso da heurística do vizinho mais próximo foi possível validar que a técnica é apropriada para resolver esse tipo de problema de forma eficiente

Abstract: The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem that has been extensively studied in computational mathematics due to its complexity in obtaining an optimal solution. This study applies a clustering strategy using K-means and a Genetic Algorithm to address a high-complexity problem with the objective of optimizing tourist routes. Using points of interest in the city of Rio de Janeiro as an example to generate an itinerary with tourist attractions tailored to the user's preferences, the application of the nearest neighbor heuristic made it possible to validate that the technique is suitable for efficiently solving this type of problem