Groupe d’études et de recherche en analyse des décisions

G-2013-71

La recherche à voisinages variables

et

La recherche à voisinages variables (RVV), ou Variable Neighborhood Search (VNS) en anglais est une métaheuristique dont l'invention est due à Nenad Mladenovic et Pierre Hansen et développée au GERAD (Groupe d'Études et de Recherche en Analyse des Décisions, Montréal) à partir de 1997. Depuis cette période, la recherche à voisinages variables a connu divers développements et améliorations ainsi que de très nombreuses applications. Selon le Journal of Citation Reports, les travaux initiaux [N. Mladenovic and P. Hansen. Variable neighborhood search. Comput. Oper. Res., 24:1097-1100, 1997.] [P. Hansen and N. Mladenovic. Variable neighborhood search: Principles and applications. European J. Oper. Res., 130:449-467, 2001.] sur la RVV ont été cités plus de 600 et 500 fois respectivement à ce jour (plus de 1700 et 1200 fois selon Google Scholar), ce qui indique l'intérêt pour la méthode tant au niveau des développements qu'elle a connu que de ses applications.

Le but de cet article n'est pas de faire un exposé exhaustif des variantes et des applications de la RVV, mais plutôt de poser, le plus clairement possible, ses bases afin d'en faciliter la mise en oeuvre.

, 21 pages