Heurística baseada em modelo para problemas de localização de concentradores capacitados

• Ano de defesa: 2014
• Autor(a) principal: Wesley Gomes de Almeida
• Orientador(a): Edson Luiz França Senne, Horacio Hideki Yanasse
• Banca de defesa: Stephan Stephany, Antônio Augusto Chaves, André Gustavo dos Santos
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Instituto Nacional de Pesquisas Espaciais (INPE)
• Programa de Pós-Graduação: Programa de Pós-Graduação do INPE em Computação Aplicada
• País: BR
• Resumo em Inglês: This work aims to propose a solution strategy for hub location problems with capacity constraints. A technique called Local Branching (LB) was applied to the development of this solution strategy. This technique is based on a Mathematical Programming model and consists of an improvement heuristic that uses the branch-and-cut strategy, but incorporates ideas present in local search techniques and metaheuristics. In the LB technique, the search for solutions begins with a reference solution which can be obtained by a metaheuristic. The method alternates between strategic ramifications for defining neighborhoods solution branches and tactical ramifications for exploring these neighborhoods. In order to generate the reference solutions, four metaheuristics were developed. The results obtained by these metaheuristics were compared and the best performance metaheuristic was used as a generator of the initial reference solution for the LB method. Comparative studies with the proposed LB strategy and the solver CPLEX with and without the use of initial solution applied to hub location problems with single and multiple allocation are presented.
• Link de acesso: http://urlib.net/sid.inpe.br/mtc-m21b/2014/07.19.19.02

Este trabalho tem como objetivo propor uma estratégia de solução para problemas de localização de concentradores com restrições de capacidade. A técnica denominada \emph{Local Branching} (LB) foi aplicada para o desenvolvimento desta estratégia de solução. Tal técnica baseia-se em um modelo de Programação Matemática e consiste de uma heurística de melhoramento que utiliza a estratégia \emph{branch-and-cut}, mas incorpora ideias presentes em técnicas de busca local e metaheurísticas. Na técnica LB, a busca por soluções inicia-se com uma solução de referência, que pode ser obtida por uma metaheuristica. O método alterna-se entre ramificações estratégicas para definir vizinhanças de solução e ramificações táticas para explorar estas vizinhanças. Para obter as soluções de referência, foram desenvolvidas quatro metaheurísticas. Os resultados obtidos por estas metaheurísticas foram comparados e a de melhor desempenho foi utilizada como geradora da solução inicial de referência para o método LB. Neste trabalho apresentam-se estudos comparativos de resultados obtidos com a estratégia LB proposta e resultados obtidos pelo solver CPLEX com e sem a utilização de solução inicial, aplicados a problemas de localização de concentradores capacitados com alocação simples e múltipla.