Algoritmo GVNS Híbrido Aplicado ao Problema das p-Medianas Capacitado

Autores

  • Marcone Jamilson Freitas Souza Universidade Federal de Ouro Preto (UFOP)
  • Anderson Moreira Vasconcelos Centro Federal de Educação Tecnológica de Minas Gerais
  • SERGIO RICARDO DE SOUZA Centro Federal de Educação Tecnológica de Minas Gerais https://orcid.org/0000-0001-7831-6740

DOI:

https://doi.org/10.5540/tcam.2021.022.03.00453

Palavras-chave:

Problema das p-Medianas Capacitado, General Variable Neighbourhood Search, GRASP, metaheurísticas

Resumo

O Problema das p-Medianas Capacitado (PMPC) consiste em localizar p depósitos em uma rede composta por n clientes e decidir qual depósito atenderá cada cliente, a fim de minimizar a soma de todas as distâncias de cada depósito para cada cliente, sujeito à restrições de capacidade do cluster. Neste trabalho, quatro variações da metaheurística General Variable Neighbourhood Search (GVNS) são implementadas para resolver o PMPC: GVNS com busca local Random Variable Neighbourhood Descent (G-RVND), GVNS com busca local Variable Neighborhood Descent (G-VND), GVNS com a solução inicial gerada durante a fase de construção do método Greedy Randomized Adaptive Search Procedure (GRASP) e busca local RVND (GG-RVND) e GVNS com a solução inicial gerada durante a fase de construção do método GRASP e busca local VND (GG-VND). Os resultados foram comparados com os melhores resultados da literatura e mostram que a variação GG-VND é, em parte, superior aos melhores resultados da literatura.

Downloads

Publicado

2021-09-02

Como Citar

Freitas Souza, M. J., Vasconcelos, A. M., & DE SOUZA, S. R. (2021). Algoritmo GVNS Híbrido Aplicado ao Problema das p-Medianas Capacitado. Trends in Computational and Applied Mathematics, 22(3), 453–473. https://doi.org/10.5540/tcam.2021.022.03.00453

Edição

Seção

Artigo Original