Algoritmos híbridos para a solução do "Team Orienteering Problem"
Arquivos
Data
2023-06-28
Autores
Macêdo, Eduardo Állysson Alves Gonçalves 
Orientadores
Senne, Edson Luiz França
Tipo
Dissertação de mestrado
Título da Revista
ISSN da Revista
Título de Volume
Resumo
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.
This work addresses the resolution of the Team Orienteering Problem (TOP) through the utilization of two hybrid methods. These hybrid methods are derived from the integration of the Iterated Local Search (ILS) metaheuristic with the Fix-And-Optimize (F&O) matheuristic, as well as the Biased Random-Key Genetic Algorithm (BRKGA) with the F\&O. The Team Orienteering Problem is a challenging combinatorial optimization problem classified as an NP-hard. The main objective of TOP is to maximize the total prize collected by a fleet of vehicles by determining the optimal sequence and selection of locations to visit for each vehicle, while adhering to the maximum route duration constraint. The ILS implementation incorporated local search heuristics that employed specific metrics to decide on the inclusion or replacement of locations. Likewise, a dedicated decoder for TOP was proposed in the BRKGA implementation. As for F&O, a definition of variable subsets based on adjacent nodes was used for solving subproblems, prioritizing the inclusion of nodes and associated variables in each subset based on the distance from unvisited nodes to nodes belonging to the routes. All implementations were carried out in the Julia language, with Gurobi serving as the solver for solving mixed integer programming problems within the scope of F&O. To evaluate the effectiveness of the proposed methods, computational experiments were conducted using three sets of instances from the existing literature. These sets consist of a total of 179 instances, with the number of locations ranging from 100 to 400. Each algorithm was executed 20 times for each instance. The ILS + F&O achieved identical results to the best known solutions in 94 instances, with an average percentage deviation of 0.53%, performing better in smaller instances. On the other hand, the BRKGA + F&O achieved better performance in larger instances and obtained identical results to the best known solutions in 92 instances, with an average percentage deviation of 0.50%. The results demonstrated that both methods effectively solve the problem and exhibit performance comparable to other methods documented in the literature.
This work addresses the resolution of the Team Orienteering Problem (TOP) through the utilization of two hybrid methods. These hybrid methods are derived from the integration of the Iterated Local Search (ILS) metaheuristic with the Fix-And-Optimize (F&O) matheuristic, as well as the Biased Random-Key Genetic Algorithm (BRKGA) with the F\&O. The Team Orienteering Problem is a challenging combinatorial optimization problem classified as an NP-hard. The main objective of TOP is to maximize the total prize collected by a fleet of vehicles by determining the optimal sequence and selection of locations to visit for each vehicle, while adhering to the maximum route duration constraint. The ILS implementation incorporated local search heuristics that employed specific metrics to decide on the inclusion or replacement of locations. Likewise, a dedicated decoder for TOP was proposed in the BRKGA implementation. As for F&O, a definition of variable subsets based on adjacent nodes was used for solving subproblems, prioritizing the inclusion of nodes and associated variables in each subset based on the distance from unvisited nodes to nodes belonging to the routes. All implementations were carried out in the Julia language, with Gurobi serving as the solver for solving mixed integer programming problems within the scope of F&O. To evaluate the effectiveness of the proposed methods, computational experiments were conducted using three sets of instances from the existing literature. These sets consist of a total of 179 instances, with the number of locations ranging from 100 to 400. Each algorithm was executed 20 times for each instance. The ILS + F&O achieved identical results to the best known solutions in 94 instances, with an average percentage deviation of 0.53%, performing better in smaller instances. On the other hand, the BRKGA + F&O achieved better performance in larger instances and obtained identical results to the best known solutions in 92 instances, with an average percentage deviation of 0.50%. The results demonstrated that both methods effectively solve the problem and exhibit performance comparable to other methods documented in the literature.
Descrição
Citação
MACEDO, E. A. A. G. Algoritmos híbridos para a solução do “Team Orienteering Problem”. 2023. 76f. Dissertação de Mestrado – Instituto Tecnológico de Aeronáutica e Universidade Federal de São Paulo, São José dos Campos.