Um algoritmo branch-and-cut-and-price para o Problema de Localização de Instalações Capacitado com Única Fonte

Favoritar este trabalho
Como citar esse trabalho?
Detalhes
  • Tipo de apresentação: Trabalho completo (oral)
  • Eixo temático: 14. OC – Otimização Combinatória
  • Palavras chaves: localização de instalações capacitado; programação inteira; Algoritmo de Otimização;
  • 1 Universidade Federal Fluminense

Um algoritmo branch-and-cut-and-price para o Problema de Localização de Instalações Capacitado com Única Fonte

Veronica de Miranda Prottes

Universidade Federal Fluminense

Resumo

Este trabalho apresenta um algoritmo exato para o SSCFLP - Problema de Localização de Instalações Capacitado de Única Fonte. O algoritmo é desenvolvido em duas etapas. A primeira utiliza planos de corte para fortalecimento da formulação e fixação das variáveis, de modo a reduzir substancialmente o tamanho do problema, e a segunda etapa aplica BCP no VRPSolver, um solver genérico para problemas de roteamento e demais problemas com estrutura semelhante.No modelo criado no VRPSolver, as restrições de capacidade são modeladas como recursos em grafos, permitindo que os subproblemas de pricing sejam resolvidos como Problemas de Caminho mais Curto Restringido por Recursos-RCSPs. Os resultados computacionais mostram o grande potencial em desenvolvimento deste algoritmo em comparação com o estado-da-arte, apresentando baixos gaps entre o limite inferior e a solução ótima e tendo um desempenho muito superior em algumas instâncias consideradas difíceis até o momento.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!