Problemas de cobertura máxima e de cobertura de hub sob condição de incerteza com alocação única e custo fixo
Data
2026-03-26
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Centro Federal de Educação Tecnológica de Minas Gerais
Resumo
Esta tese tem como objetivo estudar e propor algoritmos para problemas de localização de hubs, com foco nos problemas de cobertura, não capacitados, com alocação única e custos fixos, considerando uma rede completa e não permitindo conexões diretas entre nós não hubs. Inicialmente, o estudo propõe o problema denominado Uncapacitated Single Allocation Hub Maximal Covering Problem (USAHMCP), no qual se busca selecionar os hubs a serem abertos e determinar a alocação de cada nó não hub a um único hub, respeitando um orçamento para abertura e sem pré-fixar o número de hubs. O fato de considerar custos fixos de instalação e restrições orçamentárias distingue este trabalho de outros existentes na literatura. Além disso, demonstrou-se que o USApHMCP padrão (versão em que a quantidade de hubs é previamente fixada) é um caso particular do problema introduzido e que, portanto, este novo problema é NP-difícil. Para tratar o problema proposto, foram desenvolvidas duas heurísticas baseadas na meta-heurística Iterated Local Search com Variable Neighborhood Descent (ILS-VND), que se diferenciam quanto ao critério de alocação gulosa. A estratégia de alocação baseada em potencial de cobertura, proposta neste trabalho, apresentou melhor desempenho em comparação à estratégia de alocação baseada em distância, frequentemente utilizada na literatura. Os testes computacionais consideraram instâncias de até 1000 nós, utilizando quatro conjuntos clássicos: Australian Post (AP) com até 200 nós, Civil Aeronautics Board (CAB) com até 25 nós, Contreras com até 500 nós e URAND com 1000 nós. As heurísticas propostas foram capazes de atualizar as melhores soluções conhecidas para as instâncias de 1000 nós. Os resultados mostraram que, quando o custo de abertura dos hubs é maior em nós com maiores demandas, o problema tende a abrir mais hubs que o modelo tradicional. Por outro lado, quando essa diferenciação não ocorre, o número de hubs abertos tende a ser o mesmo, ainda que o conjunto de hubs selecionados possa variar. Em continuidade a esse estudo, uma extensão do clássico problema Uncapacitated Single Allocation Hub Covering Problem (USAHCP) foi proposta. A extensão foi denominada Uncapacitated Single Allocation Hub Covering Problem with Minimum Coverage (USAHCPMC) e se diferencia por permitir que nem toda a demanda da rede seja necessariamente totalmente coberta. O problema USAHCPMC visa selecionar os hubs a serem abertos e determinar a alocação de cada nó não-hub a um único hub, minimizando o custo com instalação de hub para cobrir pelo menos uma parte previamente fixada do fluxo total da rede. Dessa forma, o USAHCPMC é NP-difícil, já que é mais geral do que o problema USAHCP (que exige a cobertura de toda a demanda e já foi provado ser da classe NP-difícil). Além disso, este trabalho considera cobertura binária e parcial e analisa os impactos de se tratar incerteza no fluxo de demanda do nó de origem até o nó de destino por meio de uma abordagem robusta. O problema robusto se baseia na modelagem do conjunto de incertezas utilizando restrições de cardinalidade. Um algoritmo ILS-VND foi proposto para resolver instâncias do problema nominal e do problema robusto. Experimentos computacionais, utilizando dois conjuntos de instâncias da literatura, mostraram que o problema proposto neste trabalho pode gerar soluções interessantes para os investidores, devido ao potencial de economias significativas nos custos de abertura de hubs ao não cobrir uma pequena parcela do fluxo total da rede. Além disso, experimentos computacionais considerando condições de incerteza mostraram que os custos de instalação de hubs aumentam (ou pelo menos permanecem os mesmos) à medida que o nível de robustez aumenta. Nós que não são instalados como hubs em cenários de baixa incerteza podem estar na configuração de hubs em cenários de maior incerteza. Finalmente, este trabalho mostrou que o modelo com cobertura parcial tende a exigir custos de abertura de hubs menores em comparação com o modelo com cobertura binária. Ademais, a heurística implementada conseguiu encontrar boas soluções em tempos computacionais menores do que o solver CPLEX.
Descrição
Palavras-chave
Otimização matemática, Redes de computadores, Incerteza (Economia), Meta-heuristica, Computação - Matemática