Lagrangian decomposition methods for large-scale fixed-charge capacitated multicommodity network design problem

Abstract

Tipicamente presente nas áreas de logística e telecomunicações, o problema de síntese de redes multi-fluxo de custo fixo e capacitada permanece desafiador, especialmente quando contextos de grande escala estão envolvidos. Nesse caso, a capacidade de produzir soluções de boa qualidade em um tempo computacional praticável depende da disponibilidade de algoritmos eficientes. Nesse sentido, a presente tese propõem abordagens lagrangianas capazes de fornecer limites relativamente próximos ao ótimo para instâncias de grande escala. A eficiência dos métodos depende do algoritmo aplicado para resolver duais Lagrangianos, portanto escolhemos entre dois dos solvers mais eficientes da literatura: o Algoritmo de Volume e o Método Bundle, proporcionando uma comparação entre eles. Os resultados mostraram que o Algoritmo de Volume é mais eficiente no contexto considerado, sendo o escolhido para o desenvolvimento do projeto de pesquisa. Uma primeira heurística Lagrangiana foi desenvolvida para produzir soluções viáveis de boa qualidade para o problema, obtendo resultados muito melhores do que Cplex, para as maiores instâncias. Em relação aos limites inferiores, um algoritmo Relax-and-Cut foi implementado incorporando análise de sensibilidade e uma normalização das restrições, o que melhorou os resultados. Os aumentos nos limites inferiores atingiram 11%, mas em média permaneceram abaixo de 1%. O algoritmo Relax-and-Cut foi então incluído em um esquema Branch-and-Cut, para resolver programas lineares em cada nó da árvore de busca. Além disso, uma heurística de Feasibility Pump lagrangiana foi implementada para acelerar a busca por boas soluções viáveis. Os resultados obtidos mostraram que o esquema proposto é competitivo com os melhores algoritmos da literatura, e fornece os melhores resultados em contextos de larga escala. Além disso, foi testada uma versão heurística do algoritmo Branch-and-Cut baseado no Feasibility Pump lagrangiano, proporcionando os melhores resultados em geral quando comparada às heurísticas mais eficientes da literatura.