3.3.3 Intégration de la recherche locale dans
l'algorithme DMD-ATA
Au vu de la complexité de certaines des
procédures de recherches locales présentées, nous ne
pouvons pas toutes les appliquer à chaque fois qu'une fourmi revient au
dépôt. Par conséquent, seules les procédures
2-opt, insertion, simplification et suppression
sont appliquées, dans cet ordre, lors du retour au
dépôt de chaque fourmi. Chaque procédure, ainsi que la
séquence dans son intégralité, est
répétée tant que des améliorations sur le
coût de la solution sont obtenues.
La procédure dropstar est appliquée
uniquement lorsque la différence entre le coût de la solution
courante et la meilleure solution connue est inférieure à 10% et
que ces deux solutions ont un degré de différence assez
important. Cette différence est évaluée à l'aide de
la mesure suivante :
diff(S, S*) = |(S ?
S*)\(S n S*)|
|S ? S*|
pour laquelle S et S* sont
respectivement l'ensemble des marchés visités par la
solution
courante et par la meilleure solution connue. On considère
que les deux solutions ont
un degré de différence assez important lorsque
diff = 2 3, ce qui signifie que les deux solutions ont moins de la
moitié de leurs marchés en commun.
Par cette condition supplémentaire, nous accentuons
l'exploration du voisinage de bonnes solutions qui diffèrent de
manière significative de la meilleure solution connue. Ceci permet
d'éviter la répétition d'une intensification excessive
dans la même région de l'espace de solutions.
| 
