Authors
Thiago Ferreira de Oliveira, Christophe Duhamel, Dario José Aloise, Andréa Cynthia Santos,
Title
Um algoritmo de programação dinâmica para partições em grafos: aplicação ao problema dos anéis SONET
In
Proceedings of the XLVI Simpósio Brasileiro de Pesquisa Operacional (SBPO), Salvador, Brésil
Pages
2493–2501
Year
2014
Indexed by
Abstract
Dado um grafo G = (V, E), o problema de partições em grafos consiste em dividir V em conjuntos disjuntos, sem otimizar uma função objetivo. Neste trabalho, propomos um método sofisticado de separação de partições em grafos, considerando uma otimização da quantidade devpartições e restrições de capacidade associadas às partições. O procedimento proposto utiliza programacão dinâmica e é semelhante ao split proposto por Beasley (1983), comumente aplicado a problemas de roteamento de veículos. Para testar a validade do método, aplicamos a idéia ao problema dos anéis SONET (Synchronous Optical NETwork), referenciado aqui como SRAP (Sonet Ring Assignment Problem). SRAP é um problema NP-difícil e encontra aplicações em topologias de redes de fibras óticas. O método baseado em programação dinâmica é utilizado para gerar partições a partir de sequências aleatórias e também em um algoritmo baseado em BRKGA (Biased Random Key Genetic Algorithm), sendo o mesmo empregado como decodificação de chaves aleatórias. Resultados utilizando a decodagem baseada em programação dinâmica são promissores.
Affiliations
Offprint