Table des matières
Introduction Générale 10
I Favoriser l'obtention rapide de solutions dans les
méthodes de recherche arborescente 15
1 Dynamic Learning Search : une méthode par
apprentissage 19
1.1 Introduction 19
1.2 État de l'art des recherches arborescentes 20
1.2.1 Méthode de parcours de l'arbre de recherche 21
1.2.2 Méthode de structuration de l'arbre de recherche
22
1.2.3 Parcours réduit de l'arbre 22
1.2.4 Ordre dynamique 24
1.2.5 Apprentissage : look-back 26
1.2.6 Métaheuristiques combinées à la
recherche arborescente 27
1.3 Dynamic Learning Search : une méthode par
apprentissage 28
1.4 Learning : une méthode basée sur un
apprentissage 29
1.4.1 Sondage 29
1.4.2 Apprentissage 30
1.4.3 Prévision 32
1.4.4 Remise en question 32
1.5 Dynamic : un ordre dynamique de choix des variables et de
sélection des
valeurs 33
1.6 Search: un schéma de recherche adapté à
la méthode 34
1.7 Algorithme général de la méthode 34
1.8 Méthode Dynamic Learning Search : critères de
sélection 34
1.8.1 Problèmes de Satisfaction des Contraintes 35
1.8.2 Problèmes d'Optimisation Combinatoire 38
1.8.3 Méthode commune aux deux types de problèmes
39
1.9 Résultats expérimentaux 40
1.9.1 Application au problème du Voyageur de Commerce
40
1.9.2 Application au problème d'Emploi du Temps de Garde
d'Infir-
mières 41 1.9.3 Application à des
problèmes de Satisfaction de Contraintes aca-
démiques 43
1.10 Conclusion et perspectives
II Utiliser des méthodes exactes au sein des
métaheuristiques : méthodes
de grands voisinages
2 La recherche à grand voisinage : un nouvel
opérateur
|
47
49 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
|
85
|
|
|
3.3.2 Application de l'opérateur Dropstar
|
85
|
|
|
3.3.3 Intégration de la recherche locale dans l'algorithme
DMD-ATA .
|
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
III Tronquer les méthodes exactes : méthode
de Branch & Price heuristique 121
5 Application au problème de Tournées de
Véhicules avec Contraintes de Chargement 125
5.1 Préambule : Intérêt du problème
126
5.2 Problèmes de calcul de tournées de
véhicules 127
5.2.1 Du problème du Voyageur de Commerce au
problème de Tour-
nées de Véhicules 127
5.2.2 Le 2L-VRP parmi les problèmes de Tournées de
Véhicules . . . 128
5.3 État de l'art 128
5.3.1 Résolution du 2L-VRP 128
5.3.2 Algorithmes de chargement 131
5.4 Modèle classique du problème du 2|RO|L-VRP
132
5.5 Génération de colonnes 134
5.5.1 Modélisation d'un ESPPRC 138
5.5.2 Résolution par programmation dynamique 139
5.6 Notre approche : un schéma de Branch & Price
141
5.6.1 Méthode de séparation 142
5.6.2 Initialisation de 1 pour la génération de
colonnes 143
5.6.3 Remontées de colonnes 143
5.6.4 Problème esclave : ESPPRC 144
5.6.5 Problème de chargement séquentiel à
deux dimensions 147
5.7 Deux approches différentes pour la
réalisabilité du chargement 153
5.7.1 Vérification de la réalisabilité a
posteriori 153
5.7.2 Construction de routes réalisables dans le
sous-problème 155
5.8 Branch & Price heuristique 159
5.8.1 Problème esclave heuristique 159
5.8.2 Gestion des colonnes 160
5.8.3 Méthode de séparation 160
5.9 Résultats expérimentaux 161
5.9.1 Paramètres retenus 161
5.9.2 Classes d'instances 161
5.9.3 Analyses des résultats 162
5.10 Conclusions et perspectives 165
Conclusion et perspectives 171
Liste des illustrations 175
Liste des tableaux 177
Bibliographie 179
|