PROPOSTA DE UM MODELO MATEMÁTICO PARA UMA REDE DE ALTA VELOCIDADE UMA ABORDAGEM DO PROBLEMA DO CAIXEIRO VIAJANTE COM COLETA DE PRÊMIOS.
Infovia, Caixeiro viajante com coleta de prêmios, BRKGA.
A evolução das redes de alta velocidade é uma realidade cada vez mais constante nos centros urbanos. No Brasil não tem sido diferente, um exemplo disso são as Redes Comunitárias de Educação e Pesquisa (REDECOMEP). Os modelos de implantação da REDECOMEP têm como base central a instalação de uma infraestrutura de fibra óptica com o intuito de conectar centros de pesquisa e educação superior na formação de um consórcio que financiará a sustentação da rede. Diante desse cenário está a rede GigaMossoró, uma rede de alta velocidade que abrangerá todas as instituições públicas de ensino superior da cidade de Mossoró. Que interligará os clientes chaves e tentará abranger um número máximo possível de potenciais clientes, para isso se faz necessário criar um modelo que determine a rota de melhor caminho. Para encontrar a solução do problema a pesquisa se utilizou de um conjunto de ações sistematizadas com a finalidade de gerar novos conhecimentos. Assim o trabalho foi dividido em etapas que, como: entendimento do problema, levantamento bibliográfico, análise dos modelos e a última etapa é a conclusão. Para realizar o embasamento científico do trabalho foi necessário realizar um levantamento bibliográfico, onde entendeu-se os conceitos de heurística e metaheurística, onde o primeiro foi desenvolvido para solucionar problemas de alta complexidade com um tempo computacional razoável, já a metaheurística é destinada a encontrar uma boa solução, algumas vezes a ótima, onde a cada etapa é aplicada uma heurística subordinada, assim a metaheurística é um conjunto de heurísticas. Dentre essas metaheurísticas destaca-se o Problema do Caixeiro Viajante (PCV) e o Problema do Caixeiro Viajante com Coleta de Prêmios (PCV-CP). O PCV tem como objetivo sair de um ponto inicial passar por todos os pontos existentes e retornar para o ponto inicial, de modo que alcance todos os pontos com a menor rota possível e sem repetir nenhum ponto, já o PCV-CP usa a sistemática de sair de um ponto inicial, passar pelo máximo de pontos possíveis e retornar ao ponto inicial, de modo que para cada ponto não contemplado pelo modelo o problema receberá uma pontuação negativa, já os pontos contemplados terão uma pontuação positiva. Normalmente para solucionar o PCVCP é utilizado metaheurísticas como: Procedimento de busca adaptativa gulosa e randomizada (GRASP), Pesquisa em Vizinhança Variável (VNS) e o Método de Descida em Vizinhança Variável. Com base nas informações conseguimos definir os pontos de conexão da rede GigaMossoró e seus futuros potenciais clientes e foi desenvolvido um modelo matemático genérico para abordar o problema de melhor caminho para rede GigaMossoró. Como o problema proposto é reconhecidamente um problema NP-Completo, será utilizado como método de resolução a metaheurística Algoritmo Genético de Chaves Aleatórias, mais conhecido como BRKGA.