MÉTODO DE PESQUISA EM VIZINHANÇA VARIÁVEL APLICADO À RESOLUÇÃO DO PROBLEMA DE ROTEAMENTO DE VEÍCULOS

Dárlinton B. Feres Carvalho

dioncons@iceb.ufop.br

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

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.

Características:

Representação dos consumidores:

Pontos no plano (x,y).

Depósito:Num. veículos.

Consumidores:Identificador,Demanda.

Cálculo das distâncias entre dois consumidores:

Matriz de Distância Euclidiana:

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):

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ão21 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ão12 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:

Teste

Instância#

cidCap.vei.

Melhor Valor

conhecido

TempoCPU (seg)

GRASP_VNS

Melhor Valor Valor MédioDesvio

(%)

#veic

*

Média# veic

1 c50.dat 50 160 524.61 150 0,01 524.61 532.87 1.57 5 5

2 c50.dat 50 160 524.61 150 0,35 527.67 545.99 4.07 5 5.44

3 c50.dat 50 160 524.61 300 0,35 524.61 541.24 3.17 5 5.28

4 c75.dat 75 140 835.26 300 0,01 842.96 865.56 3.62 10 10.96

5 c75.dat 75 140 835.26 150 0,35 844.44 875.54 4.82 11 10.92

*

* 100

f

ff Desvio =

http://ina.eivd.ch/collaborateurs/etd/problemes.dir/vrp.dir/vrp.html

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.

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.