ROTEIRIZAÇÃO
Parte II
Marcone Jamilson Freitas Souza
http://www.decom.ufop.br/prof/marcone
Problema de Roteamento de Veículos
SUMÁRIO
Aproximações para o cálculo da distância
Princípios para uma boa roteirização e
programação de veículos
Roteamento periódico de veículos
Roteirização probabilística
Problema das p-medianas
Metaheurísticas



Simulated Annealing
Busca Tabu
Algoritmos Genéticos
Aproximações para o
cálculo da distância
Distância percorrida por um veículo
em uma rota:



Distância do depósito ao bolsão de
entrega;
Distância percorrida dentro do bolsão;
Distância do bolsão ao depósito.
Aproximações para o
cálculo da distância
Nem sempre se dispõe de dados
exatos sobre todos os pontos de
entrega;
Aplicar fórmulas aproximadas para se
planejar o sistema de distribuição
 Dreal = k1 * Dreta
 k1 obtido por amostragem

DAB  ( x A  xB )  ( y A  y B )
2
2
Aproximações para a distância
percorrida dentro do Bolsão
Se o bolsão não tiver forma muito
irregular:
L  k0  k1  A n
A = área do bolsão (Km2)
n = número de clientes visitados
k0=0,765
k1=coeficiente de correção
Aproximações para a distância
percorrida dentro do Bolsão
Exemplo: Para um roteiro com n=50
clientes, em um bolsão com área A=4Km2,
tomando-se k1=1,40 tem-se:
L  k0  k1  A n 
 0,7651,40 4  50  15,15Km
Aproximações para a distância
percorrida dentro do Bolsão
Conhecendo-se a densidade  da
região (clientes por Km2), pode-se
reescrever L como:
L  k0  k1  A  n  k0  k1 
L
k0  k1  n

n

n
Tempo para completar um
roteiro
Tempo de ciclo (em horas) para se
completar um roteiro (tp em minutos):
2  k1  d k0  k1  n n  t p
TC 


V1
60
V2 
Tempo de deslocamento
do depósito ao bolsão e
vice-versa
Tempo de
parada total
Tempo de deslocamento
dentro do bolsão
Tempo para completar um
roteiro
Exemplo: Para o exemplo anterior,
considerando V1=35Km/h, V2=30Km/h e
tp=7 minutos, tem-se:
2  k1  d k0  k1  n n  t p
TC 


V1
60
V2 
2 1,4012 0,7651,40 50 50 7
TC 


35
60
30 12,5
TC  5,83h
Roteiro restrito pela
capacidade útil do veículo
Seja W a capacidade útil (em Kg) do veículo
e q a demanda média dos clientes
Número máximo de visitas do veículo no
roteiro:
W
n
q
Área do bolsão que pode ser visitada:
n
W
AW  
  q
Roteiro restrito pela
capacidade útil do veículo
Exemplo: Se o serviço de entrega for
realizado por um veículo de capacidade
W=3.980Kg de capacidade útil, em uma região
com densidade média =12,5 clientes/Km2 e
demanda média de clientes de 30 Kg, obtémse:
n
W
AW  
  q
3980
2
AW 
 10,6 Km
12,5  30
Roteiro restrito pela jornada
diária de trabalho
Fazendo-se TC = 8 horas na expressão
do tempo de ciclo de um roteiro e
extraindo-se o valor de n, obtém-se:
2  k1  d
8
V1
n
k0  k1 t p

V2 d 60
Roteiro restrito pela jornada
diária de trabalho
Dividindo-se a expressão anterior por 
obtém-se a área máxima do bolsão
restrita pela jornada de trabalho:
2  k1  d
8
1
V1
AT 

k0  k1 t p 

V2 d 60
Roteiro restrito pela jornada
diária de trabalho
Exemplo: Para o exemplo considerado,
tem-se:
2  k1  d
8
1
V1
AT 

k0  k1 t p 

V2 d 60
2 1,4012
8
1
2
35
AT 

 4,44 Km
0,7651,40 7 12,5

60
30 12
Roteiro restrito pela jornada
diária de trabalho
A área A do bolsão é o menor valor
entre AW e AT;
No exemplo considerado, o sistema está
limitado pela duração da jornada diária
de trabalho;
A partir dessa área, calculam-se:




Número de clientes a serem atendidos;
Carregamento do veículo;
Tempo de ciclo;
Custos operacionais.
Princípios para uma boa roteirização
e programação de veículos
1. Carregar os veículos com volumes de
paradas que estão próximas entre si;
RUIM
MELHOR
Princípios para uma boa roteirização
e programação de veículos
2. As paradas em dias diferentes devem ser
combinadas para produzir agrupamentos densos;
RUIM
MELHOR
Princípios para uma boa roteirização
e programação de veículos
3. Construir rotas começando com a parada mais
distante do depósito;
• Construir rota em torno da parada mais distante do
depósito e então trabalhar a volta ao depósito;
• A capacidade atribuída ao veículo deve ser preenchida
pela seleção do conjunto mais denso de paradas próximo a
essa parada mais distante;
• Após fazer a rota de um veículo, selecione outro e
identifique a parada remanescente mais distante do
depósito
• Prosseguir até que todas as paradas tenham sido
atendidas
Princípios para uma boa roteirização
e programação de veículos
4. A sequência das paradas em uma rota rodoviária
deve formar um padrão de gota-d’água;
RUIM
BOA
Princípios para uma boa roteirização
e programação de veículos
5. As rotas mais eficientes são construídas usando os
maiores veículos disponíveis;
• Veículos maiores conseguem atender a um maior
número de paradas, minimizando a distância ou o
tempo total requerido para servir as paradas;
• Veículos maiores devem ser alocados primeiro;
Princípios para uma boa roteirização
e programação de veículos
6. As coletas devem ser combinadas com as rotas de
entrega, ao invés de serem deixadas para o final
das rotas;
• As coletas devem ser feitas, tanto quanto possível,
durante as entregas de forma a minimizar a
quantidade de cruzamentos de trajeto que podem
ocorrer quando tais paradas são servidas depois que
todas as entregas foram feitas
Princípios para uma boa roteirização
e programação de veículos
7. Paradas isoladas de um agrupamento de rota são
boas candidatas para um meio alternativo de
entrega;
Princípios para uma boa roteirização
e programação de veículos
8. Janelas de tempo estreitas devem ser evitadas;
• Restrições da janela de tempo nas paradas, quando
estreitas, podem gerar rotas muito ruins, fora dos
padrões ideais;
• Renegociar o intervalo da janela de tempo;
Roteamento Periódico de
Veículos
Um conjunto de n clientes
Um conjunto de veículos
Um período de planejamento de t dias
Uma demanda qi associada a cada
cliente
Um custo associado ao atendimento de
cada cliente
Problema: Determinar as rotas dos
veículos no período
Roteamento Periódico de
Veículos
Um conjunto de n clientes
Um conjunto de veículos
Um período de planejamento de t dias
Uma demanda qi associada a cada
cliente
Um custo associado ao atendimento de
cada cliente
Problema: Determinar as rotas dos
veículos no período
Roteamento Periódico de
Veículos: Exemplo
Depósito
Segunda
Terça
Quarta
Roteamento Periódico de
Veículos: Exemplo
Depósito
Segunda
Terça
Quarta
Roteamento Periódico de
Veículos: Exemplo
Depósito
Segunda
Terça
Quarta
Roteamento Periódico de
Veículos: Exemplo
Depósito
Segunda
Terça
Quarta
Roteamento Periódico de
Veículos: Outra situação
Cada cliente é atendido uma única vez no período de 3 dias!
Roteamento Periódico de
Veículos: Outra situação
Cada cliente é atendido uma única vez no período de 3 dias!
Roteamento Periódico de
Veículos: Outra situação
Cada cliente é atendido uma única vez no período de 3 dias!
ROTEIRIZAÇÃO PROBABILÍSTICA
Clientes nem sempre emitem pedidos
de forma regular
Estratégias a adotar:
1.
2.
Definir um roteiro ótimo a priori,
eliminando os clientes sem pedidos;
Redefinir a roteirização sempre que
houver alterações na lista de clientes a
serem visitados.
VANTAGENS DE UM ROTEIRO ÚNICO
Roteirizador aplicado uma única vez,
dispensando a alimentação contínua
do sistema;
Maior eficiência no trabalho do
motorista

memorização mais fácil do percurso,
passando pelos mesmos locais
aproximadamente à mesma hora;
DESVANTAGENS DE ALTERAR O
ROTEIRO
Alimentação contínua do
Roteirizador;
Diminuição na eficiência de
trabalho dos motoristas

Nem sempre alterar
sistematicamente o roteiro é
financeiramente compensador;
EXEMPLO
Cliente
x
y
Prob. visita
1
2
3
7,50
8,10
8,50
7,80
6,95
8,20
1,0
1,0
1,0
4
5
6
7
8
9
10
8,75
6,20
6,00
5,90
5,45
5,00
5,00
6,50
6,60
6,00
7,45
8,30
7,60
6,80
1,0
1,0
1,0
1,0
1,0
0,2
0,2
EXEMPLO
EXEMPLO
EXEMPLO: Roteiro ótimo
7
L = 11,6 Km
2
D
8
6
4
9
1
3
5
D->2->3->1->4->5->9->8->7->6->D
EXEMPLO: Roteiro sub-ótimo
7
L = 12,2 Km
2
D
8
6
4
9
1
3
5
D->2->3->1->5->4->6->9->8->7->D
EXEMPLO: Roteiro sub-ótimo
7
L = 12,2 Km
2
D
8
6
4
9
1
3
5
D->2->3->1->5->4->6->9->7->D
Roteiro quando o cliente 8 não é visitado
EXEMPLO: Roteiro sub-ótimo
7
L = 11,2 Km
2
D
8
6
4
9
1
3
5
D->2->3->1->5->4->6->8->7->D
Roteiro quando o cliente 9 não é visitado
EXEMPLO: Roteiro sub-ótimo
7
L = 10,5 Km
2
D
8
6
4
9
1
3
5
D->2->3->1->5->4->6->7->D
Roteiro quando os clientes 8 e 9 não são visitados
EXEMPLO
Qual a extensão média dos roteiros
após um longo período?
Uma visita ao cliente 8 ou 9 ocorre
20% das vezes
Probabilidade de um desses clientes
não ser visitado = 80%
Admitir independência entre os
eventos
Extensão esperada
Evento
A: Todos
visitados
B: Cliente 8 não
visitado
C: Cliente 9 não
visitado
D: Clientes 8 e
9 não visitados
Total
Probabilidade
0,2 x 0,2 = 0,04
Extensão
Valor
(Km)
esperado
LT = 12,2
0,49
0,8 x 0,2 = 0,16
L8 = 12,2
1,95
0,2 x 0,8 = 0,16
L9 = 11,2
1,79
0,8 x 0,8 = 0,64
L8,9 = 10,5
6,72
-
10,95
1,00
Observações
Extensão média quando o roteiro
utilizado é o ótimo = 11,25 Km (Valor
obtido repetindo-se o procedimento
anterior)
11,25 / 10,95 = 1,027
Extensão média é 2,7% maior do
que partindo de uma solução subótima!
LOCALIZAÇÃO:
Problema das p-medianas
Dado um conjunto de n clientes
Para cada cliente há uma demanda
qi
Existe matriz de distâncias dij
Necessário instalar p facilidades
Problema: Onde instalar as p
facilidades?
LOCALIZAÇÃO:
Problema das p-medianas
Sejam dados:
n locais
qi = demanda do local i
dij  distânciaentreos locais i e j
 Variável de decisão:
1
xij  
0
se o locali for atendidopela facilidade j
caso contrário
1
yj  
0
se a facilidade j for instalada
caso contrário
LOCALIZAÇÃO:
Problema das p-medianas
n
n
min  qi dij xij
i 1 j 1
n
x
j 1
ij
 1 i  1,...,n
xij  y j i, j  1,...,n
n
y
j 1
j
p
xij {0,1} i, j  1,...,n
y j {0,1} j  1,...,n
LOCALIZAÇÃO: Problema
das p-medianas capacitado
Dado um conjunto de n clientes
Para cada cliente há uma demanda qi
Existe matriz de distâncias dij
Necessário instalar p facilidades
Cada facilidade possui uma capacidade
capj
Problema: Onde instalar as p
facilidades?
LOCALIZAÇÃO: Problema
das p-medianas capacitado
Sejam dados:
n locais
qi = demanda do local i
capj = capacidade da facilidade j
cij = custo de atendimento do local i pela
facilidade j
 Variável de decisão:
1
xij  
0
1
yj  
0
se o locali for atendidopela facilidade j
caso contrário
se a facilidade j for instalada
caso contrário
LOCALIZAÇÃO: Problema
das p-medianas capacitado
n
n
min  qi cij xij
i 1 j 1
n
x
j 1
n
ij
 1 i  1,...,n
q x
i 1
n
i ij
y
j 1
j
 capj y j j  1,...,n
p
xij {0,1} i, j  1,...,n
y j {0,1} j  1,...,n
Problema da Localização de
Unidades Capacitado
Dado um conjunto de n clientes
Para cada cliente há uma demanda qi
Existe matriz de distâncias dij
Necessário instalar p facilidades
Cada facilidade possui uma capacidade
capj
Existe custo fixo de instalação
Problema: Onde instalar as p
facilidades?
Problema da Localização de
Unidades Capacitado
Sejam dados:
n locais, fj = custo de instalação da facilidade j
qi = demanda do local i
capj = capacidade da facilidade j
cij = custo de atendimento do local i pela
facilidade j
 Variável de decisão:
1
xij  
0
1
yj  
0
se o locali for atendidopela facilidade j
caso contrário
se a facilidade j for instalada
caso contrário
Problema da Localização de
Unidades Capacitado
n
n
n
min  qi cij xij   f j y j
i 1 j 1
n
x
j 1
n
ij
j 1
 1 i  1,...,n
q x
i 1
n
i ij
y
j 1
j
 capj y j j  1,...,n
p
xij {0,1} i, j  1,...,n
y j {0,1} j  1,...,n
EXEMPLO