Problema do caixeiro viajante: uma abordagem para o caso quadrático

Abstract

The 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.