Algoritmo de pesquisa em vizinhança variável aplicado ao problema de orientação de redes fortemente conexas

Citation:

Martino DP, Martins AX, de Oliveira PB, de Butinholi MA. Algoritmo de pesquisa em vizinhança variável aplicado ao problema de orientação de redes fortemente conexas. LI Simpósio Brasileiro de Pesquisa Operacional [Internet]. 2019;2:107799.

Abstract:

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.

Publisher's Version