XXIV Encontro Nac. de Eng. de Produção - Florianópolis, SC, Brasil, 03 a 05 de nov de 2004
Um método híbrido para a resolução do
problema de roteamento de veículos
Alexandre Xavier Martins (UFMG) [email protected]
Marcone Jamilson Freitas Souza (UFOP) [email protected]
Otávio Mello Castro (UFOP) [email protected]
Resumo
Neste trabalho propomos um método híbrido, no qual técnicas heurísticas são combinadas
com um método exato para resolver o problema de roteamento de veículos (PRV).
Inicialmente, uma solução é gerada randomicamente. A seguir esta solução é refinada por
um procedimento de duas fases. Na primeira, um procedimento baseado em Simulated
Annealing é aplicado com o objetivo de encontrar uma solução viável. Na segunda fase, a
solução resultante é refinada por um procedimento de Busca Tabu (BT). O procedimento de
Busca Tabu também chama periodicamente um método exato para melhorar a rota de cada
veículo, isto é, ele aciona um método para resolver o problema do caixeiro viajante (PCV).
Os resultados computacionais demonstram a robustez do método proposto para as instâncias
testadas.
Palavras-chave: Roteamento de Veículos, Otimização Combinatória, Metaheurísticas.
1. Introdução
O Problema de Roteamento de Veículos (PRV) pode ser definido como segue: dado um
conjunto de cidades (ou consumidores), cada um com uma demanda qi por um produto, e um
depósito com veículos de capacidade Q, encontre a rota dos veículos minimizando os custos
de transporte.
Numerosas aplicações práticas do PRV são reportadas na literatura. Veja, por exemplo,
Brown & Graves (1981), Fisher et al. (1982), Bell et al. (1983), Evans & Norback (1985),
Golden & Watts (1987) para aplicações em indústrias químicas, de bebidas, de alimentos e
petrolíferas.
O interesse no PRV é devido à sua importância prática e também à sua grande dificuldade de
solução. Como uma generalização do Problema do Caixeiro Viajante (PCV), o PRV pertence
à classe de problemas NP-difíceis (LENSTRA, 1981), e um algoritmo em tempo polinomial
para encontrar a solução ótima não é conhecido. Existem algoritmos exatos que raramente
resolvem instâncias envolvendo mais que 50 cidades (RENAUD & BOCTOR, 2002).
Devido ao limitado sucesso de métodos exatos, pesquisas têm sido desenvolvidas no sentido
de desenvolver heurísticas capazes de encontrar boas soluções para instâncias de maior porte.
Exemplos dessas heurísticas podem ser encontradas em Taillard (1993), Osman (1993),
Gendreau et al. (1994) e Renaud et al.(1996).
Para revisar as mais importantes heurísticas aplicadas ao PRV veja Cordeau et al. (2002) e
Laporte (1992). Uma bibliografia sobre o PRV pode ser vista em Laporte & Osman (1995).
Neste trabalho é proposto um método híbrido, no qual técnicas heurísticas são combinadas
com um método exato, para resolver o PRV. Inicialmente uma solução é gerada
aleatoriamente. Depois, esta solução é refinada por um procedimento de duas fases. Na
primeira, é aplicada a metaheurística Simulated Annealing. Na segunda fase, a solução
ENEGEP 2004
ABEPRO
3167
XXIV Encontro Nac. de Eng. de Produção - Florianópolis, SC, Brasil, 03 a 05 de nov de 2004
resultante da primeira é refinada por um procedimento de Busca Tabu (BT). O procedimento
BT também chama periodicamente um método exato para melhorar a rota de cada veículo,
isto é, um método para resolver o Problema do Caixeiro Viajante (PCV).
2. Formulação do Problema de Roteamento de Veículos
Seja G = (V, A) um grafo direto onde V = {v0, v1,..., vn} é o conjunto de vértices e A = {(vi, vj):
i ≠ j} é o conjunto de arcos. O vértice v0 representa um depósito onde se encontra um
conjunto de veículos idênticos de capacidade Q, enquanto os vértices restantes correspondem
às cidades ou consumidores. Cada consumidor vi tem uma demanda não-negativa qi e q0 = 0.
A cada arco (vi, vj) está associada uma distância não-negativa cij que representa a distância
entre os consumidores (nós).
O PRV consiste em determinar o conjunto de rotas que devem ser seguidas pelos veículos
minimizando os custos de transporte dado pelas distâncias obedecendo às seguintes restrições:
(a) Cada rota começa e termina no depósito;
(b) Cada cidade de V\{v0} é visitada somente uma única vez por somente um veículo;
(c) A demanda total de cada rota não pode exceder a capacidade do veículo.
3. Método exato para o PCV
Para encontrar a melhor seqüência de visitas em cada rota é necessário resolver o Problema do
Caixeiro Viajante (PCV). Seja Vr um subconjunto de V incluindo o depósito, isto é, uma
permutação de um conjunto de cidades começando do depósito (uma pétala da solução do
PRV). Uma formulação exata citada em Laporte (1992) é apresentada abaixo.
min ∑ ∑ cij xij
(1)
∑x
= 1 ∀j ∈ Vr
(2)
i∈Vr j∈Vr
j ≠i
sujeito a:
i∈Vr
i≠ j
ij
∑x
ij
= 1 ∀i ∈ Vr
(3)
∑y
ji
− ∑ y ij = 1 ∀j ∈ Vr \ {v0 }
(4)
j∈Vr
j ≠i
i∈Vr
i≠ j
ENEGEP 2004
i∈Vr
i≠ j
y ij ≤ (n − 1) xij ∀i, j ∈ Vr
(5)
xij ∈ {0,1} ∀i, j ∈ Vr
(6)
y ij ≥ 0 ∀i, j ∈ Vr
(7)
ABEPRO
3168
XXIV Encontro Nac. de Eng. de Produção - Florianópolis, SC, Brasil, 03 a 05 de nov de 2004
4. Representação do PRV
Neste trabalho foi adotada 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 cidades, 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, chamadas pétalas, são {0-3-4-0}, {0-1-5-2-0} e {0-6-0}.
5. Estrutura de vizinhança
Seja S o conjunto de soluções para o PRV. Afim de derivar um algoritmo baseado em busca
local para resolver o PRV, é necessário definir uma estrutura de vizinhança, isto é, uma
função N a qual está associado um conjunto de soluções N(s) com cada solução s ∈ S obtida
por uma modificação parcial de s, chamada movimento. Neste trabalho são considerados dois
tipos de movimentos, definindo assim duas estruturas de vizinhança, N 1 e N 2 . O primeiro
movimento consiste em trocar dois números inteiros da solução. Este número pode
representar o consumidor ou o depósito. O segundo movimento consiste em trocar dois
consumidores que pertencem a rotas diferentes.
A vizinhança N 1 ( s ) de uma dada solução s é o conjunto de todos vizinhos s' gerados pelo
primeiro movimento. Por exemplo, s' ={0-3-4-0-1-0-5-2-6-0} ∈ N 1 ( s ) .
A vizinhança N 2 ( s ) de uma dada solução s é o conjunto de todos vizinhos s' gerados pelo
segundo movimento. Por exemplo, s' ={0-3-5-0-1-4-2-0-6-0} ∈ N 2 ( s ) .
6. Função de avaliação
A função de avaliação usada neste trabalho é apresentada a seguir. Seja f1(s) a função objetivo
propriamente dita de uma dada solução s, isto é, a soma de todas as distâncias percorridas, e
O(s) a sobrecarga dos veículos que seguem rotas acima de suas capacidades, caso haja algum
associado a esta solução. O algoritmo desenvolvido trabalha com a seguinte função de
avaliação f(s) = f1(s) + β×O(s), onde β é um fator de penalidade não-negativo.
7. Simulated Annealing
Simulated Annealing é uma classe de metaheurística proposta originalmente por Kirkpatrick
et al. (1983), sendo uma técnica de busca local probabilística, que se fundamenta em uma
analogia com a termodinâmica, ao simular o resfriamento de um conjunto de átomos
aquecidos, operação conhecida como recozimento. Esta técnica começa sua busca a partir de
uma solução inicial qualquer. O procedimento principal consiste em um loop que gera
aleatoriamente, em cada iteração, um vizinho s’ da solução corrente s.
A cada geração de um vizinho s’ de s, é testada a variação ∆ do valor da função objetivo, isto
é, ∆ = f(s’) – f(s). Se ∆ < 0, o método aceita a solução e s’ passa a ser a nova solução corrente.
Caso ∆ ≥ 0 a solução vizinha candidata também poderá ser aceita, mas neste caso, com uma
probabilidade e-∆/T, onde T é um parâmetro do método, chamado de temperatura e que regula
a probabilidade de aceitação de soluções com custo pior.
ENEGEP 2004
ABEPRO
3169
XXIV Encontro Nac. de Eng. de Produção - Florianópolis, SC, Brasil, 03 a 05 de nov de 2004
A temperatura T assume, inicialmente, um valor elevado T0. Após um número fixo de
iterações (o qual representa o número de iterações necessárias para o sistema atingir o
equilíbrio térmico em uma dada temperatura), a temperatura é gradativamente diminuída por
uma razão de resfriamento α, tal que Tn ← α * Tn-1, sendo 0 < α < 1. Com esse procedimento,
dá-se, no início uma chance maior para escapar de mínimos locais e, à medida que T
aproxima-se de zero, o algoritmo comporta-se como o método de descida, uma vez que
diminui a probabilidade de se aceitar movimentos de piora (T→0⇒ e-∆/T →0).
O procedimento pára quando a temperatura chega a um valor próximo de zero e nenhuma
solução que piore o valor da melhor solução é mais aceita, isto é, quando o sistema está
estável.
Os parâmetros de controle do procedimento são a razão de resfriamento α, o número de
iterações para cada temperatura (SAmax) e a temperatura inicial T0. A Figura 1 apresenta o
algoritmo Simulated Annealing básico.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
Procedimento S.A. (f(.), N(.), α, SAmax, T0, s)
s* ← s;
{Melhor solução obtida até então}
IterT ← 0;
{Número de iterações na temperatura T}
{Temperatura corrente}
T ← T0;
enquanto (T > 0) faça
enquanto (IterT < SAmax) faça
IterT ← IterT + 1;
Gere um vizinho qualquer s’ ∈ N(s);
∆ = f(s’) – f(s);
se (∆ < 0)
então s ← s’;
se (f(s’) < f(s*)) então s* ← s’;
senão Tome x ∈ [0,1];
se (x < e-∆/T) então s ← s’;
fim-se;
fim-enquanto;
T ← α × T;
IterT ← 0;
fim-enquanto;
s ← s*;
Retorne s;
Fim S.A.;
Figura 1 – Algoritmo Simulated Annealing
8. Busca Tabu
A Busca Tabu é um procedimento adaptativo, originado do trabalho de Glover (1986), que
aceita movimentos de piora para escapar de ótimos locais. O procedimento começa com uma
solução inicial s0 e a cada iteração explora um subconjunto V da vizinhança N(s) da solução
corrente s. O membro s’ de V com menor valor nessa região segundo a função f(.) torna-se a
nova solução corrente mesmo que s’ seja pior que s, isto é, que f(s’) > f(s).
O critério de escolha do melhor vizinho é usado para escapar de um mínimo local. Esta
estratégia, entretanto, pode fazer com que o algoritmo cicle, isto é, que retorne a uma solução
já gerada anteriormente. De forma a evitar que isso ocorra, existe uma lista tabu T, a qual é
uma lista de movimentos proibidos. A lista tabu clássica contém os movimentos reversos aos
últimos |T| movimentos realizados e funciona como uma fila de tamanho |T|, isto é, quando
ENEGEP 2004
ABEPRO
3170
XXIV Encontro Nac. de Eng. de Produção - Florianópolis, SC, Brasil, 03 a 05 de nov de 2004
um novo movimento é adicionado à lista, o mais antigo sai. Assim, na exploração do
subconjunto V da vizinhança N(s) da solução corrente s, ficam excluídos da busca os vizinhos
s’ que são obtidos de s por movimentos m que constam na lista tabu.
procedimento BT_PCV_Exato(s, BTmax, NCWImax, NCEmax)
{Melhor solução até o momento}
1
s* ← s;
2
BestIter ← 0;
{Iteração na qual s* foi encontrada}
3
Iter ← 0;
{Contador de iterações}
4
T ← ∅;
{Lista Tabu}
5
NCWI ← 0;
{Número de iterações sem melhora de f(s*)}
6
NCE ← 0;
{Número de vezes que a Busca Tabu foi chamada}
7
Exact ← true;
8
enquanto (não exceder o tempo limite) faça
9
enquanto (Iter – BestIter < BTmax) faça
10
Iter ← Iter + 1;
11
Seja s’ ← s ⊕ m o melhor vizinho em N1(s) tal que o movimento
12
m não seja tabu ou s’ satisfaça o critério de aspiração;
13
Atualize a Lista Tabu T;
14
s ← s’;
15
se (f(s) < f(s*)) então
16
s ← s*; BestIter ← Iter; Exact ← true; NCWI ← 0;
17
fim-se;
18
fim-enquanto;
19
s ← s*; NCWI ← NCWI + 1; T ← ∅;
20
Sorteia |T| ∈ [|T|min, |T|max];
21
se (NCWI ≥ NCWImax e Exact = true) então
22
s’ ← Exact_TSP(s); {Todas as pétalas}
23
se (f(s’) < f(s*))
24
então s* ← s’; BestIter ← Iter; NCWI ← 0;
25
senão
26
NCE ← 0;
27
enquanto (NCE < NCEmax) faça
28
Iter ← Iter + 1;
29
s’ ← s ⊕ m o melhor vizinho em N2(s)
30
tal que o movimento m não seja tabu);
31
Atualize a lista tabu;
32
s” ← PCV_Exato(s); {Somente as pétalas modificadas}
33
se (f(s”) < f(s*))
34
então s ← s”; BestIter ← Iter; NCWI ← 0;
35
senão NCE ← NCE + 1; Exact ← false;
36
fim-se;
37
fim-enquanto;
38
fim-se
39
fim-se;
40
fim-enquanto;
fim TS_Exact_TSP;
Figura 2 – Algoritmo BT_PCV_Exato
Além da lista tabu, existe uma função de aspiração, que é um mecanismo que retira, sob certas
circunstâncias, o status tabu de um movimento. Mais precisamente, para cada possível valor v
da função objetivo existe um nível de aspiração A(v): uma solução s’ em V pode ser gerada se
f(s’) ≤ A(f(s)), mesmo que o movimento esteja na lista tabu. No nosso caso, o critério de
aspiração adotado foi por objetivo, isto é, um movimento ainda que tabu é realizado caso ele
melhore a melhor solução encontrada até então.
ENEGEP 2004
ABEPRO
3171
XXIV Encontro Nac. de Eng. de Produção - Florianópolis, SC, Brasil, 03 a 05 de nov de 2004
Duas regras são normalmente utilizadas de forma a interromper o procedimento. Pela
primeira, pára-se quando é atingido um certo número máximo de iterações sem melhora no
valor da melhor solução. Pela segunda, quando o valor da melhor solução chega a um limite
inferior conhecido (ou próximo dele). Esse segundo critério evita a execução desnecessária do
algoritmo quando uma solução ótima é encontrada ou quando uma solução é julgada
suficientemente boa. No nosso caso, adotamos o tempo de CPU como critério de parada.
Os parâmetros principais de controle do método de Busca Tabu são a cardinalidade |T| da lista
tabu, a função de aspiração A, a cardinalidade do conjunto V de soluções vizinhas testadas em
cada iteração e BTmax, o número máximo de iterações sem melhora no valor da melhor
solução.
A Busca Tabu proposta também chama uma DLL (Dynamic Link Library) do LINGO Solver
para resolver de forma exata uma instância do Problema do Caixeiro Viajante (PCV), isto é, a
Busca Tabu usa o LINGO para melhorar a rota de cada veículo. Apesar do PCV também ser
um problema NP-completo, quando o número de cidades é pequeno este pode ser resolvido de
forma eficiente por um modelo exato, e como a rota de cada veículo é limitada pela sua
capacidade, o número de cidades que este visita permite o uso do modelo exato sem a perda
de eficiência computacional. O pseudo-código da Busca Tabu usando o modelo exato do
PCV, chamado BT_PCV_Exato, é mostrado na Figura 2.
9. O método híbrido proposto
O método híbrido proposto combina Simulated Annealing e a versão da Busca Tabu relatada
na seção anterior.
Inicialmente, uma solução é gerada aleatoriamente. Esta solução passa por um procedimento
de duas fases. Na primeira, o algoritmo Simulated Annealing é aplicado com o objetivo de
encontrar uma boa solução. Depois, a solução gerada é refinada pelo procedimento
BT_PCV_Exato. A Figura 3 ilustra o pseudo-código do método proposto.
1
2
3
4
procedimento SA_BT_PCV_Exato;
s0 ← Construa uma solução randômica;
s ← SA(s0);
s* ← BT_PCV_Exato(s, BTmax, NCWImax, NCEmax);
Return s*;
{Retorne a melhor solução}
fim SA_BT_PCV_Exato;
Figura 3 – Algoritmo SA_BT_PCV_Exato
10. Testes Computacionais
O método proposto foi codificado em C++ e testado em 3 instâncias clássicas do PRV
disponíveis em http://ina.eivd.ch/collaborateurs/etd/problemes.dir/vrp.dir/vrp.html. Todos os
experimentos foram rodados em um PC com processador Pentium IV, 1.6 GHz de clock e 256
MB de RAM. Os parâmetros utilizados para o método Simulated Annealing foram os
seguintes: Temperatura Inicial = T0 = 10000; Número de Iterações sem Resfriamento =
SAmax = 10000; Taxa de Resfriamento = α = 0.7. Para o método BT_PCV_Exato os
parâmetros adotados foram: Cardinalidade da lista Tabu = 0.2 × |V| ≤ |T | ≤ 0.9 × |V|, onde |V|
é o número de cidades a ser visitadas; Número de Iterações Sem Melhora = BTmax = 2000;
NCWImax = 4; NCEmax = 25.
ENEGEP 2004
ABEPRO
3172
XXIV Encontro Nac. de Eng. de Produção - Florianópolis, SC, Brasil, 03 a 05 de nov de 2004
Para cada instância foram executados 25 testes, cada qual partindo de sementes diferentes de
números aleatórios. Na Tabela 1 são apresentados os resultados obtidos, na qual se compara
os desempenhos dos procedimentos heurísticos com e sem o método exato, denotados
respectivamente por SA_BT e SA_BT_PCV_Exato. As colunas 2 e 3 representam o número
de cidades e a capacidade dos veículos para cada instância, respectivamente. A coluna
“desvio” significa a porcentagem de desvio entre o melhor valor conhecido na literatura e o
( f − f * )× 100 .
valor médio encontrado pelo algoritmo e é dado pela fórmula seguinte,
f*
Ins-
Melhor Tempo
valor
de
tân#
Cap
Melhor
conhecido CPU
Valor
cia cidades
(sec.)
SA_BT
SA_BT_PCV_Exato
Valor
Médio
Desvio
(%)
Melhor
Valor
Valor
Médio
Desvio
(%)
1
50
160
524.61
300
524.61
528.44
0.73
524.61
526.84
0.43
2
75
140
835.26
600
844.57
859.28
2.88
845.00
852.56
2.07
3
100
112
1082.65
900
1119.14 1130.83
4.45
1110.31 1121.71
3.61
Tabela 1 – Resultados Computacionais
11 – Conclusões
Este trabalho propõe a combinação das metaheurísticas Simulated Annealing e Busca Tabu
com um método exato para resolução do Problema de Roteamento de Veículos. Foi mostrado
que o método proposto produz soluções de boa qualidade e é mais robusto do que o
procedimento que não faz uso do método exato, já que é capaz de encontrar soluções
próximas das melhores soluções conhecidas com um menor desvio.
É importante observar, no entanto, que o método proposto deve ser usado quando o número
de cidades em cada rota for pequeno; caso contrário, o método exato utilizado na resolução do
PCV pode falhar, em vista da NP-completude deste último problema.
Referências
BELL, W.; DALBERTO, L.; FISHER, M. L.; GREENFIELD, A.; JAIKUMAR, R.; MACK, R. &
PRUTZMAN, P. (1983), Improving distribution of industrial gases with an on-line computerized routing and
scheduling systems, Interfaces, Vol. 13, p. 4-23.
BROWN, G. & GRAVES, G. (1981), Real-time dispatch of petroleum tank trunks, Management Science, Vol.
27, p. 19-32.
CORDEAU, J. F.; GENDREAU, M.; LAPORTE, G.; POTVIN, J. Y. & SEMET, F. (2002), A guide to vehicle
routing heuristics, Journal of the Operational Research Society, Vol. 53, p. 512-522.
EVANS, S & NORBACK, J (1985), The impact of a decision-support system for vehicle routing in a food
service supply situation, Journal of the Operational Research Society, Vol. 36, p. 467-472.
FISHER, M. L.; GREENFIELD, R.; JAIKUMAR, R. & LESTER, J. (1982), A computerized vehicle routing
application, Interfaces, Vol. 1, p. 45-52.
GENDREAU, M.; HERTZ, A. & LAPORTE, G. (1994), A tabu search heuristic for the vehicle routing problem,
Management Science, Vol. 40, p. 1276-1290.
GLOVER, F. (1986), Future paths for integer programming and links to artificial intelligence, Computers and
Operations Research, Vol. 13, p. 533-549.
GLOVER, F. & LAGUNA, M. (1997), Tabu Search, Kluwer Academic Publishers, Boston.
ENEGEP 2004
ABEPRO
3173
XXIV Encontro Nac. de Eng. de Produção - Florianópolis, SC, Brasil, 03 a 05 de nov de 2004
GOLDEN, B. L. & WATTS, E. (1987), Computerized vehicle routing in the soft drink industry, Operations
Research, Vol. 35, p. 6-17.
KIRKPATRICK, S.; GELOTT, D. C. & VECCHI, M. P. (1983), Optimization by Simulated Annealing, Science,
Vol. 220, p. 671-680.
LAPORTE, G. (1992), The Vehicle-Routing Problem – An Overview of exact and approximate algorithms,
European Journal of Operational Research, Vol. 59, p. 345-358.
LAPORTE, G & OSMAN, I. H. (1995), Routing Problems: A bibliography, Annals of Operations Research,
Vol. 61, p. 227-262.
LENSTRA, J. & RINNOOY KAN, A. (1981), Complexity of vehicle routing and scheduling problems,
Networks, Vol.11, p. 221-228.
LINDO SYSTEMS INC. (2001), http://www.lindo.com, Optimization modeling with LINGO.
PRADENAS, L. & PARADA, V. (1999), Use of Genetic Algorithms, Tabu Search and Simulated Annealing in
the Vehicle Routing Problem, Proceedings of the Third Metaheuristics International Conference (MIC'99), p.
371-374.
OSMAN, I. H. (1993), Metastrategy simulated annealing and tabu search algorithms for the vehicle routing
problem, Annals of Operations Research, Vol. 41, 421-451.
RENAUD, J.; BOCTOR, F. F. &. LAPORTE, G. (1996), An improved petal heuristic for the vehicle routing
problem, Journal of the Operational Research Society, Vol. 47, p. 329-336.
RENAUD, J. & BOCTOR, F. F. (2002), A sweep-based algorithm for the fleet size and mix vehicle routing
problem, European Journal of Operational Research, Vol. 140, p. 618-628.
TAILLARD, E. D. (1993), Parallel iterative search methods for vehicle routing problems, Networks 23, 661-673.
ENEGEP 2004
ABEPRO
3174