Techniques hybrides de recherche exacte et approchée: application à des problèmes de transport

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