Anais do Simpósio Brasileiro de Pesquisa Operacional
Anais do Simpósio Brasileiro de Pesquisa Operacional

A infraestrutura inadequada e o intenso fluxo de pessoas e veı́culos resultam em problemas associados às vias urbanas no mundo. O Problema de Orientação de Redes Fortemente Conexas (Strong Network Orientation Problem – SNOP) é uma alternativa para amenizar esse cenário na medida em que objetiva minimizar a soma das distâncias percorridas a partir de cada ponto de interseção entre vias, tendo em vista os custos associados à rede urbana. Classificado como NP-Difı́cil, algoritmos heurı́sticos são eficazes para atingir soluções de qualidade, uma vez que obter a melhor solução exige grande esforço computacional. Este artigo apresenta o algoritmo de pesquisa em vizinhança variável General Variable Neighborhood Search (GVNS) para a resolução do SNOP, bem como as estratégias utilizadas. Os resultados obtidos indicam que o GVNS é eficiente em tempo e qualidade de solução quando comparado com outras abordagens aproximadas e exata para o problema.