Algoritmos híbridos para a solução do "Team Orienteering Problem"

• Ano de defesa: 2023
• Autor(a) principal: Macêdo, Eduardo Állysson Alves Gonçalves [UNIFESP]
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de São Paulo
• Palavras-chave em Português: Hybrid Algorithms; Iterated Local Search; Biased Random-Key Genetic Algorithm; Fix-and-Optimize; Mixed Integer Programming; Metaheuristics
• Link de acesso: https://repositorio.unifesp.br/handle/11600/68965

Neste trabalho, o Team Orienteering Problem (TOP) é resolvido utilizando dois métodos híbridos resultantes da integração da metaheurística Iterated Local Search (ILS) com a matheuristic Fix-and-Optimize (F&O) e da metaheurística Biased Random-Key Genetic Algorithm (BRKGA) com o F&O. O Team Orienteering Problem é um problema de otimização combinatória NP-difícil pertencente à classe de problemas de roteamento com prêmios. Seu objetivo é maximizar um prêmio total coletado por uma frota de veículos, determinando quais localidades são visitadas por cada veículo e em que sequência, restrito ao tempo máximo de duração de cada rota. A implementação do ILS contou com heurísticas de busca local contendo métricas específicas para a inclusão ou substituição de localidades. De modo semelhante, um decoder específico para o TOP foi proposto na implementação do BRKGA. Quanto ao F&O, foi utilizada, para a solução dos subproblemas, uma definição de subconjuntos de variáveis baseada em nós adjacentes, priorizando a inclusão dos nós e variáveis associadas em cada subconjunto baseada na distância dos nós não visitados aos nós pertencentes às rotas. Todas as implementações foram realizadas em linguagem de programação Julia e o Gurobi foi utilizado como pacote de otimização para a solução dos problemas de programação inteira mista no âmbito do F&O. Para analisar a efetividade dos métodos propostos, foram realizados experimentos computacionais com 3 conjuntos de instâncias de maior porte constantes da literatura, contendo ao todo 179 instâncias com número de localidades variando de 100 a 400 e os algoritmos foram executados 20 vezes para cada uma das instâncias. O ILS + F&O obteve resultados idênticos aos das melhores soluções conhecidas em 94 instâncias e um desvio percentual médio de 0,53% com melhor desempenho nas instâncias de menor porte. Já o BRKGA + F&O alcançou um melhor desempenho nas instâncias de grande porte e obteve resultados idênticos aos das melhores soluções conhecidas em 92 instâncias e um desvio percentual médio de 0,50%. Verificou-se que os métodos demonstraram efetividade na solução do problema, sendo comparáveis a outros métodos apresentados na literatura.