ALGORITMOS PARA IDENTIFICAR ESTRUTURAS CRÍTICAS EM UMA REDE DE TRANSPORTE HUB-AND-SPOKE

Resumo

Hubs são facilidades especiais que servem como transbordo e pontos de troca em sistemas de transporte de algum tipo de fluxo, geralmente produtos ou dados. Fluxos diferentes podem ser agregados e transportados através dos hubs antes de chegar aos seus destinos, diminuindo o custo total de transporte em decorrência do desconto no custo unitário de transporte entre hubs. O funcionamento de um hub está sujeito à interdição total ou parcial, desativando suas capacidades funcionais normais. Um hub interditado não pode ser utilizado e, por isso, todos os fluxos que utilizem esse hub devem ser realocados para outro hub, ocasionando um aumento de custo indesejado. Neste contexto, o presente trabalho lida com o problema da mediana com interdição em hubs (PMIH), que consiste em identificar em uma rede de transporte o subconjunto de hubs que, uma vez interditados, provocam o maior aumento no custo total de transporte. A primeira contribuição para o problema dada neste trabalho é a proposição de um estudo que mostra que o modelo exato existente na literatura demanda um tempo computacional várias ordens de magnitude maior do que um algoritmo puramente enumerativo para todos os tamanhos de instância testados. Assim, é proposta aqui também uma heurística gulosa para o problema, onde é mostrado que esta encontra a solução ótima para grande parte as instâncias testadas.