ROTEIRIZAÇÃO
Marcone Jamilson Freitas Souza
http://www.decom.ufop.br/prof/marcone
SUMÁRIO
Introdução
Objetivos
Métodos de solução
Problema do Caixeiro Viajante
Problema de Roteamento de
Veículos
Introdução
Objetivos
Atender ao cliente com o nível de
serviço desejado
Reduzir os custos de transporte tanto
quanto
possível,
escolhendo
os
trajetos mais adequados de forma a
aproveitar eficientemente a frota e a
mão-de-obra operacional
Métodos de solução

Programação matemática
Vantagem: garantem a solução ótima (menor custo)
Desvantagens:



Difícil modelagem
Nem sempre conseguem produzir uma solução
Heurísticas
Vantagens:


De fácil implementação
Produzem boas soluções rapidamente
Desvantagem:

Não garantem a otimalidade da solução obtida
Exemplo: Problema da Mochila
Imagine que os estudantes do curso de
especialização em logística empresarial
estejam fazendo um cruzeiro marítimo
patrocinado pela coordenação do curso
Em alto mar o navio começa a afundar ...
Só existe um barco salva-vidas, que, no
entanto, só pode levar c quilos
Exemplo: Problema da Mochila
Cada pessoa no navio tem um certo peso pi
Cada pessoa i proporciona um benefício bi
se for levada para o barco salva-vidas
O problema consiste em escolher as
pessoas que trarão o maior benefício
possível sem ultrapassar a capacidade do
barco
Exemplo: Problema da Mochila
Pessoa
cruzeirense

Peso (Kg) Benefício
140
0
Capacidade do barco: 250 Kg.
Exemplo: Problema da Mochila
Pessoa
cruzeirense
Recém-graduado

Peso (Kg) Benefício
140
0
60
1
Capacidade do barco: 250 Kg.
Exemplo: Problema da Mochila
Pessoa
cruzeirense
Recém-graduado
ATLETICANO

Peso (Kg) Benefício
140
0
60
1
100
3
Capacidade do barco: 250 Kg.
Exemplo: Problema da Mochila
Pessoa
cruzeirense
Recém-graduado
ATLETICANO
Funcionário da CVRD

Peso (Kg) Benefício
140
0
60
1
100
3
80
4
Capacidade do barco: 250 Kg.
Exemplo: Problema da Mochila
Pessoa
cruzeirense
Recém-graduado
ATLETICANO
Funcionário da CVRD
Morena “olhos verdes”

Peso (Kg) Benefício
140
0
60
1
100
3
80
4
75
3
Capacidade do barco: 250 Kg.
Exemplo: Problema da Mochila
Pessoa
cruzeirense
Recém-graduado
ATLETICANO
Funcionário da CVRD
Morena “olhos verdes”
Loira burra

Peso (Kg) Benefício
140
0
60
1
100
3
80
4
75
3
60
2
Capacidade do barco: 250 Kg.
Exemplo: Problema da Mochila
Pessoa
cruzeirense
Recém-graduado
ATLETICANO
Funcionário da CVRD
Morena “olhos verdes”
Loira burra
João Esmeraldo
Peso (Kg) Benefício
140
0
60
1
100
3
80
4
75
3
60
2
90
10

Capacidade do barco: 250 Kg.

Solução 1: J + L + A
(250 Kg) Benefício = 15
Exemplo: Problema da Mochila
Pessoa
cruzeirense
Recém-graduado
ATLETICANO
Funcionário da CVRD
Morena “olhos verdes”
Loira burra
João Esmeraldo
Peso (Kg) Benefício
140
0
60
1
100
3
80
4
75
3
60
2
90
10

Capacidade do barco: 250 Kg.

Solução 1: J + L + A
(250 Kg) Benefício = 15

Solução 2: J + M + F
(245 Kg) Benefício = 17
Complexidade do
Problema da mochila
Para n pessoas há 2n configurações possíveis
Exemplo: Para n = 50 há 1015 soluções para
serem testadas
Um computador que realiza uma avaliação em
10-8 segundos gastaria cerca de 130 dias
para encontrar a melhor solução!
Conclusão: O barco afundaria antes que
fosse tomada a decisão de quem seriam os
escolhidos
Problema da Mochila:
observações
Problema NP-difícil: tempo de
resolução cresce exponencialmente
com a dimensão
Abordado por métodos
heurísticos
Um modelo Heurístico para
o Problema da Mochila
1º Passo: Calcular a relação benefício/custo
Pessoa
Peso (Kg)
Benefício
Benefício/
Peso
cruzeirense
140
0
0
Recém-graduado
60
1
0,017
ATLETICANO
100
3
0,030
Funcionário da CVRD
80
4
0,050
Morena “olhos verdes”
75
3
0,040
Loira burra
60
2
0,030
João Esmeraldo
90
10
0,111
Um modelo Heurístico para
o Problema da Mochila
2º Passo: Ordenar os elementos
Pessoa
Peso (Kg)
Benefício
Benefício/
Peso
João Esmeraldo
90
10
0,111
Funcionário da CVRD
80
4
0,050
Morena “olhos verdes”
75
3
0,040
Loira burra
60
2
0,030
ATLETICANO
100
3
0,030
Recém-graduado
60
1
0,017
cruzeirense
140
0
0
Um modelo Heurístico para
o Problema da Mochila
3º Passo: Escolher o elemento que produzir a maior
relação benefício/peso, e que respeite a capacidade
do barco
Pessoa
Peso (Kg)
Benefício
Benefício/
Peso
João Esmeraldo
90
10
0,111
Funcionário da CVRD
80
4
0,050
Morena “olhos verdes”
75
3
0,040
Loira burra
60
2
0,030
ATLETICANO
100
3
0,030
Recém-graduado
60
1
0,017
cruzeirense
140
0
0
Um modelo Heurístico para
o Problema da Mochila
4º Passo: Repetir o passo anterior até que nenhum
elemento possa ser colocado no barco sem
ultrapassar a capacidade deste.
Pessoa
Peso (Kg)
Benefício
Benefício/
Peso
João Esmeraldo
90
10
0,111
Funcionário da CVRD
80
4
0,050
Morena “olhos verdes”
75
3
0,040
Loira burra
60
2
0,030
ATLETICANO
100
3
0,030
Recém-graduado
60
1
0,017
cruzeirense
140
0
0
Um modelo Heurístico para
o Problema da Mochila
4º Passo: Repetir o passo anterior até que nenhum
elemento possa ser colocado no barco sem
ultrapassar a capacidade deste.
Pessoa
Peso (Kg)
Benefício
Benefício/
Peso
João Esmeraldo
90
10
0,111
Funcionário da CVRD
80
4
0,050
Morena “olhos verdes”
75
3
0,040
Loira burra
60
2
0,030
ATLETICANO
100
3
0,030
Recém-graduado
60
1
0,017
cruzeirense
140
0
0
Um modelo de programação
matemática para o Problema
da Mochila
Sejam:
n elementos
c = capacidade da mochila
bi = benefício do elemento i
pi = peso do elemento i
Variável de decisão:
1 se o elementoi for colocadona mochila
xi  
0 caso contrário
Um modelo de programação
matemática para o Problema
da Mochila
n
max bi xi
i 1
n
px
i 1
i i
c
xi {0,1} i  1,...,n
Problema do Caixeiro Viajante
Há um conjunto de n cidades (clientes)
e uma matriz de distâncias entre elas
O objetivo é sair de uma cidade,
chamada origem, visitar cada uma das
restantes n-1 cidades apenas uma
única vez e retornar à cidade origem
percorrendo a menor distância possível
Problema do Caixeiro Viajante
5
4
7
10
9
8
12
1
2
Uma rota possível:
3
1->2->4->3->5->1
Custo: 46
Problema do Caixeiro Viajante
Número
elevado
de
soluções
existentes
Há (n-1)!/2 rotas possíveis, supondo
que a distância de uma cidade i à outra
j seja simétrica (dij = dji)
Para n=20 cidades há 6x1016 rotas
Um computador que avalia uma rota
em cerca de 10-8 segundos, gastaria 19
anos para encontrar a melhor rota!
Um modelo de programação
matemática para o Problema
do Caixeiro Viajante
Sejam dados:
n cidades
dij  distânciaentreas cidades i e j
 Variáveis de decisão:
1
xij  
0
se o arco (i, j) for usado
caso contrário
yij  quantidadede fluxo de i para j
Um modelo de programação
matemática para o Problema
do Caixeiro Viajante
min  dij xij
iV jV
x
iV
i j
ij
 1 j V
x
iV
i j
ji
 f  f
iV
i j
ij
iV
i j
ji
 1 j V
 1 j V , j  1
fij  (n 1) xij i, j V
xij {0,1} i, j V
fij  0 i, j V
Heurísticas p/a resolução do
Problema do Caixeiro Viajante
Heurísticas construtivas
Constroem uma rota, elemento por
elemento
Heurísticas de refinamento
Melhoram uma rota existente por
meio de trocas sistemáticas na
ordem das cidades visitadas
Heurística (Construtiva) do
Vizinho mais próximo para o
Problema do Caixeiro Viajante
Idéia: Começar da cidade origem e
adicionar à rota a cidade mais próxima
da última cidade adicionada. Terminar
quando todas as cidades forem
visitadas.
Heurística (Construtiva) do
Vizinho mais próximo para o
Problema do Caixeiro Viajante
Cidade
1
2
3
4
5
1
0
12
7
9
8
2
12
0
11
7
6
3
7
11
0
12
13
4
9
7
12
0
8
5
8
6
13
8
0
Rota resultante: 1->3->2->5->4->1
Custo: 41
Heurística (Construtiva) da
Inserção Mais Barata para o
Problema do Caixeiro Viajante
Idéia:
 Começar com uma subrota envolvendo
três cidades (as quais podem ser obtidas
pela heurística do vizinho mais próximo)
 Adicionar a cidade k (entre as
cidades i e j) que produzir a inserção
mais barata sij = cik + ckj - cij
 Terminar quando todas as cidades
forem visitadas
Heurística (Construtiva) da
Inserção Mais Barata para o
Problema do Caixeiro Viajante
Cidade
1
2
3
4
5
1
0
12
7
9
8
2
12
0
11
7
6
3
7
11
0
12
13
4
9
7
12
0
8
5
8
6
13
8
0
Rota resultante: 1->3->2->5->4->1
Custo: 41
Heurística (Construtiva) da
Inserção Mais Barata para o
Problema do Caixeiro Viajante
i
j
k
sij
1
2
4
9 + 7 - 12 = 4
1
3
4
9 + 9 – 7 = 11
2
3
4
9 + 7 – 11 = 5
1
2
5
8 + 6 – 12 = 2
1
3
5
8 + 10 – 7 = 11
2
3
5
10 + 6 – 11= 5
Subrota: 1->3->2->5->1
Custo parcial = 32
Heurística (Construtiva) da
Inserção Mais Barata para o
Problema do Caixeiro Viajante
i
j
k
sij
1
3
4
9 + 9 – 7 = 11
5
1
4
9+8–8= 9
3
2
4
9 + 7 – 11 = 5
2
5
4
8+7–6= 9
Rota final: 1->3->4->2->5->1
Custo: 37
Heurística de refinamento 2optimal para o Problema do
Caixeiro Viajante
Passo 1: Iniciar com uma rota qualquer
Passo 2: Para cada 2 arcos não consecutivos
da rota corrente, removê-los, reconectá-los
e avaliar a nova rota formada.
Passo 3: Se a melhor dessas rotas for
melhor que a rota corrente, substituí-la pela
nova rota e repetir o passo 2. Caso
contrário, vá para o Passo 4.
Passo 4: Fim, não é mais possível melhorar
uma rota
Heurística de refinamento 2-optimal
para o Problema do Caixeiro Viajante
(a) Rota original
i
i+1
j+1
j
c
(b) Rota modificada
i
i+1
j+1
j
C = c – di,i+1 – dj,j+1 + dij + di+1,j+1
Heurística de refinamento 2-optimal
para o Problema do Caixeiro Viajante
(a) Rota original
i
i+1
11
3
2
7
(b) Rota modificada
i
i+1
3
2
7
1
6
9
4
j+1
8
c=41
6
1
9
5
j
10
7
4
j+1
5
j
C = 41 – 11 – 8 + 10 + 7 = 39
Problema de Roteamento de Veículos
Problema de Roteamento de Veículos
com frota homogênea
 Seja G = (V, E) um grafo não direcionado, onde V = {v0, v1,..., vn}
é o conjunto dos vértices e E = {(vi, vj): vi ,vj  V, i < j} é o
conjunto de arestas.
 O vértice v0 representa o depósito, sendo este a base de uma
frota de veículos idênticos de capacidade Q, enquanto os
vértices remanescentes correspondem às cidades ou
consumidores.
 Cada consumidor vi tem uma demanda não negativa qi e q0 = 0.
 A cada aresta (vi, vj) está associada uma distância não negativa
cij que representa a distância entre os consumidores.
Problema de Roteamento de Veículos
com frota homogênea
 O Problema de Roteamento de Veículos consiste em
determinar o conjunto de rotas que deverão ser feitas
pelos veículos minimizando os custos de transporte,
dado pela distância e respeitando as seguintes
condições:
a) Cada rota começa e termina no depósito;
b) Toda cidade de V \ {v0} é visitada somente uma vez por
somente um veículo;
c) A demanda total de qualquer rota não deve superar a
capacidade Q de um veículo.
Um modelo de programação matemática para
o Problema de Roteamento de Veículos
com frota homogênea
Sejam dados:
n cidades
m veículos de capacidade VCAP
A demanda qi de cada cidade
A distância dij entre cada par de cidade
Variáveis de decisão:
1
xij  
0
se o arco (i, j) for usado
caso contrário
yij  quantidadede fluxo de i para j
Um modelo de programação matemática para
o Problema de Roteamento de Veículos
com frota homogênea
min  dij xij
iV jV
(a)
x
iV
i j
ij
 1 j V , j  1
(b)
x
iV
i j
ji
 1 j V , j  1
(c)  f ij   f ji  qi j V , j  1
iV
i j
(e)
iV
i j
x
jV
j 1
1j
(d ) fij  (VCAP) xij i, j V
m
( f )  x j1  m
jV
j 1
( g ) xij {0,1} i, j V
(h) fij  0 i, j V
Adaptação da Heurística do Vizinho mais
próximo para o Problema de Roteamento de
Veículos com frota homogênea
Idéia básica:
Passo 1: Parte-se do depósito com um
novo veículo até a cidade mais próxima
Passo 2: Calcular a cidade mais próxima
da última cidade inserida na rota e
verificar se é possível atender sua
demanda
Passo 3: Se for possível atender a
demanda dessa cidade, adicioná-la à rota.
Caso contrário, retornar ao depósito e
voltar ao Passo 1.
Adaptação da Heurística do Vizinho mais
próximo para o Problema de Roteamento de
Veículos com frota homogênea
s ={0-2-1-0-5-3-4-6-7-0-8-9-10-0}
Heurística Construtiva de Clark & Wright
para o Problema de Roteamento de Veículos
com frota homogênea
Idéia básica:
Parte-se da pior situação possível: o
veículo sai do depósito, atende um
único cliente e retorna
Unir as rotas de cada veículo com base
no conceito de economia
À medida que se reduz a distância
total percorrida, o número de veículos
necessários também é reduzido
Heurística Construtiva de Clark & Wright
para o Problema de Roteamento de Veículos
com frota homogênea
(a) Rota inicial
i
(b) Rota combinada
j
0
i
j
0
Economia sij = di0 + d0j - dij
Cidades
Demanda
i
j
1
15
di0
2
17
dj0
3
27
dij
4
12
Sij
5
23
CAP
50
Dem
1
52
52
32
34
28
27
5
2
27
24
32
Sij = di0 + dj0 - dij
43
43
20
38
4
13
28
3
1
Cidades
Demanda
1
15
2
17
3
27
4
12
5
23
CAP
50
j
2
3
di0
dj0
28
28
27
13
52
32
3
9
1
4
28
38
34
32
1
2
2
2
3
3
4
5
3
4
5
4
5
5
28
27
27
27
13
13
38
24
13
38
24
38
24
24
52
20
43
27
28
32
43
0
20
22
24
23
5
19
Total percorrido:
Nº de caminhões:
dij
260
5
Sij
Dem
32
42
27
38
44
29
40
39
50
35
28
24
5
i
1
1
28
27
24
27
13
38
38
4
2
13
3
1
Cidades
Demanda
1
15
2
17
3
27
4
12
5
23
CAP
50
j
2
3
5
3
4
di0
dj0
dij
Sij
28
28
28
27
27
27
13
24
13
38
52
32
52
20
43
3
9
0
20
22
2
5
27
24
27
24
3
3
4
4
5
5
13
13
38
38
24
24
28
32
43
23
5
19
Total percorrido:
Nº de caminhões:
228
4
Dem
44
54
50
44
44
40
54
50
50
28
24
5
i
1
1
1
2
2
34
27
24
2
27
13
38
4
13
3
1
Cidades
Demanda
1
15
2
17
3
27
4
12
5
23
CAP
50
34
28
27
5
i
1
1
1
2
2
j
2
3
5
3
4
di0
dj0
dij
Sij
28
28
28
27
27
27
13
24
13
38
52
32
52
20
43
3
9
0
20
22
3
4
13
38
28
23
3
4
5
5
13
38
24
24
32
43
5
19
Total percorrido:
Nº de caminhões:
204
3
Dem
67
54
67
67
67
54
67
67
24
2
27
13
38
4
13
3