O problema do caixeiro viajante contínuo ou CTSP, do inglês Continuous Traveling Salesman Problem, é uma variante do problema do caixeiro viajante (TSP) na qual cada cidade pertence a um conjunto arbitrário e o objetivo é determinar o tour de menor comprimento que passa por cada um dos conjuntos e retorna ao primeiro. Neste trabalho consideramos o CTSP em que os conjuntos visitados são dados por bolas pertencentes ao R^2. Ou seja, dado um conjunto de m bolas do R^2, estamos interessados em determinar pontos x^i, um em cada bola, e uma permutação de modo que o tour passando pelos pontos x^i com a ordem dada pela permutação tenha comprimento mínimo. Para resolver este problema propomos quatro algoritmos, nos quais unimos heurísticas já consolidadas para o TSP clássico, como a heurística 2-Opt, com um método de busca em bloco de coordenadas. Os algoritmos foram implementados na linguagem de programação Fortran 90 e para testá-los geramos 60 instâncias de pontos aleatórios, sendo 10 para cada número de bolas m = 50, 100, 200, 300, 400 e 500. Além disso, foram realizados experimentos numéricos com 10 instâncias da biblioteca TSPLIB adaptadas ao CTSP. Tabelas foram geradas para cada experimento, detalhando as soluções encontradas pelos métodos e seus desempenhos, permitindo realizar comparações entre eles. Figuras das soluções encontradas pelos métodos também são apresentadas para algumas instâncias.

The Continuous Traveling Salesman Problem (CTSP) is a variant of the Traveling Salesman Problem (TSP) in which each city belongs to an arbitrary set and the aim is to determine the shortest tour passing through each of the sets and returning to the first. In this work we consider the CTSP in which the sets visited are given by balls in R^2. That is, given a set of m balls in R^2, we are interested in determining points x^i, one on each ball, and a permutation such that the tour among the balls that visit each point x^i exactly once with the order given by the permutation has minimum length. To solve this problem we propose four algorithms, in which we combine consolidated heuristics for the classical TSP, such as the 2-Opt heuristic, with a block coordinate descent method. The algorithms were implemented with Fortran 90 programming language and to test them we generated 60 instances of random points, being 10 for each number of balls m = 50, 100, 200, 300, 400, 500. In addition, numerical experiments were performed with 10 instances of the TSPLIB library adapted to CTSP. Tables were generated for each experiment, detailing the solutions obtained by the methods and their performances, allowing comparisons among them. Figures of the solutions obtained by the methods are also presented for some instances.