Aplicação de uma metaheurística para o problema de orientação de redes fortemente conexas.

Abstract

A gestão da mobilidade em grandes centros urbanos pode ser vista como um desafio no que se refere à adoção de alternativas para mitigar problemas comuns de mobilidade urbana, sejam eles previamente planejados ou inesperados. Um deles é a orientação de ruas e avenidas de forma a garantir um deslocamento eficiente em termos de distância percorrida, bem como a reestruturação da malha urbana, quando surgem situações que possam bloquear determinados pontos de conexão. Nesse sentido, um estudo sobre o Problema da Orientação de Redes Fortemente Conexas (Strong Network Orientation Problem) é explorado neste trabalho. O objetivo do problema consiste em determinar a orientação de uma rede de forma que a soma das distâncias percorridas a partir de cada ponto em relação aos demais seja mínima e que a configuração final permita que todos os pontos da rede sejam alcançáveis pelos demais. Trata-se de um problema de natureza combinatória pertencente à classe de problemas não determinísticos “difíceis” (NP-Difícil) e que, por este motivo, algoritmos de resolução exata não são suficientes para a resolução do problema em um curto intervalo de tempo dependendo do tamanho da rede. Este trabalho propõe um algoritmo metaheurístico baseado na variação de estruturas de vizinhança como forma de explorar um espaço diversificado de busca por soluções adequadas para o problema. Um novo conjunto de instâncias reais, baseadas em um centro urbano brasileiro, também é proposto neste trabalho. Um conjunto de experimentos computacionais são realizados tanto para o algoritmo proposto quanto para o resolvedor comercial CPLEX. Os resultados indicam que a metaheurística é eficiente e permite encontrar soluções de igual ou melhor qualidade que o resolvedor comercial, considerando o fato de que a otimalidade não é provada pelo CPLEX para todas as instâncias testadas, dentro do limite de tempo pré-estabelecido.