Métodos exato e heurístico para resolução do problema do caixeiro viajante em famílias

Abstract

No campo da Pesquisa Operacional, uma tendência é o desenvolvimento de métodos hı́bridos exatos e heurı́sticos para obter resultados de boa qualidade em problemas de otimização combinatória. Existem diversas maneiras de hibridização. Uma possibilidade de hibridizar métodos exatos é através da integração de um método exato com heurı́sticas de busca local. Uma versão hı́brida de metaheurı́sticas pode ser obtida com a integração de técnicas de Aprendizado de Máquinas. Um dos problemas mais clássicos de otimização combinatória é o Problema do Caixeiro Viajante (TSP). Nesse problema considera-se a minimização apenas dos custos operaciona- is envolvidos no percurso do vendedor. Contudo, o TSP pode ser adaptado para diferentes problemas que empresas logı́sticas enfrentam, como, por exemplo, diferentes categorias de produtos, prioridades de entregas, e localização de produtos em armazéns. Este trabalho aborda o Problema do Caixeiro Viajante em Famı́lia (FTSP, do inglês Family Traveling Salesman Problem), em que os clientes são agrupados em famı́lias que correspondem a produtos de mesma similaridade e com a demanda de visitas predefinidas. O objetivo do FTSP é determinar a rota de custo mı́nimo visitando apenas um subconjunto de clientes de cada famı́lia. Assim como o TSP, trata-se de um problema de otimização combinatória pertencente a classe NP-Difı́cil. Para solucionar o problema proposto foram desenvolvidos dois métodos: (i) um branch- and-cut paralelo com um procedimento de busca local eficiente para obter a solução ótima, e (ii) uma metaheurı́stica adaptativa que combina o método Biased Random-key Genetic Algorithm (BRKGA) com um algoritmo de aprendizado por reforço, Q-Learning (QL). Neste caso, o algoritmo Q-Learning é utilizado para controlar os parâmetros do BRKGA durante o processo evolutivo. Experimentos computacionais foram realizados em um conjunto de dados de referência bem conhecido, que possui 185 instâncias. O algoritmo P-B&C desenvolvido para o FTSP prova o valor ótimo para 179 instâncias e o BRKGA-QL encontrou os melhores limites superiores para as outras quatro instâncias. Os resultados foram comparados com os melhores resultados da literatura, e ambos os métodos mostram robustez e eficiência para resolver o FTSP.