MODELAGEM MATEMÁTICA E APLICAÇÃO DA METAHEURÍSTICA VNS PARA O PROBLEMA DE PROJETO DE REDE.
Problema de Projeto de Rede, Otimização Combinatória, Metaheurística.
Este trabalho apresenta um problema de projeto de rede (Network Design Problem - NDP), um problema de otimização combinatória classificado como NP-Difícil. O NDP consiste em encontrar um projeto, dentro de vários projetos de modificações da infraestrutura de uma malha viária que promova uma melhoria do seu fluxo total. Neste contexto, é proposto resolver o NDP com a determinação de vias de mão única e mão dupla em uma malha viária, com o propósito de encontrar uma melhor configuração da malha viária de modo que minimize o tempo total de viagem. É proposta uma nova formulação matemática para este problema, e como mostra alguns resultados preliminares neste trabalho, o modelo matemático proposto é válido. Ainda faz parte deste trabalho, um estudo experimental com o método de solução proposta para o NDP. O método de solução proposta consiste na utilização do algoritmo de Floyd-Warshall para encontrar os caminho mais curtos para todos os viajantes na malha viária entre origens e destinos, e na aplicação da metaheurística VNS ( Variable Neighborhood Search) ao NDP.