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

Abstract

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.

Keywords

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