Logística/Localização/Localização em redes/Localização em redes em árvore/Localização de cobertura

Origem: Wikilivros, livros abertos por um mundo aberto.

O objectivo é localizar o menor número de novas instalações, em vários pontos de uma rede em árvore, de modo a que não seja ultrapassada uma certa distância , entre cada nó da árvore e a instalação nova mais próxima. As novas instalações chamam-se centros. Esses centros prestam serviços, por exemplo, de abastecimento ou distribuição, aos nós da árvore, onde se localizam os clientes. As novas localizações podem ser localizadas em qualqeur ponto da árvore (Francis, 1992, p. 411-414).


Figura 9.12.1.3.1 Exemplo de resolução do algoritmo da Localização de Cobertura


Considerando o exemplo da Figura 9.12.1.3.1, onde as linhas tracejadas ligadas aos nós de a representam os limites superiores das restrições de cobertura. Sendo assim, os valores de são os seguintes:







Para se poder dizer que um centro de distribuição cobre o nó da árvore a seguinte condição deve ser cumprida:



A resolução deste problema consiste em escolher uma das pontas da árvore, por exemplo , como chega ao nó adjacente à ponta à distância de 8.

Após constatar que chega a pode-se remover o nó , sendo que o novo valor de passa a ser , estando a nova árvore representada na Figura 9.12.1.3.2.


Figura 9.12.1.3.2 Exemplo de resolução do algoritmo da Localização de Cobertura


O passo seguinte é a escolha de outra ponta da árvore, por exemplo , constata-se que é maior que a distância ao nó adjacente , pode-se assim remover , isso faz com que existam dois valores para , sendo então escolhido o menor, portanto passa a ser . Dando o origem a uma nova árvore, representada na Figura 9.12.1.3.3.


Figura 9.12.1.3.3 Exemplo de resolução do algoritmo da Localização de Cobertura


No passo seguinte escolhe-se , como não chega ao nó adjacente , então, localiza-se um centro num ponto a uma distância 2 de , de seguida remove-se todo o arco que liga a , a nova árvore está representada na Figura 9.12.1.3.4.


Figura 9.12.1.3.4 Exemplo de resolução do algoritmo da Localização de Cobertura


Pode-se observar que é um nó distinto, dado que tem origem na restrição do nó , então , pode-se observar também que o novo centro apenas cobre os nós , e , com isto continua-se a analisar os restantes nós, por exemplo, analisa-se o nó . Pode-se observar que o que não é suficiente para cobrir a distância de ao nó adjacente , portanto regista-se um novo centro em e regista-se o facto de ser um nó distinto, ou seja, . Observa-se que é suficiente para cobrir o novo centro , portanto, podemos remover ambos os nós, dando origem a árvore representada na Figura 9.12.1.3.5.


Figura 9.12.1.3.5 Exemplo de resolução do algoritmo da Localização de Cobertura


Observando o nó , pode-se ver que não é suficientemente grande para chegar ao nó adjacente nem suficientemente grande para atingir ou , então, existe um novo centro de distribuição a uma distância de 4 do nó , portanto o nó é um nó distinto, dando origem a . A árvore resultante encontra-se representada na Figura 9.12.1.3.6.


Figura 9.12.1.3.6 Exemplo de resolução do algoritmo da Localização de Cobertura


Sendo assim, pode-se dizer que para o exemplo referido a solução óptima consiste em três centros de distribuição, tendo os mesmos as seguintes localizações:


- Localizado no arco que liga a , estando a uma distância de dois de ;


- Localizado no arco que liga a , estando a uma distância de oito de ;


- Localizado no arco que liga a , estando a uma distância de quatro de .