Un algorithme tabou stochastique pour le problème de recouvrement d'ensemble à coûts unitaires

Le problème de recouvrement d'ensemble avec coûts unitaires (USCP) est un problème NP-difficile. Ce problème possède plusieurs applications importantes comme le problème d'affectation des équipages. Le but de notre travail est de résoudre de manière efficace le problème USCP. Pour atteindre cet objectif, nous avons commencé par développer un algorithme tabou qui s'inspire du meilleur algorithme conçu pour résoudre ce problème. L'un des points faibles de ce dernier algorithme est l'absence d'une technique permettant un réglage efficace des paramètres. Notre principal objectif était de trouver une manière efficace de régler les paramètres. Durant notre travail, nous avons exploré plusieurs approches. La première approche consistait à trouver des formules générales pour nos listes taboues. Nous n'avons pas réussi à trouver des formules simples, mais les résultats des tests réalisés avec nos deux formules compliquées sont meilleurs que ceux obtenus par le meilleur algorithme de la littérature. La deuxième approche consistait à adapter l'algorithme tabou réactif à notre problème USCP. Les tests réalisés avec cette approche ont montré que l'algorithme ne produit pas des cycles avec les jeux de grande taille, donc incapable de régler dynamiquement les longueurs des listes taboues. Notre troisième idée consistait à combiner le recuit simulé avec l'algorithme tabou. Nos tests ont révélé que l'algorithme obtient des résultats médiocres lorsque la température n'est pas suffisamment basse. Grâce aux résultats obtenus avec la troisième approche, nous avons développé notre algorithme tabou stochastique STS. Notre algorithme STS nous a permis de régler plus facilement les longueurs des listes taboues. Les résultats de STS sont meilleurs que ceux obtenus par RWLS -- le meilleur algorithme de la littérature publié récemment. Notre algorithme obtient 6 nouveaux records et atteint tous les meilleurs résultats sur le reste des jeux de données. Pour rendre nos algorithmes plus rapides, nous avons développé une implémentation efficace. Notre implémentation est fondée sur deux caractéristiques clés. La première est l'utilisation d'algorithmes de bas niveau incrémentaux. Le deuxième point fort de notre implémentation est l'utilisation des files de priorité qui rendent la sélection d'un mouvement plus rapide. Les tests effectués montrent l'efficacité de nos files de priorités sur la majorité des jeux de données traités dans notre travail.