Algoritmo de descida em vizinhança variável aplicado ao problema de cobertura máxima de p-eixos não capacitados com alocação simples

Vol 51, 2019 - 107798
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

O presente artigo aborda o problema de cobertura máxima de p-eixos não capacitados com alocação simples (Uncapacitated Single Allocation p-hub Maximal Covering Problem - USApHMCP), que objetiva maximizar a cobertura de um conjunto de nós de uma rede através de p-eixos. Uma heurística baseada na estratégia de busca em descida com vizinhança variável (Variable Neighborhood Descent - VND) foi desenvolvida para o problema. Dois diferentes conjuntos de instâncias, Civil Aeronautics Board (CAB) e Australian Post (AP), são utilizados para avaliar e comparar o desempenho do VND à metaheurística Busca Tabu (Tabu Search - TS) encontrada na literatura. Como resultado, o VND apresentou limites superiores melhores para instâncias de grande porte (AP), bem como um desempenho médio ligeiramente superior em tempo computacional de resolução para as instâncias CAB, de menor porte.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Federal de Ouro Preto
Eixo Temático
  • MH – Metaheuristicas
Palavras-chave
Problema de cobertura máxima
P-eixos não capacitados com alocação simples
Descida em vizinhança variável