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

O objectivo é localizar uma nova 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 as instalações existentes localizadas nos nós da árvore, $v_i$. Este ponto designa-se por centro absoluto (Francis, 1992, p. 405-411).

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)$ for o máximo das distâncias ponderadas entre $y$ e os nós da árvore, tem-se:

$g(y)=\max \{w_{i}d(y,v_1),...,w_{m}d(y,v_m)\}$

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^{\prime }$, que esteja mais afastada de $v$

3. Encontrar uma ponta da árvore $v^{″}$, que esteja mais afastada de $v^{\prime }$. O ponto a meio do caminho que liga $v^{\prime }$ a $v^{″}$ é o único centro absoluto.

Figura 9.12.1.2.1 Rede em árvore

Para determinar a localização central de um centro de distribuição, na árvore da Figura 9.12.1.2.1, escolhe-se por exemplo $v_1$. $v_3$ é a ponta da árvore mais afastada de $v_1$. $v_1$ é a ponta da árvore mais afastada de $v_3$. Então o centro absoluto $y^{*}$,localiza-se o no arco $(v_2,v_3)$.

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

$g(y^{*})=6$

Procedimento para Determinar o Centro Absoluto Ponderado

Primeiro calcule-se $b_{st}$. Então $y*$ é o ponto único no caminho que liga os nós $s$ e $t$ que satisfaz as seguintes equações:

$d(y^{*},v_s)=w_{t}d(v_s,v_t)/(w_s+w_t)$

$d(y^{*},v_t)=w_{s}d(v_s,v_t)/(w_s+w_t)$

com

$b_{st}=\max \{b_{ij}:1\le j\le m\}\le z$

e

$w_{i}d(y,v_i)\le z,i=1,...,m$

Portanto, $b_{st}$ é o menor valor de $z$, que, por sua vez, é o menor valor da função objectivo do problema do centro absoluto.

Com

$b_{ij}=w_i{w}_{j}d(v_i,v_j)/(w_i+w_j)$

Para calcular $b_{st}$, o maior valor da matriz $B=(b_{ij})$, o procedimento é o seguinte:

1. Calcular os valores de uma linha qualquer de $B=(b_{ij})$, por exemplo $l(1)$ e encontrar o maior valor na linha $l(1)$, por exemplo na coluna $c(1)$.

2. Calcular os valores da coluna $c(1)$ e encontrar o maior valor na coluna $c(1)$, que ocorre, por exemplo, na linha $l(2)$.

3. Calcular os valores da linha $l(2)$ e encontrar o maior valor na linha $l(2)$ e assim sucessivamente, continuando até se encontrar, pela primeira vez, a mesma entrada da matriz duas vezes seguidas; este número será o maior elemento da matriz $B$.

Considere-se, por exemplo, a rede em árvore da Figura 9.12.1.2.2, onde os nós representam localizações de instalações existentes e os pesos, tempo por unidade de distância.

Figura 9.12.1.2.2. Exemplo de rede em árvore onde os nós representam as localizações e os pesos tempo por unidade de distância

Para determinar a localização de uma nova instalação que minimize o tempo máximo das viagens de entregas as instalações existentes, o centro absoluto da rede em árvore da Figura 9.12.1.2.2, pode-se ver que o maior valor da matriz $B$ é $(b_{35}=27,4$. Portanto, o tempo máximo para fazer uma entrega, $g(y^{*})$, é 27,4. Para determinar a localização da nova instalação, $y^{*}$, utilizam-se as equações acima e, uma vez que $d(y^{*},v_s)=9,15$ e $d(y^{*},v_t)=6,85$, conclui-se que a nova instalação,$y^{*}$ , deve ficar a uma distância de 9,15 do nó 3 e a uma distância de 6,85 do nó 5, ou seja, essa localização será no arco que liga $v_4$ a $v_5$

$\left[\begin{array}{cccccc}0& 5& 8,4& 13,3& 25,3& 18\\ 5& 0& 2,4& 8& 18,6& 13\\ 8,4& 2,4& 0& 13,7& 27,4& 18\\ 13,3& 8& 13,7& 0& 20& 9,3\\ 24,3& 18,6& 27,4& 20& 0& 20\\ 18& 13& 18& 9,3& 10& 0\end{array}\right]$

Interpretando $w_{1}d(y,v_i)$ como o tempo de transporte de $y$ para o nó $i$, pode-se designar por adenda, $h_i$, o tempo de preparar o transporte mais o tempo de carga ou descarga do nó, mais o tempo de viagem do nó $i$ para qualquer outro ponto conhecido na rede, tal como um centro de recolha de veículos. Naturalmente, dependendo das circunstâncias, alguns destes tempos podem ser nulos.

Neste caso, a função $g(y)$ que se pretende minimizar é

$g(y)=\max \{w_{1}d(y,v_1)+h_1,...,w_{m}d(y,v_m)+h_m\}$

Procedimento para Determinar o Centro Absoluto Ponderado com Adendas

1.Para cada $i$ e $j$ tais que $1\le i\le j\le m$ Calcular $b_{ij}$ definido por:

$b_{ij}=(w_i{w}_{j}d(v_i,v_j)+w_j{h}_i+w_i{h}_j)/(w_i+w_j)$

Seguidamente encontrar $b_{st}$, valor máximo de $b_{ij}$.

2.Calcular $h_p$, máximo dos $h_i$.

3. Calcular $b$, máximo de $b_{st}$ e $h_p$.

4. Se $b=h_p$, então $y^{*}=v_p$ é a solução do problema.

5. Caso o ponto 4 não se verifique, $b=b_{st}$, então $y^{*}$ é o ponto que liga os vértices $s$ e $t$ que satizafaz as seguintes equações:

$d(y^{*},v_s)=(w_{t}d(v_s,v_t)+h_t-h_s)/(w_s+w_t)$

$d(y^{*},v_t)=(w_{s}d(v_s,v_t)+h_s-h_t)/(w_s+w_t)$

Quando se pretende determinar o centro absoluto ponderado num nó, deve-se avaliar $g$ nos nós do arco que contém $y^{*}$ e escolher como centro absoluto ponderado num nó aquele que tenha menor valor de $g$.