Integrando a busca iterativa em espaço restrito e métodos exatos : uma abordagem alternativa para o problema do caixeiro viajante

Abstract

Resumo: Este trabalho propõe uma matheurística baseada no princípio da Busca Iterativa em Espaço Restrito, ou Iterative Restricted Space Search (IRSS), associando a utilização da heurística de Lin-Kernighan (LK) e abordagens exatas para resolver diversas instâncias da versão simétrica do Problema do Caixeiro Viajante. O objetivo central deste estudo é avaliar a integração da heurística LK e abordagens exatas no contexto da estratégia IRSS de busca e propor uma alternativa superior em relação às abordagens exatas e heurística quando aplicadas de maneira exclusiva. Foram avaliadas vinte e duas instâncias do TSP, com dimensões variando 16 e 202 nós, utilizando o valor da função objetivo, gap e tempo de processamento como parâmetros de desempenho das abordagens. Os resultados indicam que, embora o método exato tenha alcançado a otimalidade em todas as instâncias, seu tempo de processamento cresce acentuadamente a partir de 124 nós. A heurística LK apresentou o menor tempo de processamento, resolvendo instâncias com mais de duzentos nós em frações de segundos, no entanto, esta apresentou perdas expressivas na qualidade das soluções encontradas com o aumento das dimensões das instâncias. Já a matheurística apresentou tempos de processamento consideravelmente inferiores aos do método exato e foi capaz de produzir soluções de elevada qualidade com gaps inferiores. A abordagem puramente exata é recomendável quando se exige otimalidade e o tamanho do problema não for impeditivo; a heurística LK atende a situações em que se demandam respostas rápidas com menor rigor quanto à qualidade da solução; já a matheurística se destacou como uma alternativa promissora por conciliar tempos inferiores de processamento e qualidade de solução

Abstract: This study proposes a matheuristic based on the Iterative Restricted Space Search (IRSS) principle, combining the Lin-Kernighan (LK) heuristic with exact methods to solve various instances of the symmetric Traveling Salesman Problem (TSP). The main objective of this research is to assess the integration of the LK heuristic and exact methods within the IRSS framework, aiming to offer a superior alternative compared to the isolated application of heuristic or exact approaches. Twenty-two TSP instances, ranging from 16 to 202 edges, were assessed and the objective function value, optimality gap, and processing time were used as performance metrics. The results show that, although the exact method reached optimality in all cases, its processing time increased notably for instances with more than 124 nodes. The LK heuristic achieved the fastest execution times, solving large instances in fractions of a second, but its solution quality tended to deteriorate as the instance size increased. The proposed matheuristic, in turn, produced high-quality solutions with substantially lower gaps and reduced processing times compared to the exact method. The exact approach is recommended when optimality is required, and instance size is not prohibitive; the LK heuristic is suitable for scenarios demanding quick responses with less concern for solution quality; and the matheuristic emerged as a promising alternative by combining fast processing times with high-quality results