Teoria dos grafos e otimização em redes

UNIVERSIDADE FEDERAL FLUMINENSE

ESCOLA DE ENGENHARIA INDUSTRIAL E METALÚRGICA DE VOLTA REDONDA

ENGENHARIA DE PRODUÇÃO

AMANDA CRISTINA DOS SANTOS, GABRIEL DE ALMEIDA CANIL, ANDERSON FREITAS DE SOUSA

PROBLEMA DO CAMINHO MÍNIMO

VOLTA REDONDA – RJ

2018

AMANDA CRISTINA DOS SANTOS, GABRIEL DE ALMEIDA CANIL, ANDERSON FREITAS DE SOUSA.

PROBLEMA DO CAMINHO MÍNIMO ENTRE DEZ CIDADES DA REGIÃO RESOLVIDO PELO ALGORITMO DE FLOYD

[pic 1]

VOLTA REDONDA – RJ

2018

1. INTRODUÇÃO

A pesquisa operacional é uma área de conhecimento da matemática que estuda, desenvolve e aplica modelos matemáticos, estatísticos e algoritmos que auxiliam na análise e tomada de decisões de sistemas complexos do cotidiano. Seu objetivo é otimizar esses sistemas e, para isso, antes é preciso de uma clara definição do que é o problema para, então, construir um modelo matemático para resolvê-lo.  

Um exemplo disso é o problema do Caminho Mais Curto (ou Caminho Mínimo), que é abordado neste trabalho. O problema do caminho mínimo determina o menor caminho entre o destino e a origem de uma rede de transporte.  Além de trabalhar como a minimização de distâncias, também pode ser utilizado para minimizar, por exemplo, o custo ou o tempo total de uma sequência de atividades. Para resolver problemas do tipo caminho mínimo, que são considerados problemas de redes cíclicas, podemos utilizar de dois algoritmos: Dijkstra e Floyd.  

Neste trabalho, abordaremos o problema utilizando como método de solução o algoritmo de Floyd para definir a menor distância, o menor custo e menor tempo entre algumas cidades da região Médio Vale do Paraíba do Sul, sendo elas: Volta Redonda, Resende, Barra Mansa, Quatis, Porto Real, Rio Claro, Pinheiral, Piraí, Valença e Barra do Piraí.

1. REFERENCIAL TEÓRICO

1. . Algoritmo de Floyd

O algoritmo de Floyd, também conhecido como algoritmo de Floyd – Warshall, é um algoritmo que resolve o problema de encontrar o caminho mais curto entre todos os pares de vértices de um grafo orientado G = (V,E), ou seja, entre quaisquer dois nós da rede. Ele vai representar uma rede de n nós como sendo uma matriz quadrada de n linhas e n colunas.

A distância dij de um nó ao outro se dá com a entrada de (i,j) apenas se i estiver ligado diretamente a j, caso não esteja, a distância é considerada infinita.  Para se resolver um problema usando o algoritmo de Floyd, é preciso aplicar as seguintes etapas à rede:

Etapa 0: É preciso definir a matriz de distâncias inicial D0  e a matriz de sequências S0, marcando o elementos na diagonal principal com 0 ou (–) para indicar que estão bloqueados. Feito isso, terá que determinar a etapa k = 1.

Etapa Geral k: Nessa etapa, será preciso definir a linha k e coluna k como pivôs e trave. Feito isso, com os elementos que restarem, será preciso comparar as distâncias, sempre passando pelo vértice k, e vendo se as distâncias são menores ou não do que as que constavam na etapa anterior. Se for menor, substituir. Caso isso aconteça, será necessário fazer as seguintes mudanças: dik+ dkj < dij , (i ≠ k, j ≠ k, i ≠ j)

     a. Crie Dk substituindo dij em  Dk-1 por dik + dkj

      b. Crie Sk substituindo rij em Sk-1 por k. Determine k = k+1. Se k = n+1, pare; caso contrário, repita a etapa k.

Feito isso, após n etapas, poderá ser possível determinar o caminho mais curto entre os nós com base nas matrizes Dn e Sn. A matriz Dn mostrará a menor distância entre os nós i e j, já com a matriz Sn será possível determinar o nó intermediário que dá a rota da distância entre os nós escolhidos.

1. DESENVOLVIMENTO

Para o desenvolvimento do presente trabalho, foram escolhidas dez cidades do interior do estado do Rio de Janeiro a fim de avaliar quais seriam as melhores rotas entre elas, avaliando, para tal, as distâncias percorridas, tempo que seria gasto, bem como o custo do percurso. São elas:

1. Volta Redonda;
2. Resende;
3. Barra Mansa;
4. Quatis;
5. Porto Real;
6. Rio Claro;
7. Pinheiral;
8. Piraí;
9. Valença;
10. Barra do Piraí.

- Grafo das Cidades

                

[pic 2]

1. Distâncias

        Após uma pesquisa no Google Maps, encontramos as distâncias, em quilômetros, entre as cidades da região e montamos uma matriz. Cidades que não têm ligação direta o Tora reconhece como “infinity”.

[pic 3]

Após a montagem da matriz, utilizamos o programa Tora para calcular o caminho mínimo entre as cidades escolhidas. O programa resolveu o problema de caminho mínimo pelo algoritmo de Floyd e obtemos a seguinte matriz resultado:

Tabela 1 – Matriz resultado: caminho mínimo entre as cidades.

[pic 4]

1. Custos

        Para calcularmos o custo, pesquisamos a distância média que um carro popular faz por litro de gasolina e encontramos 15 km por litro. Após isso, dividimos a distância entre as cidades por 15 km e depois multiplicamos pelo preço atual do litro da gasolina (R$5,00). E, além disso, acrescentamos R$7,00 em algumas rotas por conta do pedágio. Assim, obtemos a seguinte matriz custos:

[pic 5]

Após o preenchimento da matriz de custos no Tora, o programa resolveu o problema de caminho mínimo pelo algoritmo de Floyd e obtivemos a seguinte matriz resultado: