Problemas de cobertura máxima e de cobertura de hub sob condição de incerteza com alocação única e custo fixo

Página do item simplificado
dc.contributor.advisorSá, Elisangela Martins de
dc.contributor.advisor-coSouza, Sérgio Ricardo de
dc.contributor.advisor-coLatteshttp://lattes.cnpq.br/3677015295211434
dc.contributor.advisorLatteshttp://lattes.cnpq.br/4686246805500174
dc.contributor.authorSilva, Fernando Félix Oliveira
dc.contributor.authorLatteshttp://lattes.cnpq.br/9796054093839255
dc.contributor.refereeSá, Elisangela Martins de
dc.contributor.refereeSouza, Sérgio Ricardo de
dc.contributor.refereeOliveira, Fabrício Alves
dc.contributor.refereeFreitas, Nayane Carvalho
dc.contributor.refereeSouza, Marcone Jamilson Freitas
dc.contributor.refereeMenezes, Gustavo Campos
dc.date.accessioned2026-10-07T19:00:54Z
dc.date.available2026-10-07T19:00:54Z
dc.date.issued2026-03-26
dc.description.abstractEsta 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.
dc.description.abstractotherThis thesis aims to study and propose algorithms for hub location problems, with a focus on uncapacitated covering problems with single allocation and fixed costs, considering a complete network and not allowing direct connections between non hub nodes. Initially, the study proposes the problem called Uncapacitated Single Allocation Hub Maximal Covering Problem (USAHMCP), in which the goal is to select the hubs to be opened and determine the allocation of each non-hub node to a single hub, respecting a budget for opening and without predefining the num ber of hubs. The fact of considering fixed installation costs and budget constraints distinguishes this work from others in the literature. Furthermore, it was demons trated that the standard USApHMCP (the version in which the number of hubs is previously fixed) is a particular case of the introduced problem and that, therefore, this new problem is NP-hard. To address the proposed problem, two heuristics ba sed on the Iterated Local Search metaheuristic with Variable Neighborhood Descent (ILS-VND) were developed, which differ in the greedy allocation criterion. The al location strategy based on coverage potential, proposed in this work, showed better performance compared to the distance-based allocation strategy frequently used in the literature. The computational tests considered instances of up to 1000 nodes, using four classical sets: Australian Post (AP) with up to 200 nodes, Civil Aeronau tics Board (CAB) with up to 25 nodes, Contreras with up to 500 nodes, and URAND with 1000 nodes. The proposed heuristics were capable of updating the best-known solutions for the 1000-node instances. The results showed that, when the opening cost of the hubs is higher in nodes with higher demands, the problem tends to open more hubs than the traditional model. On the other hand, when this differentia tion does not occur, the number of opened hubs tends to be the same, although the set of selected hubs may vary. Continuing this study, an extension of the classical Uncapacitated Single Allocation Hub Covering Problem (USAHCP) was proposed. The extension was named Uncapacitated Single Allocation Hub Covering Problem with Minimum Coverage (USAHCPMC) and differs by allowing that not all network demand must necessarily be fully covered. The USAHCPMC problem aims to select the hubs to be opened and to determine the allocation of each non-hub node to a single hub, minimizing the installation cost of hub to cover at least a previously fixed portion of the total network flow. Thus, the USAHCPMC is NP-hard, since it is more general than the USAHCP problem (which requires covering all demand and has already been proven to be NP-hard). In addition, this work considers binary and partial coverage and analyzes the impacts of dealing with uncertainty in the flow from the origin node to the destination node through a robust approach. The robust problem is based on modeling the uncertainty set using cardinality constraints. An ILS-VND algorithm was proposed to solve instances of the nominal problem and the robust problem. Computational experiments, using two sets of instances from the literature, showed that the problem proposed in this work can generate interesting solutions for investors, due to the potential for significant savings in hub opening costs by not covering a small portion of the total network flow. Furthermore, computatio nal experiments considering uncertainty conditions showed that the installation costs of hubs increase (or at least remain the same) as the level of robustness increases, and nodes that are not installed as hubs in low-uncertainty scenarios may belong to the hub configuration in higher-uncertainty scenarios. Finally, this work showed that the partial coverage model tends to require lower hub opening costs compared to the binary coverage model. Moreover, the implemented heuristic was able to find good solutions in computational times shorter than the CPLEX solver.
dc.description.sponsorshipFundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG) e Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq).
dc.identifier.urihttps://repositorio.cefetmg.br//handle/123456789/3116
dc.language.isopt
dc.publisherCentro Federal de Educação Tecnológica de Minas Gerais
dc.publisher.countryBrasil
dc.publisher.initialsCEFET-MG
dc.publisher.programPrograma de Pós-Graduação em Modelagem Matemática e Computacional
dc.subjectOtimização matemática
dc.subjectRedes de computadores
dc.subjectIncerteza (Economia)
dc.subjectMeta-heuristica
dc.subjectComputação - Matemática
dc.titleProblemas de cobertura máxima e de cobertura de hub sob condição de incerteza com alocação única e custo fixo
dc.typeTese

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Problemas de cobertura máxima e de cobertura de hub sob condição de incerteza com alocação única e custo fixo.pdf
Tamanho:
3.44 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.39 KB
Formato:
Item-specific license agreed to upon submission
Descrição:
Baixar

Coleções

Doutorado em Modelagem Matemática e Computacional