Algoritmos para as versões determinística e robusta do problema de localização de concentradores com maximização do lucro
| dc.contributor.advisor | Sá, Elisângela Martins de | |
| dc.contributor.advisor-co | Souza, Sérgio Ricardo de | |
| dc.contributor.advisor-coLattes | http://lattes.cnpq.br/3677015295211434 | |
| dc.contributor.advisorLattes | http://lattes.cnpq.br/4686246805500174 | |
| dc.contributor.author | Oliveira, Fabricio Alves | |
| dc.contributor.authorLattes | http://lattes.cnpq.br/4686246805500174 | |
| dc.contributor.referee | Elisângela Martins de Sá | |
| dc.contributor.referee | Sérgio Ricardo de Souza | |
| dc.contributor.referee | Mateus, Geraldo Robson | |
| dc.contributor.referee | Morabito Neto, Reinaldo | |
| dc.contributor.referee | Souza, Marcone Jamilson Freitas | |
| dc.contributor.referee | Menezes, Gustavo Campos | |
| dc.date.accessioned | 2025-03-19T17:24:33Z | |
| dc.date.available | 2025-03-19T17:24:33Z | |
| dc.date.issued | 2024-02-27 | |
| dc.description.abstract | Esta tese estuda o problema de localização de concentradores, com objetivo direcionado para a maximização do lucro. Esse problema consiste em estabelecer a localização de concentradores, o projeto da rede e a alocação dos nós de demanda aos concentradores para maximizar o lucro total da rede. O problema considera que a rede de concentradores é incompleta, nenhuma estrutura topológica específica é requerida e é assumido que os concentradores e arcos entre concentradores possuem capacidade suficiente para lidar com o fluxo de demanda na rede. Este trabalho apresentou novas formulações e investigou suas propriedades. As formulações propostas assumem a estratégia de alocação múltipla; não impõem quaisquer restrições ao número de concentradores ou arcos entre concentradores instalados na rede; não permitem conexões diretas entre nós não concentradores e permitem que a demanda da rede seja parcialmente satisfeita, sendo atendida apenas quando for rentável. Essa última característica e o foco na maximização do lucro diferenciam o problema abordado nesta tese em relação aos problemas clássicos de localização de concentradores, nos quais a demanda completa entre todos os pares de origem e destino é atendida, e, além disso, os problemas são modelados sob o ponto de vista dos custos. Esta tese também investigou as propriedades e realizou uma análise comparativa das formulações propostas com outra da literatura. Para resolver o problema, foram desenvolvidos algoritmos baseados no método de decomposição de Benders, incluindo várias estratégias de aprimoramento. Uma vez que o problema aqui abordado é NP-difícil, também foram propostos dois algoritmos heurísticos baseados em busca local e troca sistemática de estruturas de vizinhança para solucionar instâncias do problema de grande porte. Para analisar a eficiência dos procedimentos de solução propostos, foram realizados extensivos experimentos computacionais com instâncias de referência na área de localização de concentradores. Os resultados desses testes mostraram que os algoritmos propostos possuem um bom desempenho. Em particular, com o método de decomposição de Benders, foram resolvidas até a otimalidade instâncias com até 150 nós. Por outro lado, com os algoritmos heurísticos, foram solucionadas instâncias contendo até 500 nós. Adicionalmente, foi realizada uma análise das estruturas de vizinhança consideradas nos algoritmos heurísticos e uma comparação estatística entre os dois algoritmos. Nesta tese também foi abordado o problema de localização de concentradores com maximização do lucro em que as demandas e os custos de instalação de concentradores e arcos entre concentradores são incertos. Uma formulação robusta, que permite controlar o grau de conservadorismo do modelo por meio de um budget de incerteza, é desenvolvida para este caso. São apresentadas discussões sobre a influência que a incerteza nos dados tem sobre a configuração da rede e sobre o lucro associado a ela. Para resolver o problema robusto, foram propostos um algoritmo exato baseado em decomposição de Benders e outro heurístico baseado na meta-heurística Iterated Local Search, adaptados dos melhores métodos identificados na resolução do problema determinístico. As soluções obtidas com o problema robusto possuem diferenças significativas em relação às soluções do problema determinístico, o que evidencia a importância de se estudar este tipo de problema, principalmente em aplicações reais. A incerteza nos dados pode levar a necessidade de um redesenho da rede de concentradores, o que influencia diretamente o lucro associado a ela. | |
| dc.description.abstractother | This thesis studies the hub location problem to maximize profit. This problem consists of establishing the location of hubs, the network design, and the allocation of demand nodes to hubs to maximize the total network profit. The problem considers that the hub network is incomplete, no specific topological structure is required and it is assumed that the hubs and hub arcs have sufficient capacity to handle the demand flow in the network. This work presented new formulations and investigated their properties. The proposed formulations assume the multiple allocation strategy; they do not impose any restrictions on the number of hubs or hub arcs installed in the network, do not allow direct connections between non-hub nodes, and allow network demand to be partially satisfied, only being met when it is profitable. This last characteristic and the focus on profit maximization differentiate the problem addressed in this thesis in relation to classical hub location problems, in which the complete demand between all origin and destination pairs is met, and the problems are modeled under the point from a cost perspective. This thesis also investigated the properties and carried out a comparative analysis of the proposed formulations with others in the literature. To solve the problem, the Benders decomposition algorithms were developed, including several enhancement strategies. Since the problem addressed here is NP-hard, two heuristic algorithms based on local search and systematic exchange of neighborhood structures were also proposed to solve large-scale problem instances. Extensive computational experiments were carried out with benchmark instances in the hub location area to analyze the efficiency of the proposed solution procedures. The results of these tests showed that the proposed algorithms have good performance. In particular, with the Benders decomposition algorithm, instances with up to 150 nodes were resolved to optimality. On the other hand, with heuristic algorithms, instances containing up to 500 nodes were solved. Additionally, the neighborhood structures considered in the heuristic algorithms and a statistical comparison between the two algorithms were analyzed. This thesis also addressed the hub location problem with profit maximization, in which the demands and costs of installing hubs and hub arcs are uncertain. A robust formulation, which allows controlling the model’s degree of conservatism through an uncertainty budget, is developed for this case. Discussions are presented about the influence that data uncertainty has on the network configuration and the profit associated with it. To solve the robust problem, an exact Benders decomposition algorithm and an Iterated Local Search-based algorithm were proposed, adapted from the best methods identified in solving the deterministic problem. The solutions obtained with the robust problem have significant differences concerning the solutions of the deterministic problem, which highlights the importance of studying this type of problem, especially in real applications. Uncertainty in the data may lead to redesigning the hub network, which directly influences its profit. | |
| dc.identifier.uri | https://repositorio.cefetmg.br//handle/123456789/858 | |
| dc.language.iso | pt | |
| dc.publisher | Centro Federal de Educação Tecnológica de Minas Gerais | |
| dc.publisher.country | Brasil | |
| dc.publisher.initials | CEFET-MG | |
| dc.publisher.program | o Programa de Pós-Graduação em Modelagem Matemática e Computacional | |
| dc.subject | Algoritmos | |
| dc.subject | Métodos de decomposição | |
| dc.subject | Métodos numéricos de otimização | |
| dc.title | Algoritmos para as versões determinística e robusta do problema de localização de concentradores com maximização do lucro | |
| dc.type | Thesis |
Arquivos
Pacote Original
1 - 1 de 1
Carregando...
- Nome:
- Algoritmos para as versões determinística.pdf
- Tamanho:
- 4.99 MB
- Formato:
- Adobe Portable Document Format
Licença do Pacote
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: