Abordagens complementares para problemas de p-medianas
Carregando...
Data
2003-01-01
Autores
Senne, Edson Luiz França [UNESP]
Lorena, Luiz Antonio Nogueira
Título da Revista
ISSN da Revista
Título de Volume
Editor
Associação Brasileira de Engenharia de Produção
Resumo
A localização de p-medianas é um problema clássico de otimização combinatória. O objetivo é localizar em uma rede p nós (denominados medianas), de forma a minimizar a soma das distâncias de cada nó de demanda até sua mediana mais próxima. Neste trabalho aborda-se a relaxação lagrangeana/surrogate como técnica para resolver tais problemas. Discute-se a utilização desta relaxação em combinação com métodos de otimização por subgradientes e com métodos de geração de colunas. O trabalho apresenta testes computacionais que demonstram a eficiência dos algoritmos propostos, considerando problemas obtidos da literatura e problemas reais obtidos a partir de Sistemas de Informações Geográficas.
The search for p-median vertices on a network is a classical combinatorial optimization problem. The objective is to locate p facilities (medians) such as the sum of the distances from each demand vertex to its nearest facility is minimized. This work presents the lagrangean/surrogate relaxation as a technique for solving such combinatorial problems. The paper discusses the use of this relaxation combined with subgradient optimization methods and with column generation methods. Computational tests which demonstrate the eficiency of the proposed approaches for solving p-median instances taken from the literature and obtained from Geographical Information Systems are presented.
The search for p-median vertices on a network is a classical combinatorial optimization problem. The objective is to locate p facilities (medians) such as the sum of the distances from each demand vertex to its nearest facility is minimized. This work presents the lagrangean/surrogate relaxation as a technique for solving such combinatorial problems. The paper discusses the use of this relaxation combined with subgradient optimization methods and with column generation methods. Computational tests which demonstrate the eficiency of the proposed approaches for solving p-median instances taken from the literature and obtained from Geographical Information Systems are presented.
Descrição
Palavras-chave
Problemas de localização, problemas de p-medianas, relaxação lagrangeana, geração de colunas, programação inteira, Location problems, p-median problems, lagrangean, column generation, integer programming
Como citar
Produção. Associação Brasileira de Engenharia de Produção, v. 13, n. 3, p. 78-87, 2003.