Apresentacao SBPO 18

UM PROCEDIMENTO PARA GERAR FRONTEIRAS DE PARETO
ÓTIMAS PARA O PROBLEMA BIOBJETIVO DA
ÁRVORE GERADORA DE CUSTO E DIÂMETRO MÍNIMOS
Ernando Gomes de Sousa [e-mail] Universidade do Estado do Rio Grande do Norte
Andréa C. Santos [e-mail] Université de Technologie de Troyes

Dario J. Aloise [e-mail] Universidade do Estado do Rio Grande do Norte

Natal, set/2013

1

Roteiro da Apresentação



Descrição do Problema



Revisão Bibliográfica



Metodologia



Resultados



Conclusões e trabalhos futuros

2

Descrição do Problema


O Problema bi-objetivo da Árvore Geradora de Custo e Diâmetro Mínimos (biAGCMD) consiste em encontrar uma árvore geradora com custo e diâmetro mínimos 

O bi-AGCDM possui relação com outros 2 (dois) problemas:
◦ AGMRD (Árvore Geradora Mínima com Restrição de Diâmetro)
◦ AGDM (Árvore Geradora de Diâmetro Mínimo)



Diâmetro de uma árvore geradora é o número de arestas no maior caminho entre qualquer par de nós

D=2

D=3
AGMRD

AGDM
3

Descrição do Problema


O problema bi-objetivo da Árvore Geradora de Custo e Diâmetro Mínimos é um problema NP-Difícil (Ho et al., 1991)

1

0
8

32
2

1
2

4

0

1

2

4

1

1
2

3

Custo = 7
Diâmetro = 3


0

2

16
3

1

2

16
3

Custo = 19
Diâmetro = 2

Modela vários problemas... o o o Problemas de telecomunicações
Problema de logística de transporte
Redes elétricas
4

Revisão Bibliográfica


O problema da Árvore Geradora de Custo Mínimo com Restrição de Diâmetro
(AGMRD)
◦ Formulações: (Gouveia, Magnanti, 2003), (Santos et al., 2004)
◦ Métodos exatos: (Gouveia et al., 2011), (Noronha et al., 2010)
◦ Heurísticas e Metaheurísticas: (Raidl et al., 2003), (Requejo, et al., 2009)



Árvore geradora bi-objetivo com duas funções de custos.
◦ B&B: (Sourd et al., 2008), enumeração: (Ramos et al., 1998), (Zapounidis et al.,
2010)
◦ Heurísticas e Metaheurísticas: (Zhou et al, 1999), (Arroyo et al., 2008)



Problema bi-AGCDM:
◦ Formulação exata resolvida em duas fases: