Liste des illustrations
2.1 LNS : Exemple de solution initiale 63
2.2 LNS : Application d'un échange entre les
sommets 2 et 6 63
2.3 LNS : Application de l'opérateur insertion
63
2.4 LNS : Application de l'opérateur suppression
64
2.5 LNS : Application d'un 2-opt entre les sommets 2 et
5 64
2.6 LNS : Exemple de Profitable Tour Problem 66
2.7 LNS : Exemple de Profitable Tour Problem: Solution initiale
66
2.8 LNS : Profitable Tour Problem : après un Drop 67
2.9 LNS : Profitable Tour Problem : après un
2-ConsecutiveDrop 67
2.10 LNS : Autre exemple de Profitable Tour Problem 68
2.11 LNS : Autre exemple de Profitable Tour Problem: Solution
initiale . . . 68
2.12 LNS : Profitable Tour Problem : après un
3-ConsecutiveDrop 69
2.13 LNS : Profitable Tour Problem : Solution ptimale 69
2.14 LNS : Graphe résultant de la procédure
Dropstar 70
2.15 LNS : Extension depuis le sommet 0 72
2.16 LNS : Extension depuis le sommet 1 73
2.17 LNS : Extension depuis le sommet 2 73
2.18 LNS : Extension depuis le sommet 3 73
3.1 TPP : graphe complet utilisé par la procédure
dropstar 87
3.2 TPP : graphe réduit utilisé par la
procédure dropstar 88
4.1 GTSP : croisement et graphe résultant utilisé
par dropstar : vue agrégée 102
4.2 GTSP : croisement et graphe résultant utilisé
par dropstar : vue détaillée 102
4.3 GTSP : croisement et graphe résultant réduit
utilisé par dropstar : vue
agrégée 105
4.4 GTSP : opérateur
Move et graphe réduit correspondant : vue agrégée
en
terme de groupes 107
5.1 2L-VRP: Surface de chargement 133
5.2 2L-VRP : Méthode de génération de
colonnes 137
5.3 2L-VRP : Un SPRC à une ressource 138
5.4 2L-VRP : Trace de l'algorithme de programmation dynamique
141
5.5 2L-VRP: Règle de dominance affinée 145
Liste des illustrations
5.6 2L-VRP : Recherche de chemins élémentaires par
un LDS paramétré à 1
bon voisin 146
5.7 2L-VRP : Next Fit Decreasing Height 150
5.8 2L-VRP: First Fit Decreasing Height 151
5.9 2L-VRP: Best Fit Decreasing Height 152
5.10 2L-VRP: Représentation des coordonnées des
objets 153
5.11 2L-VRP: Représentation des coordonnées des
objets après insertion. . 154
5.12 2L-VRP: Représentation des coordonnées des
objets sur un autre exemple 155 5.13 2L-VRP : Mise à jour des
coordonnées des objets après insertionsur un
autre exemple 156
5.14 2L-VRP: Bottom Left 156
5.15 2L-VRP: Improved Bottom Left 156
5.16 2L-VRP : Max Touching Perimeter 157
5.17 2L-VRP: Structure d'un annuaire 157
5.18 2L-VRP: Calcul de l'aire restante d'un chargement 158
Liste des tableaux
1.1 Résultats expérimentaux pour plusieurs
méthodes appliquées au pro-
blème du Voyageur de Commerce 41
1.2 Résultats
expérimentaux pour plusieurs méthodes appliquées au
pro-
blème d'emploi du temps pour les gardes
d'infirmières 43
1.3 DLS : Résultats expérimentaux,
instances de Sac-à-dos Multidimensionnel 45
1.4 DLS : Résultats expérimentaux, instances de
Carré Magique 45
1.5 DLS : Résultats expérimentaux, instances de
Coloration de Graphes . . 47
3.1 TPP : Résultats expérimentaux, instances
fermées 91
3.2 TPP : Résultats expérimentaux, instances
ouvertes 91
3.3 TPP : Résultats expérimentaux, instances
ouvertes améliorées (1) . . . 92
3.4 TPP : Résultats expérimentaux, instances
ouvertes améliorées (2) . . . 93
4.1 GTSP : Résultats expérimentaux : qualité
des solutions sur instances fer-
mées 113
4.2 GTSP : Résultats
expérimentaux : qualité des solutions sur instances ou-
vertes 114
4.3 GTSP : Résultats expérimentaux : meilleures
solutions connues 114
4.4 GTSP : Résultats expérimentaux : comparaisons
des opérateurs de croi-
sement sur instances fermées 115
4.5 GTSP :
Résultats expérimentaux : comparaisons des opérateurs de
croi-
sement sur instances ouvertes 116 4.6 GTSP :
Résultats expérimentaux : comparatifs entre plusieurs algorithmes
117 4.7 GTSP : Résultats expérimentaux : comparatif des
opérateurs de croise-
ment sur de nouvelles instances (1) 118
4.8 GTSP :
Résultats expérimentaux : comparatif des opérateurs de
croise-
ment sur de nouvelles instances (2) 119
5.1 2L-VRP: Récapitulatif de quelques problèmes
classiques 128
5.2 2L-VRP: Caractéristiques des objets des classes
d'instances 162
5.3 2L-VRP: Caractéristiques des objets des classes
d'instances 163
5.4 2L-VRP : Résultats expérimentaux :
qualité des solutions sur instances
moyennes 164
5.5 2L-VRP : Résultats
expérimentaux : qualité des solutions sur l'ensemble
des instances 166
Liste des tableaux
5.6 2L-VRP: Résultats expérimentaux : comparaisons
des deux heuristiques 167
| 
