Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/75933
Type: | Dissertação |
Title: | Uma abordagem de decomposição de Benders com aproximação externa para a localização de instalações com regra de escolha limitada |
Authors: | Thalles Vinícius Frade Mota |
First Advisor: | Ricardo Saraiva de Camargo |
First Referee: | Fátima Machado de Souza Lima |
Second Referee: | Gilberto de Miranda Júnior |
Third Referee: | Ricardo Poley Martins Ferreira |
Abstract: | Neste trabalho, uma nova abordagem exata para problemas de localização de instalações competitivas com regra de escolha limitada é proposta. A abordagem envolve a criação de um método híbrido baseado na decomposição de Benders com aproximação externa, em que o problema mestre da aproximação externa é resolvido usando um algoritmo de decomposição de Benders. Dada a estrutura de decomposição do problema, é possível separar um corte de viabilidade de Benders para cada cliente por vez. No entanto, em vez de adicioná-los todos de uma vez ao problema mestre, esses cortes foram agrupados seguindo uma clusterização dos clientes em pequenos grupos. Para otimizar ainda mais o processo de solução, os cortes de viabilidade de Benders foram separados por inspeção. Instâncias de médio e grande porte foram usadas para avaliar o desempenho computacional da abordagem proposta em relação aos métodos existentes na literatura. Os resultados encontrados evidenciam a superioridade do método proposto em relação aos métodos existentes na literatura, quando avaliados em instâncias de médio e grande porte. |
Abstract: | In this study, a new exact approach for competitive facility location problems with limited choice rule is proposed. The approach involves the development of a hybrid method based on Benders decomposition with outer approximation, where the outer approximation master problem is solved using a Benders decomposition algorithm. Given the decomposition structure of the problem, it is possible to generate a Benders feasibility cut for each customer at a time. However, instead of adding them all at once to the master problem, these cuts were grouped following a clustering of customers into small groups. To further optimize the solution process, the Benders feasibility cuts were separated through inspection. Medium and large-scale instances were used to evaluate the computational performance of the proposed approach in comparison to existing methods in the literature. The results demonstrate the superiority of the proposed method over existing methods in the literature, particularly when evaluated on medium and large-scale instances. |
Subject: | Modelos matemáticos Algoritmos Programação (Computadores) Métodos numéricos |
language: | por |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ENG - DEPARTAMENTO DE ENGENHARIA PRODUÇÃO |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Engenharia de Produção |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/75933 |
Issue Date: | 27-Feb-2024 |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Dissertação_Thalles_Mota_Repositório_Final.pdf | 1.03 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.