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 {\big \{}w_{i}d(y,v_{1}),...,w_{m}d(y,v_{m}){\big \}}$

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 mais afastada de $\ v$

3. Encontrar uma ponta da árvore $\ v''$, que esteja mais afastada de $\ v'$. O ponto a meio do caminho que liga $\ v'$ 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 {\big \{}b_{ij}:1\leq j\leq m{\big \}}\leq z$

e

$w_{i}d(y,v_{i})\leq 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}$

${\begin{bmatrix}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{bmatrix}}$

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 {\big \{}w_{1}d(y,v_{1})+h_{1},...,w_{m}d(y,v_{m})+h_{m}{\big \}}$

Procedimento para Determinar o Centro Absoluto Ponderado com Adendas

1.Para cada $\ i$ e $\ j$ tais que $\ 1\leq i\leq j\leq 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$.