Algoritmo GVNS Híbrido Aplicado ao Problema das p-Medianas Capacitado
RESUMO O Problema das p-Medianas Capacitado (PPMC) consiste em localizar p facilidades em uma rede composta por n vértices e decidir qual facilidade atenderá cada vértice, a fim de minimizar a soma de todas as distâncias de cada facilidade para cada vértice e atender às restrições de capacidade máxima de cada facilidade. Neste trabalho, dado que o PPMC é da classe NP-difícil, quatro variantes da metaheurística General Variable Neighborhood Search (GVNS) são implementadas para resolver o PPMC: G-VND, G-RVND, GG-VND e GG-RVND. Elas diferem entre si com relação ao método usado para construir uma solução inicial e o usado para a busca local. Nas duas primeiras variantes, a solução inicial é gerada de forma aleatória e o método de busca local é feita via Variable Neighborhood Descent (VND) ou Random Variable Neighborhood Descent (RVND), respectivamente. Por sua vez, nas duas últimas, a solução inicial é feita via a fase de construção do método Greedy Randomized Adaptive Search Procedure (GRASP). Usando instâncias padrões de teste da literatura, mostramos, inicialmente, que a variante GG-VND teve melhor desempenho quando comparada com as demais. Em seguida, mostramos que, quando comparada com os algoritmos da literatura, esta variante possui desempenho equivalente ou superior.
| Main Authors: | , , |
|---|---|
| Format: | Digital revista |
| Language: | Portuguese |
| Published: |
Sociedade Brasileira de Matemática Aplicada e Computacional - SBMAC
2021
|
| Online Access: | http://old.scielo.br/scielo.php?script=sci_arttext&pid=S2676-00292021000300453 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|