Detalhes bibliográficos
Ano de defesa: |
2022 |
Autor(a) principal: |
Vianna, Bárbara Lessa [UNIFESP] |
Orientador(a): |
Não Informado pela instituição |
Banca de defesa: |
Não Informado pela instituição |
Tipo de documento: |
Dissertação
|
Tipo de acesso: |
Acesso aberto |
Idioma: |
por |
Instituição de defesa: |
Universidade Federal de São Paulo
|
Programa de Pós-Graduação: |
Não Informado pela instituição
|
Departamento: |
Não Informado pela instituição
|
País: |
Não Informado pela instituição
|
Palavras-chave em Português: |
|
Link de acesso: |
https://repositorio.unifesp.br/handle/11600/67303
|
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. |