Recherche à voisinage variable

La stratégie de recherche de voisinage variable implique l’exploration itérative de voisinages de plus en plus grands pour un optima local donné jusqu’à ce qu’une amélioration soit localisée, après quoi la recherche dans ces voisinages est répétée. La stratégie est motivée par trois principes: 1) un minimum local pour une structure de voisinage peut ne pas être un minimum local pour une structure de voisinage différente, 2) un minimum global est un minimum local pour toutes les structures de voisinages possibles, et 3) les minima locaux sont relativement proche des minima globaux pour de nombreuses classes de problèmes.