Benders do CPLEX aplicado ao problema de orientação de redes fortemente conexas

Citation:

Diego Perdigão Martino, Alexandre Xavier Martins, and Paganini Barcellos de Oliveira. 8/2018. “Benders do CPLEX aplicado ao problema de orientação de redes fortemente conexas.” L Simpósio Brasileiro de Pesquisa Operacional. Link para acesso

Abstract:

O crescimento demográfico aliado à intensa utilização de veículos devido à necessidade diária de locomoção por grande parte da população tem acarretado problemas de ordem estrutural nos grandes centros urbanos, uma vez que a maioria das cidades não dispõe de infraestrutura adequada para controlar o intenso fluxo de trânsito. Uma estratégia para solucionar esses problemas diz respeito à reconfiguração das redes urbanas. O Problema da Orientação em Redes Fortemente Conexas (Strong Network Orientation Problem – SNOP) surge como uma alternativa para a resolução do problema, o qual objetiva minimizar os custos associados às distâncias entre os nós de uma rede urbana por meio do remanejamento das redes já existentes, de tal forma a estabelecer uma configuração de custo mínimo fortemente conexa. Considerando que se trata de um problema de Otimização em Sistemas de Grande Porte, a utilização de algoritmos exatos e/ou heurísticos possibilita a obtenção de soluções eficientes viáveis para problemas reais e fictícios presentes na literatura. Neste sentido, este trabalho propõe apresentar e discutir os resultados obtidos através da resolução de um modelo para o SNOP utilizando o CPLEX 12.8 e comparando seu desempenho com a estratégia de Benders oferecida pelo solver. Os resultados computacionais obtidos mostraram que a utilização do método de Benders promove a exploração de um quantitativo de nós de Branch-and-Bound e tempo computacional de resolução muito superior ao CPLEX via método SIMPLEX.
Last updated on 05/28/2020