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.

Abstract

The unicost set covering problem (USCP) is an NP-hard problem. This problem has many important real-life applications such as the crew scheduling problem. In this work, we aim to effectively solve the USCP. To achieve this goal, we first developed a tabu search algorithm inspired by the best algorithm designed to solve the USCP. One of the weaknesses of the latter algorithm is the absence of an effective technique for setting the parameters. Our main objective was to find an effective way to adjust the tabu lists parameters. During our work, we explored several approaches. The first approach was to find general formulas for our tabu lists. We have not managed to find simple formulas, but the results of the tests performed with our two complicated formulas are better than those obtained by the best performing algorithms in the literature. The second approach was to adapt the reactive tabu algorithm to our problem. Tests performed with this approach have shown that the algorithm does not produce cycles when applied to big instances, so it is unable to dynamically adjust the length of the tabu lists. Our third idea was to combine a simulated annealing algorithm with the tabu algorithm. Our tests revealed that the algorithm performs poorly when the temperature is not low enough. Thanks to the results obtained with the third approach, we have developed our stochastic tabu algorithm STS. Our STS algorithm allowed us to easily adjust the lengths of the tabu lists. STS results are better than those obtained by RWLS - the best algorithm in the literature which was recently published. Our algorithm obtains 6 new records and achieves the best results on all the remaining instances. To make our algorithm faster, we have developed an efficient implementation. Our implementation is based on two features. The first is the use of incremental low level algorithms. The second feature of our implementation is the use of priority queues that make the selection of the movements faster. The tests show the effectiveness of using the priority queues on the majority of the instances used in this work.