Busca em Vizinhança Variável (VNS)

Busca em Vizinhança Variável (VNS) é um framework de otimização meta-heurística introduzido por Mladenović e Hansen em 1997. Ele escapa de ótimos locais alternando sistematicamente entre um conjunto pré-definido de estruturas de vizinhança — primeiro perturbando a solução atual (agitação) para alcançar uma região diferente do espaço de busca, depois aplicando uma busca local dentro dessa região e, finalmente, aceitando a nova solução apenas se ela melhorar a incumbente. O método é flexível o suficiente para lidar com problemas combinatórios (roteamento, escalonamento, problemas de grafos) bem como otimização contínua, tornando-o uma das meta-heurísticas baseadas em vizinhança mais utilizadas em pesquisa operacional.