Usando VNS
Por: Vitor de Araújo
Gabriel Leffa
André Moraes
(E Mestre Huang Ho)
O que é o problema?
 Parecido com o caixeiro viajante
 Deve-se visitar os nós uma unica vez
 Grafo completo não direcionado
 Dado um ponto inicial e um final
 Percorrer um caminho


Que seja menor que uma Distância dada
Que some o maior número de pesos dos nós percorrido.
20
Valor do Ponto
50
18
30
16
14
30
40
30
30
12
40
20
20
10
20
15
15
8
20
Distância limite = 15
10
10
0
6
15
20
Pontuação Máxima=120
Distancia=14.95
10
25
0
4
Pontos iniciais e finais
2
0
0
2
4
6
8
10
12
14
16
Fonte: VNS for the Orienteering Problem-ISCIS'06 Nov 1-2-3
O que é o VNS
 Uma meta-heuristica
 Se contenta com uma solução boa ao invés da ótima.
 Requer muito menos computação.
 A análise começa com uma solução factivel qualquer
 O algoritmo então dá saltos (shaking) para que possa
buscar soluções distantes.
 O algoritmo busca uma solução local.
 O algoritmo mantém a melhor solução, e repete o
processo.
O que uma solução
 Vetor de tamanho N-2
 O nó inicial e final são desconsiderados, já que são fixos.
 Permutação das cidades intermediarias
 Apenas a parte inicial que respeita a restrição identifica a
solução de nós que fazem parte da solução e a ordem
deles.
Como gerar soluções
 Busca Local:
 Mudança de apenas 1 elemento por vez: pode ser uma
troca entre 2 elementos

Entretanto podem significar que um nó saia da solução final
sem que outro entre e vice versa.
4
2
9
13
7
2
1
5
4
1
4
2
13
9
7
2
1
5
4
1
Valor máximo aceito: 15
Shaking
 Grandes Pertubações no sistema:
 Pode ser haver mudança de sequências de nós inteiras.
1º
2º
3º
4º
5º
6º
7º
8º
9º
10º
5º
6º
7º
8º
1º
2º
3º
4º
9º
10º
A solução é totalmente outra e portanto uma busca local pode melhorá-la
Estruturas de vizinhança
 Path insert
 Sequências são deslocadas
 Path exchange
 Sequências são trocadas de posição
 Point insert
 Nó é inserido e a sequência é deslocada.
 Point exchange
 2 nós trocam de posição, sem afetar posição dos demais.
 Path Randomize
 Faz permutação aleatória entre elementos em um conjunto
local.
Modificações do Mestre
 Quando o algoritmo fica muitas iterações sem
encontrar uma solução melhor
 Ele armazena esta solução.
 Desenvolve busca locais sobre uma solução pior em
separado.
 No final, compara se a solução pior pode ser melhorada
de tal forma que ultrapasse a melhor solução anterior.
Timings
Problema
S. Inicial
S. Final
S. Ótimo
Melhora
Dif. GLPK T. Solver
T. GLPK
Brazil, tipo1
5
43
46
760%
6.52%
18.859s
8.6s
Brazil, tipo2
285
1975
2220
592.98%
11.03%
18.721s
55.4s
Brazil, tipo3
206.72
1723.04
1702
733.48%
1,23%
19.149s
14.5s
Eil, tipo1
10
58
64
480%
9.37%
118.89s
50.5s
Eil, tipo 2
495
3356
3655
577.97%
8.18%
127.13s
113.3s
Eil, tipo 3
443.12
3237
3345
630.53%
3.22%
2m 3s
244.8s
Gil tipo 1
12
127
158
958.33%
19.62%
22m
-
Gil tipo 2
586
6551
8321
1018%
21.27%
22.2m
-
Gil tipo 3
653
8054
9246
1132.5%
12.88%
23m
-
Obrigado!