MÉTODO DE PESQUISA EM
VIZINHANÇA VARIÁVEL
APLICADO À RESOLUÇÃO
DO PROBLEMA DE
ROTEAMENTO DE VEÍCULOS
Dárlinton B. Feres Carvalho
[email protected]
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.
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 de construção GRASP.
Refinamento usando o Método de Pesquisa em
Vizinhança Variável (VNS).
 Baseado em função de avaliação que procura
minimizar as distâncias percorridas.
 As estruturas de vizinhança utilizadas no VNS são
simples e proporcionam alterações na solução
capazes de escapar de ótimos locais.
 O método para busca local no VNS é o Método de
Descida em Vizinhança Variável (VND) que
também foi projetado com estruturas simples e de
baixa complexidade para uma rápida execução.
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 a distância total da viagem.
Representação dos consumidores:
Consumidores:
Identificador,
Demanda.
Depósito:
Num. veículos.
Pontos no plano (x,y).
Cálculo das distâncias entre dois
consumidores:
Matriz de Distância Euclidiana:
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 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.
 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.

O elemento separador é representado pelo valor
zero e indica o depósito.
 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 seis estruturas de
vizinhança, a saber: N1, N2, N3, N4, N5, N6.
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, terceiro, quarto, quinto e
sexto movimentos consistem em efetuar
uma, duas, três, quatro ou cinco trocas,
respectivamente, entre quaisquer
elementos da solução.
Exemplo das Estruturas de
Vizinhança:
 A vizinhança N1(s) de uma dada solução s é o
conjunto de todos os vizinhos s' gerados pelo
primeiro movimento.

Por exemplo, s' ={0-3-4-0-1-2-5-0-6-0}  N1(s).
 A vizinhança N2(s) de uma dada solução s é o
conjunto de todos os vizinhos s' gerados pelo
segundo movimento.

Por exemplo, s' ={0-3-5-0-1-4-2-0-6-0}  N2(s).
 A vizinhança N3(s) de uma dada solução s é o
conjunto de todos os vizinhos s' gerados pelo
terceiro movimento.

Por exemplo, s' ={0-3-5-0-6-4-2-0-1-0}  N3(s).
Exemplo das Estruturas de
Vizinhança:
 A vizinhança N4(s) de uma dada solução s é o
conjunto de todos os vizinhos s' gerados pelo
quarto movimento.

Por exemplo, s' ={0-3-5-6-0-4-2-0-1-0}  N4(s).
 A vizinhança N5(s) de uma dada solução s é o
conjunto de todos os vizinhos s' gerados pelo
quinto movimento.

Por exemplo, s' ={0-3-5-6-0-4-0-2-1-0}  N5(s).
 A vizinhança N6(s) de uma dada solução s é o
conjunto de todos os vizinhos s' gerados pelo
sexto movimento.

Por exemplo, s' ={0-4-5-6-0-3-0-2-1-0}  N6(s).
Função Objetivo:
 Função objetivo baseada em penalização.
 Seja f1(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) = f1(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:
 S={0}.
 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).


A LCR é composta pelos melhores candidatos de
LC.
O tamanho da LCR é definido segundo um fator 
 [0,1], tal que |LCR| =   |LC|.
 Se o consumidor selecionado exceder a
capacidade do veículo insere-se um zero na
solução, relativo ao depósito, significando o fim
de uma rota e início de outra.


{0-2-3-1-?} C = 5. som(2+3+1+5) > q
=> {0-2-3-1-0-5}.
Método de Pesquisa em
Vizinhança Variável:
 O Método de Pesquisa em Vizinhança Variável,
conhecido como VNS (do termo em inglês
Variable Neighborhood Search) é um método de
busca local proposto por Mladenovic & Hansen
(1997) que consiste em explorar o espaço de
soluções através de trocas sistemáticas de
estruturas de vizinhança.

Não segue uma trajetória, mas explora vizinhanças
gradativamente mais “distantes” da solução
corrente.
procedimento VNS(s, t);
1
enquanto ( tempo_execução < t )
2
k  1;
3
enquanto ( k <= 10 )
4
escolha(k)
5
1: s’vizinho_qualquer(s, N1);
6
2: s’vizinho_qualquer(s, N2);
7
3: s’vizinho_qualquer(s, N3);
8
4: s’vizinho_qualquer(s, N4);
9
5: s’vizinho_qualquer(s, N5);
10
6: s’vizinho_qualquer(s, N5);
11
7: s’vizinho_qualquer(s, N6);
12
8: s’vizinho_qualquer(s, N6);
13
9: s’vizinho_qualquer(s, N6);
14
10: s’vizinho_qualquer(s, N6);
15
fim escolha;
16
s’VND(s’);
17
se ( f(s’) < f(s))
18
s  s’;
19
k  1;
20
senão
21
k  k + 1;
22
fim-se;
23
fim enquanto;
24
fim enquanto;
25
Retorne s;
{Retorne a melhor solução}
fim VNS;
Figura 1: Método VNS aplicado ao PRV.
Método de Descida em
Vizinhança Variável:
 O Método de Descida em Vizinhança Variável,
conhecido como VND (do termo em inglês
Variable Neighborhood Descent) é um método
de busca local proposto por Mladenovic &
Hansen (1997) que consiste em explorar o
espaço de soluções através de trocas
sistemáticas de estruturas de vizinhança,
aceitando somente soluções de melhora da
solução corrente e retornando à primeira
estrutura quando uma solução melhor é
encontrada.
Método de Descida em
Vizinhança Variável:
 Por explorar sistematicamente toda a
estrutura de vizinhança foram
consideradas apenas as estruturas de
vizinhança N1 e N2.
 As pesquisas nas estruturas de
vizinhança N3 a N6 , por terem alta
complexidade, e implicam na
degradação da performance do método
de busca local.
procedimento VND(s);
1 s’ s;
2 k  1;
3 enquanto ( k <= 2 )
4
escolha(k)
5
1: s’descida_1opt(s’);
6
2: s’ descida_2opt (s’);
7
fim escolha;
8
se ( f(s’) < f(s))
9
s  s’;
10
k  1;
11
senão
12
k  k + 1;
13
fim-se;
14 fim enquanto;
15 Retorne s;
{Retorne a melhor solução}
fim VND;
Figura 2: Método VND aplicado ao PRV.
Método proposto:
procedimento GRASP_VNS(, t);
1
s  ConstruaSolucaoInicial();
2
s  VNS(s, t);
3
Retorne s;
{Retorne a melhor solução}
fim GRASP_VNS;
Figura 3: Método proposto.
Alguns testes:
T
e
s
t
e
Instância
1
GRASP_VNS
#
cid
Cap.
vei.
Melhor
Valor
conhecido
c50.dat
50
160
524.61
150
2
c50.dat
50
160
524.61
3
c50.dat
50
160
4
c75.dat
75
5
c75.dat
75
Tempo
CPU (seg)

Melhor Valor
Valor Médio
Desvio
(%)
#
veic
*
Média
# veic
0,01
524.61
532.87
1.57
5
5
150
0,35
527.67
545.99
4.07
5
5.44
524.61
300
0,35
524.61
541.24
3.17
5
5.28
140
835.26
300
0,01
842.96
865.56
3.62
10
10.96
140
835.26
150
0,35
844.44
875.54
4.82
11
10.92
Todos os experimentos foram realizados em um PC com processador Pentium
IV, de 1.8 GHz, 512 MB de RAM rodando a plataforma Windows XP.
 f  f 100
*
Desvio =
f*
http://ina.eivd.ch/collaborateurs/etd/problemes.dir/vrp.dir/vrp.html
Conclusões:
 Geração de diferentes estruturas de
vizinhança que devem ser usadas em
uma ordem progressiva de
complexidade.
 O método proposto requer poucos
parâmetros, basicamente o fator de
aleatoriedade relativo à construção de
uma solução inicial, o tempo de
processamento e a seqüência de
estruturas de vizinhança.
Conclusões:
 A partir desses parâmetros pode-se representar
características do problema que irão guiar o
método e muitas vezes determinar a qualidade
da solução.

Por exemplo, partindo de um conhecimento prévio
do problema onde os consumidores estão
agrupados em regiões distantes entre si
(clustered), é conveniente adotar um critério de
baixa aleatoriedade na construção da solução
inicial. Em outros, um índice de aleatoriedade um
pouco mais elevado resulta em soluções finais de
melhor qualidade na média.