Geração eficiente de soluções iniciais de alta qualidade para o problema de minimização de trocas de ferramentas

Resumo

Como problema de otimização, o problema de minimização de trocas de ferramentas retém diversos estudos no campo da pesquisa operacional sobre suas diferentes variações, enfatizado por sua relevância acadêmica e industrial. Embora os métodos atuais para solução deste problema reportem soluções de altíssima qualidade, o tempo computacional requerido tem se mostrado proibitivo frente ao aspecto prático do problema. Assim, neste trabalho, apresenta-se um método para geração de soluções válidas de alta qualidade em baixo tempo computacional, que possam ser utilizadas como soluções iniciais por métodos mais robustos, visando acelerá-los e contribuir para a qualidade final das soluções. A abordagem proposta consiste em uma nova implementação do método de descida randômica em vizinhança variável contendo buscas locais tradicionais e especializadas. Para geração do ponto inicial de exploração do método proposto, foram consideradas cinco heurísticas propostas originalmente para o problema do caixeiro viajante. Os resultados obtidos foram comparados com uma estratégia recente da literatura para geração de soluções iniciais e demonstraram melhoria significativa. Adicionalmente, o método proposto foi comparado ao atual estado da arte para o problema tratado e reportou um gap médio de apenas 5,36%, evidenciando a alta qualidade das soluções reportadas para o objetivo proposto.