Use este identificador para citar ou linkar para este item: http://www.repositorio.ufc.br/handle/riufc/17871
Título: Algoritmos para o problema de localização simples baseados nas formulações clássica e canônica
Título em inglês: Algorithms to the problem of location based on simple formulations classical and canonical
Autor(es): Dias, Fábio Carlos Sousa
Orientador(es): Campelo Neto , Manoel Bezerra
Palavras-chave: Ciência da computação
Problemas de localização de facilidades
Relaxação Lagrangeana
Redução do Tamanho do Problema
Facility Location Problems
Lagrangean Relaxation
Problem Reduction
Data do documento: 2008
Citação: DIAS, F. C. S. (2008)
Resumo: Neste trabalho, estudamos o problema de localização simples (SPLP - Simple Plant Location Problem). Usando a formulação matemática clássica e uma outra formulação proposta recentemente, desenvolvemos vários algoritmos para encontrar limites inferiores e superiores, bem como algoritmos tipo branch-and-bound. Com a formulação clássica, tais limites são obtidos utilizando o método de correção de dados e critérios de dominância entre os custos …xos e de transporte. Propomos uma projeção dessa formulação, que se mostrou computacionalmente atrativa. Usando a nova formulação propomos e mostramos a corretude de vários procedimentos iterativos que procuram encontrar uma solução para o problema, resolvendo uma seqüência de subproblemas paramétricos obtidos com a remoção de variáveis e restrições da formulação original. Em cada iteração desse processo, podemos gerar limites inferiores e superiores. Aplicamos ainda relaxação lagrangeana a essa nova formulação para obter outros limites. Analisamos várias possibilidades de relaxação das restrições. Desenvolmento também algoritmos branch-and-bound baseados em ambas as formulações e nos limites obtidos. Avaliamos a e…ciência computacional de todos os algoritmos com instâncias de teste difíceis, disponíveis na literatura. Resultados computacionais e comparações com outros algoritmos da literatura são reportados.
Abstract: In this work, we study the Simple Plant Location Problem (SPLP). Using its classical mathematical programming formulation and another recently proposed formulation, we develop several algorithms to …nd lower and upper bounds for the problem as well as branch-and-bound algorithms. With the classical formulation, such bounds are obtained via the data correction method and dominance criteria between …xed and transportation costs. We propose a projection of this formulation that has shown to be computationally atractive. Using the new formulation, we propose and prove the correctness of several iterative procedures that attempt to …nd an optimal solution to the problem by solving a sequence of parametric sub-problems, each one obtained by removing some variables and constraints of the original formulation. At each iteration of this process, we can obtain lower and upper bounds. We also apply Lagrangean relaxation to this new formulation in order to get other bounds. We consider several possibilities of relaxing the constraints. In addition, we develop branch-and-bound algorithms based on both formulations and the obtained bounds. We evaluate the computational e¢ ciency of all proposed algorithms with hard test instances from the literature. Computational results are reported and comparisons with other algorithms from the literature are carried out.
Descrição: DIAS, Fábio Carlos Sousa. Algoritmos para o problema de localização simples baseados nas formulações clássica e canônica. 2008. 81 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2008.
URI: http://www.repositorio.ufc.br/handle/riufc/17871
Aparece nas coleções:DCOMP - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2008_dis_fcsdias.pdf520,64 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.