Maia, Sílvia Maria Diniz MonteiroSilva, Ítalo Epifânio de Lima e2023-12-182023-12-182023-12-08SILVA, Ítalo Epifânio de Lima e. Problema do caixeiro viajante: uma abordagem para o caso quadrático. Orientadora: Sílvia Maria Diniz Monteiro Maia. 2023. 59 f. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação) - Departamento de Informática e Matemática Aplicada, Universidade Federal do Rio Grande do Norte, Natal, 2023.https://repositorio.ufrn.br/handle/123456789/56039The traveling salesman problem (TSP) is one of the most studied optimization problems in the literature, with various applications and variations. One such variation, the quadratic traveling salesman problem (QTSP), was initially introduced in the field of bioinformatics, focused on optimally finding binding sites. Like the TSP, the QTSP variation is also NP-hard, with no known exact solutions in polynomial time for instances of significant size. The present study aims to investigate the state of the art of QTSP, employing exploratory and experimental methods. Both exact solutions and heuristics were evaluated, in addition to introducing two new meta-heuristic approaches: one based on genetic algorithms and another on memetic algorithms. The genetic and memetic meta-heuristics are compared in terms of efficacy and efficiency for different sizes of QTSP instances. The results indicate that the memetic algorithm proved to be the best solution for larger instances of the problem, while the genetic algorithm did not show good results, sometimes being worse than the heuristics. For smaller instances, the cheapest insertion algorithm achieved better results. We conclude that memetic algorithms can be a promising solution for solving the QTSP, offering new perspectives for future approaches.Attribution 3.0 Brazilhttp://creativecommons.org/licenses/by/3.0/br/Problema do caixeiro viajante quadráticoMeta-heurísticasAlgoritmos evolucionáriosAlgoritmos genéticosAlgoritmos meméticosQuadratic traveling salesman problemMeta heuristicsEvolutionary algorithmsGenetic algorithmsMemetic algorithmsbachelorThesisCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAO