Navegando por Palavras-chave "Biased Random-Key Genetic Algorithm"

Agora exibindo 1 - 2 de 2
  • Imagem de Miniatura
    Item
    Acesso aberto (Open Access)
    Algoritmos híbridos para a solução do "Team Orienteering Problem"
    (Universidade Federal de São Paulo, 2023-06-28) Macêdo, Eduardo Állysson Alves Gonçalves [UNIFESP]; Senne, Edson Luiz França [UNIFESP]; http://lattes.cnpq.br/1338008237590056; https://lattes.cnpq.br/6111444839287695
    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.
  • Imagem de Miniatura
    Item
    Acesso aberto (Open Access)
    Hybrid metaheuristics to solve a multi-product two-stage capacitated facility location problem
    (Wiley, 2021) Chaves, Antonio Augusto [UNIFESP]; Mauri, Geraldo Regis; Biajoli, Fabricio Lacerda [UNIFESP]; Rabello, Rômulo Louzada; Ribeiro, Glaydston Mattos; Lorena, Luiz Antônio Nogueira [UNIFESP]; http://lattes.cnpq.br/4973949421738244
    This paper presents two hybrid metaheuristics to solve a multi-product two-stage capacitated facility location prob- lem (MP-TSCFLP). In this problem, a set of different products must be transported from a set of plants to a set of intermediate depots (first stage) and from these depots to a set of customers (second stage). The objective is to minimize the cost related to open plants and depots plus the cost for transporting the products from the plants until the customers satisfying demand and capacity constraints. Recently, the methods Clustering Search (CS) and Biased Random-Key Genetic Algorithm (BRKGA) were successfully applied to solve a single-product problem (SP-TSCFLP). Therefore, in this paper we propose adaptations and implementations of these methods for handling with a multi-product approach. To the best of our knowledge, CS and BRKGA presented the best results for the SP-TSCFLP and both have not yet been applied to solve the problem with multiple products. Four sets of large- sized instances with different characteristics are proposed and computational experiments compare the obtained results to those from a commercial solver.