PROPOSTA DE MODELAGEM E MÉTODO DE RESOLUÇÃO PARA UMA REDE DE ALTA VELOCIDADE, UMA ABORDAGEM DO PROBLEMA DO CAIXEIRO VIAJANTE COM COLETA DE PRÊMIOS

- 84710
Pôster
Favoritar este trabalho
Como citar esse trabalho?
Resumo

As Redes Comunitárias de Educação e Pesquisa (REDECOMEP) tem como base o desenvolvimento científico através da conexão de instituições de ensino superior, um exemplo disso é a rede GigaMossoró. Este trabalho discute aspectos e desafios de como encontrar a melhor rota, propondo um método de resolução que defina o perímetro da rede GigaMossoró, de modo a obter um caminho que contemple todos os pontos prioritários e consiga alcançar o máximo de possíveis clientes dentro do mesmo. Como parâmetro será utilizado o Problema do Caixeiro Viajante com Coleta de Prêmios (PCVCP), O PCVCP foi desenvolvido inicialmente por Balas em 1989 para a programação de fabricas que produzia lâminas de aço. Em seguida, vieram outras aplicações com [Goemans et al 1992] que desenvolveram um procedimento de aproximação para uma versão do PCVCP no qual o prêmio mínimo a ser coletado foi removido e o objetivo passou a ser simplesmente minimizar o custo e as penalidades. Dado que o problema proposto é reconhecidamente um problema de alta complexidade computacional, ou seja, comprovadamente NP-difícil, será utilizada uma abordagem via Metaheurística com base em um algoritmo genético de chaves aleatórias viciadas (BRKGA), cujo as principais características são o seu elitismo acentuado e sua codificação de soluções na forma de chaves aleatórias. O BRKGA é um algoritmo derivado dos algoritmos genéticos, que se baseiam em fenômenos da natureza, utilizando o elitismo para encontrar soluções ótimas fugindo de “ótimos locais”. Diante dessa abordagem a pesquisa apresentou contribuições quanto a definição de conceitos da rede GigaMossoró de modo a conhecer seus futuros clientes, e definir sua estrutura e restrições, além do mais foi possível entender abordagem de solução do problema través de Metaheurística proposta.

Instituições
  • 1 Universidade do Estado do Rio Grande do Norte
  • 2 UERN (UNIVERSIDADE DO ESTADO DO RIO GRANDE DO NORTE)
  • 3 UERN/UFERSA; Programa de pós-graduação em ciência da computação - PPGCC
Eixo Temático
  • OC – Otimização Combinatória
Palavras-chave
Redes Comunitárias de Educação e Pesquisa
Problema do Caixeiro Viajante com Coleta de Prêmios (PCVCP)
algoritmo genético de chaves aleatórias viciadas (BRKGA)