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. O trabalho apresentado neste artigo poderá ser usado por outras Meta-heurísticas, como o Algoritmo Genético, através a criação de uma população inicial já melhorada pelo processo da Busca Local, dentre outros.