8 ENG1545 Problemas de Roteirização

Prévia do material em texto

DISTRIBUIÇÃO FÍSICA
ENG1545
Graduação em Engenharia de Produção
Prof. Rafael Martinelli – martinelli@puc-rio.br
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
8. PROBLEMAS DE 
ROTEIRIZAÇÃO
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Qualquer processo de Distribuição Física incorpora, nas pontas, um roteiro de coleta e/ou
distribuição, no qual o veículo visita, de uma só vez, um determinado número de clientes
localizados numa zona de uma região.
1
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
1. Definição de Rotas e Roteirização
Coloca-se frequentemente o problema de saber qual a rota, ou rotas, que permitem prestar
determinado serviço a um conjunto de pontos (clientes) minimizando uma determinada
função objetivo (distância total percorrida, tempo de percurso ou custo total).
ROTA: define o percurso a efetuar por um veículo para percorrer o clientes que deve servir.
PROBLEMA DE ROTEIRIZAÇÃO: problema de distribuição no qual veículos localizados em um
depósito central devem ser programados para visitar clientes geograficamente dispersos, de
modo a atender as suas demandas. O problema está normalmente restringido devido à
capacidade dos veículos.
Christofides (1985)
A definição das rotas de entrega de um produto (duração, percurso, frequência) tem
influência:
• na política de estoque da cadeia de suprimentos.
• na constituição da frota.
• no nível de serviço prestado ao cliente.
2
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Os transportes representam 54% dos custos logísticos no Brasil (ILOS, 2013). A otimização da
função de transportes permite reduzir consideravelmente o custo logístico total.
No Brasil o custo por unidade transportada por distância tendo o custo do modal rodoviário como
referência é da seguinte ordem:
• 6,1 vezes maior do que o ferroviário.
• 3,0 vezes maior do que o aquaviário.
• 8,2 vezes menor do que o aéreo.
Lima (2006)
Um Problema real de roteirização é definido por três fatores fundamentais:
• Decisões
• Objetivos
• Restrições
Considera-se que um ou mais veículos partem de um ponto inicial, percorrem vários clientes e, no
final da jornada de trabalho, retornam ao ponto inicial.
As decisões operacionais concernantes aos transportes devem incidir em dois aspetos:
• Otimização da frota (minimização do número de veículos e maximização da utilização)
• Otimização das rotas (definição dos caminhos mais curtos e das zonas de entrega)
Nota: indiretamente estão atreladas a decisões de estocagem.
3
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
4
Que objetivos podem ser definidos?
E que restrições?
E que tipo de decisões precisam ser tomadas?
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Função Objetivo:
• Minimização dos custos totais de distribuição incluindo custos fixos (capital dos
veículos, salários, despesas de licenciamento, seguros, taxas, etc.) e custos variáveis
(custos do veículo dependentes da distância percorrida).
• Minimização da distância total percorrida.
• Minimização do número total de veículos.
• Maximização da função de utilidade (nível de serviço e/ou prioridades dos clientes).
NOTA: um dos objetivos gerais da roteirização é proporcionar um serviço de alto nível aos
clientes mantendo um baixo custo operacional e de capital (maior desafio da logística => trade-
off: nível de serviço vs. custo)
Variáveis de decisão:
• Roteiro a ser percorrido por cada veículo.
• Qual veículo é atribuído para cada cliente.
• Qual a quantidade de carga transportada para cada cliente da rota.
• Tempo de início de atendimento do primeiro cliente da rota.
5
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Restrições dos veículos:
• Limite de capacidade.
• Limite com relação ao tipo de carga.
• Operação e carga e descarga.
• Número e tipo de veículos disponíveis.
Restrições com os clientes:
• Janela de tempo dos clientes.
• Atendimento total ou parcial das demandas.
• Tempo máximo permitido para a carga e descarga.
• Necessidade ou restrição de serviço em algum dia específico da semana/mês.
• Disponibilidade de área para estacionamento do veículo.
Quais são os aspetos que devemos considerar ao caracterizar o problema?
6
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Tipo de operação:
• Coleta.
• Entrega.
• Coleta e entrega simultaneamente.
• Logística reversa.
Tipo de carga:
• Única ou carga de lotação.
• Múltiplas cargas ou carga fragmentada.
Tipo de demanda:
• Determínistica.
• Estocástica.
Localização da demanda:
• Localizada somente nos arcos.
• Localizada somente nos nós.
• Localizada nos nós e nos arcos.
7
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Tamanho da frota:
• Limitada.
• Ilimitada.
Tipo de frota:
• Homogênea.
• Heterogênea.
Depósito e localização de veículos:
• Um único depósito ou vários depósitos.
• Quantidade de produtos disponíveis no depósito central para entrega aos clientes.
• Número de bases de origem e destino dos veículos.
Jornadas de trabalho:
• Duração.
• Horário de almoço e outras interrupções.
• Permissão para viagem com mais de um dia de duração.
• Número de tripulantes por veículo.
8
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Pagamento dos tripulantes:
• Por jornada de trabalho.
• Por produtividade.
• Jornada e horas extra.
Estrutura da rede:
• Direcionada.
• Não direcionada.
• Mista.
• Euclidiana.
Horizonte de planejamento:
• Curto prazo.
• Longo prazo.
Outras hipóteses:
• Cada veículo só pode visitar um cliente uma única vez durante a rota.
• Um cliente pertence a uma única rota ou a várias rotas.
• Quando um veículo visita um cliente da rota todos o clientes da rota são visitados.
Rotas para um único veículo: um único veículo
percorre todos os clientes; o problema consiste em
determinar qual a ordem de visita aos clientes.
Rotas para múltiplos veículos: múltiplos veículos
servem múltiplos clientes, sendo que cada veículo
tem sua rota e seus clientes específicos.
Normalmente a alocação de clientes a veículos é
limitada por restrições de capacidade do veículo,
tempo de percurso, distância percorrida, nº máximo
de paradas.
9
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
(Mundo-real)
PROBLEMA
IMPLEMENTAÇÃO
(da solução)
MODELO
(Matemático)
simplificação SOLUÇÃO
(modelo)
Resolve Válidos ? Y
N
Ingredientes de um problema
• Decisões: identificar as possíveis soluções; definição das variáveis de decisão.
e.g.: localização dos CD, atribuição de veículos, capacidade.
• Objetivos: definir critérios de avaliação capazes de mostrar que uma decisão (ou 
conjunto de decisões) é preferível às outras.
e.g., minimizar custos sociais, maximizar acessibilidade agregada.
• Restrições: identificar quais as condicionantes para as decisões a serem tomadas
e.g.: Lógicas, Físicas (e.g., continuidade), Técnicas (e.g., capacidade), Orçamentais, Legais, 
Metas (e.g., satisfazer toda a demanda, cumprir critérios ambientais).
Revisão
REVISÃO!
2. Revisão de Modelos de Otimização
10
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
)( xx

 fzopt 
0 )(













x

g
sujeito a
x: variáveis de decisão
representam as decisões que têm de ser tomadas
z:valor da solução encontrada
f: função objetivo
quantifica o valor da solução óptima
g: restrições
representam condições a satisfazer ou/e objetivos a cumprir
Outros aspectos:
• Variáveis contínuas ou inteiras  Otimização contínua, discreta ou mista
• Restrições lineares ou não lineares  Otimização linear ou não linear (e.g. quadrática)
REVISÃO!
11
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
3. Classificação P. Roteirização, Bodin et al. (1983)
Os problemas de roteirização podem ser classificados em diversas categorias e tipos. Dada a
multiplicidade de fatores e parâmetros possíveis não existe um consenso quanto a uma classificação
geral. Ainda assim uma das mais aceites é a de Bodin et al. (1983).
• Problemas de roteirização pura: não tem restrições temporais (horário de atendimento dos
clientes), nem relações de precedência entre os clientes. Considera apenas aspetos espaciais e o
objetivo é determinar um conjunto de roteiros viáveis com o menor custo possível.
• Problemas de programação de veículos: há restrições horárias preestabelecidas para cada
atividade (horário de chegada, horário de saída das lojas, horário do depósito, parada para
reabastecimento, etc.). Considera aspetos espaciais e temporais.
• Problemas combinados de roteirização e programação de veículos: há restrições de precedência
entre tarefas e/ou restrições de janela de tempo. Restrições de precedência ocorrem por
exemplo quando a entrega de um produto tem de ser precedida da sua coleta. As janelas de
tempo marcam os períodos nos quais os clientes podem ser atendidos.
12
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
4. Problemas clássicos de roteirização
Um dos problemas mais comuns nas áreas urbanas é a definição de rotas para transportar bens ou
pessoas. A literatura clássica aponta dois problemas em particular:
• Edge-covering: aqueles em que é necessário cobrir exaustivamente todos os segmentos de uma
dada região.
EXEMPLOS?
Problema do Carteiro Chinês (Chinese Postman Problem, CPP)
• Node-covering: aqueles em que é necessário visitar todos os pontos (locais onde a demanda está
concentrada) de uma dada região por forma a providenciar um serviço ou coletar bens.
EXEMPLOS?
Problema do Caixeiro Viajante (Travel Salesman Problem, TSP)
13
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
4. Problemas clássicos de roteirização
Um dos problemas mais comuns nas áreas urbanas é a definição de rotas para transportar bens ou
pessoas. A literatura clássica aponta dois problemas em particular:
• Edge-covering: aqueles em que é necessário cobrir exaustivamente todos os segmentos de uma
dada região.
Ex.: limpeza de ruas, limpeza de neve depois de uma tempestade, entrega de correio, coleta de
lixo urbano, distribuição e jornais porta a porta, etc..
Problema do Carteiro Chinês (Chinese Postman Problem, CPP)
• Node-covering: aqueles em que é necessário visitar todos os pontos (locais onde a demanda está
concentrada) de uma dada região por forma a providenciar um serviço ou coletar bens.
Ex.: autocarros escolares, distribuição de jornais pelos quiosques, coleta de moedas dos
orelhões,etc..
Problema do Caixeiro Viajante (Travel Salesman Problem, TSP)
14
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
PROBLEMA DO CARTEIRO CHINÊS, PCC: consiste em determinar um único roteiro com o
menor custo possível que permita o carteiro chinês (veículo) visitar todos os arcos
(clientes) de uma rede uma única vez. Não há restrições de capacidade e a demanda é
determinística.
Problema típico do carteiro que está entregando cartas.
• Arcos = rua onde cartas precisam ser entregues
• Nós = interseção das ruas
O carteiro precisa percorrer cada rua para entregar as cartas, mas deseja minimizar a
quantidade de travessias repetidas necessárias.
O PCC está ligado ao Circuito de Euler. Distingue-se do circuito euleriano por nele ser
permitida a repetição de arcos. É claro que o circuito euleriano, quando existente no grafo,
é a solução do carteiro chinês.
O carteiro chinês pode ser considerado sobre um grafo orientado ou não.
5. Problema do Carteiro Chinês
15
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Formulação matemática do Problema do Carteiro Chinês

 

n
1i
n
1j
ijijxc z min
inteiro e 0 x 
 1-S x 
),(( 1xx 
n)1,2,...,(i 0 x - x s.a.
ij
n
1i
n
1j
ij
 jiij
n
1j
n
1j
jiij





 
 
 
Aji
Variável de Decisão:
Xij => número de vezes que a aresta (i,j) é percorrida de i para j
Parâmetro:
Cij = > comprimento ou o custo da aresta (i,j)
16
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
6. Problema do Caixeiro Viajante
Em 1857 Rowan Hamilton propôs um jogo 
(“Around The World”) que era feito sobre 
um dodecaedro em que cada vértice 
estava associado a uma cidade 
importante na época.
O desafio consistia em encontrar uma rota 
através dos vértices do
dodecaedro que iniciasse
e terminasse em uma
mesma cidade sem
nunca repetir
uma visita.
O PCC está ligado ao Circuito de Hamilton. Distingue-se do circuito hamiltoniano por nele
ser permitida a repetição de arcos.
17
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
As solução do jogo passaram a denominar-se ciclos hamiltonianos (ainda que Hamilton não tenha
sido o primeiro a propor esse problema).
18
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
PROBLEMA DO CAIXEIRO VIAJANTE, TSP: consiste em determinar um único roteiro com o menor
custo possível que permita o caixeiro-viajante (veículo) visitar todos os nós (clientes) de uma rede
uma única vez. O problema é baseado num único depósito e o veículo deve sair e retornar à mesma
base. Não há restrições de capacidade e a demanda é determinística.
Trata-se de um dos problemas de otimização mais estudados na literatura. É formulado da seguinte
forma: dada uma lista de cidades e distâncias entre cada par delas, qual o circuito mais curto que
visita cada cidade uma única vez e regressa à origem?
Se o caixeiro não repetir nenhuma cidade então trata-se de um circuito de Hamilton.
A grande dificuldade em resolver um TSP (simétrico) está associada ao número de soluções
alternativas existentes. Na verdade há (n-1)! Maneiras diferentes de ordenar os ciclos de visitas. Isso
representa (n-1)!/2 soluções alternativas para o TSP (cada ciclo pode ser percorrido em duas
direções sendo a distância a mesma).
Devido à sua complexidade é normalmente resolvido através de processos heurísticos.
19
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Formulação matemática do TSP

i j
ijijxc z min



N
1i
ij N)1,2,...,j (para 1 x s.a.



N
1j
ij N)1,2,...,i (para 1 x
0c ,c , 1ou 0 xos ijiiij  MTodos
(1)
(2)
(3)
cij = distância da cidade i à cidade j, 
cii = M, valor grande (garante que o 
caixeiro não vá à cidade i logo após tê-la 
deixado ). 
xij = 1 se a solução considera ir de i à j, 
caso contrário, xij = 0.
(1) - comprimento total de todos os arcos
incluídos no percurso.
(2) asseguram que se passe uma vez só
por cada cidade.
(3) obrigam que se deixe cada cidade uma
vez só.
O problema do caixeiro viajante tem solução ótima (matemática), contudo para problemas com mais
de 20 nós o tempo computacional pode ser inviável. Para superar este obstáculorecorre-se
normalmente a algoritmos heurísticos de forma a obter uma “boa” solução num espaço de tempo
razoável. Mathur & Solow (1993) em Gutierez (1994)
20
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
7. Outros Problemas de Roteirização de Veículos
TSP – Problema do caixeiro viajante
CPP – Problema do carteiro chinês
MTSP Problema de múltiplos caixeiros-viajantes (multiple traveling salesman problem)
Extensão do problema do caixeiro-viajante, onde, ao invés de um único roteiro, determinam-se
múltiplos roteiros. O problema consiste em determinar múltiplos roteiros com o menor custo
possível, de modo que cada caixeiro-viajante deva visitar pelo menos um nó da rede, e cada nó
deve ser visitado uma única vez. O problema é baseado em um único depósito e o veículo deve
retornar e sair da mesma base. Não há restrições de capacidade de veículos e a demanda é
determinística.
VRP Problema clássico de roteirização de veículos (vehicle routing problem)
Tem como objetivo encontrar um conjunto de rotas de menor custo possível (minimizar o custo
total de viagem, a distância total percorrida etc.), iniciando e terminando no depósito, de forma
que a demanda de todos os nós é atendida . A demanda é determinística. Este problema é uma
extensão do problema de múltiplos caixeiros-viajantes, em que se acrescenta a restrição de
capacidade de veículos (e eventualmente de tempo/distância). Algumas formulações também
apresentam restrições de tempo máximo de viagem.
MDVRP VRP com múltiplos depósitos (multidepot vehicle)
21
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
CARP VRP com demanda em arcos (capacitated arc routing problem)
SVRP VRP com demanda estocástica (stochastic vehicle routing problem)
VRPSD VRP com entregas fracionadas (vehicle routing problem with split deliveries)
Cada ponto de demanda pode ser abastecido por mais de um veículo.
FSVRP VRP com dimensionamento frota homogênea de veículos (fleet size and vehicles routing
problem)
Determinar o número de veículos necessários (frota ilimitada). Os veículos são homogêneos em
custo e capacidade.
HFFVRP VRP com frota heterogênea fixa (heterogeneous fixed fleet vehicle routing problem )
O número de veículos de cada tipo é limitado (fixo). O objetivo é minimizar a soma dos custos fixos
e dos custos variáveis que podem ser dependentes ou não do tipo de veículo.
FSMVRP VRP com dimensionamento de uma frota de veículos heterogênea (fleet size and mix
vehicle routing problem)
Generalização do FSVRP com frota heterogênea.
22
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
PVRP VRP multiperíodo ou periódico (periodic vehicle routing problem – PVRP)
Extensão do problema clássico de roteirização de veículos onde o horizonte de tempo passa a ser
M dias ao invés de um único dia.
TDVRP VRP com tempo dependente (time dependent vehicle routing problem)
O tempo de viagem entre dois clientes ou entre um cliente e o depósito depende, além da distância
entre pontos, do horário do dia.
VRSPTW VRP com janelas de tempo (vehicle routing and scheduling problem with time windows)
Adiciona as restrições de janela de tempo ao VRP clássico.
VRSPSTW VRP com janelas de tempo flexível (vehicle routing and scheduling problem with “soft”
time windows)
As janelas de tempo podem ser violadas mediante o pagamento de penalidades.
DVRSPTW VRP com janelas de tempo dinâmicas (dynamic vehicle routing and scheduling problem with
“soft” time windows)
As janelas de tempo vão sendo atualizadas durante a operação de entregas.
PDP Problema de coleta e entrega, (pickup and delivery problems)
Extensão do problema de roteirização de veículos (VRP), acrescentando-se relações de precedência
entre clientes, no qual a tarefa de coleta de um cliente deve preceder a de entrega no ponto de
destino. As cargas são transportadas do depósito aos clientes e entre os clientes, resultando na
relação de precedência.
23
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
24
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Roteirização sem restrições: a separação dos clientes por roteiros já foi realizada previamente e as
restrições de tempo e capacidade estão resolvidas. O problema a ser resolvido é o de encontrar a
sequência de visitas aos clientes que torna mínimo o percurso dentro do bolsão de distribuição.
• Métodos de construção do roteiro.
• Métodos de melhoria do roteiro: buscam aperfeiçoar uma solução inicial obtida.
A maior parte dos problemas está, no entanto, condicionada a limites de tempo e/ou capacidade.
Deve-se, inclusive muitas vezes, dividir a região em bolsões. Aplicam-se aos TSPs.
Roteirização com restrições: o processo de roteirização ocorre simultaneamente ao processo de
divisão da região em bolsões de entrega. Aplicam-se aos VRPs.
• Método de Varredura: de computação rápida mas com um erro médio maior.
• Método das economias, Clarke e Wright (C&W).
8. Métodos de Roteirização
25
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Método pouco eficaz mas
rápido. É útil para obter uma
solução inicial para o PCV.
1
1
1,41
A
B
1
1
1,41
A
B
C
1
1
1,41
A
B
C
D
1
1
1,41
A
B
C
D
Ponto
Inicial
Em geral a solução obtida
não é satisfatória. É
necessária a aplicação de
métodos de melhoria.
1. Elege-se o nó inicial e liga-se
ao ponto mais próximo.
2. Partir do novo nó e repetir o
processo.
3. Terminar quando não houver
mais nós livres.
d1 = 1 d2 = 2,8 d3 = 4,1 d4 = 4,2
dT = 12,1
d1 d2
d3
d4
C
D D
Métodos de construção do roteiro: MÉTODO DO VIZINHO MAIS PRÓXIMO
9. Roteirização sem restrições
26
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
EXERCÍCIO: Uma carrinha de distribuição deve sair de um armazém (nó 0) e percorrer 3 lojas da
empresa (nós 1, 2 e 3) para entregar mercadoria, retornando depois ao armazém. Pretende-se
definir uma rota que permita percorrer a menor distância possível. As distâncias (km) são dadas na
tabela. Resolva pelo vizinho mais próximo.
Vértice inicial: 0
1 2 3
0 9 16 7
1 11 8
2 10
0
1
2
3
27
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
EXERCÍCIO: Uma carrinha de distribuição deve sair de um armazém (nó 0) e percorrer 3 lojas da
empresa (nós 1, 2 e 3) para entregar mercadoria, retornando depois ao armazém. Pretende-se
definir uma rota que permita percorrer a menor distância possível. As distâncias (km) são dadas na
tabela. Resolva pelo vizinho mais próximo.
Vértice inicial: 0
Vértice, não selecionado mais próximo de 0: 3
Vértice, não selecionado mais próximo de 3: 1
Vértice, não selecionado mais próximo de 1: 2
0 3 1 2 0
Distância Total = 42km
1 2 3
0 9 16 7
1 11 8
2 10
0
1
2
3
28
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Ex 7a. Problemas de Roteirização
EXERCÍCIO: Um veículo de distribuição necessita visitar um conjunto de localidades,
pretendendo-se percorrer uma distância total tão pequena quanto possível. A viagem inicia-se
e termina na localidade 0. As distâncias (km) são dadas na tabela. Resolva pelo vizinho mais
próximo.
1 2 3 4 5 6
0 15 10 17 23 27 22
1 17 29 32 15 21
2 13 17 20 13
3 17 27 16
4 21 20
5 19
29
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
1
1
1,41
A
B
C
D
d4 = 4,2
d4
Pode-se perceber à primeira vista que a solução não é ótima, 
pois existe um cruzamentona rota obtida. 
NOTA: Havendo cruzamento, poder-se-á substituí-lo, com vantagem, por uma ligação não cruzada.
Um teorema da geometria afirma que um lado do triângulo é 
menor ou igual à soma dos outros 2 lados. 
Temos então IK ≤ IC + CK e JL ≤ JC + CL
K
I
C
J
L
K
I
C
J
L
≥
30
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Métodos de construção do roteiro: HEURÍSTICA DA INSERÇÃO MAIS PRÓXIMA
Método aproximado mais trabalhoso mas que produz por norma resultados mais satisfatórios.
1º Passo: Circuito inicial composto pelo nó de origem e o nó mais próximo deste. “𝑖, 𝑗, 𝑖”
2º Passo: No sub ciclo corrente, calcular para cada ligação do tipo (𝑖, 𝑗) a inserção do vértice “𝑘”
(não selecionado) a que corresponda o aumento mínimo de distância dado por
𝑀𝑖𝑛 𝑐𝑖𝑘 + 𝑐𝑘𝑗 − 𝑐𝑖𝑗
3º Passo: Repetir o passo 2 até ter selecionado todos os vértices do grafo.
Nota: este algoritmo leva a que os últimos arcos adicionados representem, por norma, distâncias
muito grandes.
0k
j
i
j
i
31
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
A B C D E
A 16 12 18 16
B 10 18 20 20
C 18 20 18 16
D 14 18 10 8
E 8 12 12 12
A ABA=26 ACA=30 ADA=32 AEA=24
B BCB=38 BDB=38 BEB=32
C CDC=28 CEC=28
D DED=20
1º Passo:
ED D
A
B
C
A
B
C
14
18
10
16
20
16
8 12
8
12
12
18
20
18Vértice 
a inserir
Aumento da 
distância de D para E
Aumento da 
distância de E para D
A 14+16-8=22 8+18-12=14
B 30 20
C 18 18
2º Passo:
Inserimos o nó A entre E e D. Repetimos o processo.
Solução final: DEBACD com distância total = 60 km.
Ex 7b. Pretende-se definir uma rota que permita percorrer a menor distância possível entre 5 lojas
e voltar à loja de origem. As distâncias (km) são dadas na tabela. Resolva pela inserção mais
próxima.
32
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
MÉTODOS DE CONSTRUÇÃO DO ROTEIRO: Método do Ponto Mais Distante (mais eficiente)
3. Dentre os pontos não
incluídos no roteiro busca-se o
mais distante dos arcos que
formam o roteiro parcial.
4. Repetir 2. e 3. até todos
os nós serem incluídos.
1. Elege-se o ponto inicial e
liga-se ao ponto mais distante.
2. Busca-se o ponto mais
distante do roteiro parcial
existente (A-D).
Mais eficiente que o método
do Vizinho Mais Próximo!
1
1
1,41
A
B
Ponto
Inicial
d1 = 4,2
d1
C
D
1 1,41
A
B
d1=4,2 d2=4,1
d3=2,2
d1
C
D
1 1,41
A
B
d1
C
D
d1=4,2 d2=4,1
d3=2,2, d4=1
1 1
dT = 10,9
dt = 12,1
33
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Método do Ponto Mais Distante: exemplo Novaes (2001)
34
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Ex 7c. Problemas de Roteirização
EXERCÍCIO: Pretende-se definir uma rota que permita percorrer a menor distância possível entre 5
lojas e voltar à loja de origem. As distâncias (km) são dadas na tabela. Resolva pelo método do
ponto mais distante.
A B C D E
A 16 12 18 16
B 10 18 20 20
C 18 20 18 16
D 14 18 10 8
E 8 12 12 12
35
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Métodos de melhoria do roteiro: MÉTODO 2-OPT
O método parte de um roteiro inicial (obtido através de um outro método qualquer) e tenta
melhorá-lo de forma a diminuir o custo/tempo/distância total do roteiro.
O algoritmo do método 2-OPT processa-se da seguinte forma:
Passo 1: Iniciar o processo com o roteiro inicial gerado com o auxílio de um método de construção.
Passo 2: Removem-se 2 arcos do roteiro inicial e reconectam-se os nós que formam esses arcos.
• Se a solução for melhor (roteiro de menor extensão) aceitamos
• Caso contrário recusamos e mantemos os arcos originais. Escolhemos outros dois arcos e
repetimos o passo 2.
Passo 3: O processo repete-se até que não
seja possível conseguir nenhuma melhoria ao
fazer todas as trocas possíveis.
36
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
DE - FA
DF - EA
BC - DF
BD - CF
Manter esse novo roteiro se ele
tiver menor extensão, caso
contrário, manter roteiro anterior.
Terminar o processo quando
não houver mais melhoria ao
se fazer todas as trocas de
arcos possíveis.
O 2-OPT começa com um
roteiro inicial. Remover 2
arcos e adicionar 2 novos.
B
A
C
dT = 15,3
Solução obtida c/ o método 
do vizinho mais próximo
É a mesma solução obtida que 
foi obtida com o método de 
inserção do ponto mais distante
E F
D
Ponto
Inicial
B
A
C
dT = 16,6
> 15,3
E F
D
B
A
C
dT = 14,7
< 15,3
E F
D
B
A
C
dT = 12,1
< 14,7
E F
D
FA - BC
CA - BF
Recusar Aceitar Aceitar
NOTA: A orientação dos arcos que se mantém pode ser alterada.
37
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Métodos de melhoria do roteiro: MÉTODO 3-OPT
O método parte de um roteiro inicial (obtido através de um outro método qualquer) e tenta
melhorá-lo de forma a diminuir o custo/tempo/distância total do roteiro.
O algoritmo do método 3-OPT processa-se da mesma forma do 2-OPT com a diferença que
as alterações processam-se agora em cada passo a tomando 3 arcos invés de 2. Outra
diferença é que para trio de arcos a alterar são possíveis agora 7 configurações diferentes ao
invés de 1.
38
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
B
A
C
dT = 15,3
Solução obtida c/ o método do 
vizinho mais próximo
E F
D
Ponto
Inicial
B
A
C
dT = 16,3
> 15,3
E F
D
B
A
C
dT = 12,1
< 15,3
E F
D
FA - BC - DE
AC - EB – DF 
Recusar
FA - BC - DE
AE - BD - CF 
Aceitar
Manter esse novo roteiro se ele
tiver menor extensão, caso
contrário, manter roteiro anterior.
Terminar o processo quando
não houver mais melhoria ao
se fazer todas as trocas de
arcos possíveis.
O 3-OPT começa com um
roteiro inicial. Remover 3
arcos e adicionar 3 novos.
NOTA: A orientação dos arcos que se mantém pode ser alterada.
39
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Novaes (2001), Comparação de resultados dos métodos
Roteiro obtido através do Método do 
Vizinho mais Próximo.
Roteiro obtido através da aplicação do 
Método 3-OPT usando como roteiro 
inicial o do Vizinho mais próximo.
40
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Ex 7d. Problemas de Roteirização
2
4
1
5
3
6
1. Defina um roteiro pelo MÉTODO DE CONSTRUÇÃO: Método do Vizinho Mais
Próximo.
2. Melhore o roteiro utilizando o MÉTODO 2OPT.
41
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Roteirização Estática
com Janelas de Tempo
Projeto Final de Graduação
Gabriela Ruiz Thedim
Rafaela Gonçalves Ourofino
EXEMPLO DE APLICAÇÃO
42
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Processo em dois estágios. Primeiro atribuem-se as paradas (clientes) ao roteiro e depois se
determina a sequência das paradas na rota.
MÉTODO DE VARREDURA
Método de uso fácil e de computação rápida. Contudo por vezes distorce os resultados.
Recomendável quando são necessárias respostas rápidas para a formação de rotas por causa do
pouco tempo para operacionalizar o carregamento e expedição dos veículos, ou seja, é
principalmente utilizado em problemas muito dinâmicos, cujo tempo de reação é curto.
NOTA: A desvantagem é que produz, em média, um erro de 10% em relaçãoao ótimo absoluto
(Ballou, 1999).
10. Roteirização com restrições
Elaborar boas soluções para problemas de roteirização e programação de veículos torna-se mais
difícil ao serem impostas restrições adicionais. Janelas de tempo, caminhões múltiplos com
diferentes capacidades de peso e cubagem, jornada de trabalho, tempo máximo de permanência ao
volante, velocidades máximas, barreiras ao tráfego, etc.
43
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Passo 1 : Representar num mapa ou grafo todas as paradas (clientes) incluindo os depósitos.
Passo 2: Tomando o depósito como centro, definir um eixo passando por ele. Esse eixo geralmente
coincide com a linha horizontal (eixo das abscissas).
Passo 3: Pense o eixo como se fosse uma linha. Gire a linha no sentido horário, ou no sentido anti-
horário, até que cruze uma parada. Isto é até incluir um cliente.
Passo 4: Teste o potencial cliente, verificando se pode ser incluído no roteiro em formação:
(a) O tempo de jornada de trabalho por dia é violado?
(b) A capacidade do veículo é violada?
(c) Se as restrições não forem violadas, incorporar o novo cliente e voltar a passo 2.
Passo 5: Se alguma restrição for violada, exclua o último cliente e defina o roteiro. Recomece um novo
roteiro com o último cliente excluído da rota anterior. Continuar com a varredura até todos os pontos
estarem atribuídos a roteiros.
Passo 6: Dentro de cada rota, arranje, em sequência, as paradas para minimizar a distância recorrendo
a um dos métodos de resolução do problema do caixeiro viajante.
Passo 7: Para cada roteiro, aplicar um método de melhoria (e.g. 3-opt) de forma a minimizar os
percursos.
44
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
EXEMPLO 1
45
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
EXEMPLO 1
Restrições:
1. Veículo de 4 toneladas de capacidade útil.
2. Jornada de trabalho de 8 horas por dia.
3. Tempo de descarga em cada cliente é uniforme e igual a 15 minutos.
4. Poderiam existir outras como, por exemplo, velocidade máxima.
Outras considerações:
60 clientes cuja localização está na tabela anterior. A distância entre dois pontos quaisquer
foi estimada multiplicando-se a distância em linha reta por um fator k1 = 1,40.
NOTA: O CD está localizado em (0,0), distante da região de distribuição (o ponto mais
próximo está a 75,2 km e o mais distante a 79,8 km.
Será que a localização do centro do eixo de aplicação do Método de 
Varredura tem influência no resultado final? 
46
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
EXEMPLO 1
Restrições:
1. Veículo de 4 toneladas de capacidade útil.
2. Jornada de trabalho de 8 horas por dia.
3. Tempo de descarga em cada cliente é uniforme e igual a 15 minutos.
4. Poderiam existir outras como, por exemplo, velocidade máxima.
Outras considerações:
60 clientes cuja localização está na tabela anterior. A distância entre dois pontos quaisquer
foi estimada multiplicando-se a distância em linha reta por um fator k1 = 1,40.
NOTA: O CD está localizado em (0,0), distante da região de distribuição (o ponto mais
próximo está a 75,2 km e o mais distante a 79,8 km). Se aplicarmos o método da varredura
nesse problema, teremos rotas bem alongadas. Para evitar distorções acentuadas numa das
dimensões, deve-se escolher um outro centro para o eixo, por exemplo o centro de
gravidade.
NOTA: Existem restrições de tempo e capacidade.
47
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Nó X (km) Y (Km) Q (kg) Nó X (km) Y (Km) Q (kg)
1 1,26 55,65 203 31 2,67 56,26 175
2 1,56 55,12 125 32 1,87 55,38 228
3 2,66 55,01 183 33 3,48 54,07 177
4 2,33 56,2 208 34 0,83 55,38 133
5 2,79 55,8 141 35 0,83 54,88 162
6 3,27 56,23 188 36 2,4 55,41 243
7 2,53 56,67 209 37 2,44 54,04 310
8 3,26 55,62 215 38 3,67 55,86 39
9 0,5 55,78 300 39 3,2 55,73 167
10 3,26 55,63 172 40 2,04 55,42 274
11 1,34 55,04 267 41 1,43 55,82 68
12 3,77 55,41 251 42 3,01 55 199
13 3,29 55,69 128 43 3,37 55,35 206
14 3,41 55,3 230 44 1,37 54,93 150
15 3,14 55,67 158 45 1,07 56,43 307
16 3,54 56,02 254 46 2,27 54,77 173
17 0,84 55,14 207 47 3,54 54,76 198
18 2,82 55,81 189 48 2,7 55,19 159
19 1,29 55,98 147 49 1,36 56,32 253
20 2,27 54,99 223 50 2,48 56,93 91
21 3,4 54,49 171 51 2,13 56,54 198
22 2,29 56,12 112 52 3,49 55,36 216
23 2,37 55,16 340 53 1,92 55,5 225
24 1,4 54,15 175 54 2,44 54,25 315
25 3,59 54,32 309 55 2,62 56,01 303
26 0,7 55,55 75 56 3,17 56,35 252
27 1,38 54,16 220 57 1,69 55,28 76
28 2,03 53,8 286 58 3,55 55,11 159
29 2,21 53,7 218 59 1,47 56,17 187
30 3,32 56,43 165 60 0,9 54,65 94
Método de Varredura – Exemplo 2
48
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Método de Varredura – Evolução Inicial
49
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
3 OPT
ou
2OPT
MÉTODO DE VARREDURA + MÉTODOS DE MELHORIA DO ROTEIRO
SOLUÇÃO: 7 roteiros (veículos)
Quilometragem total diária da frota (km): 1.101,9
Custo médio por cliente visitado (R$): 16,58
Os veículos foram carregados no máximo com 1,8 toneladas, o que significa que o caminhão
escolhido tem sobra de capacidade. A restrição forte foi, neste caso, o tempo de jornada.
50
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Ex 8. Problemas de Roteirização
“Sweep” (Varredura) Method for VRP
Example A trucking company has 10,000-unit 
vans for merchandise pickup to be consolidated 
into larger loads for moving over long distances. 
A day’s pickups are shown in the figure below. 
How should the routes be designed for minimal 
total travel distance?
51
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Geographical
region
Depot
1,000
2,000
3,000
2,000
4,000
2,000
3,000 3,000
1,000
2,000
2,000
2,000
Pickup
points
Stop Volume and Location
52
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
11. Métodos das economias - Clarke e Wright, C&W
O método Clarke & Wright evidencia-se em relação à maioria dos demais por sua flexibilidade para
aplicação computacional de uma grande gama de restrições práticas, com relativa rapidez para um
número moderado de paradas, e capaz de gerar soluções que são próximas das ótimas. O método
aparece embutido dentro de muitos softwares de roteirização.
O método gera roteiros que respeitam as restrições de tempo e de capacidade, e ao mesmo
tempo, minimizam a distância total percorrida pela frota e, consequentemente, o tamanho da
frota.
A comparação do método com os resultados ótimos de problemas pequenos, revela que o Método
das Economias dá soluções 2% piores do que as soluções ótimas (Ballou, 2001).
É um método mais preciso que o da Varredura.
O método de C&W baseia-se no conceito de ganho, onde se parte da pior situação possível:
veículo sai do CD com a mercadoria destinada a um único cliente e, após a entrega, o veículo
retorna ao CD. Em seguida insere-se um outro cliente nessa rota.
REVISÃO!
53
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Ao integrar os clientes i e j num único roteiro, temos uma economia de percurso gij. 
gij = L–L` = dCD,i + dCD,j - dij
L = 2 x dCD,i + 2 x dCD,j L` = dCD,i + di,j + dj,CD
i
j
CD
ro
te
ir
o
co
m
b
in
ad
o
Quanto maiores e maior será o ganho.
Quanto mais próximo i estiver de j, maiorserá o ganho.
Admissível somente 
se as restrições de 
capacidade e tempo 
não forem quebradas.
iCD,d
i
j
CD 
en
tr
eg
as
se
p
ar
ad
as
jCD,d
Integrando 2 clientes num roteiro compartilhado
O Método parte de um conjunto de rotas onde todos os pontos são ligados diretamente a origem e 
vai-se unindo os pares de rotas, desde que a economia gerada pela união seja positiva.
REVISÃO!
54
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Passo 1: Combinam-se todos os pontos (que representam os clientes) dois a dois e calcula-se
o ganho para cada combinação (segundo relação gi,j).
Passo 2: Ordenam-se todas as combinações i, j, de forma decrescente segundo os valores dos
ganhos gi,j.
Passo 3: Comecemos com a combinação de dois nós que apresentou o maior ganho.
Posteriormente, na análise de outras situações, vai-se descendo na lista de combinações,
sempre obedecendo à sequência decrescente de ganhos.
Passo 4: Para um par de pontos (i,j), tirado da sequência de combinações, verificar se os 2
pontos são pontos isolados ou extremos (se estão na ponta de um roteiro):
a) se sim então unir os dois pontos i e j no caso das restrições de tempo e
capacidade não serem violadas;
b) Caso contrário, então desprezar a ligação.
Passo 5: O processo termina quando todos os pontos (clientes) tiverem sido incluídos num 
roteiro.
REVISÃO!
55
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
EXEMPLO 1
Restrições:
1. Veículo de 4 toneladas de capacidade útil.
2. Jornada de trabalho de 8 horas por dia.
3. Tempo de descarga em cada cliente é uniforme e igual a 15 minutos.
4. Poderiam existir outras como, por exemplo, velocidade máxima.
Outras considerações:
60 clientes cuja localização está na tabela anterior. A distância entre dois pontos quaisquer foi
estimada multiplicando-se a distância em linha reta por um fator k1 = 1,40.
NOTA: O CD está localizado em (0,0), distante da região de distribuição (o ponto mais próximo
está a 75,2 km e o mais distante a 79,8 km. Se aplicarmos o método da varredura nesse problema,
teremos rotas bem alongadas. Para evitar distorções acentuadas numa das dimensões, deve-se
escolher um outro centro para o eixo, por exemplo o centro de gravidade.
NOTA: Existem restrições de tempo e capacidade.
REVISÃO!
56
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
X (km) Y (Km) Q (kg) T (min) X (km) Y (Km) Q (kg) T (min)
1 1,26 55,65 203 31 2,67 56,26 175
2 1,56 55,12 125 32 1,87 55,38 228
3 2,66 55,01 183 33 3,48 54,07 177
4 2,33 56,2 208 34 0,83 55,38 133
5 2,79 55,8 141 35 0,83 54,88 162
6 3,27 56,23 188 36 2,4 55,41 243
7 2,53 56,67 209 37 2,44 54,04 310
8 3,26 55,62 215 38 3,67 55,86 39
9 0,5 55,78 300 39 3,2 55,73 167
10 3,26 55,63 172 40 2,04 55,42 274
11 1,34 55,04 267 41 1,43 55,82 68
12 3,77 55,41 251 42 3,01 55 199
13 3,29 55,69 128 43 3,37 55,35 206
14 3,41 55,3 230 44 1,37 54,93 150
15 3,14 55,67 158 45 1,07 56,43 307
16 3,54 56,02 254 46 2,27 54,77 173
17 0,84 55,14 207 47 3,54 54,76 198
18 2,82 55,81 189 48 2,7 55,19 159
19 1,29 55,98 147 49 1,36 56,32 253
20 2,27 54,99 223 50 2,48 56,93 91
21 3,4 54,49 171 51 2,13 56,54 198
22 2,29 56,12 112 52 3,49 55,36 216
23 2,37 55,16 340 53 1,92 55,5 225
24 1,4 54,15 175 54 2,44 54,25 315
25 3,59 54,32 309 55 2,62 56,01 303
26 0,7 55,55 75 56 3,17 56,35 252
27 1,38 54,16 220 57 1,69 55,28 76
28 2,03 53,8 286 58 3,55 55,11 159
29 2,21 53,7 218 59 1,47 56,17 187
30 3,32 56,43 165 60 0,9 54,65 94
Método de C&W – Exemplo 1
REVISÃO!
57
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Passo 1: Combinam-se todos os clientes 2 a 2 e calcula-se o ganho p/cada combinação (gi,j)
Passo 2: Ordenam-se todas as combinações i, j, de forma decrescente segundo os valores dos
ganhos gi,j.
20 maiores ganhos
No Ponto i Ponto j Ganho No Ponto i Ponto j Ganho
1 7 50 10,65 11 31 50 9,5
2 30 56 10,19 12 7 30 9,48
3 6 30 10,03 13 6 16 9,47
4 50 51 10,03 14 7 56 9,46
5 6 56 9,92 15 45 49 9,44
6 7 51 9,83 16 16 38 9,43
7 30 50 9,61 17 16 56 9,35
8 16 30 9,58 18 4 50 9,28
9 50 56 9,55 19 4 7 9,26
10 7 31 9,52 20 31 56 9,23
Iteração 1
REVISÃO!
58
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Passo 3: Comecemos com a combinação dos dois nós que apresentaram o maior ganho.
Passo 4: Para um par de pontos (i,j), tirado da sequência de combinações, verificar se os 2
pontos já fazem parte de um roteiro iniciado: (a) se i e j não foram incluídos em nenhum dos
roteiros já iniciados, criar um novo roteiro com esses dois pontos.
No Ponto i Ponto j Ganho No Ponto i Ponto j Ganho
1 7 50 10,65 11 31 50 9,5
2 30 56 10,19 12 7 30 9,48
3 6 30 10,03 13 6 16 9,47
4 50 51 10,03 14 7 56 9,46
5 6 56 9,92 15 45 49 9,44
6 7 51 9,83 16 16 38 9,43
7 30 50 9,61 17 16 56 9,35
8 16 30 9,58 18 4 50 9,28
9 50 56 9,55 19 4 7 9,26
10 7 31 9,52 20 31 56 9,23
Iteração 1
REVISÃO!
59
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
PASSO 5: Iteração 1
Passo 5: Cada vez que se acrescentar
um ou mais pontos num roteiro, ou
quando se fundir 2 roteiros num só,
verificar se a nova configuração satisfaz
as restrições de tempo e de
capacidade. Se atender aos limites das
restrições, a nova configuração é
aceita.
Temos o roteiro embrião que,
partindo do CD, visita o cliente
50, depois o 7 e retorna ao CD.
REVISÃO!
60
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
REVISÃO!
PASSO 5: Iteração 16, 17 e 18
Ambos já incluídos,
conforme Passo 4.D
50 não é extremoLiga-se 16 ao 38,
conforme Passo 4.B
No Ponto i Ponto j Ganho
16 16 38 9,43
No Ponto i Ponto j Ganho
17 16 56 9,35
No Ponto i Ponto j Ganho
18 4 50 9,28
61
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Passo 6: O processo termina
quando todos os pontos
(clientes) tiverem sido
incluídos num roteiro.
R1
R3
R4
R2
R5
R6
Passo 6
Solução obtida pelo Método C&W
62
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Solução final obtida pelo Método C&W + Método 3-OPT
3-OPT
63
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Solução Método Varredura (e Método 3-OPT) X Solução Método C&W (e Método 3-OPT)
Número de roteiros (no de veículos): 7
Quilometragem total diária da frota (km): 1.101,9
Custo médio por cliente visitado (R$): 16,58.
Número de roteiros (no de veículos): 6
Quilometragem total diária da frota (km): 950,7
Custo médio por cliente visitado (R$): 14,24
64
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
12. Impacto das restrições tempo e capacidade
O impacto das restrições de tempo e capacidade é muitas vezes dramático. Pequenas alterações
em alguns fatores que governam o processo alteram por completo a solução dos problemas.
EXEMPLO 2.1
Restrições:
1. Veículo de 4 toneladas de capacidade útil.
2. Jornada de trabalho de 8 horas por dia.
3. Tempo de descarga em cada cliente é uniforme e igual a 15 minutos.
4. Poderiam existir outras como, por exemplo, velocidade máxima.
Outras considerações:
60 clientes cuja localização está na tabela anterior. A distância entre dois pontos quaisquer foi
estimada multiplicando-se a distância em linha reta por um fator k1 = 1,40.
Vamos supor que o CD está localizado junto à zona de entrega. Trata-se agora de um problema dedistribuição urbana. O CD continua localizado ao sul da região, mas desta vez a distância para o
cliente mais próximo é 1,2 km e para o cliente mais distante é 5,7 km.
65
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Roteiros
No 
Número de 
clientes
Tempo de ciclo 
diário
Lotação do 
veículo (t)
1 21 5h42 3,9
2 22 6h 4,0
3 17 4h36 3,9
Exercício 2: Resultados C&W com CD fora da zona urbana
Exercício 2.1: Resultados C&W com CD em zona urbana
• Número de roteiros (no de veículos): 6
• Quilometragem total diária da frota (km): 950,7
• Custo médio por cliente visitado (R$): 14,24
• A lotação dos veículos (t) deverá ser cerca de 2 t
(relembre que no método de varredura com 6
veículos a lotação máxima obtida foi de 1,8 t.)
1. Veículo de 4 toneladas de capacidade útil.
2. Jornada de trabalho de 8 horas por dia.
1. Veículo de 4 toneladas de capacidade útil.
2. Jornada de trabalho de 8 horas por dia.
Que fator está a restringir o resultado? 
66
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
EXEMPLO 2.2
Restrições:
1. Veículo de 8 toneladas de capacidade útil.
2. Jornada de trabalho de 8,5 horas por dia.
3. Tempo de descarga em cada cliente é uniforme e igual a 15 minutos.
4. Poderiam existir outras como, por exemplo, velocidade máxima.
Outras considerações:
Vamos supor que o CD está localizado junto à zona de entrega. Trata-se agora de um problema de
distribuição urbana. O CD continua localizado a sul da região, mas desta vez a distância para o
cliente mais próximo é 1,2 km e para o cliente mais distante é 5,7 km.
Apesar da jornada de trabalho ser de 8 horas, verifica-se que o resultado obtido para a
distribuição urbana (Exemplo 2.1) contempla 3 rotas com templos de ciclo com pelo menos mais
de 2 horas abaixo das 8 horas. Isto significa que a restrição forte é, neste caso, a capacidade. Os
veículos estão subdimensionados. Aumentando a capacidade dos veículos para 8 t verificou-se
que a solução era igual. Neste caso significa que o tempo de jornada passou a ser a restrição
forte. Finalmente estabeleceu-se o tempo de jornada igual a 8h30min.
67
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Roteiros
No 
Número de 
clientes
Tempo de ciclo 
diário
Lotação do 
veículo (t)
1 21 5h42 3,9
2 22 6h 4,0
3 17 4h36 3,9
Exercício 2.1: Resultados C&W com CD em zona urbana
Roteiros
No 
Número de 
clientes
Tempo de ciclo 
diário
Lotação do 
veículo (t)
1 31 8h18 5,9
2 29 7h48 5,9
Exercício 2.2: Resultados C&W com CD em zona urbana
1. Veículo de 4 toneladas de capacidade útil.
2. Jornada de trabalho de 8 horas por dia.
1. Veículo de 8 toneladas de capacidade útil.
2. Jornada de trabalho de 8,5 horas por dia.
68
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
13. Problemas reais de roteirização
Nos problemas da vida real existem, na maior parte das vezes, vários parâmetros incertos:
• Número de pontos de entrega: adição de clientes durante o período de atividade dos
veículos.
• Morosidade dos processos de distribuição: congestionamento, acidentes.
• Cancelamento de clientes.
Roteirização Estática vs. Roteirização Dinâmica
Roteirização Estática:
• Toda a informação necessária para o planejamento das rotas está disponível.
• Os dados do problema não mudam durante a execução do algoritmo de solução nem
durante a execução da rota.
Roteirização Dinâmica:
• Os dados podem mudar ou serem atualizados durante a execução do algoritmo ou
durante a execução da rota.
• As rotas sofrem alteração dinâmica durante a execução.
69
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
EXEMPLO: Um serviço de reparação de internet tinha uma pré-marcação de 5
clientes. No entanto, já durante a jornada de serviço recebeu um pedido adicional.
Como satisfazer esse pedido?
Uma solução passa por tentar alocar o novo serviço dentro do roteiro pré-definido
sem prejudicar significativamente o plano previamente traçado.
Base
70
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
1. Dimensão de tempo
• ESTÁTICA
Pode ou não ser um fator importante.
• DINÂMICA
No mínimo, precisa-se conhecer a localização espacial de todos os veículos em um determinado
momento durante a sua programação, em particular, quando as solicitações de novos clientes
forem conhecidas.
2. O problema pode ser aberto
• ESTÁTICA
Rota fechada que inicia e termina a rota num depósito.
• DINÂMICA
Uma rota inicia no depósito, mas não deve retornar ao depósito ao fim dos atendimentos
programados. O veículo deve aguardar sempre por instruções dos seus próximos destinos a
serem seguidos. Os veículos retornam ao depósito quando a capacidade foi totalmente utilizada
ou se for necessário ao depósito para chegar antes do fim da janela de tempo do depósito.
71
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
3. Informações futuras podem ser imprecisas ou desconhecidas
• ESTÁTICA
Todas as informações são assumidas como conhecidas e possuem a mesma qualidade.
• DINÂMICA
As informações são precisas para os eventos que acontecem em tempo real e experimentais (ex.
probabilísticas) para os eventos que podem ocorrer no futuro.
4. Eventos de curto prazo são mais importantes
• ESTÁTICA
Dada a uniformidade da qualidade da informação e a falta de atualizações, todos os eventos
possuem o mesmo peso.
• DINÂMICA
Os eventos de curto prazo são mais importantes do que as de longo prazo, visto que não é ideal
comprometer os recursos de um veículo aos requisitos que terão de ser satisfeitos no futuro,
porque outros eventos intermediários podem fazer tais decisões se tornarem subotimizadas e
porque tais informações futuras poderão mudar, de qualquer maneira.
72
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
5. Mecanismos de atualização da informação são essenciais
• DINÂMICA
Está sujeita a revisão durante o dia de operação (veículos quebrados, atrasos, tráfego, acidentes).
É necessário que os mecanismos de atualização de informação sejam parte integrante da
estrutura do algoritmo e da interface de entrada e saída
6. Novo sequenciamento dos serviços e re-atribuição aos veículos podem ser necessários
• DINÂMICA
Novas entradas podem implicar que as decisões já tomadas relativas ao sequenciamento dos
atendimentos se tornem sub-ótimas. Assim, o aparecimento de uma nova entrada, como um
novo cliente, pode exigir tanto um novo sequenciamento dos serviços de um ou mais veículos e
até a mudança de serviços entre os veículos (re-atribuição).
7. Mecanismos que evitem uma prorrogação indefinida são essenciais
• DINÂMICA
Pode ocorrer de um serviço ser sistematicamente adiado indefinidamente (ex. solicitações mais
perto da localização atual do veículo). Para resolver o problema há uma variedade de maneiras:
restrições de horário (janelas de atendimento) podem forçar o veículo a atender uma demanda
independentemente da localização geográfica em que ponto está; restrições de prioridade –
limitação do número de alterações da posição de atendimento de cada ponto.
73
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
8. Tempos de computação mais rápidos são necessários
• ESTÁTICA
É possível aguardar algumas horas para obter a melhor solução, muitas vezes a solução ótima.
• DINÂMICA
Precisa-se chegar a uma solução satisfatória o mais rápido possível em questão de minutos ou
até segundos – utilização de heurísticas.
9. A função objetivo podeser diferente
• ESTÁTICA
Minimizar a distância total das rotas ou a duração total da programação.
• DINÂMICA
Se o processo for aberto, a duração total da programação poderá ser ilimitada também.
10. A flexibilidade para variar o tamanho da frota de veículos é menor
• ESTÁTICA
o intervalo de tempo entre a execução do algoritmo e execução do percurso é geralmente
suficiente para permitir a alteração da frota.
• DINÂMICA
Pode não ser viável por não ser possível ter acesso a tais recursos em tempo real.
74
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
11. As restrições de tempo podem ser diferentes
• ESTÁTICA
Todas as informações são assumidas como conhecidas e possuem a mesma qualidade.
• DINÂMICA
As restrições de tempo como as janelas de tempo, tendem a ser flexíveis (podem ser atualizadas
ou podem ser violadas com algum custo ou penalidade)
12. Enfileiramento pode se tornar importante
• DINÂMICA
Pode, às vezes, tornar-se saturado. Isso acontecerá se a taxa de demanda dos clientes ultrapassar
um determinado limite além do qual o sistema simplesmente não consegue lidar com todas as
solicitações, sem que sejam criados atrasos excessivos. Neste caso, qualquer algoritmo que tenta
fazer as atribuição e programações de acordo com critérios clássicos da roteirização estática
acaba produzindo resultados sem sentido.
75
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Figura 1 - Exemplo de Roteirização Dinâmica
Fonte: Silva Junior, 2013
76
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
1. Carregar os caminhões com volumes de paradas que estejam mais próximas entre si.
São um conjunto de boas práticas que, na ausência de um esquema de roteirização mais
estruturado e programado , pode minimizar as perdas.
15. Princípios empíricos de Roteirização
Má roteirização
As paradas estão 
muito distantes
Boa roteirização
As paradas estão 
próximas
D D
Depot
Stops
77
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
2. Paradas em dias diferentes devem ser combinadas para produzir agrupamentos concentrados.
3. Os roteiros devem começar a partir da parada mais distante do depósito.
Ex.: Transporte escolar.
4. A coleta deve ser combinada nas rotas de entrega em vez de reservada para o final dos roteiros.
Depende do tamanho dos veículos e do grau de obstrução às mercadorias para entrega.
5. Os roteiros mais eficientes são aqueles que fazem uso dos maiores veículos disponíveis.
O custo por unidade transportada é menor.
Mas será que o custo de estocagem também é menor?
F
F
F
F
F
F
F
T
T T
T
T
T
T
D
Depot
F
F
F
F
F
T
T
T
F T
F
T
T
T
D
Depot
(a) Weak clustering--
routes cross
(b) Better clustering
Stop
78
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
6. O sequenciamento das paradas deve ter forma de lágrima.
7. Paradas isoladas dos agrupamentos de pontos, em particular as de baixo volume, são boas
candidatas a um meio de entrega alternativo.
Ex.: Transporte terceirizado.
8. Janelas de tempo de paradas pequenas devem ser evitadas.
Podem forçar sequências de parada longe do padrão ideal – são muito restritivas.
Má roteirização
Os trajetos cruzam-se
Boa roteirização
Os trajetos não se cruzam
79
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Passado
• Roteiros baseados na experiência de motoristas / supervisores, antigos na operação / região.
• Comunicação por rádio ou telefone em pontos de parada (comunicações ocasionais).
Tendências presentes
• Veículos equipados com RFID e rastreador
• GPS (global positioning system) com latitude e longitude.
• GPS + Sistema com base de dados GIS (geographic information system) + comunicação por 
satélite - localização do veículo, a cada instante, na malha viária.
• Softwares de Roteirização e Programação dos veículos com tecnologia GIS.
• Softwares de roteirização de uso direto na Internet.
• Internet com informações sobre o pedido para o cliente.
• Internet com acesso wireless, exemplo: motoristas receberem informações online durante a 
viagem.
16. Utilização de novas tecnologias
80
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
• TruckStops (1984) – www.bestroutes.com
• TransCAD – (1988) – www.caliper.com
• RouteSmart (1989) – www.routesmart.com
• Roadshow (1993) – www.routing.com.br
• ArcLogistics Route (1999) – www.esri.com
Network Analyst (2005)
ILOG Transp (2005)
Softwares de Roteirização
81
http://www.bestroutes.com/
http://www.caliper.com/
http://www.routesmart.com/
http://www.routing.com.br/
http://www.esri.com/
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
• Necessitam de suporte técnico para serem instalados, dada a complexidade.
• Alguns softwares exigem simplificações para resolver certos problemas. Deve-se portanto
verificar qual o impacto que essas simplificações podem ter na precisão final dos resultados. Ex.:
a quantidade máxima de pontos de entrega ser limitada.
• A base de dados da representação digital da rede viária (ruas, rodovias, etc.) do roteirizador
deve estar disponível e atualizada, caso contrário a sua utilização será comprometida.
• Nem sempre os clientes são fixos (ex.: CD e suas lojas de varejo). Pontos de entrega que variam
diariamente (ex.: entregas em domicílios) dificultam a roteirização, pois o cadastro dos clientes
não está previamente preparado.
• Informações importantes antes de se adotar um software específico: preço; tempo para
instalação; tamanho máximo de aplicações (No. de visitas por dias, No. de veículos, de CDs);
Características operacionais (distâncias calculadas sobre rede viária; monitoramento de veículos
em tempo real, programação de carregamento dos veículos, etc.).
SOFTWARES de Roteirização: cuidados a ter
82
DEPARTAMENTO DE 
ENGENHARIA INDUSTRIAL
ENG1545 – Distribuição Física
Prof. Rafael Martinelli
8. Problemas de Roteirização
Bibliografia 
• Novaes, A.G. 2001. Logística e gerenciamento da cadeia de distribuição. Editora Campos, Rio de
Janeiro, Brasil.
• Rodrigues, J. C. 1999. "Aplicações da Teoria de Sistemas“. Ediliber, Coimbra, Portugal.
• Larson, R.C., Odoni, A.R. 1981. Urban operations research. Prentice-Hall, NJ, EUA.
• Silva, R.C.O. 2007. Tese Mestrado. Avaliação da implantação de softwares de roteirização de
veículos. PUC-Rio.
83