Uma nova proposta de resolução para o problema das p-medianas ponderado

Abstract

Neste trabalho é apresentada uma nova abordagem para resolver o problema das p-medianas ponderado, a qual modela importantes e complexos problemas de localização. A partir de um estudo sobre a medida de centralidade de autovetor, foi observado uma forte relação entre determinação do vetor centro com a determinação da mediana de saída de um grafo não-dirigido, onde a centralidade de autovetor hierarquiza os vértices segundo a importância de cada um. Um algoritmo que combina o Método das Potências com o algoritmo clássico de Teitz e Bart é desenvolvido com o intuito de possibilitar uma maior avaliação sobre os resultados observados. Testes computacionais realizados com redes pequenas e médias geradas aleatoriamente mostraram que a busca da centralidade de autovetor de um vértice aponta para uma solução das medianas, indicando que o Método das Potências pode ser um fator determinístico da solução inicial para o método de Teitz e Bart.

In this work is presented a new approach to solve the p-median problem, that model important and complex problems of locations. From a study of the measure of eigenvector centrality, was observed a strong relation between the determination of the vector center with the determination of the output median of an undirected graph, where the centrality of eigenvector ranks the vertexes in order of importance of each one. An algorithm that combine the Power's Method with the classic algorithm of Teitz and Bart is developed with the purpose of enable a greater evaluation of the results. Computational test with small and medium networks random showed that the search of the eigenvector centrality of a vertex points to a solution of the medians, indicating that the power's method can be a deterministic factor of the initial solution for the method of Teitz and Bart.