Maia, Sílvia Maria Monteiro DinizAquino, João Victor Malheiros Farias de2025-07-212025-07-212025-07-11AQUINO, João Victor Malheiros Farias de. An algorithmic approach for the quadratic travelling salesman problem. Orientadora: Sílvia Maria Diniz Monteiro Maia. 2025. 48 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, 2025.https://repositorio.ufrn.br/handle/123456789/64698This undergraduate thesis explores the application of exact and meta heuristic algorithms to solve the Quadratic Travelling Salesman Problem (QTSP). The QTSP is a variant of the Traveling Salesman Problem in which the cost function is quadratic, depending on each sequence of 3 cities visited. This variant emerged as a model of a real problem in bioinformatics but also has some application in robotics. We implemented a Tabu Search algorithm to deal with QTSP. We also implemented the Cheapest Insertion heuristic. A computational experiment is designed to evaluate and compare the performance of the proposed approaches concerning solution quality and execution time. The comparison of the (meta)heuristic algorithms presented with genetic and memetic algorithms from the literature is reported. Another experiment with exact algorithms, such as brute force, branch and bound, and dynamic programming, all of them using the same ideas employed in TSP, is also reported. The findings provide insights into the strengths and weaknesses of each algorithm, helping researchers and practitioners select suitable methods to solve the QTSP.en-USAttribution 3.0 Brazilhttp://creativecommons.org/licenses/by/3.0/br/Problema do caixeiro viajante quadráticoMetaheurísticasAlgoritmos exatosBranch and boundProgramação dinâmicaInserção mais barataBusca tabuQuadratic traveling salesman problemMetaheuristicsExact algorithmsBranch and boundDynamic programmingCheapest insertionTabu searchbachelorThesisCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO