Métodos exatos e heurísticos para o problema do fluxo com rotulação mínima

Abstract

Um grafo com arestas rotuladas (GAR) é um grafo no qual cada aresta é associada a um rótulo, ou cor. Esses rótulos permitem representar características qualitativas, em contraste às características quantitativas que podem ser expressas por custos ou capacidades. A literatura tem dado atenção crescente a problemas definidos sobre GARs. Este trabalho introduz o problema do fluxo com rotulação mínima (PFRM), definido sobre um dígrafo com arcos rotulados e capacitados. Nele, busca-se um conjunto mínimo de rótulos tal que seja possível encontrar um fluxo com valor igual ou superior a um valor dado. São propostos métodos exatos e heurísticos para o PFRM. Como métodos exatos, são propostos uma formulação baseada em cortes coloridos e dois algoritmos de branch and cut. Como métodos heurísticos, um GRASP reativo e um algoritmo genético melhorado com construção gulosa aleatorizada baseada em GRASP, elitização e recombinação por caminhos, além de um método de manutenção dinâmica de fluxo. Os experimentos computacionais realizados demonstraram a eficiência dos métodos propostos em instâncias de tamanho moderado, em comparação com as soluções encontradas na literatura.