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

Citation:

Matheus Araújo de Butinholi, Alexandre Xavier Martins, Paganini Barcellos de Oliveira, and Diego Perdigão Martino. 2019. “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.” In LI SBPO - Simpósio Brasileiro de Pesquisa Operacional, 2: Pp. 107798. Limeira, SP. Publisher's Version

Abstract:

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.