segunda-feira, maio 08, 2006

 

Localização central de centro de distribuição / hipermercado numa rede em árvore (I)


O objectivo é localizar um novo centro de distribuição, hipermercado ou outra instalação num ponto y*, de uma rede em árvore, que minimize o máximo das distâncias ponderadas entre a nova instalação e um conjunto de hipermercados, centros populacionais ou outros, localizados nos nós da árvore, vi. Esse ponto designa-se por centro absoluto.

A nova instalação deve ser localizada de modo a minimizar um tempo, custo ou perda: a preocupação é com o pior caso que se quer tornar no menor mal possível.

Se g(y) fôr o máximo das distâncias ponderadas entre y e os nós da árvore, tem-se:

g(y) = max {w1 d(y, v1), …, wm d(y, vm)}.


O centro absoluto y* é um ponto na árvore que minimiza g (y). O centro absoluto não ponderado localiza-se a meio do caminho mais longo da árvore, de onde se poder usar o algoritmo particularmente simples, seguinte, para resolver o problema.


Algoritmo para determinar o centro absoluto não-ponderado

1) Escolher um nó qualquer, v.

2) Encontrar uma ponta da árvore, v', que esteja o mais afastada de v (por exemplo, v3).

3) Encontrar uma ponta da árvore, v", que esteja o mais afastada de v' (por exemplo, v1). O ponto a meio do caminho que liga v' a v" é o único centro absoluto.


Para determinar a localização central de um centro de distribuição, na árvore da Figura 1, comece-se por escolher, por exemplo, v1. v3 é a ponta da árvore mais afastada de v1. v1 é a ponta da árvore mais afastada de v3. Então o centro absoluto, y* localiza-se no arco (v2, v3), a uma unidade de distância de v2.

Figura 1. Rede em árvore
(carregar com o cursor na figura para ver em tamanho grande)
Fonte: Francis et al. (1992)


O valor óptimo da função objectivo é g(y*) = 5

FRANCIS, Richard L. et al. - Facility Layout and Location: An Analytical Approach, 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?