Prévia do material em texto
Roteirização
Grafo:
Modelo que representa as
relações e os elementos
de um problema de
relacionamento.
Aplicações Logísticas:
Distribuição de
mercadorias
Roteirização em redes
Modelagem – Teoria dos Grafos
Objetivo:
Analisar as relações de causa e efeito de sistemas de apoio a decisões
estratégicas, táticas e operacionais relativas à distribuição.
Métodos Quantitativos na Distribuição de Carga
Definição Matemática:
É uma estrutura G = (X,A), onde:
X = conjunto de nós X = {x1, x2, ... , xn}
A = conjunto de arcos A = {a1, a2, ... , am}
Cada arco ak é definido por um par de nós do conjunto X, isto é:
ak = (xi, xj).
A esses arcos são associados valores, que normalmente estão
associados ao custo de se percorrer esse arco, e os algoritmos visam
cumprir determinada tarefa com o menor custo total possível.
Teoria dos Grafos – Modelagem Matemática
Esquema:
O esquema de um grafo é um desenho
que utiliza símbolos
gráficos para representar os elementos
e as relações do modelo.
Nó: X = {x1, x2, ... , x10};
Representa o elemento do modelo.
É também chamado de vértice, ponto
ou rótula.
Seu símbolo pode ser um círculo ou
um ponto com label.
Elementos do Grafo
Arco:
Representa a relação orientada
do modelo.
Seu símbolo é uma seta.
Aresta:
Representa a relação não
orientada do modelo.
Uma reação não orientada é
chamada de recíproca.
Seu símbolo é uma linha.
Elementos do Grafo
Ordem:
É a quantidade de nós de um grafo.
Exemplo: Esquema de um grafo de 4a ordem
x1
x4
x2
x3
u1
u2
u3
u4 u5
G
Onde:
G representa o esquema do grafo.
x1, x2, x3 e x4 representam os nós.
u2, u4 e u5 representam os arcos.
u1 e u3 representam as arestas.
Teoria dos Grafos - Exemplo
Grafo Orientado:
É aquele cujas relações são orientadas.
Grafo Simétrico:
É aquele que só possui relações recíprocas.
Grafo Valorado:
É aquele cujas relações possuem valor previamente conhecido.
Ex: tempo, distância, valor monetário, etc
Grafo Bipartido:
É aquele que possui um conjunto de nós origens e um conjunto
de nós destinos. Nesse tipo de grafo não são permitidas
ligações entre dois nós do mesmo conjunto.
Teoria dos Grafos - Tipos
VANTAGENS
Menores tempos de carga e descarga
Maximização do quilometro transportado
Menores gastos com manutenção e combustíveis
Otimização da frota
Fim dos desvios de rotas
Padronização, aumento da qualidade e pontualidade
Vantagens da Roteirização
Fonte: Adaptado de caddesign (http://www.rccaddesign.com)
Modelo
Algoritmo
Objetivo:
Otimizar
Custos,
distância,
tempo, ...
Informações
disponíveis
nos SI
Tipos de
Problemas de
Distribuição
Abordagem do Problema
Problema do Caixeiro Viajante
Distribuição física que incorpora um roteiro de entregas no qual o
veículo visita, de uma só vez, um determinado número de clientes
(nós) localizados numa determinada região e retorna à origem,
(circuito fechado) percorrendo a rota de menor valor.
Aplicação – Vehicle Routing Problem – VRP
Tem como objetivo encontrar um conjunto de rotas com o menor
valor possível (minimizar distância total percorrida, número de
veículos, etc.), iniciando e terminando no CD, de forma que a
demanda de todos os nós seja atendida.
A demanda é determinística. Cada nó é atendido uma única vez, por
um único veículo, e cada veículo possui capacidade limitada.
Algumas formulações também apresentam restrição de tempo
máximo de viagem.
Aplicação – Vehicle Routing Problem – VRP
PROBLEMAS CLÁSSICOS
Problemas de valor mínimo
São problemas que visam determinar rotas (caminhos) que otimizem
o valor total entre uma origem e um destino previamente
conhecidos dentro de uma rede.
Problemas de rota mínima:
São problemas que visam determinar rotas (caminhos) que
otimizem a quantidade de nós a serem percorridos entre uma origem
e um destino previamente conhecidos dentro de uma rede.
Aplicação – Vehicle Routing Problem – VRP
Problema Milk Run
Sistema de coletas programadas, que utiliza um único equipamento
de transporte, de algum Operador Logístico, para realizar as coletas
em um ou mais fornecedores (nós) e entregar os materiais no
destino final, sempre em horários pré-estabelecidos.
Aplicação – Vehicle Routing Problem – VRP
Problema do Carteiro Chinês
Visa encontrar um caminho de menor valor ou circuito fechado que
visite cada aresta de um grafo (conectado) não-direcionado.
Quando o grafo possui um circuito Euleriano1 (circuito fechado
que abrange toda aresta uma vez), esse circuito é uma ótima
solução.
1 - Leonhard Euler em 1736
(matemático e físico suíço):
As pontes da cidade alemã de
Königsberg possuía sete
pontes sobre o rio Pregel.
Aplicação – Vehicle Routing Problem – VRP
Definição de Valor:
Valor total:
É obtido a partir do somatório dos valores unitários de ligação entre
os nós adjacentes que fazem parte da mesma rota.
Valor unitário:
É o valor (Cij) de ligação entre dois nós adjacentes. Podemos
entender valor como: capital, tempo, distância, quantidade de fluxo,
etc.
Os custos de roteirização (determinação da rota) são FIXOS.
Aplicação – Vehicle Routing Problem – VRP
Algoritmo da Árvore Geradora
1º PASSO: Desenhar o nó origem (raiz da árvore) e as ligações
diretas, desse nó para os outros nós da rede.
2º PASSO: Acumular os custos das ligações sobre os nós
alcançados no passo anterior. O custo inicial do nó origem é 0.
3º PASSO: Repetir o algoritmo até que todas as rotas (caminhos),
para o nó destino da rede, tenham sido desenhados.
OBS: Em uma rota não são admitidos nós repetidos.
4º PASSO: Escolher a rota (ramo da árvore) que
apresenta o menor custo acumulado no nó destino.
Algoritmos – Vehicle Routing Problem – VRP
CASE:
O operador logístico TransXYZ
Ltda. fechou contrato para
transportar 25t de soja do Centro
de Distribuição (CD) localizado
na cidade “1” para um atacadista
localizado na cidade “6”.
O grafo representa as possíveis
ligações entre as cidades da
região e as distâncias (km).
A composição média dos custos
de transporte foi definida em
US$ 0,10 / t.km transportado.
Algoritmos – Vehicle Routing Problem – VRP
Solução:
O gerente de logística da
TransXYZ Ltda. usou o
algoritmo de “Árvore
Geradora” e determinou
a rota de menor
distância.
Rota ótima:
Cidades (nós): 1, 3, 5 e 6
Distância: 450 km
Custo total:
US$ 0,10 / km.t x 450
km x 25 t = US$
1.125,00
Algoritmos – Vehicle Routing Problem – VRP
Algoritmo dos Ajustes Sucessivos
1º PASSO: Construir a Matriz de Dispersão (matriz de adjacências
de um grafo valorado) que apresenta os custos Cij das ligações
diretas da rede.
OBS: Quando não houver ligação direta usar Cij igual a infinito e
na diagonal principal da matriz usar Cij igual a 0.
2º PASSO: Criar uma nova linha na matriz, para o nó origem,
com os seguintes custos: Cij = 0 quando i = j e Cij = infinito
quando i diferente de j.
3º PASSO: Selecionar o menor custo da nova linha.
Algoritmos – Vehicle Routing Problem – VRP
Algoritmo dos Ajustes Sucessivos
4º PASSO: Criar uma nova linha onde:
a) A célula do 3º passo deve ser fechada (cij = X);
b) As demais posições da linha são determinadas, comparando o
resultado da soma do custo do 3º passo e os custos da matriz, com
os custos da linha anterior, escolhendo-se o menor.
5º PASSO: Repetir o 3º e o 4º passo até que todos os Cij tenham
sido fechados.
OBS: Para identificar a rota mínima devemos indicar, na célula
fechada, a origem do Cij.
Algoritmos – Vehicle Routing Problem – VRP
Solução do case anterior:
Rota ótima:
Matriz de Adjacências:
Solução:
Algoritmos – Vehicle Routing Problem – VRP
Algoritmo de Indução e Ajuste
1º PASSO: Construir a Matriz de Dispersão (matriz de adjacências
de um grafo valorado) que apresenta os custos Cij das ligações
diretas da rede.
2º PASSO: Escolher uma célula (posição da matriz) e somar os Cij
das posições da linha, com os Cij das posições da coluna da célula
escolhida.
3º PASSO:Preencher a nova matriz, repetindo o 2º passo para
todas as células da matriz.
4º PASSO: Repetir o 2º e o 3º passo, até que a
matriz (Sn) construída no 3º passo seja igual a anterior (Sn-1).
Algoritmos – Vehicle Routing Problem – VRP
CASE:
Uma empresa de telefonia celular deseja minimizar o tempo total
de transmissão entre as estações (A,B,C,D) do sistema de uma
cidade.
Determinar, usando o algoritmo de Indução e Ajuste as conexões
entre as estações, de modo a minimizar os tempos entre todas as
estações do sistema.
Algoritmos – Vehicle Routing Problem – VRP
Desenvolvimento:
Rotas ótimas entre
todos os NÓS
Algoritmos – Vehicle Routing Problem – VRP
Algoritmo do “Caixeiro Viajante”
1º PASSO: Construir a Matriz de Dispersão (matriz de adjacências
de um grafo valorado) que apresenta os custos Cij das ligações
diretas da rede.
2º PASSO: Criar uma nova linha na matriz, preenchendo as suas
posições com os custos e a indicação das ligações diretas entre o nó
origem e os demais nós da rede.
OBS: Essa linha inicial apresenta as rotas do primeiro nível.
3º PASSO: Criar uma linha para cada rota do 2º passo, preenchendo
as posições dessas novas linhas com as indicações
das novas rotas e com os custos acumulados, em função
dos nós alcançados. Repetir todos os passos.
Algoritmos – Vehicle Routing Problem – VRP
CASE:
Uma distribuidora necessita determinar uma rota que passe,
somente uma vez, por todos os pontos de distribuição (A, B, C e D)
de uma região e retorne a origem.
Resolva o problema do “caixeiro viajante”, cujos coeficientes de
custo estão apresentados na tabela a seguir, determinando a rota que
percorre todos os nós da rede, a partir da origem B e o seu custo
total.
Algoritmos – Vehicle Routing Problem – VRP
Desenvolvimento:
Rotas ótimas
Algoritmos – Vehicle Routing Problem – VRP