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

Quando se fala em localização mediana o objectivo é encontrar um ponto $x^{*}$ que minimiza a soma das distâncias ponderadas entre a nova instalação e os clientes localizados nos nós de uma rede em árvore, $v_i$. Ao ponto $x^{*}$ dá-se o nome de mediana absoluta (Francis, 1992, p. 400-403).

O número de deslocações, o custo de transporte ou o tempo de deslocação por unidade de distância, durante um periodo de tempo, entre o ponto $x$ e o vértice $v_i$ representa-se por $w_i$, logo, o objectivo é minimizar:

$f(x)=w_{1}d(x,v_1)+...+w_{m}d(x,v_m)$

Neste problema, apenas os vértices são considerados como localizações potenciais, em que pelo menos um deles é uma localização óptima ou mediana absoluta e a localização mediana depende dos pesos, $w_i$, assim como da estrutura da árvore, mas é independente das distâncias entre os nós. Estas distâncias só influenciam o valor de $f(x)$.

Algoritmo da Maioria

Este algoritimo é utilizado para determinar o valor da mediana, seguindo os dois passos indicados abaixo:

1. Escolher um nó $v_t$ com peso $w_t$ em qualquer um dos extremos da árvore. Se $w_t$ for maior que $W/2$, onde $W$ é a soma dos pesos dos nós, esse nó é a mediana, caso contrário executar o passo 2.

2. Designar por $v_a$ o nó adjacente a $v_t$. Somar $w_t$ a $w_a$, de forma a encontrar o novo peso do nó $v_a$ e apagar da árvore o arco $[v_t,v_a]$, excepto $v_a$, e voltar ao passo 1.

Na Figura 9.12.1.1.1 o peso dos nós está representado nos quadrados, sendo $W/2=8,5$.

Figura 9.12.1.1.1 Exemplo de rede em árvore com o peso dos nós dentro dos quadrados

Para encontrar a mediana da árvore representada na Figura 9.12.1.1.1 escolhe-se, por exemplo, $v_1$.

O peso de $v_1$ é 2, como $2<W/2$, $v_1$ não é mediana, segue-se, portanto, para o passo 2, ou seja, adiciona-se o peso de $v_1$ ao vértice adjacente $v_2$, eliminando o caminho que ligava $v_1$ a $v_2$, dando origem à seguinte rede em árvore (Figura 9.12.1.1.2):

Figura 9.12.1.1.2 $v_2=v_1+v_2$

Seguidamente escolhe-se $v_3$. Como o peso de $v_3$ é inferior a $W/2$, adiciona-se o peso de $v_3$ ao vértice adjacente $v_2$, eliminando o caminho que ligava $v_3$ a $v_2$. A rede resultante é apresentada na Figura 9.12.1.1.3.

Figura 9.12.1.1.3 $v_2=v_3+v_2$

De seguida escolhe-se o vértice $v_2$. Como $w_2=7$ é menor que $W/2$, volta-se a repetir o passo 2, dando origem a outra árvore, representada na Figura 9.12.1.1.4.

Figura 9.12.1.1.4 $v_4=v_2+v_4$

Como $w_4>W/2$, $v_4$ é a localização mediana, sendo o valor óptimo da função objectivo dado por:

$f(x^{*})=(2\times 11)+(2\times 6)+(3\times 8)+(4\times 8)+(2\times 7)=104$

Predefinição:AutoCat