A branch-and-price method for p-median location problems / Um método branch-and-price para problemas de localização de ρ-medianas

AUTOR(ES)

Marcos Antonio Pereira

DATA DE PUBLICAÇÃO

2005

RESUMO

Este trabalho apresenta a implementação de um algoritmo branch-and-price para resolver problemas de localização de facilidades baseados no modelo matemático do problema de p-medianas. A abordagem tradicional de geração de colunas é comparada com uma nova proposta, onde o critério de custos relativos empregado na seleção de colunas é modificado pelo multiplicador da relaxação lagrangeana/surrogate. A eficiência da nova abordagem foi comprovada por testes computacionais envolvendo instâncias com até 900 vértices. Também foram realizados estudos com dados reais de problemas de máxima cobertura, formulados como problemas de p-medianas, cuja esparsidade nos vetores de custos e na matriz de restrições representam grande dificuldade para métodos baseados em geração de colunas.

ASSUNTO(S)

branch and price relaxação lagrangeana/surrogate lagrangean/surrogate relaxation combinatorial optimization computaÇÃo aplicada localização de facilidades computer science facility location branch and price otimização combinatória

Documentos Relacionados

• Um método branch-and-price para problemas de localização de ρ-medianas
• Um algoritmo exato para problemas das P-medianas
• HEURÍSTICAS PARA O PROBLEMA DAS P-MEDIANAS CONECTADAS
• ALGORITMOS PRIMAIS E DUAIS PARA O PROBLEMA DAS P-MEDIANAS
• LOCATING PUBLIC SCHOOLS IN FAST EXPANDING AREAS: APPLICATION OF THE CAPACITATED p-MEDIAN AND MAXIMAL COVERING LOCATION MODELS