Colloque

Introduction à la recherche à voisinage variable

P. Hansen

N. Mladenovic

Membre a labase

P. Hansen

Résumé du colloque

Un changement systématique de voisinage au sein d'un algorithme de recherche locale, éventuellement randomisé, conduit à une métaheuristique simple et effective pour l'optimisation combinatoire et globale, appelée Recherche à Voisinage Variable (RVV). Nous présentons un schéma de base pour ce faire, qui peut être aisément mis en œuvre, à l'aide de n'importe quelle sous-routine de recherche locale. Son efficience est illustrée par la résolution de plusieurs problèmes classiques d'optimisation combinatoire. De plus, pour résoudre des problèmes de grande taille, ce schéma est utilisé au sein de la méthode d'approximations successives, conduisant ainsi à une méthode RVV à deux niveaux, appelée Recherche et Décomposition à Voisinage Variable (RDVV). Enfin, on présente divers moyens d'utiliser RVV en théorie des graphes, domaine où les métaheuristiques ne semblent pas avoir été utilisées auparavant, afin de suggérer, réfuter ou donner des indications de preuve pour des conjectures.

Contexte

Section :

Recherche opérationnelle

Thème du colloque :

Recherche opérationnelle

Responsables :

Bernard Lamond

Hôte : Université Laval

Découvrez d'autres communications scientifiques

Dans le même colloque
Du même congressiste

Titre du colloque :

Recherche opérationnelle

Un algorithme pour la gestion des engagements en temps réel

Goran Stojkovic

Stabilisation dans le cadre de la génération de colonnes

O. Du Merle

Recherche à voisinage variable de graphes extrêmaux

G. Caporossi

Voir tous les contenus de ce colloque

Autres communications du même congressiste :

Thème du colloque :

Recherche opérationnelle

Introduction à la recherche à voisinage variable

P. Hansen

Résolution du problème de plus court chemin bicritère par les deux bouts

P. Hansen

Stabilisation dans le cadre de la génération de colonnes

O. Du Merle