Algoritmo de busca tabu

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 conjunto de 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 um algoritmo 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 facility location 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 the uncapacitated 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 quality