An algorithmic approach for the quadratic travelling salesman problem

Abstract

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