Retour aux résultats
Documents de travail (2002), ESSEC Business School

A Path-relinking Algorithm for the Generalized Assignement Problem

ALFANDARI Laurent , PLATEAU A., TOLLA P.

Le Problème d'Affectation Généralisé (GAP) consiste à rechercher une affectation optimale de tâches à des agents soumis à des contraintes de capacité. Nous proposons un algorithme de Recomposition de Chemins (Path Relinking) pour ce problème, explorant à la fois l'espace des solutions réalisables et non réalisables. Les expériences numériques menées sur des instances de taille réduite de la OR-library illustrent l'efficacité de l'algorithme comparativement à la plupart des autres méthodes de la littérature. En particulier, les optima de plus de 95% des instances du fichier-test ont été trouvés en des temps de calcul relativement restreints.

ALFANDARI, L., PLATEAU, A. and TOLLA, P. (2002). A Path-relinking Algorithm for the Generalized Assignement Problem. ESSEC Business School.