ANÁLISE COMPARATIVA ENTRE HEURÍSTICAS E
METAHEURÍSTICAS APLICADAS AO PROBLEMA DE
ROTEAMENTO DE VEÍCULOS
Marcelo Caggiani Luizelli, Vinicius Jacques Garcia
Centro de Tecnologia de Alegrete – Universidade Federal do Pampa – UNIPAMPA
{mcluizelli, viniciusjg}@gmail.com
Resumo. Este artigo apresenta o clássico
problema de roteamento de veículos e
métodos factíveis de resolvê-lo. Dentre os
métodos abordados, citam-se: a heurística
das economias, proposta por Clarke e
Wright; a heurística de varredura, de Gillet
e Miller; e a metaheurística GRASP,
proposta por Feo e Resende. Para tanto, é
mostrado características de cada método,
assim como, os resultados obtidos com a
implementação dos algoritmos com relação
a custo da função objetivo e tempo de
execução para algumas instâncias referentes
ao problema.
Palavras-chave: Heurística, Metaheurística,
Roteamento de Veículos.
1.
INTRODUÇÃO
O problema de roteamento de veículos
(VRP) forma uma classe ampla de
algoritmos que, genericamente, resolvem o
problema de rotear uma frota de veículos a
partir de um depósito para um conjunto
disperso de consumidores. O objetivo do
VRP é atender os consumidores com um
custo mínimo de sua função objetivo
atendendo a certas restrições.
Na busca de uma solução factível,
encontram-se alguns meios admissíveis à
resolução do problema de roteamento.
Dentre os métodos, destaca-se a heurística
das economias, baseado na expansão
gradativa das rotas; a heurística de varredura
que parte do princípio de que os trajetos são
desenvolvidos
preferencialmente
entre
vizinhos; a metaheurística GRASP que é um
relevante método de solução de problemas
combinatório, diferencia-se dos demais por
possuir características gulosas, adaptativas e
aleatórias, podendo a aplicação resultar em
soluções de ótima qualidade.
2.
MODELO MATEMÁTICO
O problema de roteamento de veículos
clássico é a base para problema de
roteamento com configurações de restrições
mais elaboradas. O problema clássico VRP
consiste em determinar rotas de veículos
com um custo mínimo. Estas devem partir
de um único depósito e atender a todos os
pontos de demanda uma única vez. Para
tanto, é necessário respeitar a capacidade
dos veículos. Neste modelo é considerado
que a frota de veículos é homogênea, ou
seja, todos os veículos possuem as mesmas
características. Não é considerado janela de
tempo, tempo máximo de percurso ou outras
características particulares que descrevem
outros problemas. Uma das formulações
mais utilizadas como base a diversos
métodos de solução para o VRV é a de
Fisher e Jaikumar (1981), como segue:
Minimizar:
(1)
Sujeito a:
=1
i = 2,...,n
(2)
=m
<=
i=m
(3)
ponto
de
demanda
é
individualmente por um veículo.
atendido
k = 1,...,m (4)
=
=
i = 1,...,n k = 1,...,m
(5)
<=|S|-1
(6)
Figura 1. Esquema do processo de economia.
i = 1,...,n k = 1,...,m
(7)
i,j = 1,...,n k = 1,...,m
(8)
Onde:
= variável binária que assume valor 1
quando o veículo k visita o cliente j
imediatamente após o cliente i, 0 em caso
contrário.
= variável binária que assume valor 1 se
o cliente i é visitado pelo veículo k, 0 em
caso contrário.
é a demanda do cliente i.
é a capacidade do veículo k.
é o custo de percorrer o trecho que vai do
cliente i ao j.
3. MÉTODOS DE RESOLUÇÃO
Como mencionado, existem inúmeros
meios de resolução para o VRP. Cabe o
estudo de tais métodos para empregar
adequadamente a tal problema.
3.1 Heurística das economias
A heurística proposta por Clarke e
Wright (1964) é um método pioneiro e
tradicional na resolução do problema de
roteamento de veículos. Tal método baseiase no ganho de distâncias que pode ser
obtida ao atender dois pontos de forma
sucessiva em um roteiro, sem retornar ao
depósito.
A heurística parte do pressuposto que a
solução inicial é a pior possível, isto é, cada
A partir da solução inicial, calculam-se
todos os possíveis pares de pontos de
demanda passiveis de pertencer a uma
mesma rota. A cada par de pontos de
demanda, existe uma economia associada,
que é calculada como mostrado na Fig. 1.
Escolhe-se o par que oferecer maior
economia e faz-se as devidas inserções e
remoções de arestas respeitando a
configuração do problema. O processo
supracitado é repetido até que não restem
mais pontos de demanda sem atendimento
ou que as restrições do problema sejam
excedidas.
3.2 Heurística de varreduras
A heurística de Gillet e Miller (1974),
também conhecida como sweep algorithm, é
uma estratégia onde se procura obter a
solução do problema em duas etapas
distintas. A primeira visa agrupar os pontos
de demanda segundo algum critério de
proximidade, enquanto na segunda etapa
cada
grupo
é
solucionado
independentemente.
Este método parte do princípio de que
os trajetos entre os nós são desenvolvidos
preferencialmente entre os vizinhos. O
algoritmo explora a proximidade entre
vizinhos selecionando o ponto de demanda
que possuir o menor ângulo em relação ao
depósito. Para tanto, é desejável que estes
estejam em coordenada polar. Dado uma
lista de todos os pontos de demanda
passíveis de escolha, seleciona-se o ponto
com o menor ângulo. Este é adicionado à
rota desde que não exceda as restrições do
problema. O processo é repetido até que não
haja pontos sem atendimento.
A segunda etapa consiste em aplicar o
procedimento k-ótimo a cada rota
construída. O procedimento k-ótimo é um
procedimento de busca local que tem como
objetivo intensificar a qualidade da solução
obtida. A heurística k-ótima proposta por
Lin (1965) propõe uma busca em uma kvizinhança de uma solução de roteamento. A
busca se faz pelo exame da possibilidade de
troca de k arcos entre dois pontos. Na
medida em que k cresce, o procedimento
aproxima-se
da
enumeração
total.
Christofides et al. [1] relata soluções
eficientes para k = 2 e k = 3.
As duas abordagens utilizadas para a
heurística de busca local, First Improvement
e Best Improvement, apresentam diferenças.
First Improvement realiza a busca de
soluções melhores, com a troca de aresta, até
que se encontre uma primeira solução
melhor do que a original. O procedimento é
reiniciado e este somente acaba quando não
é mais encontrado melhoria alguma. Best
Improvement realiza uma busca completa no
espaço e seleciona a melhor opção. O
procedimento é reiniciado e para quando não
é mais encontrado melhoria.
3.3 Metaheurística GRASP
A metaheurística GRASP, proposta por
Feo e Resende (1989), é um método que
combina aspectos gulosos e aleatórios na
construção da solução.
O GRASP é um processo iterativo que a
cada iteração é construída uma solução e
então melhorada. A estratégia de construção
de uma solução no GRASP, consiste na
definição de um critério de avaliação dos
elementos, que podem ser inseridos em um
conjunto que, ao final do processo, será uma
solução para o problema. Esse critério
adapta-se à solução já construída, de forma
que a valoração dos elementos muda durante
a construção da solução.
O fato que permite que soluções com
qualidade superior sejam obtidas, se deve a
aleatoriedade e a adaptabilidade imposta na
etapa construtiva. Para cada ponto de
demanda corrente, é gerado uma lista de
possíveis candidatos a serem inseridos na
rota. Um fator α (alpha), no processo de
construção da lista restrita de candidatos,
determina seu tamanho, como mostra a Fig.
2.
Figura 2. Processo de criação da lista de
candidatos restrita.
A escolha do próximo ponto de
demanda a ser inserido na rota é aleatório,
para tanto, algumas abordagens são
possíveis: escolha uniforme; escolha baseada
no peso dos elementos; proporcional a
ocorrência; etc. Neste artigo implementouse o método usando a aleatoriedade com
base nas ocorrências, ou seja, proporcional
ao número de vezes que um par de pontos de
demanda apareceu em soluções anteriores.
Assim, soluções iniciais são propícias a
serem mais aleatórias e de pouca qualidade.
Enquanto são geradas novas soluções, a
ponderação da ocorrência de pares de pontos
de
demanda
vai
sendo
alterado,
determinando a adaptabilidade do método.
Para a etapa de melhoramento, usam-se
algoritmos de busca local.
4. RESULTADOS
A partir das implementações das
heurísticas e metaheurísticas, analisou-se o
desempenho em termos de tempo de
execução e custo da função objetivo para
instâncias propostas por Ref. [1],
comparando os resultados com os seus
respectivos custos ótimos conhecidos.
Para os referidos testes, usou-se um
computador com processador Turion X2 2.0
GHz, 2 GB de memória RAM e sistema
operacional
Ubuntu
64bits.
As
implementações foram realizadas em
linguagem Java.
A heurística das economias apresentou
resultados distantes do ótimo proposto por
Ref. [1]. Em média as instâncias obtiveram
disparidade de 100% em relação ao
resultado ótimo. Em relação ao tempo de
processamento, necessitou-se de curto
espaço de tempo para resolver tais
instâncias.
A heurística de varredura obteve tempo
de processamento mediano em comparação
com as demais abordagens. Em função de
possuir uma etapa de busca local, o tempo
de processamento aumenta em relação ao
algoritmo usado. O valor da função objetivo
obteve melhores valores com o uso do
procedimento 2-ótimo Best Improvement. O
uso da abordagem First Improvement
permite que, às vezes, obtenham-se soluções
melhores, pois optar por um mínimo local
pode ser melhor que um mínimo global. Tais
resultados podem ser observados na Tabela
1.
Tabela 1. Resultados
significativo em relação às demais
abordagens. Isto é diretamente influenciado
pelo número de iterações que o algoritmo
executa.
5. CONSIDERAÇÕES FINAIS
A roteirização de veículos requerer
obtenção de melhores resultados para tratar
de problemas mais complexos e com
configurações de restrições reais.
A partir dos resultados obtidos, nota-se
uma substancial superioridade dos resultados
do algoritmo de varredura. Isto se deve ao
fato de o método gerar soluções nos quais os
pontos de demanda estão agrupados.
Para trabalhos futuros, é interessante
avaliar a possibilidade de unir características
positivas de métodos de resolução a fim de
produzir soluções com maior qualidade.
REFERÊNCIAS
[1] CHRISTOFIDES, N; MINGOZZI, A;
TOTH, P. Combinatorial optimization, John
Wiley, Chichester 1979.
A metaheurística GRASP apresentou
resultados distante do ótimo conhecido para
as instâncias propostas em Ref. [1]. Para os
valores de α (alpha) foi utilizado valor igual
a 0,3. Assim, obteve-se soluções com
granularidade mediana. As soluções
rapidamente tendem a convergirem para
soluções mais homogêneas, pois as escolhas
aleatórias
vão
se
tornando
mais
direcionadas, consequência do histórico de
escolhas. Em relação ao tempo de
processamento, nota-se um aumento
[2]
LAPORTE, G.: “The vehicle routing
problem: an overview of exact and
approximate methods”. European
Journal of Operation Research, Vol.
59, p. 345-358, 1992.
[3]
T. A. Feo e M. G. C. Resende.
“Greedy randomized adaptive search
procedures.”. Jounal of Global
Optimization, 6:109–133, 1995.
[4]
CLARKE, G. & WRIGHT, J.W.:
“Scheduling of vehicles from a central
depot to a number of delivery points”.
Operations Research, Vol. 12, p. 568581, 1964.
[5]
GILLETT, B.E. & MILLER, L.R.: “A
heuristic algorithm for the vehicledispatch
problem”.
Operations
Research, Vol. 22, p. 341-349, 1974.