Navegando por Autor "Almeida, Guilherme Barbosa de"

Agora exibindo 1 - 1 de 1
  • Imagem de Miniatura
    Item
    Algoritmos para o problema capacitado de localização de facilidades com fonte única e sua variante robusta
    (Centro Federal de Educação Tecnológica de Minas Gerais, 2026-06-29) Almeida, Guilherme Barbosa de; Souza, Marcone Jamilson Freitas; Souza, Sergio Ricardo de; Sá, Elisangela Martins de; http://lattes.cnpq.br/3677015295211434; http://lattes.cnpq.br/4686246805500174; http://lattes.cnpq.br/6078945717558464; http://lattes.cnpq.br/3173964416432908; Souza, Marcone Jamilson Freitas; Souza, Sergio Ricardo de; Sá, Elisangela Martins de; Morabito Neto, Reinaldo; Bruck, Bruno Petrato; Vargas, Dênis Emanuel da Costa; Menezes, Gustavo Campos
    Esta tese aborda o Problema Capacitado de Localização de Facilidades com Fonte (SSCFLP) e sua variante robusta (RSSCFLP). O SSCFLP consiste em determinar locais para a abertura de facilidades capacitadas para atender às demandas dos clientes, de modo que cada cliente seja atendido por uma única facilidade. Já o RSSCFLP estende o SSCFLP ao considerar incertezas nos custos de alocação e abertura, nas demandas e nas capacidades. Para formular o RSSCFLP, adota-se a abordagem robusta de Bertsimas e Sim. Para resolver os problemas, são propostos três algoritmos: HILS e NCS, para o SSCFLP, e o B&B-GVNS, para o RSSCFLP. O HILS combina a resolução de subproblemas com procedimentos baseados em ILS para obter soluções de qualidade. O NCS combina um método de planos de corte, uma heurística baseada em busca local e um procedimento cut-and-solve para encontrar a solução ótima do problema. O B&B-GVNS combina um procedimento de planos de corte, uma heurística baseada em GVNS e um algoritmo branch-and-bound aprimorado com heurísticas. Experimentos computacionais indicam que o HILS é competitivo em relação aos algoritmos do estado da arte, produzindo soluções com valores de gap ligeiramente menores em conjuntos mais desafiadores. Os resultados obtidos com o NCS mostraram que ele encontrou mais soluções ótimas ou reduziu o tempo necessário para obtê-las em 85% dos subconjuntos analisados, quando comparado ao algoritmo do estado da arte, e em 73% dos subconjuntos, quando comparado ao CPLEX. Além disso, em vários subconjuntos, o NCS foi mais de 100 vezes mais rápido do que o CPLEX e mais de 10 vezes mais rápido do que o algoritmo do estado da arte para encontrar um número maior ou igual de soluções ótimas. Por fim, o B&B-GVNS apresentou desempenho superior ao do CPLEX em todos os conjuntos testados, com reduções no gap superiores a 20% e 25% nos dois conjuntos mais desafiadores. Esses resultados evidenciam que os algoritmos desenvolvidos nesta tese constituem contribuições metodológicas relevantes para a resolução de problemas capacitados de localização de facilidades e de sua variante robusta.