domingo, maio 07, 2006

 

Localização mediana de centro de distribuição / hipermercado numa rede em árvore


O objectivo é localizar um novo centro de distribuição, hipermercado ou outra instalação num ponto, x*, de uma rede em árvore, que minimize a soma 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 é chamado de mediana absoluta.

O novo centro de distribuição pode abastecer os hipermercados localizados nos nós ou o novo hipermercado abastecer centros populacionais. A nova instalação deve ser localizada de modo a minimizar a distância total percorrida, durante um determinado período, entre a nova localização e as existentes.

Designando wi como sendo o número de deslocações de ida e volta, o custo de transporte ou o tempo de deslocação por unidade de distância, por unidade de tempo, entre o ponto x e o vértice vi, o objectivo é minimizar:

f(x) = w1 d(x, v1) + ... + wm d(x, vm).

Este problema tem algumas características que convém salientar. Uma delas é que pelo menos um vértice é uma localização óptima ou mediana absoluta. Só os vértices precisam de ser considerados como localizações potenciais.

Outra propriedade importante é que a localização mediana depende dos pesos, wi, e da estrutura da árvore, mas não das distâncias entre os nós. É claro que o valor de f(x) depende das distâncias entre os nós.

Outra, ainda, é que uma sub-árvore que contenha pelo menos metade dos pesos, contém a localização mediana


Algoritmo para determinar a mediana

Algoritmo da Maioria:

1) Escolher uma ponta qualquer vt com peso wt. Se wt for maior ou igual a W / 2 (metade da soma dos pesos), essa ponta é a mediana e parar.

2) Designar por va o nó adjacente a vt; adicionar wt a wa para obter o novo peso para va. Apagar da árvore todos os pontos do arco [vt, va], excepto va, e voltar ao passo 1.


Para determinar a localização mediana de um hipermercado, na árvore da Figura 1, comece-se por escolher uma ponta, por exemplo, v1.
Figura 1. Exemplo de rede em árvore com os pesos dos nós dentro dos quadrados
(carregar com o cursor na figura para ver em tamanho grande)


Como o peso de v1 é inferior a W / 2 = 6, adiciona-se o peso de v1 ao peso do vértice adjacente v2 e apaga-se v1 e o caminho que o liga a v2 (Figura 2).
Figura 2. v2 = v1 + v2
(carregar com o cursor na figura para ver em tamanho grande)


Escolhendo v3, como o peso de v3 é inferior a W / 2 = 6, adiciona-se o peso de v3 ao peso do vértice adjacente v2 e apaga-se v3 e o caminho que o liga a v2 (Figura 3).

Como o peso de v2 é maior que W / 2 = 6, v2 é a localização mediana.
Figura 3. v2 = v3 + v2
(carregar com o cursor na figura para ver em tamanho grande)


O valor óptimo da função objectivo é dado por:

f(x*) = 1 × 6 + 2 × 4 + 2 × 4 + 2 × 10 + 1 × 12 = 54

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?