XXXVI SBPO
XXXVI SBPO
XXXVI Simpósio Brasileiro
de Pesquisa Operacional
São João del-Rei, 23 a 26 de novembro de 2004
Modelagens Exata e Heurística
para uma Generalização do
Problema do Caixeiro Viajante
Autores:
Antonio Augusto Chaves
Fabrício Lacerda Biajoli
Otávio Massashi Mine
Marcone Jamilson Freitas Souza
(INPE)
(INPE)
(UFES)
(UFOP)
Roteiro
• INTRODUÇÃO
• PROBLEMA DO CAIXEIRO VIAJANTE COM COLETA DE
PRÊMIOS
• MODELAGEM
– PROGRAMAÇÃO MATEMÁTICA (EXATA)
– HEURÍSTICA
• RESULTADOS COMPUTACIONAIS
• CONCLUSÃO
Introdução
• Justificatica do trabalho
– fácil adaptação a situações da vida real
– existem poucos trabalhos sobre este problema
– número elevado de soluções existentes (n - 1)! / 2
• Utiliza-se uma formulação matemática proposta por Egon Balas
para encontrar a solução ótima para o problema
• Utiliza-se Greedy Randomized Adaptive Search Procedure
(GRASP), Variable Neighborhood Search (VNS) e Variable
Neighborhood Descent (VND) para solucionar aproximadamente
o problema
Problema do Caixeiro Viajante com
Coleta de Prêmios (PCVCP)
• Dado um conjunto de clientes com um custo de deslocamento
entre eles, o PCVCP consiste em determinar uma rota para um
Caixeiro Viajante, sabendo-se que para cada cliente visitado é
coletado um prêmio e para cada cliente não visitado é pago uma
penalidade.
• Objetivos:
– Minimizar o custo de deslocamento total
– Minimizar a soma das penalidades
– Coletar um prêmio mínimo pré-estabelecido
Problema do Caixeiro Viajante com
Coleta de Prêmios (PCVCP)
w1 / p1
C15
1
C14
w5 / p5
5
C45
C05
C01
DEPÓSITO
C13
C12
C04
w4 / p4
C25
C02
2
w2 / p2
4
C24
C23
C03
C35
C34
3
w3 / p3
Depósito:
w=0
p=
Modelagem Exata
• Encontrar o ótimo global
• Implementada a partir da formulação matemática proposta por
Egon Balas em 1985
• Utilizou-se o software LINGO versão 7.0
• Devido à natureza combinatorial do problema, somente problemas
de pequenas dimensões podem ser resolvidos através desse
procedimento
• Importância: permite a validação das soluções obtidas pela
metodologia heurística desenvolvida
Formulação Matemática
(P CVCP ) minimizar
 c x
iV jV
ij ij

 p (1  y )
iV
i
i
sujeito à :
x
 yi
 i  V \ {0}
(1)
x
 yj
 j  V \ {0}
(2)
jV \{i}
iV \{ j }
ij
ij
w y
iV
f
jV
i
ij
i
 wmin
(3)
  f ji  yi  i  V \ {0}
(4)
jV
f ij  | V |  1xij
 (i, j )  E
(5)
xij  {0,1}
 (i, j )  E
(6)
y j  {0,1}
 i V
(7)
Modelagem Heurística
• Procura encontrar boas soluções a um custo computacional
razoável, sem no entanto, garantir a otimalidade das solução finais
obtidas, nem o quão próximo esta solução está da solução ótima;
• Utilizou-se o conceito de metaheurísticas híbridas combinando
GRASP e VNS
Função de Avaliação
• Uma solução é avaliada pela seguinte função de avaliação:
f ( x)   cij xij 
iV jV
 p (1  y )   * max{ 0, -  w * y
iV
i
i
iV
i
i
 wmin}
• As demais restrições foram contempladas através da representação
adotada.
Estruturas de Vizinhança
m1: Retirar vértice de maior economia
economia (k) = cik + ckj – cij – pk
k
j
N1(s) = {s’ : s + m1}
i
vértice com maior economia de remoção
Solução (s)
0
3
1
Solução (s’)
0
3
5
5
Estruturas de Vizinhança
m2: Inserir vértice de maior economia
economia (k) = cij + pk – cik – ckj
i
N2(s) = {s’ : s + m2}
k
j
Solução (s)
0
3
1
5
Solução (s’)
0
3
1
2
5
vértice com maior economia de inserção
Estruturas de Vizinhança
m3: Trocar 2 vértices da solução;
N3(s) = {s’ : s + m3}
Solução (s)
0
3
1
5
Solução (s’)
0
5
1
3
Estruturas de Vizinhança
m4: Retirar vértice aleatoriamente;
N4(s) = {s’ : s + m4}
vértice escolhido aleatoriamente
Solução (s)
0
3
1
Solução (s’)
0
1
5
5
Estruturas de Vizinhança
m5: Inserir vértice aleatoriamente;
N5(s) = {s’ : s + m5}
Solução (s)
0
3
1
5
Solução (s’)
0
3
4
1
5
vértice escolhido aleatoriamente
GRASP + VNS
GRASP
Fase de Construção
Lista de Candidatos
LCR
1.
Criar uma lista de candidatos calculando a economia de inserção dos vértices
que não fazem parte da rota
2.
Definir a LCR como as 10 maiores economias de inserção
3.
Escolher aleatoriamente um candidato da LCR e inserir na rota
4.
Atualizar a lista de candidatos
 Este procedimento é executado enquanto o prêmio mínimo não for coletado ou
existir economia positiva
 Aplicação de filtro na fase de construção
Fase de Busca Local
Aplicar VNS
Algoritmo GRASP + VNS
Procedimento GRASP+VNS
f*  ;
// Fase de Construção
para j = 1, ..., MaxIter faça
s  ;
Inserir a origem em s;
para todo k não pertencente a s faça
Calcule a economia de inserção;
fim-para;
enquanto prêmio < wmin ou existir economia positiva faça
LCR  Lista dos vértices com maior economia;
Selecione aleatoriamente um vértice v  LCR;
s  s  {v};
Atualizar Lista de Candidatos;
fim-enquanto;
se f(s) < f* então s*  s;
f*  f(s);
fim-para;
s  s*;
// Fase de Busca Local
Aplicar VNS(s);
fim GRASP+VNS
VNS Aplicado ao PCVCP
Procedimento VNS(s)
r  Número de vizinhanças (no caso, r=5);
enquanto tempo sem melhora < MaxTempo faça
k  1;
enquanto k  r faça
Selecione um vizinho s’ qualquer na vizinhança Nk(s);
s’’  VND(s’);
se f(s’’) < f(s) então
s  s’’;
k  1;
senão
k  k + 1;
fim-enquanto;
fim-enquanto;
Retorne s;
fim VNS
VND Aplicado ao PCVCP
Procedimento VND(s)
r = Número de procedimentos de refinamento;
k  1;
enquanto k  r faça
Seja s’ um ótimo local segundo o k-ésimo procedimento de refinamento;
se f(s’) < f(s) então
s  s’;
k  1;
senão
k  k + 1;
fim-enquanto
Retorne s;
fim VND
Procedimentos de Refinamento
Método AddDrop
• Consiste em inserir o vértice que possuir a maior economia de inserção e
retirar o vértice que possuir a maior economia de remoção.
Solução (s)
0
3
1
5
vértice com maior economia de inserção
0
3
1
2
5
e(k) = cik + ckj – cij – pk
0
3
1
2
5
e(k) = cij + pk – cik – ckj
vértice com maior economia de remoção
Solução (s’)
0
1
2
5
Procedimentos de Refinamento
Método SeqDropSeqAdd
• Método iterativo, que consiste em duas fases.
– Na primeira fase, retira-se, a cada iteração, o vértice que fornecer a maior
economia de remoção, sendo executado enquanto houver vértices com
economia de remoção positiva.
– Na segunda fase, insere-se, a cada iteração, o vértice que fornecer a maior
economia de inserção, sendo executado enquanto houver vértices com
economia de inserção positiva.
Procedimentos de Refinamento
Método Descida 2-Optimal
• Examina todas as possíveis trocas de 2 arestas, realizando a que
fornecer o maior ganho na função de avaliação, sendo executado
enquanto existir movimento de melhora.
123456
125436
1
1
2
6
3
5
4
2
6
3
5
4
Experimentos Computacionais
• Não existe nenhuma biblioteca pública de problemas-teste para o
PCVCP;
• Todas as instâncias foram geradas aleatoriamente:
• Custo de deslocamento: [50, 1000]
• Prêmio: [1, 100]
• Penalidade: [1, 750]
Instâncias disponíveis em:
http://www.decom.ufop.br/prof/marcone/Orientacoes/OrientacoesConcluidas.htm
• Ambiente computacional:
• Linguagem C++ (C++ Builder 5.0)
• PC Athlon XP 1.53 GHZ, 256 MB RAM
Experimentos Computacionais
Comparação de Resultados entre o Modelo Exato e o Modelo Heurístico
Instância
v10
v20
v30a
v30b
v30c
v50a
v50b
|V|
11
21
31
31
31
51
51
Modelo Exato
Tempo
Ótimo Global
1
1765
65
2302
86
3582
100
2515
1786
3236
10800
Não encontrado
10800
Não encontrado
Desvio =
Modelo Heurístico
Tempo FOMelhor
1
1765
2
2302
6
3582
4
2515
11
3236
326
4328
292
3872
 FOMedia FOMelhor

 100
FOMelhor


Desvio
0,00%
0,00%
0,00%
0,00%
0,05%
0,42%
0,31%
Experimentos Computacionais
Resultados - Modelo Heurístico
Instância
v100a
v100b
v250a
v250b
v500a
v500b
|V|
101
101
251
251
501
501
Tempo
510
446
1033
796
2140
2410
FOMelhor
6892
6814
15310
14378
28842
28524
Desvio
0,52%
0,12%
0,88%
0,76%
0,67%
0,82%
Conclusões
• Os algoritmos heurísticos sempre atingiram o ótimo global para
instâncias onde este é conhecido;
• A metaheurística híbrida proposta mostrou-se robusta;
• Os resultados obtidos validam a utilização desta metodologia para
a resolução do Problema do Caixeiro Viajante com Coleta de
Prêmios;
Referências Bibliográficas
•
BALAS, E., The prize collecting traveling salesman problem. ORSA/Tims
Meeting in Los Angeles, (1986).
•
CHAVES, A. A., Modelagens Exata e Heurística para Resolução do
Problema do Caixeiro Viajante com Coleta de Prêmios. Relatório Técnico em
Ciência da Computação – DECOM, Universidade Federal de Ouro Preto, Ouro
Preto (2003).
•
Dell’ Amico, M., Maffioli, F., sciomachen, A., A Lagrangian heuristic for the
Prize Collecting Travelling Salesman Problem. Annals of Operations
Research, 81: 289-306, (1998).
•
MELO, V. A., Metaheurísticas para o Problema do Caixeiro Viajante com
Coleta de Prêmios, Dissertação de Mestrado, Instituto de Computação,
Universidade Federal Fluminense, Niterói, Rio de Janeiro (2001);