Um Estudo da Aplicação de Heurísticas Construtivas e de

Um Estudo da Aplicação de Heurísticas Construtivas e de
Melhoramento para um Problema de PRV
Eliseu Celestino Schopf1, Claudio Schepke1, Marcus Lucas da Silva1,
Pablo Furlan da Silva1
1
Centro de Eletrônica e Tecnologia – Universidade Federal de Santa Maria (UFSM)
Faixa de Camobi, km 9 – Santa Maria – RS – Brasil
{eliseu, schepke, marc, pablof}@inf.ufsm.br
Resumo. O problema de roteamento de veículos é um problema de otimização
combinatória, definido a mais de quarenta anos, que continua sendo uma
tarefa desafiadora. Este problema consiste em arranjar o conjunto ótimo de
rotas para determinada frota de veículos de maneira a servir um dado
conjunto de clientes. O interesse no problema de roteamento de veículos é
motivado pela sua relevância prática e pela sua considerável dificuldade. Na
resolução desse problema, tratada neste artigo, é estabelecida uma
comparação entre as heurísticas construtivas do “Vizinho Mais Próximo”, do
“Vizinho Mais Próximo Dá Chance” e o de Savings. Também, as heurísticas
de Melhoramento 2-OPT Intra-rotas, 2-OPT Inter-rotas e algoritmo de Swap,
são comparadas a partir da execução sobre as soluções iniciais resultantes
das heurísticas construtivas. Dessa forma, conseguiu-se quantificar, neste
estudo de caso, as melhorias definidas por cada heurística.
1. INTRODUÇÃO
Uma classe de problemas que desperta interesse, por parte de pesquisadores, devido a
sua complexidade, são os problemas não determinísticos em tempo polinomial (NP).
Esses problemas não apresentam soluções viáveis através de algoritmos tradicionais,
devido à alta exigência de tempo para a sua resolução. Uma alternativa, normalmente
adotada, é fazer uso de métodos heurísticos.
Os métodos heurísticos visam encontrar uma solução que satisfaça o problema,
não necessariamente a melhor, em um tempo computacional aceitável. Estes métodos
são aplicados a problemas cuja obtenção da solução ótima é computacionalmente
dispendiosa quando calculada por métodos exatos1.
O Problema do Roteamento de Veículos (PRV) é o nome genérico dado a uma
classe de problemas no qual é preciso determinar as rotas que minimizem o custo de
percorrimento de todos os pontos em uma dispersão geográfica. O PVR é um problema
da classe NP que pode ser utilizado em uma série de situações práticas no âmbito local
(centros distribuidores de produtos) a nacional (indústria automotiva)
[GALBIER,2004].
Este artigo apresenta uma comparação entre as heurísticas construtivas do
1
Método exato é aquele que testa todas as alternativas existentes do problema, resultando sempre na melhor solução
possível.
“Vizinho Mais Próximo”, “Vizinho Mais Próximo Dá Chance” e Savings. Também, as
heurísticas de melhoramento 2-OPT Intra-rotas, 2-OPT Inter-rotas e algoritmo de Swap,
são comparadas a partir da execução sobre as soluções iniciais resultantes das
heurísticas construtivas.
2. DESCRIÇÃO DAS HEURÍSTICAS APLICADAS
Para resolução do problema de roteamento de veículos, foram empregadas heurísticas
construtivas e de melhoramento, que seguem abaixo descritas.
2.1 Heurísticas Construtivas
Algoritmo “Vizinho Mais Próximo”
A heurística do vizinho mais próximo, descrita por [SOLOMON,1987] utiliza uma
matriz para definir a distância entre os pontos. O percurso é construído com base na
distância entre estes pontos, sendo o ponto mais próximo da origem adicionado primeiro
e os demais pontos adicionados posteriormente. Esses pontos são inseridos segundo a
sua proximidade em relação ao último ponto adicionado na rota.
Algoritmo “Vizinho Mais Próximo Dá Chance”
Este método é semelhante ao método de busca do mais próximo, porém, em vez de
encerrar a rota quando estoura a demanda, ele escolhe o ponto seguinte ao mais
próximo. Se também não couber, tenta o seguinte e assim sucessivamente. Se não achar
nenhum, encerra a rota.
Algoritmo de Savings
O Algoritmo de Savings, ou Algoritmos das Economias, proposto por Clarke e Wright
[CLARKE,1964], baseia-se na noção de economias, que pode ser definido como o custo
da combinação, ou união, de duas sub-rotas existentes. Trata-se de uma heurística
iterativa de construção baseada numa função gulosa de inserção.
Um algoritmo de Savings inicia com um processo iterativo que visa percorrer
todas as cidades duas a duas, de maneira a calcular as economias, ou seja, sendo i e j
cidades distintas, Cij o custo entre as duas cidades, e 0 o depósito, tem-se as economias
Sij:
Sij = C0i + Cj0 - Cij
Esta fórmula permite, então, ter o conhecimento das cidades com distâncias mais
próximas. Em segunda instância, um outro processo iterativo busca o maior Savings,
toma as duas cidades mais próximas e as roteia em relação à cidade-base. Segundo a
definição de [LIU, 1999], duas rotas contendo os clientes i e j podem ser combinadas,
desde que i e j estejam ou na primeira ou na última posição de suas respectivas rotas e
que a demanda total das rotas combinadas não ultrapasse a capacidade do veículo. Por
ser sempre escolhida a maior economia dentre as possíveis, a função de escolha é dita
gulosa.
2.2 Heurísticas de Melhoramento
Heurística 2-OPT Intra-rotas
O método de melhoramento 2-OPT intra-rotas proposto por [LINS,1973], consiste na
possível troca de dois arcos, não consecutivos, de uma rota e refazer as conexões,
criando uma nova rota. Se o custo da nova rota for menor que o custo da rota original, a
nova é mantida. O processo termina através de um critério de parada, que foi
estabelecido pelo número de execuções. Como pode ocorrer inversão de sentido em
parte da rota, pressupõe-se simetria de distâncias.
Heurística 2-OPT Inter-rotas
O método de melhoramento 2-OPT inter-rotas proposto por [LINS,1973], consiste na
possível troca de dois arcos de duas rotas diferentes, um de cada rota e refazer as
conexões, criando duas rotas novas. Haverá dois possíveis casos de rotas novas. Se o
custo das novas rotas, de algum dos casos, for menor que o custo das rotas originais e a
capacidade dos veículos não for ultrapassada, as novas rotas serão mantidas. O processo
termina através de um critério de parada, que foi estabelecido pelo número de
execuções. Como pode ocorrer inversão de sentido em parte da rota, pressupõe-se
simetria de distâncias.
Swap
O algoritmo de Swap, descrito em [CORBERAN,2000], consiste de trocas simples entre
cidades das rotas. Duas cidades diferentes são escolhidas aleatoriamente e, se a troca
delas diminui o custo total das rotas, essas cidades são trocadas de posição. O processo
termina através de um critério de parada por número de iterações pré-estabelecido.
3. IMPLEMENTAÇÃO
As heurísticas, expostas neste artigo, foram implementadas sob tecnologia Java,
utilizando plataforma JDK 1.4.1_02, de acordo com os passos descritos nesta seção.
3.1 Heurísticas Construtivas
Algoritmo “Vizinho Mais Próximo”
O algoritmo “Vizinho Mais Próximo” foi implementado conforme a seqüência de
passos escrita a seguir:
1) Define a cidade corrente como sendo a garagem.
2) Enquanto a soma das demandas para as cidades da rota não ultrapassar a
capacidade do caminhão, acrescenta a cidade mais próxima da cidade corrente
na rota, passando essa a ser a cidade corrente.
3) Quando ultrapassar a capacidade, encerra a rota.
4) Se ainda houverem cidades não acrescentadas em alguma rota, cria uma nova
rota, repetindo os passos 1 a 3.
Algoritmo “Vizinho Mais Próximo Dá Chance”
O algoritmo do “Vizinho Mais Próximo Dá Chance” foi implementado a partir de uma
modificação do terceiro passo do algoritmo “Vizinho Mais Próximo”, conforme a sua
implementação detalhada a seguir:
1) Define a cidade corrente como sendo a garagem.
2) Enquanto a soma das demandas para as cidades da rota não ultrapassar a
capacidade do caminhão, acrescenta a cidade mais próxima da cidade corrente
na rota, passando essa a ser a cidade corrente.
3) Quando ultrapassar a capacidade, escolhe a cidade seguinte na ordem de
proximidade até encontrar alguma que não estoure a capacidade ou não houver
mais cidades.
4) Encerra a rota.
5) Se ainda houverem cidades não acrescentadas em alguma rota, cria uma nova
rota, repetindo os passos 1 a 4.
Algoritmo de Savings
Sendo i e j cidades distintas, Cij o custo entre as duas cidades, 0 o depósito e Sij as
economias, o algoritmo de Savings se processa da seguinte forma:
1) Enquanto existirem economias a serem calculadas vai para 2, senão vai para
3.
2) Sij = C0i + Cj0 - Cij // Calcula Savings
3) Enquanto existirem Savings sem marcas, busca_maior_nao_marcado(Sij),
marca(Sij) e vai para 4, senão encerra rota.
4) Se i ou j já estiverem roteadas entre duas outras cidades, vai para 3.
5) Se i e j não estiverem roteados, tenta ligar a rota com extremidade em i com a
rota com extremidade em j. Vai para 3.
6) Se i está roteado e j não, roteia j a i, vai para 3.
7) Se j está roteado e i não, roteia i a j, vai para 3.
3.2 Heurísticas de Melhoramento
Heurística 2-OPT Intra-rotas
O algoritmo 2-OPT Intra-rotas foi implementado conforme os passos descritos a seguir:
1) Sorteia dois arcos diferentes da rota.
2) Se os dois arcos forem consecutivos, repete 1.
3) Troca os arcos e refaz conexões.
4) Se o custo da nova rota for menor que o custo da rota original: rota_original =
rota_nova.
5) Se número de execuções menor que critério de parada vai para 1.
Heurística 2-OPT Inter-rotas
O algoritmo 2-OPT Inter-rotas foi implementado conforme os passos descritos a seguir:
1) Seleciona um arco de cada rota.
2) Se os dois arcos forem ligados com a origem repete 1.
3) Troca os arcos e refaz conexões do caso 1.
4) Se o novo_custo < custo_original e Capacidade mantida, guarda rotas.
5) Troca os arcos e refaz conexões do caso 2.
6) Se o novo_custo < custo_original e Capacidade mantida, guarda rotas.
7) Atualiza rotas
8) Se número de execuções menor que critério de parada vai para 1.
Swap
O algoritmo de Swap realiza trocas simples entre duas cidades das rotas conforme
descrito a seguir:
1) Escolhe aleatoriamente duas cidades diferentes, independe de seres da mesma
rota ou não.
2) Se o custo das rotas com essas cidades trocadas de posição for menor que o
custo atual, troca as cidades.
3) Repete os passos 1 e 2 por um número de vezes pré estabelecido.
4. RESULTADOS
Nessa seção serão feitos dois tipos de comparações. Num primeiro momento, são
comparadas apenas as heurísticas construtivas, posteriormente são feitas comparações
das heurísticas de melhoramento, sendo executadas a partir da solução gerada por cada
uma das heurísticas construtivas.
Nesta seção será demonstrada a análise dos resultados de uma instância de vinte
e oito cidades. Para a realização dos testes foi usado um computador com processador
Pentium IV com velocidade de processamento de 2.4 MHz e 512 Mb de memória RAM.
As heurísticas são analisadas levando em consideração o tempo de execução e o
custo da solução construída. A demanda total para todas as cidades somou 1886
unidades de produto. Todos os algoritmos conseguiram encontrar soluções com cinco
rotas.
4.1 Comparações das Heurísticas Construtivas
Análise de custo
Percebe-se uma vantagem no resultado (custo) final da construção por parte do
algoritmo de Savings em relação aos algoritmos do “Vizinho Mais Próximo” (VMP) e
do “Vizinho Mais Próximo Dá Chance” (VMPDC). O primeiro obteve uma melhora de
1,95% e 1,71% sobre o VMP e VMPDC, respectivamente. Pode-se notar também, que o
algoritmo de VMPDC teve um custo 0.25% melhor do que o VMP. Essas informações
podem ser visualizadas através da figura 1.
C u s to d a s H e u rís tic a s C o n s tru tiv a s
1 00 00
995 0
990 0
985 0
C u sto
980 0
975 0
970 0
965 0
VMP
V M P DC
S avings
Figura 1: Comparação de custo das soluções geradas pelas heurísticas.
4.2 Comparações das Heurísticas de Melhoramento
As heurísticas de melhoramento são executadas a partir das soluções iniciais geradas
pelas heurísticas construtivas. Todas são executadas por 500 iterações.
Análise de custo
Nesta seção são apresentadas comparações de custos entre as heurísticas de
melhoramento 2-OPT Intra-rotas, 2-OPT Inter-rotas e de Swap.
Ao aplicar as heurísticas de melhoramento sobre o algoritmo construtivo de
“Vizinho Mais Próximo” se pode notar que o 2-OPT Intra-rotas não obtém melhora
alguma, ao contrário do 2-OPT Inter-rotas e Swap, os quais possibilitam uma melhora
de 0.63% e 1.41%, respectivamente. Tais informações podem ser vistas na figura 2.
Custo das Heurísticas de Melhoramento Sobre o
VMP
10000
9950
9900
9850
Intra2OPT
Inter2OPT
Swap
9800
9750
Figura 2: Comparação do custo das soluções obtidas pelas heurísticas sobre o
construtivo VMP.
As heurísticas de melhoramento aplicadas sobre o algoritmo construtivo do
“Vizinho Mais Próximo Dá Chance” proporcionam uma modesta melhoria de 0.08%,
0.7% e 0.88% para 2-OPT Intra-rotas, 2-OPT Inter-rotas e Swap, respectivamente. As
informações citadas podem ser visualizadas na figura 3.
Quando se utiliza o algoritmo construtivo de Savings e em seu resultado são
aplicadas heurísticas de melhoramento 2-OPT Intra-rotas, 2-OPT Inter-rotas e Swap,
obtém-se como resultado (custo) final uma melhoria de 0.25%, 1.7% e 1.02%,
respectivamente, como mostra a figura 4.
Custo das Heurísticas de Melhoramento Sobre o
VMPDC
9960
9940
9920
9900
9880
9860
9840
9820
Intra2OPT
Inter2OPT
Swap
Figura 3: Comparação do custo das soluções obtidas pelas heurísticas sobre o
construtivo VMPDC.
Custo das Heurísticas de Melhoramento Sobre o
Savings
9800
9750
Intra2OPT
9700
9650
Inter2OPT
Swap
9600
9550
Figura 4: Comparação do custo das soluções obtidas pelas heurísticas sobre o
construtivo Savings.
5. CONCLUSÃO
Quanto às heurísticas construtivas, pode-se perceber que a de Savings constrói uma
solução visivelmente melhor que as demais heurísticas.
Em relação às heurísticas de melhoramento aplicadas sobre as construtivas,
neste estudo, percebemos que a 2-OPT Inter-rotas sobre Savings obteve o melhor
resultado (menor custo), seguido do Swap sobre Savings e 2-OPT Intra-rotas, também,
sobre Savings. O pior resultado (maior custo) foi encontrado na combinação de 2-OPT
Intra-rotas sobre VMP. O melhor resultado apresentou uma melhora de 0.68% em
relação ao segundo, 1.45% em relação ao terceiro e 3.61% em relação ao pior caso.
6. REFERÊNCIAS BIBLIOGRÁFICAS
[CLARKE,1964] CLARKE, G. & WRIGHT, J., "Scheduling of vehicles from a central
depot to a number of delivery points", Operations Research, 12 #4, 568-581, 1964.
[CORBERAN,2000] CORBERÁN, A. & FERNÁNDEZ, E. & LAGUNA, M. &
MARTÍ, R. Heuristic Solutions to the Problem of Routing School Buses with Multiple
Objectives. Departament d’Estadística i Investigació Operativa, Universitat de
València, Burjassot 46100, Spain.August 7, 2000.
[GALBIER,2004] GALBIER, F & LORENA, L. A. N. Uma Heurística Construtiva
aplicada a Problemas de Roteamento de Veículos. Disponível e acessado em acessado
05 de julho de 2004 http://www.lac.inpe.br/~lorena/galbier/www/vrp.html.
[LINS,1973] LINS, S. & B. W. Kernigham. An Effective Heuristic Algorithm for the
Traveling Salesman Problem, Operations Research, v.21, p.498-516, 1973.
[LIU,1999] LIU, Fuh-Hwa & SHEN, Sheng-Yuan, A Metohd for Vehicle Routing
Problem with Multiple Vehicle Types ad Time Windows, Department of Industrial
Enginnering and Management National Chiao Tung University, Hsinchu, Taiwan, Proc.
Natl. Sci. Counc., vol 23, n. 4, p. 526-536, 1999.
[SOLOMON,1987] SOLOMON, M.M. Algorithms for the Vehicle Routing and
Scheduling Problems with Time Window Constraints. Operations Research, 35(2): p.
254-265. 1987.