2.5 Perspectives : variantes possibles de la
procédure Dropstar
La procédure Dropstar est une procédure
exacte qui détermine la sous-séquence optimale à partir
d'une séquence initiale. Cette procédure peut donc s'appliquer
à l'ensemble des problèmes de type Tournées de
Véhicules ou Problème de Voyageur de Commerce, pour lesquels la
visite de l'ensemble des sommets du graphe n'est pas obligatoire. Nous avons
nommé cette classe de problèmes les Problèmes de
Tournées avec Couverture Partielle.
La procédure Dropstar est une procédure
exacte. Cette exactitude est coûteuse en temps de calcul de par sa
complexité. Il est néanmoins possible de rendre cette
méthode heuristique, en résolvant de manière
approchée le sous-problème de Plus Court Chemin avec Contraintes
de Ressources. Cela peut se faire par exemple en limitant la taille des chemins
partiels mémorisés pour chaque sommet de la séquence.
Une des limites de cette procédure réside dans
le fait que l'ordre initial est respecté; une ville située avant
une autre ville dans la séquence initiale, sera encore située
avant
2.5. Perspectives : variantes possibles de la procédure
Dropstar
dans la sous-séquence, si aucune des deux villes n'est
supprimée par la procédure. On peut cependant étendre
cette procédure à l'insertion d'un ou de plusieurs sommets et
ainsi passer outre cette limitation. La méthode de Meilleure
Insertion de groupes présentée dans la section 4.3.4 permet
par exemple de déterminer la meilleure position d'un groupe dans une
séquence. On pourrait de la même façon trouver la meilleure
position d'insertion de sommets non visités.
Les deux chapitres qui suivent présentent l'application
de la procédure Dropstar pour deux problèmes : le problème
de l'Acheteur Itinérant (Traveling Purchaser Problem ou TPP)
pour lequel l'opérateur est utilisé pour améliorer les
solutions trouvées par un algorithme d'optimisation par Colonie de
Fourmis et le problème du Voyageur de Commerce
Généralisé (Generalized Traveling Salesman Problem
ou GTSP) pour lequel la procédure Dropstar est utilisé comme
élément clé d'un algorithme mémétique.
| 
