segunda-feira, maio 22, 2006

 

Localização de cobertura de centros de distribuição/hipermercados numa rede em árvore


O objectivo é localizar o menor número de novos centros de distribuição, hipermercados ou outras instalações, em vários pontos de uma rede em árvore, de modo a que não seja ultrapassada uma certa distância si, entre cada nó i 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, por exemplo, hipermercados ou centros populacionais. As novas localizações ser localizadas em qualquer ponto da árvore.

Considere-se o caso da Figura 1a em que cada nó representa um hipermercado. As linhas sinuosas ligadas aos nós 1 a 5 são fios cujos comprimentos são os limites superiores das restrições de cobertura, portanto. s1 = 10, s2 = 5 e assim por diante. Qualquer centro de distribuição x cuja localização na árvore satisfaça d (x, vi) ≤ si diz-se que cobre o nó (hipermercado) i. Pelo menos um centro tem que estar a uma distância menor que 10 do hipermercado 1, menor que 5 do hipermercado 2 e assim por diante; isto é, pelo menos um centro tem que cobrir cada hipermercado.

Figura 1. Exemplo de aplicação do algoritmo de resolução do problema de cobertura
(carregar com o cursor na figura para ver em tamanho grande)
Fonte: Francis et al., 1992


Escolhe-se uma das pontas da árvore, por exemplo v4, e verifica-se se o fio de comprimento 14 (se não houver um fio na ponta escolhida, a ponta e o arco com esse nó podem ser apagados da árvore) chega ao nó adjacente à ponta, v6 à distância de 10. O fio chega a v6, por isso, remove-se o arco com o nó v4 e fica-se com um fio com o comprimento restante 14 - 10 = 4 (Figura 1b) ligado a v6.

Continua-se a escolher uma ponta da árvore, por exemplo v5, e verifica-se se o fio de comprimento 15 chega ao nó adjacente à ponta, v6. O fio chega a v6, por isso, remove-se o arco com o nó v5 e fica-se com um fio com o comprimento restante 15 - 12 = 3 ligado a v6. Agora há dois fios ligados a v6. Nestes casos o fio de maior comprimento é removido do modelo. Fica, portanto, um fio de comprimento 3 ligado a v6 (Figura 1c).

Suponha-se que a ponta escolhida a seguir é v6 com um fio de comprimento 3. Como este fio não chega a v2 localiza-se um centro num ponto y1, no arco que liga os nós 2 e 6, a uma distancia de 3 de v6 e remove-se todo o arco do modelo (Figura 1d). Dado que o fio com origem em v5 é que fez com que o centro 1 fosse localizado, regista-se o facto de v5 ser um nó distinto, u1 = {v5}. Determina-se, também, se algum dos fios restantes na árvore chegam a y1, para que os nós que lhes estão ligados possam ser cobertos pelo centro. Neste caso, nenhum fio restante na árvore chega a y1. O centro que se localizou cobre ambos os hipermercados 4 e 5.

Suponha-se que a seguir se escolhe o vértice v1 como ponta da árvore restante: o fio de v1 não chega a v2, por isso localiza-se um segundo centro em y2, no arco que liga os vértices 1 e 2, à distancia de 10 de v1. O fio de v2 chega a y2, por isso é removido. Regista-se o facto de v1 ser um vértice distinto. Remove-se a parte do arco (v1, v2) de v1 a y2 e y2 torna-se uma ponta da árvore sem fio. Por isso, na próxima iteração, pode-se omitir o arco que liga y2 a v2 (Figura 1e).

Neste ponto a árvore restante tem apenas um único arco ligando v2 a v3 com um fio de comprimento 3 em v3: este fio não chega a v2, por isso localiza-se um terceiro centro em y3, no arco que liga os vértices 2 e 3, à distância de 3 de v3. Não restam mais fios no modelo, por isso não há necessidade de verificar se algum outro fio chega a y3. Regista-se o facto de v3 ser um vértice distinto. Removendo o arco que liga os vértices 2 e 3, fica-se com um único nó, v2, sem fios ligados (Figura 1f).

O procedimento termina, tendo-se localizado três centros, nos pontos y1, y2 e y3, a solução óptima para o problema, e identificado três nós distintos, v1, v3 e v5.

FRANCIS, Richard L.; et al. - Facilities Layout and Location, 2.ª ed., Englewood Cliffs, NJ, Prentice Hall, 1992.

Comments: Enviar um comentário

Links to this post:

Criar uma hiperligação



<< Home

This page is powered by Blogger. Isn't yours?