Algoritmos para o problema capacitado de localização de facilidades com fonte única e sua variante robusta

Página do item simplificado
dc.contributor.advisorSouza, Marcone Jamilson Freitas
dc.contributor.advisor-coSouza, Sergio Ricardo de
dc.contributor.advisor-coSá, Elisangela Martins de
dc.contributor.advisor-coLatteshttp://lattes.cnpq.br/3677015295211434
dc.contributor.advisor-coLatteshttp://lattes.cnpq.br/4686246805500174
dc.contributor.advisorLatteshttp://lattes.cnpq.br/6078945717558464
dc.contributor.authorAlmeida, Guilherme Barbosa de
dc.contributor.authorLatteshttp://lattes.cnpq.br/3173964416432908
dc.contributor.refereeSouza, Marcone Jamilson Freitas
dc.contributor.refereeSouza, Sergio Ricardo de
dc.contributor.refereeSá, Elisangela Martins de
dc.contributor.refereeMorabito Neto, Reinaldo
dc.contributor.refereeBruck, Bruno Petrato
dc.contributor.refereeVargas, Dênis Emanuel da Costa
dc.contributor.refereeMenezes, Gustavo Campos
dc.date.accessioned2026-10-09T16:05:34Z
dc.date.available2026-10-09T16:05:34Z
dc.date.issued2026-06-29
dc.description.abstractEsta 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.
dc.description.abstractotherThis thesis addresses the Single-Source Capacitated Facility Location Problem (SSCFLP) and its robust variant (RSSCFLP). The SSCFLP involves determining locations for opening capacitated facilities to meet customer demands, ensuring that each customer is assigned to exactly one facility. The RSSCFLP extends the SSCFLP by considering uncertainty in allocation and opening costs, demands, and capacities. To formulate the RSSCFLP, the robust optimization approach proposed by Dimitris Bertsimas and Melvyn Sim is adopted. To solve these problems, three algorithms are proposed: HILS and NCS for the SSCFLP, and B&B-GVNS for the RSSCFLP. HILS combines the solution of subproblems with procedures based on Iterated Local Search to obtain high-quality solutions. NCS combines a cutting-plane method, a local-search-based heuristic, and a cut-and-solve procedure to find optimal solutions for the problem. B&B-GVNS combines a cutting-plane procedure, a heuristic based on General Variable Neighborhood Search, and a branch-and-bound algorithm enhanced with heuristics. Computational experiments indicate that HILS is competitive with state-of-the-art algorithms, producing solutions with slightly smaller gap values on more challenging instances. The results obtained with NCS showed that it found more optimal solutions or reduced the time required to obtain them in 85% of the analyzed subsets when compared with the state-of-the-art algorithm, and in 73% of the subsets when compared with CPLEX. Moreover, in several subsets, NCS was more than 100 times faster than CPLEX and more than 10 times faster than the state-of-the-art algorithm in obtaining an equal or greater number of optimal solutions. Finally, B&B-GVNS outperformed CPLEX on all tested sets, achieving reductions in gap greater than 20% and 25% on the two most challenging sets. These results demonstrate that the algorithms developed in this thesis constitute relevant methodological contributions to the solution of capacitated facility location problems and its robust variant.
dc.identifier.urihttps://repositorio.cefetmg.br//handle/123456789/3128
dc.language.isopt
dc.publisherCentro Federal de Educação Tecnológica de Minas Gerais
dc.publisher.countryBrasil
dc.publisher.initialsCEFET-MG
dc.publisher.programPrograma de Pós-Graduação em Modelagem Matemática e Computacional
dc.subjectTransporte – Modelos matemáticos – Teses
dc.subjectOtimização Robusta – Teses
dc.subjectResolução de problemas – Teses
dc.subjectMetaheurísticas – Teses
dc.subjectOtimização discreta – Teses
dc.subjectAnálise de algoritmos e complexidade de problemas – Teses
dc.titleAlgoritmos para o problema capacitado de localização de facilidades com fonte única e sua variante robusta
dc.typeTese

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Algoritmos para o problema capacitado de localização de facilidades com fonte única e sua variante robusta.pdf
Tamanho:
1.91 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.39 KB
Formato:
Item-specific license agreed to upon submission
Descrição:
Baixar

Coleções

Doutorado em Modelagem Matemática e Computacional