Heurísticas para o problema de p-concentradores não capacitados de máxima cobertura com alocação simples.

Abstract

O presente trabalho apresenta um estudo sobre 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 tem como objetivo maximizar a cobertura de um conjunto de nós de uma rede através de p-eixos. Foram desenvolvidas quatro estratégias como alternativas para solucionar o problema, um modelo de programação matemática para resolução exata do problema, duas heurísticas construtivas conectadas à procedimentos de refinamento via buscas locais, a busca em vizinhança variável (VNS) e a descida em vizinhança variável (VND), e uma meteheuristica, o Simulated Annealing (SA). Para analisar a eficiência dos algoritmos desenvolvidos, foram utilizadas duas instâncias da literatura, Civil Aeronautics Board (CAB) e Australian Post (AP). Além disso, também foi proposto um conjunto de instâncias que possui um número maior de nós quando comparadas às outras duas da literatura. Quanto ao resultado, o método exato e o VND demonstraram ser boas opções para instâncias de pequeno e médio porte, obtendo resultados formidáveis em um curto tempo de processamento, embora tenham apresentado certa deficiência em encontrar bons resultados para instâncias de maior porte. Por outro lado, o VNS e o SA foram alternativas que tiveram um bom desempenho para as instâncias de pequeno e grande porte.