Análise de desempenho da heurística Busca Local com permuta All Pairs aplicada ao problema de alocação de facilidades

Resumo

Este artigo apresenta uma Busca Local que faz a permuta All Pairs, aplicada ao problema de alocação de facilidades, tratado como o problema das p-medianas. O objetivo é alocar um número fixo de facilidades (medianas) em pontos estratégicos de uma região para minimizar a distância total envolvida, entre as facilidades abertas e os pontos de demanda atendidos, aplicando-se a Busca Local, visando a melhoria da solução inicial. Em uma nova abordagem do problema, foi imposta uma restrição de distância que informa se a facilidade mais próxima ao ponto de demanda poderá atendê-lo ou não. O trabalho apresentado neste artigo poderá ser usado por outras Meta-heurísticas, como um Algoritmo Genético, através a criação de uma população inicial já melhorada pelo processo da Busca Local, dentre outros.