UMA NOVA FORMULAÇÃO E UM CONJUNTO DE DESIGUALDADES VÁLIDAS PARA O PROBLEMA DA COBERTURA MÁXIMA p-HUB COM ALOCAÇÃO SIMPLES E COBERTURA PARCIAL

O problema da cobertura máxima p-hub com alocação simples e cobertura parcial considera uma rede hub-and-spoke com locais onde hubs podem ser instalados e diversos fluxos a serem transportados. O problema decide onde localizar p hubs e como alocar cada ponto a um único hub localizado, gerando um grau de cobertura para cada fluxo, em função do seu custo de atendimento. O problema visa maximizar a soma ponderada dos fluxos pelo seu grau de cobertura. Propomos neste trabalho uma nova formulação e um conjunto de desigualdades válidas para o problema. Propomos ainda que tais desigualdades sejam incluídas sob demanda durante o algoritmo de branch-and-bound. Nós apresentamos diversos experimentos que mostram que a formulação proposta supera a melhor formulação conhecida para todas as instâncias testadas, mesmo para o caso em que as desigualdades não são incluídas. Além disso, apresentamos a solução ótima de diversas instâncias em aberto.