Algoritmo GVNS aplicado ao problema das p-medianas capacitado abordagens determinística e robusta

Página do item simplificado
dc.contributor.advisorSouza, Marcone Jamilson Freitas
dc.contributor.advisor-coSouza, Sérgio Ricardo de
dc.contributor.advisor-coSá, Elisângela Martins de
dc.contributor.advisor-coLatteshttp://lattes.cnpq.br/4686246805500174
dc.contributor.advisorLatteshttp://lattes.cnpq.br/6078945717558464
dc.contributor.authorVasconcelos, Anderson Moreira
dc.contributor.authorLatteshttp://lattes.cnpq.br/6195947972246267
dc.contributor.refereeSouza, Marcone Jamilson Freitas
dc.contributor.refereeSouza, Sérgio Ricardo de
dc.contributor.refereeSá, Elisângela Martins de
dc.contributor.refereeSilva, Maria Amélia Lopes
dc.contributor.refereeHaddad, Matheus Nohra
dc.contributor.refereeWanner, Elizabeth Fialho
dc.contributor.refereeMenezes, Gustavo Campos
dc.date.accessioned2025-04-08T22:56:09Z
dc.date.available2025-04-08T22:56:09Z
dc.date.issued2022-12-20
dc.description.abstractO Problema das p-Medianas Capacitado (PPMC) consiste em localizar p instalações em uma rede composta por n vértices e decidir qual mediana atenderá cada vértice, a fim de minimizar a soma das distâncias dos vértices à mediana a qual ele foi alocado e atender às restrições de capacidade de cada mediana. Considerando que as demandas dos clientes são incertas, é proposta a aplicação de uma abordagem de otimização robusta para lidar com a incerteza nestes parâmetros dando origem ao problema das p-Medianas Robusto Capacitado (PPMRC). Esta tese propõe algoritmos para resolução do PPMC e o PPMRC. Para resolver o PPMC, foram propostas quatro variantes da metaheurística General Variable Neighborhood Search (GVNS), que se diferem no método usado para construir uma solução inicial e nos métodos usados para realizar a busca local. Nas duas primeiras variantes, denominadas G-VND e G-RVND, a solução inicial é gerada de forma aleatória e os métodos de busca local são o Variable Neighborhood Descent (VND) e o Random Variable Neighborhood Descent (RVND), respectivamente. Nas duas últimas variantes, denominadas GG-VND e GG-RVND, a solução inicial é gerada através da fase de construção da metaheurística Greedy Randomized Adaptive Search Procedure (GRASP) e os métodos de busca local são o VND e o RVND, respectivamente. Os resultados de experimentos computacionais usando instâncias da literatura mostraram que o algoritmo GG-RVND apresentou melhor desempenho que os outros três algoritmos. Além disso, os resultados obtidos pelo algoritmo GG-RVND foram melhores do que aqueles da literatura, tanto em termos da qualidade das soluções geradas quanto em relação ao tempo de execução. Para o PPMRC, foi proposto um algoritmo baseado na metaheurística GVNS, com a solução inicial gerada através da fase construtiva do método GRASP e uma busca local realizada via VND. Os experimentos computacionais comparam os resultados do GVNS e as soluções do solver CPLEX. Para realizar esses experimentos computacionais, foram utilizadas instâncias da literatura, variando de 318 nós e cinco medianas a 4461 nós e 1000 medianas. Este estudo considera diversos cenários, valores variados dos parâmetros de robustez e de incerteza na demanda. Os resultados mostram que o Algoritmo GVNS tem um bom desempenho em encontrar boas soluções e supera o solver CPLEX, encontrando soluções melhores mesmo quando aplicado para resolver o conjunto de dados de menor dimensão.
dc.description.abstractotherThis thesis proposes algorithms for solving PPMC and PPMRC. To solve PPMC, four variants of the General Variable Neighborhood Search (GVNS) metaheuristic were proposed, which differ in the method used to construct an initial solution and the method used to perform the local search. In the first two variants, i.e., G-VND and G-RVND, the initial solution is generated randomly, and the local search methods are the Variable Neighborhood Descent (VND) and the Random Variable Neighborhood Descent (RVND), respectively. In the last two variants, GGVND and GG-RVND, the initial solution is generated through the constructive phase of the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic, and the local search methods are the VND and RVND procedures, respectively. The results of computational experiments using instances from the literature showed that the GG-RVND algorithm performed better than the other three algorithms. Furthermore, the results obtained by the GG-RVND algorithm were better than those in the literature regarding the quality of the solutions generated and the execution time. For PPMRC, an algorithm based on the GVNS metaheuristic is proposed, with the initial solution generated through the constructive phase of the GRASP method and a local search performed via VND. The computational experiments compare GVNS results and the solver CPLEX solutions. To perform these computational experiments, this work used instances from the literature, ranging from 318 nodes and five medians to 4461 nodes and 1000 medians. This study considers several scenarios, varying values of parameters of robustness, and uncertainty in demand. The results show that the GVNS Algorithm performs well in finding good-quality solutions and outperforms the CPLEX solver, finding better solutions even when applied to solve the smallest dataset.
dc.identifier.urihttps://repositorio.cefetmg.br//handle/123456789/1152
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.subjectProgramação heurística
dc.subjectAlgoritmos
dc.subjectOtimização matemática
dc.subjectProgramação matemática
dc.titleAlgoritmo GVNS aplicado ao problema das p-medianas capacitado abordagens determinística e robusta
dc.typeTese

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Algoritmo GVNS aplicado ao problema das p-medianas capacitado abordagens.pdf
Tamanho:
1.53 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