USO DO ALGORITMO SIMULATED ANNEALING NO PROBLEMA DO CAIXEIRO VIAJANTE

Resumo

O Problema do Caixeiro Viajante (PCV) é um desafio clássico de otimização combinatória em que um vendedor ambulante precisa encontrar a rota mais curta para visitar um conjunto de cidades, passando exatamente uma vez em cada uma, e retornar ao ponto de origem. Para resolvê-lo, uma técnica de otimização probabilística inspirada no processo físico de recozimento de materiais foi utilizada, o Simulated Annealing. Ele inicia com uma solução inicial e, ao longo das iterações, aceita movimentos que levam a soluções piores com uma probabilidade decrescente baseada na temperatura do sistema. Isso permite ao algoritmo escapar de mínimos locais e explorar diferentes regiões do espaço de busca. A temperatura é gradualmente reduzida ao longo do tempo, reduzindo a probabilidade de aceitar soluções piores. A solução ótima global foi encontrada em todas as instâncias testadas pelo menos uma vez, atendendo ao objetivo proposto.