PROBLEMA DE LOCALIZAÇÃO DE CONCENTRADORES COM ALOCAÇÃO SIMPLES E ECONOMIA DE ESCALA DEPENDENTE DO FLUXO
Problemas de Localização de Concentradores, Economia de Escala Heterogênea, Economia de Escala Dependente do Fluxo, GVNS.
Problemas de localização de concentradores consistem na seleção de nós, em uma dada rede, onde os concentradores serão estabelecidos, e na determinação de rotas de transporte através dos concentradores a fim de otimizar um determinado objetivo, como a maximização de lucros ou a minimização de custos. Tais problemas estão presentes nos mais variados campos de aplicação, como nas redes de transporte (aéreo, terrestre e marítimo), rede de telecomunicação, no planejamento regional, dentre outros. Este projeto de tese propõe o estudo de problemas de localização de concentradores com alocação simples e economia de escala dependente do fluxo, considerando versões do problema com minimização de custos e maximização de lucros. O principal objetivo deste trabalho é desenvolver modelos matemáticos para os problemas abordados, bem como propor métodos heurísticos e exatos para resolvê-los. Neste projeto são apresentado os resultados já alcançados pela pesquisa que corresponde ao desenvolvimento de um algoritmo heurístico, baseado na Busca em Vizinhança Variável Generalizada (GVNS), para resolver grandes instâncias do problema de localização de concentradores de alocação simples e economia de escala variável com minimização de custos. Após um conjunto de experimentos computacionais realizados, foi possível concluir que o algoritmo proposto encontra soluções de boa qualidade em um curto tempo computacional e pode lidar com instâncias com até 500 nós. Além disso, foi proposta uma reformulação de uma formulação da literatura para o mesmo problema com minimização custos, que a deixa com uma estrutura decomponível, essa nova formulação torna-se bastante promissora para aplicação de métodos de decomposição, como o método de decomposição de Benders. Os resultados dos experimentos computacionais mostram que a formulação proposta reduz significativamente o tempo de execução quando o método de decomposição de Benders do solver CPLEX é ativado para a resolução no problema. Além disso, com esta formulação, foi possível resolver algumas instâncias que não foram abordadas em outro trabalho na literatura. Desta forma, foi possível obter limites inferiores a serem utilizados na análise do procedimento heurístico proposto. Neste projeto, também são apresentadas as propostas de trabalhos futuros junto a um cronograma de atividades para sua integralização.