|
2
|
La recherche à grand voisinage : un nouvel
opérateur
|
53
|
|
2.1
|
Introduction à la recherche locale
|
53
|
|
|
2.1.1 Bases de la recherche locale
|
53
|
|
|
2.1.2 Principales classes de recherches locales
|
54
|
|
|
2.1.3 Recherche locale à voisinage variable
|
55
|
|
|
2.1.4 Algorithmes utiisant de la recherche locale
|
55
|
|
2.2
|
Recherche à grand voisinage
|
57
|
|
|
2.2.1 Notations et définitions de la recherche à
grand voisinage . . . .
|
58
|
|
2.3
|
Classe des problèmes considérés :
Problèmes de Tournées avec Couver-
|
|
|
|
ture Partielle
|
59
|
|
|
2.3.1 Problèmes de Tournées avec Gains
|
60
|
|
|
2.3.2 Autres variantes de Problèmes de Tournées
à Couverture Partielle
|
61
|
|
|
2.3.3 Complexité des Problèmes de Tournées
avec Couverture Partielle
|
62
|
|
|
2.3.4 Quelques opérateurs de recherche locale pour les
Problèmes de
|
|
|
|
Tournées avec Couverture Partielle
|
62
|
|
2.4
|
Dropstar : une nouvelle structure de grand voisinage
|
64
|
|
|
2.4.1 Des opérateurs existants : drop,
l-ConsecutiveDrop
|
64
|
|
|
2.4.2 L'opérateur de grand voisinage : Dropstar
|
69
|
|
|
2.4.3 Plus court chemin avec contraintes de ressources (SPPRC) .
. . .
|
71
|
|
|
2.4.4 Résolution par un algorithme de programmation
dynamique . .
|
71
|
|
2.5
|
Perspectives : variantes possibles de la procédure
Dropstar
|
74
|
|
3
|
Application au Problème de l'Acheteur
Itinérant
|
77
|
|
3.1
|
Introduction au problème de l'Acheteur Itinérant
|
78
|
|
3.2
|
Notre algorithme : le DMD-ATA
|
81
|
|
|
3.2.1 Fourmis Parallèles
|
81
|
|
|
3.2.2 Fourmis Anamorphiques
|
82
|
|
|
3.2.3 Plans Multi-Dimensionnels
|
83
|
|
|
3.2.4 Dynamique
|
83
|
|
3.3
|
Opérateurs de recherche locale
|
84
|
|
|
3.3.1 Procédures de recherches locales basiques
3.3.2 Application de l'opérateur Dropstar
3.3.3 Intégration de la recherche locale dans
l'algorithme DMD-ATA
|
85
85
89
|
|
3.4
|
Résultats expérimentaux
|
89
|
|
3.5
|
Conclusion
|
93
|
|
4
|
Application au Problème du Voyageur de Commerce
Généralisé
|
95
|
|
4.1
|
Introduction au Problème du Voyageur de Commerce
Généralisé . . . .
|
96
|
|
4.2
|
État de l'art
|
96
|
|
4.3
|
Algorithme mémétique
|
98
|
|
|
4.3.1 Composants basiques de l'algorithme
|
98
|
|
|
4.3.2 Croisement
|
100
|
|
|
4.3.3 Implémentation détaillée de
l'opérateur de croisement
|
103
|
|
|
4.3.4 Heuristiques de recherche locale
|
106
|
|
4.4
|
Résultats expérimentaux
|
108
|
|
4.5
|
Conclusion et perspectives
|
112
|
