La Recherche à Voisinage Variable (RVV) est une métaheuristique récente basée sur l'idée d'un chargement systématique de voisinage, à la fois dans une phase de descente et dans une phase d'exploration, qui permet de sortir d'un optimum local. On présente le schéma de base de cette méthode et plusieurs extensions ayant pour but d'accélérer la résolution ou de permettre de résoudre de grands problèmes. Deux types d'applications sont brièvement discutés: d'une part des problèmes d'optimisation combinatoire classique, et d'autre part des applications de type nouveau, stimulées par le cadre de la RVV et basées sur son usage: analyse du choix des mouvements dans l'heuristique 2-opt pour le problème du voyageur de commerce, stabilisation de la méthode de génération de colonnes et obtention de conjectures en théorie des graphes à l'aide du système AutoGraphiX.