Problema do Caixeiro Viajante
Utilizando VNS e VND
Fernando Cota Viana
Ricardo Sérgio Prado
VNS – Algoritmo Básico
S  s0
While (critério de parada) do
K  1
While (k  max) do
Gerar aleatoriamente uma solução s’ pertencente à vizinhança Nk(s)
Aplicar busca local a partir de s’, obtendo a solução s’’
If f(s’’) < f(s)
Then
S  s’’
K1
Else k  k + 1
End-if
End-while
End-while
VND – Algoritmo Básico
S  s0
melhoria  .verdadeiro.
While (melhoria) do
K  1
melhoria  .falso.
While (k  max) do
Aplicar busca local a partir de s utilizando a vizinhança Nk(s),
obtendo a solução s’
If f(s’) < f(s)
Then
S  s’
melhoria  .verdadeiro.
Else k  k + 1
End-if
End-while
End-while
Métodos de melhoria de roteiros

Os mais utilizados são do tipo k-opt
–
K arcos são removidos de um roteiro e
substituídos por outros k arcos;
Objetivo: Diminuir a distância total percorrida;
Na prática são considerados 2-opt e 3-opt;
Método 2-opt

Testa as trocas possíveis entre pares de arcos;
Roteiro Básico
Roteiro Modificado
2_opt_VNS
fosl= (*fo - c[s[x]][s[y]] - c[s[w]][s[z]] + c[s[x]][s[w]] + c[s[y]][s[z]]);
Método 3-opt

Testa as trocas possíveis entre 3 arcos:
Resulta em 7 combinações possíveis:
Roteiro Básico
Método 3-opt
3.1_opt_VNS
3.2_opt_VNS
3.3_opt_VNS
fosl= (*fo -c[s[a]][s[a1]]-c[s[b]][s[b1]]-c[s[d]][s[d1]]
+c[s[a]][s[d]]+c[s[b1]][s[a1]]+c[s[b]][s[d1]]);
3.4_opt_VNS
Método de Descida - 2opt
Troca de duas cidades:
S=[12345]
1>2 = [ 2 1 3 4 5 ] 2>5 = [ 1 5 3 4 2 ]
1>3 = [ 3 2 1 4 5 ] 3>4 = [ 1 2 4 3 5 ]
1>4 = [ 4 2 3 1 5 ] 3>5 = [ 1 2 5 4 3 ]
1>5 = [ 5 2 3 4 1 ] 4>5 = [ 1 2 3 5 4 ]
2>3 = [ 1 3 2 4 5 ]
2>4 = [ 1 4 3 2 5 ]

Método de Descida - 3opt
Troca de três cidades:
S=[12345]
1>2>3 = [ 2 3 1 4 5 ] 2>3>5 = [ 1 3 5 4 2 ]
1>2>4 = [ 2 4 3 1 5 ] 2>4>5 = [ 1 4 3 5 2 ]
1>2>5 = [ 2 5 3 4 1 ] 3>4>5 = [ 1 2 4 5 3 ]
1>3>4 = [ 3 2 4 1 5 ]
1>3>5 = [ 3 2 5 4 1 ]
1>4>5 = [ 4 2 3 5 1 ]
2>3>4 = [ 1 3 4 2 5 ]

Teste: Problema lin105

3 Estruturas de Vizinhança VNS utilizadas:
- 2 opt
- 3.3 opt
- 3.4 opt
1 Estrutura de Vizinhança VND utilizada:
- 2 opt

Resultados Obtidos:





Solução Inicial: 17.173,4
Tempo: 60 seg.
1) 10.823,4
2) 14.116,9
3) 14.461,1
Resultados Obtidos:

S. Inicial
Parcialmente Gulosa
69.558,6
69.526,4
70.273,9
S. Final
19.669,9
20.828,8
16.563,9
Resultados Obtidos:

S. Inicial Aleatória
130.233,8
130.274,9
127.230,1
S. Final
14.581,2
19.502,0
18.281,4