OTIMIZAÇÃO DO PROJETO DE
REDES URBANAS BASEADO
NO PROBLEMA DE STEINER
Luiz Carlos de Abreu Rodrigues
Hideson Alves da Silva
Agenda




Introdução
Problema de Steiner
Busca Tabu
Pré-processamento
2
Introdução

Motivações



Demanda por Sistemas de Telecomunicações.
Projetos de Redes x Problema de Steiner.
Ferramenta de auxílio à Projetistas.
3
Redes de Telecomunicações


Cabo de Fibra Óptica
Equipamentos :



POP;
Caixas de Emenda;
Ponto de Cliente.
4
Problema de Steiner



Parte de um Grafo G = (N, M)
Minimização do custo de ligação entre n
pontos;
A solução é constituída por uma árvore que
engloba os pontos a serem ligados
(clientes) e os pontos de passagem que
serão determinados (nós de Steiner).
5
Exemplo
1
6
5
2
3
9
8
4
7
Nós de Steiner : S={2,4,9}
Nós de Demanda: D={1,3,8,7,6,5}
SV e DV
6
Exemplo
1
6
5
2
3
9
8
4
7
Nós de Steiner Ativos : S = { 2 , 4 }
7
Métodos de Solução

Exatos :



Programação Inteira
A* (Branch and Bound )
Heuristícos :

Busca Tabu

Simulated Annealing

Algoritmos Genéticos

Scatter Search
8
Busca Tabu

Busca através de soluções vizinhas,
explorando o espaço de busca, sem :




ser confundido pela ausência de “vizinhos”
aprimorantes;
retornar a locais visitados (é desejado, mas não
necessário);
Utiliza estruturas flexíveis de memória.
Parte de uma solução inicial e, a cada
iteração, move para a melhor solução na
vizinhança.
9
Busca Tabu

Movimentos no Problema de Steiner.


Inserção
Eliminação
10
Busca Tabu

Lista Tabu





Estrutura de memória Básica, formada por
soluções proibidas.
Evita que a busca fique presa em pontos de
mínimo (ou máximo) local.
Determinada por informações históricas da busca.
Soluções são proibidas por um número de
iterações.
Soluções x Movimentos proibidos.
11
Busca Tabu

Critérios de Aspiração



Movimento proibido torna-se permitido.
Vem da necessidade de explorar soluções ainda
não visitadas.
A implementação deste exige um esforço
computacional maior.
12
Busca Tabu

Intensificação


Concentrar a busca em regiões promissoras (em
torno das boas soluções).
Diversificação


Fazer com que a busca explore regiões ainda não
visitadas.
Oferecer novas opções de busca.
13
Implementação Básica
1 Enquanto o critério de parada da Diversificação não é encontrada, faça :
2
Gerar uma solução inicial (que é s);
3
Se (primeira vez) então
4
sbest = s;
5
s* = s;
6
Enquanto o critério de parada da Intensificação não é encontrada, faça :
7
Gerar a vizinhança de s através de movimentos Tabu que
melhorem s* e selecione a melhor solução s' ;
8
s = s' ;
9
Se s' é melhor que s* então
10
s* = s’;
11
Se s* é melhor que sbest então
12
sbest = s*;
13 Retornar sbest .
14
Pré-Processamento

Regra NTD1

Um nó u não terminal de grau 1 e sua
aresta adjacente (u,v) podem ser
removidos.
w
w
u
z
z
v
v
15
Pré-Processamento

Regra NTD2

Um nó u não terminal de grau=2 e suas
arestas adjacentes (u,v) e (u,w ) podem ser
substituídos pela aresta (v,w).
w
w
u
c(u,v) + c(u,w)
z
v
z
v
16
Pré-Processamento

Regra TD1

O nó e aresta adjacente ao nó terminal de
grau=1 é necessariamente ativos.
w
w
u
u
z
v
z
v
17
Pré-Processamento

Regra SD

Identificando-se o custo de menor
caminho, tal que B(u,v) < c(u,v), então a
aresta (u,v) é redundante.
w
w
u
u
z
z
v
v
18
Pré-Processamento

Regra BD3

Dado um nó u não terminal de grau=3, se:
Min {B(v,w)+B(v,z); B(w,v)+B(w,z);
B(z,v)+B(z,w)}  c(u,v) + c(u,w) + c(u,z)
w
w
u
c(u,w)+c(u,z)
c(u,v)+c(u,w)
z
z
c(u,v)+c(u,z)
v
v
19
8
8
49
2
7
7
32
2
12
8
21
19
43
17
7
6
3
7
4
8
47
7
22
3
44
6
6
40
3
10
8
1
23
2
39
5
8
10
3
41
1
46
10
7
37
2
7
7
11
5
10
2
9
36
2
18
13
1
9
1
5
5
50
10
10
26
24
6
25
8
15
10
5
45
1
8
42
38
8
20
28
16
30
2
9
8
2
4
6
4
5
3
2
7
48
10
2
31
34
7
9
14
4
7
35
1
33
3
7
29
9
5
27
Nós Terminais
Instância b01.stp
b01_artigo.vsd
8
8
49
2
7
7
32
2
12
8
21
19
43
17
7
6
3
4
8
47
7
22
3
44
6
6
40
3
10
8
1
23
2
39
5
8
10
3
41
7
7
7
7
37
2
1
46
10
11
5
10
2
9
36
2
18
13
1
9
1
5
5
50
10
10
26
24
6
25
8
15
10
5
45
1
8
42
38
8
20
28
16
30
2
9
8
2
4
6
4
5
3
2
7
48
10
2
31
34
7
9
TD1
14
4
7
35
1
33
3
7
29
9
5
27
Nós Terminais
Instância b01.stp
b01_artigo.vsd
testes
8
8
49
2
7
7
32
2
12
8
21
19
43
17
7
4
15
8
47
7
11
3
44
6
6
3
7
10
10
39
5
8
40
9
23
10
8
1
10
26
24
11
25
6
8
15
10
6
3
7
22
2
3
41
1
46
7
37
2
7
11
5
10
2
9
36
2
18
13
1
9
1
5
5
50
10
5
9
45
1
8
42
38
8
20
28
16
30
2
9
8
2
4
4
6
5
3
2
7
48
20
9
14
10
2
31
TD1
34
7
Eliminados
14
4
7
35
1
33
3
7
29
9
5
27
Terminais
BDk (k=3)
NTD2
Instância b01.stp
b01_v08_origem.vsd
49
12
9
7
21
36
2
37
41
7
2
3
15
47
8
11
22
24
2
5
9
28
20
2
14
48
10
2
34
20
TD1
4
35
27
Terminais
BDk (k=3)
NTD2
Instância b01.stp
b01_v08_origem.vsd
49
12
9
7
21
36
2
37
41
7
2
3
47
8
22
24
2
9
5
28
20
2
48
2
34
20
TD1
Terminais
4
35
27
BDk (k=3)
NTD2
Instância b01.stp
b01_v08_origem.vsd
Resultados: Pré-Processamento
Instância
B01
B02
B03
B04
B05
B06
B07
B08
B09
Ni
50
50
50
50
50
50
75
75
75
Ai
63
63
63
100
100
100
94
94
94
Ti
9
13
25
9
13
25
13
19
38
Np
15
18
28
28
30
39
19
23
46
%N
70%
64%
44%
44%
40%
22%
75%
69%
39%
Ap
19
25
39
64
66
86
31
35
64
%A
70%
60%
38%
36%
34%
14%
67%
63%
32%
Npt
13
16
28
9
14
26
16
20
43
25
Resultados: Pré-Processamento
Instância
B10
B11
B12
B13
B14
B15
B16
B17
B18
Ni
75
75
75
100
100
100
100
100
100
Ai
150
150
150
125
125
125
200
200
200
Ti
13
19
38
17
25
50
17
25
50
Np
48
47
59
23
39
61
65
60
74
%N
36%
37%
21%
77%
61%
39%
35%
40%
26%
Ap
118
118
129
42
63
90
155
142
168
%A
21%
21%
14%
66%
50%
28%
23%
29%
16%
Npt
16
20
40
19
31
53
18
27
51
26
Conclusão


Pré-Processamento.
Busca Tabu.
27
Trabalhos Futuros




Testar outras estruturas de memória da
Busca Tabu.
Estudo de novos critérios de parada.
Estudo de algoritmos para a composição das
soluções geradas.
Integração com softwares comerciais.
28
Trabalhos Futuros



Novos algoritmos para composição das
soluções geradas.
Implementar com software de
geoprocessamento.
Estudar critérios de paradas conforme a
rede em estudo.
29
Obrigado.
CONTATOS:
Luiz Carlos de Abreu Rodrigues
[email protected]
(41) 310-4659
Hideson Alves da Silva
[email protected]
(41) 331-4436
30