Um método heurístico para o problema do caixeiro viajante suficientemente próximo

Resumo

O Problema do Caixeiro Viajante (TSP, do inglês Traveling Salesman Problem) é um dos problemas de otimização combinatória mais estudados. Dado m cidades e seus pares de distâncias, busca-se encontrar um tour de distância mínima que passe por todas as cidades. Na variante Close-Enough do TSP (CETSP), não é necessário passar exatamente por cada cidade, mas por uma vizinhança de cada cidade. Esse problema pode ser modelado como um problema de otimização contínua com variáveis inteiras. Neste trabalho, apresentamos um método heurístico para encontrar soluções para o CETSP, incluindo uma heurística construtiva, uma busca local baseada no movimento 2-opt e um método de otimização contínua de busca em blocos de coordenadas. Experimentos numéricos foram realizados com 60 instâncias de pontos aleatórios e 10 instâncias da biblioteca TSPLIB adaptadas ao CETSP. O método proposto se sobressai, na maioria dos testes, em relação a qualidade de soluções e tempo de execução aos métodos que usam movimentos de realocação.