O Problema de Roteamento
de Veículos (PRV)
Componentes:
- Filipe Nunes Ribeiro
- Marcio Tadayuki Mine
- Matheus de Souza Alves Silva
Tópicos




O Problema
Heurísticas e Metaheurísticas
utilizadas
Resultados
Conclusão
O Problema

Dado um conjunto de cidades (ou
consumidores), cada qual com uma
demanda qi por um produto, e um
depósito com veículos de capacidade
Q, encontrar as rotas para os veículos
minimizando os custos de transporte.
Requisitos a serem atendidos



Cada rota começa e termina no
depósito;
Toda cidade, com exceção do
depósito, é visitada somente uma vez
por somente um veículo;
A demanda total de qualquer rota não
deve superar a capacidade Q de um
veículo
O Problema na Prática
2
3
1
4
5
10
9
6
8
7
Características do PRV


Este problema é uma generalização do Problema
do Caixeiro Viajante (PCV), distiguindo-se no fato
de que o PCV tem por objetivo visitar um
determinado número de cidades em uma rota
única, enquanto o PRV possui várias rotas.
O PRV pertence à classe de problemas NP-Difícil,
isto é, não existe solução em tempo polinomial para
este problema.
Heurísticas e Metaheurísticas
utilizadas



Para a solução do PRV, foi utilizado a
heurística GRASP:
Fase de construção da solução inicial:
Método das Economias de Clarke &
Wright ;
Fase de Busca Local: Busca Tabu.
GRASP
procedimento GRASP(, t);
1 Para iter  0 até maxGRASP, faça
2
s  melhor das iterSo soluções geradas pela
heurística de Clarke & Wright();
3 s  BuscaTabu(s, BTmax, |T|, f(), N()...);
4 Retorne s;
{Retorne a melhor solução}
fim GRASP;
Método das Economias de
Clarke & Wright

Originalmente desenvolvida para resolver o
problema clássico de roteamento de
veículos.
Baseia-se
na
noção
de
economias, que pode ser definido como o
custo da combinação, ou união, de duas
subrotas existentes. Trata-se de uma
heurística iterativa de construção baseada
numa função gulosa de inserção.
Como se aplica
Cálculo das economias:
eij = di0 + d0j - dij
Busca Tabu

A Busca Tabu é um procedimento
adaptativo que utiliza uma estrutura de
memória para guiar um método de descida
a continuar a exploração do espaço de
soluções
mesmo
na
ausência
de
movimentos de melhora, evitando que haja
a formação de ciclos, isto é, o retorno a um
ótimo local previamente visitado.
Estruturas de Vizinhança


Para tentar escapar de ótimos locais,
foram utilizadas três estruturas de
vizinhança:
Movimento 1-optimal intra-pétala
Esse
movimento
seleciona
aleatoriamente uma pétala e faz todas
as combinações possíveis entre as
cidades dessa pétala
Movimento 1-optimal Intra-pétala
Estruturas de Vizinhança

Movimento 1-optimal inter-pétalas:
Este movimento escolhe aleatoriamente
duas pétalas do vetor solução e faz todas
as combinações possíveis entre as cidades
destas pétalas calculando a função objetivo
em cada troca permanecendo com a melhor
solução ao final de todas as possíveis
combinações
Movimento 1-Optimal Inter-pétala
Resultados
Equipamento utilizado:
AMD Athlon 850 MHz, 192 MBytes de RAM
Plataforma: Windows XP
Instância # cid. Cap. veíc. Melhor valor liter.
c50.dat
c50.dat
c50.dat
50
50
50
160
160
160
524.61
524.61
524.61
GRASP + BUSCA TABU
 Melhor valor Média Desvio (%) média # veic
0.03
531.238
535.800
2.13
5
0.03
539.707
553.267
5.46
5.40
0.03
534.188
541.532
3.22
5.21
Dados da literatura:
http://ina.eivd.ch/collaborateurs/etd/problemes.dir/vrp.dir/vrp.html
Conclusões

Eficiência
na
combinação
da
heurística de Clarke e Wright com o
Busca Tabu aplicados ao GRASP

Dificuldade em encontrar ótimos
parâmetros para o Busca Tabu