Um algoritmo de busca tabu para problemas de localização não capacitados

Abstract

In this work, a tabu search algorithm for solving uncapacitated location problems is presented. The uncapacitated location problem is a classic problem of localization and occurs in many practical situations. The problem consists in determining in a network, at the minimum possible cost, the better localization, in a network, for the installation of facilities in order to attend the customers' associated demands, at the minimum possible cost. One admits that there exists a cost associated with the opening of a facility and a cost of attendance of each customer by any open facilities. In the particular case of the uncapacitated location problem there is no capacity limitation to attend the customers’ demands. There are some parameters in the algorithm that influence the solution’s quality. These parameters were tested and optimal values for them were obtained. The results show that the proposed algorithm is able to find the optimal solution for all small tested problems keeping the compromise between solution’s quality and computational time. However, to solve bigger problems, the structure of the algorithm must be changed in its structure. The implemented algorithm is integrated to a computational platform for solution of logistic problems

Neste trabalho, apresenta-se um algoritmo de busca tabu para a solução de problemas de localização não-capacitados. O problema de localização não-capacitado é um problema clássico de localização e ocorre em diversas situações práticas. O problema consiste em determinar a melhor localização, em uma rede, para a abertura de um conjunto de instalações (também conhecidas como facilidades) de modo a atender às demandas associadas aos clientes, ao menor custo possível. Admite-se que existe um custo associado à abertura de uma facilidade e um custo de atendimento de cada cliente por uma das facilidades abertas. No caso particular do problema de localização de facilidades não-capacitado não existe limitação quanto à capacidade de uma facilidade em atender às demandas dos seus clientes. O algoritmo proposto possui vários parâmetros que influenciam a qualidade da solução. Tais parâmetros foram testados e foram obtidos valores favoráveis para estes. Os resultados mostram que o algoritmo proposto é capaz de encontrar a solução ótima para todos os problemas pequenos testados, mantendo o compromisso entre a qualidade da solução e o tempo computacional. Já para problemas maiores, o algoritmo deve sofrer melhoras em sua estrutura. O algoritmo implementado está integrado a uma plataforma computacional para solução de problemas logísticos