Algoritmo GVNS aplicado ao problema das p-medianas capacitado abordagens determinística e robusta
Carregando...
Data
2022-12-20
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Centro Federal de Educação Tecnológica de Minas Gerais
Resumo
O 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.
Descrição
Palavras-chave
Programação heurística, Algoritmos, Otimização matemática, Programação matemática