UDGVNS
CODAG
Résoudre des problèmes d’optimisation combinatoire de grande taille en exploitant efficacement la décomposition arborescente au sein d’une recherche à voisinage variable. La méthode UDGVNS prend en entrée un problème défini par un ensemble de variables où chaque variable est associée à un ensemble fini de valeurs possibles. Ces variables sont soumises à des contraintes souples modélisées sous forme de fonctions de coût. Chaque fonction de coût donne le poids de violation d'une affectation pour une contrainte donnée. Plus l’affection des variables viole les contraintes, plus le coût sera élevé. L’objectif est de trouver une affectation de toutes les variables minimisant la somme des fonctions de coût, idéalement un coût égal à zéro. La résolution de ces problèmes par des méthodes exactes ne peut être envisagée à cause des délais de traitement souvent exorbitants que nécessiteraient ces méthodes pour explorer toutes les affectations possibles. UDGVNS cherche donc à trouver au plus vite des solutions dites de bonne qualité. Cette méthode a un caractère « Anytime : on peut l’arrêter à tout moment ou si une qualité désirée par l’utilisateur est atteinte », elle renverra la dernière meilleure solution trouvée.
Contributeur
Abdelkader Ouali