Algoritmo de busca tabu

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1579 palavras )
  • Download(s) : 0
  • Publicado : 13 de março de 2013
Ler documento completo
Amostra do texto
ALGORITMO HEURÍSTICO PARA PROBLEMAS NÃO-CAPACITADOS DE
LOCALIZAÇÃO DE FACILIDADES
Edson Luiz França Senne
Paula Rocha Andrade
UNESP - Universidade Estadual Paulista
Campus de Guaratinguetá - Faculdade de Engenharia
RESUMO
O problema não-capacitado de localização de facilidades consiste em determinar em uma
rede, ao menor custo possível, a melhor localização para a abertura de um conjuntode
instalações (também conhecidas como facilidades) de modo a atender às demandas dos
clientes. Admite-se que existem custos associados à abertura de facilidades e ao atendimento
de cada cliente pelas facilidades abertas. Como o problema é não-capacitado, não existe
limitação quanto à capacidade de uma facilidade em atender às demandas dos seus clientes.
Neste trabalho apresenta-se umalgoritmo heurístico baseado na metaheurística de busca tabu
para a solução do problema. Os resultados computacionais mostram que o algoritmo proposto
é capaz de encontrar boas soluções para os problemas testados, mantendo o compromisso
entre a qualidade da solução e o tempo computacional.
Palavras-chave: Metaheurísticas, Localização de facilidades, Busca tabu.
ABSTRACT
The uncapacitated facilitylocation problem consists in determining in a network, at the
minimum possible cost, the better localization for the opening of a set of installations (also
known as facilities) in order to attend the customers’ demands. One admits that there exist
costs associated to the opening of facilities and to the attendance of each customer by the
open facilities. In the particular case of theuncapacitated location problem does not exist a
capacity limitation to attend the customers’ demands. In this work, a heuristic algorithm,
which is based on tabu search metaheuristic, for solving the uncapacitated facility location
problems is presented. The results show that the proposed algorithm is able to find good
solutions for the tested problems, keeping the compromise between solutions qualityand
computational time.
Keywords: Metaheuristics, Facility location, Tabu search.
1. Introdução
O problema de localização de facilidades é um problema clássico de Otimização
Combinatória que consiste em estabelecer os locais onde devem ser abertas instalações
(conhecidas como facilidades) para atender, ao menor custo possível, um conjunto
espacialmente distribuído de pontos de demanda(conhecidos como clientes) (DREZNER,
1995). Exemplos de aplicações deste problema ocorrem na localização de escolas, postos de
saúde, corpo de bombeiros, centro de ambulâncias, viaturas de polícia, pontos de ônibus,
localização de fábricas, depósitos, torres de transmissão, lojas de franquias, dentre muitos
outros.

Tal problema apresenta uma importância crescente para alguns setoresempresariais, à medida
que os custos referentes à distribuição de seus produtos influenciam diretamente no preço do
produto oferecido ao mercado. Segundo Sun (2006), o sucesso de algumas empresas depende,
em grande parte, da sua localização. Redes de suprimentos eficazes acarretam diminuição no
custo total de produção e, como consequência, levam à satisfação do cliente, sendo, portanto,
uma grandevantagem competitiva.
Neste trabalho apresenta-se um algoritmo heurístico baseado na metaheurística de busca tabu
para a solução do problema. A metaheurística de busca tabu tem sido aplicada com sucesso
em muitos problemas de localização, em particular, a problemas de localização de facilidades.
Este algoritmo possui um conjunto de parâmetros que definem a qualidade da solução obtida
e o tempocomputacional necessário para obtenção da solução. Este trabalho também discute
a relação destes parâmetros com a eficácia do algoritmo.
Este trabalho está organizado da forma descrita a seguir. Na Seção 2 é apresentada uma
formulação do problema abordado e uma breve revisão bibliográfica. Na Seção 3 é
apresentado o algoritmo proposto. Na Seção 4 são apresentados os resultados computacionais
e...
tracking img