TSP can be defined as a problem where starting from a node it is required to visit every other node only once in a way that the total distance covered is minimized. Tabu Search is a heuristic that prevent the process from cycling in a small set of solutions, some attribute of recently visited solutions is stored in a Tabu List, which prevents their occurrence for a limited period. For our problem, the attribute used is a pair of nodes that have been exchanged recently. A Tabu structure stores the number of iterations for which a given pair of nodes is prohibited from exchange.