Introdução à Otimização
Marcone Jamilson Freitas Souza
Departamento de Computação
Universidade Federal de Ouro Preto
http://www.decom.ufop.br/prof/marcone
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
Passo iterativo: 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