Métodos exato e heurístico para resolução do problema do caixeiro viajante em famílias
Data
2022-03-28
Autores
Vianna, Bárbara Lessa [UNIFESP]
Orientadores
Chaves, Antônio Augusto [UNIFESP]
Tipo
Dissertação de mestrado
Título da Revista
ISSN da Revista
Título de Volume
Resumo
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.
Descrição
Citação
LESSA VIANNA, Bárbara. Métodos exato e heurı́stico para resolução do Problema do Caixeiro Viajante em Famı́lias. 2022. 100f. Dissertação de Mestrado – Instituto Tecnológico de Aeronáutica e Universidade Federal de São Paulo, São José dos Campos.