WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

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

( Télécharger le fichier original )
par Boris BONTOUX
Université d'Avignon et des pays de Vaucluse - Doctorat spécialité informatique 2008
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

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

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy








"Aux âmes bien nées, la valeur n'attend point le nombre des années"   Corneille