Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/17871
Title in Portuguese: Algoritmos para o problema de localização simples baseados nas formulações clássica e canônica
Title: Algorithms to the problem of location based on simple formulations classical and canonical
Author: Dias, Fábio Carlos Sousa
Advisor(s): Campêlo Neto, Manoel Bezerra
Keywords: 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
Issue Date: 2008
Citation: 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 em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2008.
Abstract in Portuguese: 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.
URI: http://www.repositorio.ufc.br/handle/riufc/17871
metadata.dc.type: Dissertação
Appears in Collections:DCOMP - Dissertações defendidas na UFC

Files in This Item:
File Description SizeFormat 
2008_dis_fcsdias.pdf520,64 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.