Resolução do Problema
de Roteamento de
Veículos com Frota
Heterogênea via GRASP
e Busca Tabu
Rodrigo Geraldo Ribeiro
Denis Pinto Pinheiro
Camila Leles Rezende
O Problema de Roteamento de
Veículos (PRV):

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,
atendendo todos as cidades.
Características do problema:


Como uma generalização do Problema do
Caixeiro Viajante (PCV), o PRV pertence à
classe de problemas NP-Difícil (LENSTRA,
1981), portanto não existem algoritmos em
tempo polinomial para encontrar soluções
ótimas.
Os algoritmos exatos existentes raramente
conseguem resolver problemas envolvendo
mais do que 50 consumidores (RENAUD &
BOCTOR, 2002).
Abordagens de resolução:

Para problemas de maior porte:




Heurísticas.
Exemplos de heurísticas bem sucedidas:
Algoritmos baseados em Busca Tabu de
Taillard (1993), Osman (1993) e
Gendreau et al. (1994).
Heurística de pétalas de Renaud et
al.(1996).
Nossa proposta:

Um método de duas fases para a resolução
do PRV:

Fase GRASP.



Construção de uma solução inicial parcialmente gulosa.
Aplicar um método de busca local para refinar a solução
inicial.
Refinamento usando Busca Tabu


Baseado em função de avaliação que procura
minimizar as distâncias percorridas.
As estruturas de vizinhança utilizadas na Busca
Tabu e no método de busca local da fase GRASP,
são simples e proporcionam alterações na solução
capazes de escapar de ótimos locais.
Exemplo:
Consumidores
Rotas
Depósito
Características:
 Depósito: qtde veículos, localização.
 Veículos: capacidade.
 Consumidores: localização, demanda.
 Informações da Rota: distância entre os
consumidores e depósito.
Função Objetivo:
 Minimizar o custo total da viagem.
Representação dos
consumidores:
Pontos no plano (x,y).
Consumidores:
Identificador,
Demanda.
Depósito:
Num. veículos.
Grafo de representação das cidades
Matriz de Distância:
0
10
15
7
16
0
12
31
20
23
0
18
50
23
19
0
• Nossa proposta de solução é aplicável a problemas assimétricos!
Formulação do Problema do
Roteamento de Veículos (PRV):
 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 de capacidade Q, possivelmente diferentes entre si, enquanto os
vértices remanescentes correspondem às cidades ou consumidores.
 Cada consumidor vi tem uma demanda não negativa qi e q0 = 0.
 Supõe-se que existe um número ilimitado de veículos no depósito.
 A cada aresta (vi, vj) está associada uma distância não negativa cij que
representa a distância entre os consumidores.
Formulação do Problema do
Roteamento de Veículos (PRV):

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.
Representação do PRV:

Assumimos a representação usada por
Pradenas & Parada (1999). Uma solução do
PRV é representada por meio de uma
permutação de cidades, numeradas de 1 a n,
separadas em tantas partições quantos forem
o número de veículos usados.

Por exemplo, se há 6 consumidores, 3 veículos e a
solução s é {0-3-4-0-1-5-2-0-6-0} então as rotas
dos veículos, denominadas pétalas, são {0-3-4-0},
{0-1-5-2-0} e {0-6-0}.
Estruturas de vizinhança:


Seja S o conjunto das soluções para o
PRV. As estruturas de vizinhança são
definidas por funções N que associam um
conjunto de soluções N(s) com cada
solução obtida por uma modificação
parcial de s, chamada movimento.
Consideramos duas estruturas de
vizinhança, a saber: N 1, N 2.
Movimentos:

O primeiro movimento consiste na troca de
dois números inteiros em uma mesma pétala
da solução.


Estes números representam apenas os
consumidores.
O segundo, representa a remoção de um
número inteiro de uma pétala e sua inserção
em uma outra pétala.

Esses números representam os consumidores.
Exemplo das Estruturas de
Vizinhança:

A vizinhança N 1(s) de uma dada solução s é
o conjunto de todos os vizinhos s' gerados
pelo primeiro movimento.


Por exemplo, dada a solução s = {0-3-4-0-1-5-20-6-0}
s' ={0-3-4-0-1-2-5-0-6-0}  N 1(s).
A vizinhança N 2(s) de uma dada solução s é
o conjunto de todos os vizinhos s' gerados
pelo segundo movimento.


Por exemplo, dada s1 = {0-3-4-0-1-5-2-0-6-0}
s’ = {0-4-0-1-5-2-0-3-6-0}
Função Objetivo:


Função objetivo baseada em penalização.
Seja f 1(s) representando a função objetivo
pura da solução s:



Soma das distâncias percorridas por todos os
veículos.
Seja O(s) o total das sobrecargas dos veículos
associada a esta solução, caso exista.
Função objetivo f (s) = f 1(s) + O(s)

 é um fator de penalidade não negativo.
Construção de uma solução
inicial:

Fase de construção do método GRASP
(Procedimento de busca adaptativa
gulosa e randomizada).

{0-2-1-6-...}.
Algoritmo da fase de construção:

Primeiro passo:



Seleciona-se um veículo aleatoriamente.
S =S U {A}. Inicialmente S={ }.
Lista_de_Candidatos = ordenar (V \ {s} ).



Critério de ordenação relativo à distância de cada um ao
último elemento adicionado à solução.
Esse processo de seleção é uma heurística adaptativa
gulosa, que estima o benefício da seleção de cada um dos
elementos.
A heurística é adaptativa porque os benefícios associados
com a escolha de cada elemento são atualizados em cada
iteração da fase de construção para refletir as mudanças
oriundas da seleção do elemento anterior.
Algoritmo da fase de construção:

Selecionar de forma aleatória a partir da lista de
candidatos restrita (LCR).



Se o consumidor selecionado exceder a capacidade
do veículo, adiciona-se a distância da cidade do
último consumidor escolhido ao depósito, finalizando
uma rota.


A LCR é composta pelos melhores candidatos de LC.
O tamanho da LCR é definido segundo um fator   [0,1],
tal que |LCR| =   |LC|.
A = {4 – 7 – 15 – 10 – 28 – 13 ... }
Repete-se este procedimento até que todos os
consumidores sejam atendidos.
Fase de Refinamento
• Refinamento via Busca Tabu
• Método de busca local que utiliza
uma estrutura de dados Lista para
evitar ciclagem.
• Função de Aspiração
Algoritmo
Procedimento Grasp_TB () {
para i = 0; i < graspMAX; i++ {
Solucao s = construcao_GRASP ();
buscaLocal(s);
}
s = buscaTabu(s);
retorne s;
}
Resultados
Tipo
Capacidade
Custo
A
300
3
B
150
1
C
200
2
Resultados
Tipo Rota
40-19-41-13-25-14-24-23
B
42-44-15-45-33-10-49-9-50-16
B
4-47-12-46-32-11-38-5-37-17
B
18-6-48-27-1-22-28-31
B
39-30-34-21-29-2-20-35
B
43-7-26-8-3-36
B
Custo Total: 1141
Demanda
141
131
147
128
148
82
Resultados
Tipo Rota
40-19-41-13-25-14-24-43
B
42-44-15-45-33-10-49-9-50-16
B
4-47-12-46-32-11-38-5-37-17
B
18-6-48-27-1-22-31-8
B
39-30-34-21-29-36-35-20
B
23-7-26-28-3-2
B
Custo Total: 1110
Demanda
136
131
147
137
124
102
Conclusão
O problema de roteamento de veículos além de
possuir grande aplicabilidade no mundo real, possui uma
grande complexidade para sua resolução computacional.