META-HEURÍSTICA PARTICLE SWARM OPTIMIZATION APLICADA AO PROBLEMA DO CAIXEIRO VIAJANTE ASSIMÉTRICO

Resumo

O Problema do Caixeiro Viajante Assimétrico (PCVA) é um desafio clássico de otimização combinatória em que um vendedor ambulante percorre um conjunto de cidades, visitando cada cidade exatamente uma vez, e retorna à cidade de origem, minimizando a distância total percorrida, porém a distância entre duas cidades pode variar dependendo do sentido do deslocamento. O Particle Swarm Optimization, uma técnica inspirada no comportamento social de organismos vivos, foi utilizado para resolver o problema. Sendo uma meta-heurística, exige um balanço entre diversidade e intensidade do método para alcançar boas soluções em tempo razoável, evitando assim, ótimos locais. Para isso, o peso de inércia é linearmente reduzido ao longo de cada iteração, explorando amplamente o espaço de busca no início do algoritmo e intensificando a busca na parte final do algoritmo. Visto que o algoritmo encontrou, pelo menos uma vez, a solução ótima global para todas as instâncias testadas, o objetivo proposto foi atingido.