Logística/Localização/Localização em redes/Localização em redes cíclicas/Localização mediana

A mediana consiste em qualquer nó $x$ de uma rede ter a menor distância total possível deste mesmo nó $x$ a todos os outros nós, então, uma mediana é qualquer nó $x$ tal que (Francis, 1992, p. 426-431):

$SVV(x)=\min \{SVV(i)\}$

onde

$SVV(i)=\sum d(i,j)$

A soma das distâncias do nó $i$ a todos os outros nós é igual a soma dos valores da linha $i$ da matriz D, sendo que esta matriz é composta pelas distâncias mais curtas entre todos os pares de nós.

Figura 9.12.2.2.1 Exemplo de rede cíclica

A considerar a Figura 9.12.2.2.1 como exemplo, a matriz D será a seguinte:

$D=\left[\begin{array}{cccc}0& 3& 5& 4\\ 6& 0& 2& 2\\ 7& 2& 0& 3\\ 4& 5& 3& 0\end{array}\right]$

Dada a matriz D pode-se concluir que:

$SVV(1)=0+3+5+4=12$

$SVV(2)=6+0+2+2=10$

$SVV(3)=7+2+0+3=12$

$SVV(4)=4+5+3+0=12$

Desta forma, $\min \{12,10,12,12\}=7=SVV(2)$. Podendo-se então concluir que a mediana desta rede é o nó 2.

Distância Nó-Arco

Para algum ponto do arco $(r,s)$, existe uma distância mais curta do nó $j$, onde esta tem o seu valor máximo, esta distância máxima chama-se distância nó-arco e é representada por $d^{\prime }(j,(r,s))$. Caso o arco $(r,s)$ não tenha direcção existem dois percursos para ir do nó $j$ ao ponto $f$ em $(r,s)$, sendo que um deles é seguir pelo nó $r$ e o outro seguir pelo nó $s$, devendo-se escolher o percurso com a distância mais curta. Existe também a possibilidade do arco $(r,s)$ ser direccionado, então, um ponto no arco $(r,s)$ só pode ser alcançado via nó $r$. Para o primeiro caso, onde o arco $(r,s)$ não é direccionado considera-se que:

$d^{\prime }(j,(r,s))=[d(j,r)+d(j,s)+a(r,s)]/2$

Já para o segundo caso, onde o arco $(r,s)$ é direccionado considera-se que:

$d^{\prime }(j,(r,s)=d(j,r)+a(r,s)$

Ao numerar os arcos de uma rede de $1$ a $m$ uma matriz, D', $n\times m$ cujo elemento $j,k$ é a distância do nó-arco do nó $j$ ao arco $k$ pode ser construída utilizando as duas equações descritas acima.

Localização Mediana Geral

Quando considerado qualquer nó $x$ com a menor distância total a cada arco, onde a distância de um nó a um arco é a distância máxima do nó aos pontos do arco, este nó $x$ é uma mediana geral, tal que:

$SVA(x)=\min \{SVA(i)\}$

onde

$SVA(i)=\sum d^{\prime }(i,(r,s))$

Uma mediana geral corresponde a qualquer linha de uma matriz D' com menor soma, onde as linhas $i$ desta matriz são compostas pelas distâncias mais curtas entre todos os pares (nós, arcos).

Ao utilizar a Figura 9.12.2.1 como exemplo e ordenando os arcos da seguinte forma:

1. $(1,2)$

2. $(1,3)$

3. $(1,4)$

4. $(2,4)$

5. $(2,3)$

6. $(3,4)$

A matriz D' das distâncias mais curtas entre todos os pares (nós, arcos) é a seguinte:

$D^{\prime }=\left[\begin{array}{cccccc}3& 5& 4& 5& 5& 6\\ 9& 12& 6& 2& 2& 3,5\\ 10& 12& 7& 4& 2& 3\\ 7& 7& 4& 9& 5& 3\end{array}\right]$

Portanto,

$SVA(1)=3+5+4+5+5+6=28$

$SVA(2)=9+12+6+2+2+3,5=34,5$

$SVA(3)=10+12+7+4+2+3=38$

$SVA(4)=7+7+4+9+5+3=35$

$\min \{SVA(i)\}=\min \{28;34,5;38;35\}=SVA(1)$

Pode-se então concluir que o nó 1 é a mediana geral desta rede.

Localização Mediana absoluta

Qualquer ponto com a menor distância total possível a todos os nós é uma mediana absoluta, sendo que esta é qualquer ponto $(f-(r,s))$ tal que:

$SPV(f-(r,s))=\min SPV(f-(t,u))$

com

$f-(t,u)\in P$, $P$ é o conjunto de todos os pares da rede

onde

$SPV(f-(t,u))=\sum d(f-(t,u),j)$

Considerando que $SPV(f-(r,s))$ é uma função côncava de $f$, então esta é minimizada quando $f=0$ ou $f=1$

Sendo assim, quando considerado um arco $(r,s)$ um de seus nós terminais será o mais indicado para ser mediana absoluta. Desta forma, só é necessário considerar os nós quando se pretende encontrar uma mediana absoluta.

Distância Ponto-Arco

Considerando um ponto $f$ do arco $(t,u)$ a sua distância ponto-arco é representada por:

$d^{\prime }(f-(r,s),(t,u))$

Existem quatro casos distintos para determinação da distância ponto-arco, são eles:

1. Arco $(r,s)$ não direccionado e diferente de $(t,u)$, então:

$d^{\prime }(f-(r,s)),(t,u))=\min \{fa(r,s)+d^{\prime }(r,(t,u)),(1-f)a(r,s)+d^{\prime }(s,(t,u))\}$

2. Arco $(r,s)$ direccionado e diferente de $(t,u)$, então:

$d^{\prime }(f-(r,s)),(t,u))=(1-f)a(r,s)+d^{\prime }(s,(t,u))$

3. Arco $(r,s)$ direccionado e igual a $(t,u)$, então:

$d^{\prime }(f-(r,s)),(r,s))=(1-f)a(r,s)+d(r,s)$

4. Arco $(r,s)$ não direccionado e igual a $(t,u)$, então:

$A=\min \{fa(r,s),[a(r,s)+d(s,r)]/2\}$

e

$B=\min \{(1-f)a(r,s),[a(r,s)+d(s,r)]/2\}$

consequentemente,

$d^{\prime }(f-(r,s),(r,s))=\max \{A,B\}$

Localização Mediana Absoluta Geral

Quando a distância total do ponto a todos os arcos é a menor possível estamos perante uma mediana absoluta geral, sendo que esta é qualquer ponto $f-(r,s)$ tal que:

$SPA(f-(r,s))=\min SPA(f-(t,u)$ com $f-(t,u)\in P$

onde

$SPA(f-(t,u))=\sum d^{\prime }(f-(t,u),(v,w))$

Predefinição:AutoCat