O problema da p-mediana aplicado ao problema da gestão óptima da diversidade

Abstract

Neste trabalho aborda-se o problema da p-mediana e a sua aplicação a um problema da gestão óptima da diversidade na indústria automóvel. O problema da p-mediana é aplicado em diversas situações práticas reais, nomeadamente na localização de equipamentos públicos, industriais, comerciais e de telecomunicações. Na sua forma geral o problema da p-mediana é NP-difícil e na sua resolução são implementados métodos heurísticos. Primeiramente é feita uma apresentação do problema, e são descritos os principais métodos heurísticos de resolução. De seguida, é descrito o problema da gestão óptima da diversidade e apresentada uma aplicação deste problema à indústria automóvel. Por último, é efectuado um estudo computacional de modo a avaliar o desempenho de diferentes versões do algoritmo híbrido e, simultaneamente, comparar essas versões com o algoritmo guloso.

This work presents the p-median problem and its application to an optimal diversity management problem in the automobile industry. The p-median problem is applied in different real practical situations, particularly in public, industrial, commercial and telecommunications equipments location. In its general form, it’s a NP-hard problem and in its resolution heuristic methods are implemented. First, there is a presentation of the problem, and the main methods of heuristic resolution are described. Next it is described the optimal diversity management problem and an application of this problem is submitted to the car industry. Finally, it is reported a computational study to assess the performance of different versions of hybrid algorithm and compare these versions simultaneously with the greedy algorithm.